Chapter 5 - Java concurrency fundamentals

What are the two java concurrency APIs?

Java has two, mostly separate concurrency APIs: the older API, which is usually called block-structured concurrency or synchronization-based concurrency or even “classic concurrency,” and the newer API, which is normally referred to by its Java package name, java.util.concurrent.

Classic Concurrency - synchronized and volatile

This was the only API available until Java 5. As you might guess from the alternative name, “synchronization-based concurrency,” this is the language-level API that is built into the platform and depends upon the synchronized and volatile keywords.

It is a low-level API and can be somewhat difficult to work with, but it is very much worth understanding. It provides a solid foundation for the chapters later in the book that explain other types and aspects of concurrency.

Concurrency and multithreading in Hardware

Let’s start with some basic facts about concurrency and multithreading:

• Concurrent programming is fundamentally about performance.

• There are basically no good reasons for implementing a concurrent algorithm if the system you are running on has sufficient performance that a serial algorithm will work.

• Modern computer systems have multiple processing cores—even mobile phones have two or four cores today.

• All Java programs are multithreaded, even those that have only a single application thread.

This last point is true because the JVM is itself a multithreaded binary that can use multiple cores (e.g., for JIT compilation or garbage collection). In addition, the standard library also includes APIs that use runtime-managed concurrency to implement multithreaded algorithms for some execution tasks

Amdahl’s law

Brief Explanation

Amdahl’s Law is a foundational model used to evaluate the efficiency of parallelizing work across multiple execution units (such as threads or processes). It demonstrates that while adding more processors can speed up a task by subdividing it, the overall speedup is strictly limited by the portion of the task that cannot be parallelized and must be executed sequentially.

Bullet Points

• Abstract Execution Units: The model applies universally to any execution units (threads, processes, etc.) and does not depend on specific hardware or implementation details.

• The Naive Assumption: It is tempting to think that if a task takes time T₁ on one processor, adding N processors will linearly reduce the time to T₁ / N.

• The Cost of Subdividing: Splitting work and recombining the results is not free. This communication/coordination overhead is known as the "serial part" of the calculation, represented by s (0 < s < 1).

• The Ultimate Speed Limit: Because the serial part cannot be parallelized, the total completion time can never be faster than s * T₁, regardless of how many processing units you add.

• Best-Case Scenario: The model assumes the overhead (s) remains constant as processors (N) increase. In reality, splitting work among more processors often increases the overhead, making the constant s assumption the most optimistic scenario.

The Example in the Text

If the communication overhead (the serial part, s) of a task is 0.05 (or 5%), the task will always take at least 5% of the original single-processor time ($0.05 * T₁) to complete. Even if you throw an infinite number of execution units at the problem, you can never eliminate this 5% baseline time requirement.

the easiest way to think about Amdhal’s law is

if s is between 0 and 1, then the maximum speedup that can be achieved is 1 / s. This result is somewhat depressing—it means that if the communication overhead is just 2%, the maximum speedup that can ever be achieved (even with thousands of processors working at full speed) is 50X.

Explaining Java’s threading model - Java’s threading model is based on the following two fundamental concepts?

Java’s threading model is based on the following two fundamental concepts:

 Shared, visible-by-default mutable state

 Preemptive thread scheduling by the operating system

What are the most important aspects of Java’s threading model?

Let’s consider the following most important aspects of these ideas:

• Objects can be easily shared between all threads within a process.

• Objects can be changed (“mutated”) by any threads that have a reference to them.

• The thread scheduler (the operating system) can swap threads on and off cores at any time, more or less.

• Methods must be able to be swapped out while they’re running (otherwise, a method with an infinite loop would steal the CPU forever).

• This, however, runs the risk of an unpredictable thread swap, leaving a method “half-done” and an object in an inconsistent state.

• Objects can be locked to protect vulnerable data.

The last point is absolutely crucial—without it there is a huge risk of changes being made in one thread not being seen correctly in other threads. In Java, the ability to lock objects is provided by the synchronized keyword in the core language.

Monitors on objects in Java

Technically, Java provides monitors on each of its objects, which combine a lock (aka mutual exclusion) with the ability to wait for a certain condition to become true.

Because every class in Java inherits from java.lang.Object, every single object you create in Java inherently comes with a hidden "monitor" (often called an intrinsic lock or monitor lock).

1. The Lock (Mutual Exclusion)

Mutual exclusion ensures that only one thread can access a block of code at a time. In Java, you activate this part of the monitor using the synchronized keyword.

Imagine a single, highly secure filing cabinet (the Object) in an office. The cabinet only has one physical key (the Lock).

• If Thread A wants to open the cabinet, it must take the key.

• If Thread B comes along while Thread A has the key, Thread B is physically blocked from opening the cabinet. It must wait outside until Thread A finishes and returns the key.

Java

public synchronized void doSecureWork() {
    // Only one thread can execute this method on this object at a time.
    // The thread automatically acquired this object's lock to get in here.
}

2. The Wait Set (Waiting for a Condition)

Sometimes, a thread successfully acquires the lock, looks inside the object, but realizes it cannot do its job yet because some condition hasn't been met (e.g., it wants to read data, but the buffer is empty).

Instead of holding onto the lock and freezing the whole program, the thread can use the object's wait/notify mechanism. These are methods built right into java.lang.Object:

• wait(): The thread says, "I have the lock, but I'm missing what I need. I am going to release the lock and go to sleep in this object's 'waiting room'."

• notify() / notifyAll(): Another thread gets the lock, changes the data (e.g., adds items to the buffer), and yells into the waiting room, "The data has changed! Wake up and try to get the lock again!"

What ate Design concepts in java.util.concurrent to be aware of?

The most important design forces, listed next, were catalogued by Doug Lea as he was

doing his landmark work producing java.util.concurrent:

 Safety (also known as concurrent type safety)

 Liveness

 Performance

 Reusability

Let’s look at each of these forces now.

Design concepts in java.util.concurrent - Safety

• Safety is about ensuring that object instances remain self-consistent, regardless of any other operations that may be happening at the same time. If a system of objects has this property, it’s said to be safe or concurrently typesafe.

• In general, one strategy for safety is to never return from a nonprivate method in an inconsistent state, and to never call any nonprivate method (and certainly not a method on any other object) while in an inconsistent state. If this practice is combined with a way of protecting the object (such as a synchronization lock or critical section) while it’s inconsistent, the system can be guaranteed to be safe.

As you might guess from the name, one way to think about concurrency is in terms of an extension to the regular concepts of object modeling and type safety. In non-concurrent code, you want to ensure that regardless of what public methods you call on an object, it’s in a well-defined and consistent state at the end of the method. The usual way to do this is to keep all of an object’s state private and expose a public API of methods that alter the object’s state only in a way that makes senses for the design domain.

Design concepts in java.util.concurrent - Liveness

A live system is one in which every attempted activity eventually either progresses or fails. A system that is not live is basically stuck—it will neither progress toward success or fail.

The keyword in the definition is eventually—there is a distinction between a transient failure to progress (which isn’t that bad in isolation, even if it’s not ideal) and a permanent failure. Transient failures could be caused by a number of underlying problems, such as

• Locking or waiting to acquire a lock

• Waiting for input (such as network I/O)

• Temporary failure of a resource

• Not enough CPU time available to run the thread

Permanent failures could be due to a number of causes. Some of the most common follow:

• Deadlock

• Unrecoverable resource problem (such as if the network filesystem [NFS] goes away)

• Missed signal

Design concepts in java.util.concurrent - Performance

The performance of a system can be quantified in a number of different ways. think of performance as being a measure of how much work a system can do with a given amount of resources.

In chapter 7, we’ll talk about performance analysis and techniques for tuning, and we’ll introduce a number of other metrics you should know about.

Design concepts in java.util.concurrent - Reusability

Reusability forms a fourth design force, because it isn’t really covered by any of the other considerations. A concurrent system that has been designed for easy reuse is sometimes very desirable, although this isn’t always easy to implement. One approach is to use a reusable toolbox (like java.util.concurrent) and build non-reusable application code on top of it.

How and why do the forces conflict & What’s the balance that you should ultimately try to achieve?

The design forces are often in opposition to each other, and this tension can be viewed as a central reason that designing good concurrent systems is difficult, as explained by the following points:

• Safety stands in opposition to liveness—safety is about ensuring that bad things don’t happen, whereas liveness requires progress to be made.

• Reusable systems tend to expose their internals, which can cause problems with safety.

• A naïvely written safe system will typically not be very performant, because it usually resorts to heavy use of locking to provide safety guarantees.

The balance that you should ultimately try to achieve is for the code to be flexible enough to be useful for a wide range of problems, closed enough to be safe, and still reasonably live and performant. This is quite a tall order, but, fortunately, some practical techniques can help with this. Here are some of the most common in rough order of usefulness:

• Restrict the external communication of each subsystem as much as possible. Data hiding is a powerful tool for aiding with safety.

• Make the internal structure of each subsystem as deterministic as possible. For example, design in static knowledge of the threads and objects in each subsystem, even if the subsystems will interact in a concurrent, nondeterministic way.

• Apply policy approaches that client apps must adhere to. This technique is powerful but relies on user apps cooperating, and it can be hard to debug if a badly behaved app disobeys the rules.

• Document the required behavior. This is the weakest of the alternatives, but it’s sometimes necessary if the code is to be deployed in a very general context.

Sources of overhead - What to think of when developing concurrent code

Many aspects of a concurrent system can contribute to the inherent overhead:

• Monitors (i.e., locks and condition variables)

• Number of context switches

• Number of threads

• Scheduling

• Locality of memory

• Algorithm design

This should form the basis of a checklist in your mind. When developing concurrent code, you should ensure that you have thought about everything on this list.

In particular, the last of these—algorithm design—is an area in which developers can really distinguish themselves, because learning about algorithm design will make you a better programmer in any language.

Synchronization and locks

As you probably already know, the synchronized keyword can be applied either to a block or to a method. It indicates that before entering the block or method, a thread must acquire the appropriate lock. For example, let’s think about a method to withdraw money from a bank account, as shown next:

The method must acquire the lock belonging to the object instance (or the lock belonging to the Class object for static synchronized methods). For a block, the programmer should indicate which object’s lock is to be acquired.

Only one thread can be progressing through any of an object’s synchronized blocks or methods at once; if other threads try to enter, they’re suspended by the JVM.

Tell me some facts about synchronization and locks in Java?

Let’s look at some basic facts about synchronization and locks in Java. Hopefully you

already have most (or all) of these at your fingertips:

• Object-Only Locking: Only objects—not primitives—can be locked.

• Array Component Isolation: Locking an array of objects does not lock the individual object elements contained within that array.

• Method vs. Block Equivalence: A synchronized instance method is conceptually equivalent to a synchronized(this) { … } block that encloses the entire method body, (but note that they’re represented differently in bytecode).

• A static synchronized method locks the Class object, because there’s no instance object to lock.

• Class Object Locking Nuance: If you need to lock a Class object, evaluate whether to do so explicitly (e.g., MyClass.class) or dynamically via getClass(). The behavior of these two approaches diverges significantly when dealing with subclasses.

• Inner Class Independence: Synchronization within an inner class is completely independent of the outer class's monitor lock due to how inner classes are structurally implemented by the compiler.

• Signature Exclusion: The synchronized modifier is an implementation detail and does not form part of the formal method signature. Consequently, it cannot be placed on method declarations within an interface.

• Unsynchronized methods don’t look at or care about the state of any locks, and they can progress while synchronized methods are running.

• Java’s locks are re-entrant (able to be re-entered)—a thread holding a lock that encounters a synchronization point for the same lock (such as a synchronized method calling another synchronized method on the same object) will be allowed to continue.

The state model for a thread - What’s the states that a thread moves through during its life cycle?

1. A Java thread object is initially created in the NEW state. At this time, an OS thread does not yet exist (and may never exist). To create the execution thread, Thread.start() must be called. This signals the OS to actually create a thread.

2. The scheduler will place the new thread into the run queue and, at some later point, will find a core for it to run upon (some amount of waiting time may be involved if the machine is heavily loaded). From there, the thread can proceed by consuming its time allocation and be placed back into the run queue to await further processor time slices. This is the action of the forcible thread scheduling that we mentioned in section 5.1.1.

3. Throughout this scheduling process, of being placed on a core, running, and being placed back in the run queue, the Java Thread object remains in the RUNNABLE state. As well as this scheduling action, the thread itself can indicate that it isn’t able to make use of the core at this time. This can be achieved in two different ways:

   1. The program code indicates by calling Thread.sleep() that the thread should wait for a fixed time before continuing.

   2. The thread recognizes that it must wait until some external condition has been met and calls Object.wait().

In both cases, the thread is immediately removed from the core by the OS. However, the behavior after that point is different in each case.

In the first case (point 3.1), the thread is asking to sleep for a definite amount of time. The Java thread transitions into the TIMED_WAITING state, and the operating system sets a timer. When it expires, the sleeping thread is woken up and is ready to run again and is placed back in the run queue.

The second case (point 3.2) is slightly different. It uses the condition aspect of Java’s per-object monitors. The thread will transition into WAITING and will wait indefinitely. It will not normally wake up until the operating system signals that the condition may have been met—usually by some other thread calling Object.notify() on the current object.

As well as these two possibilities that are under the threads control, a thread can transition into the BLOCKED state because it’s waiting on I/O or to acquire a lock held by another thread.

Finally, if the OS thread corresponding to a Java Thread has ceased execution, then that thread object will have transitioned into the TERMINATED state. Let’s move on to talk about one well-known way to solve the synchronization problem: the idea of fully synchronized objects.

Fully shnchronized objects