Excerpted from The Art of Concurrent Programming in Java

Thread communication and synchronization

In concurrent programming, there are two key issues to address:

  • How do threads communicate with each other
  • How are threads synchronized

Communication refers to the mechanism by which threads exchange information. There are two kinds of communication mechanisms:

  • Shared memory: Implicit communication through common state in read-write memory
  • Messaging: There is no common state between threads, and threads must communicate explicitly by sending messages

Synchronization is the mechanism used in a program to control the relative order in which operations occur between different threads. In the shared memory concurrency model, synchronization is explicit, and the programmer must explicitly specify that a method or piece of code needs to be executed mutually exclusive between threads. In the concurrent model of message delivery, synchronization is implicit because the message must be sent before the message is received

Java memory model

As mentioned earlier in thread communication and synchronization, communication between Java threads is controlled by the Java Memory Model (JMM), which determines when a thread’s write to a shared variable is visible to another thread

Shared variables between threads are stored in main memory, and each thread has a private local memory where it stores copies of shared variables to read/write

An abstract representation of the Java memory model is shown

If thread A and thread B want to communicate, they must go through the following two steps:

  1. Thread A flusher the updated shared variable from local memory A to main memory
  2. Thread B goes into main memory to read the shared variable that thread A updated before

These two steps are actually thread A sending messages to thread B, and the communication must go through main memory. The JMM provides Java programmers with memory visibility assurance by controlling the interaction between main memory and local memory for each thread

reorder

When executing a program, the compiler and processor often reorder instructions to improve performance. Reordering can cause memory visibility problems in threaded programs. Here are three types of reordering and their impact on memory visibility:

  1. Compiler optimized reordering

    The compiler can rearrange the execution order of statements without changing the semantics of a single-threaded program

  2. Instruction – level parallel reordering

    Modern processors use instruction-level parallelism to execute multiple instructions on top of each other. If there is no data dependency, the processor can change the execution order of the corresponding machine instructions

  3. Memory system reordering

    Because the processor uses caching and read/write buffers, this makes the load and store operations appear to be out of order

    To explain the third case in detail, modern processors use buffers to temporarily store data written to memory. This keeps the instruction pipeline running and avoids delays as the processor pauses to wait for data to be written to memory. However, the write buffer on each processor is visible only to the processor in which it resides. This feature may cause the processor to perform read/write operations on memory in a different order than the actual read/write operations on memory. To illustrate the situation, look at the following table:

    Processor A Processor B
    code a = 1; // A1

    x = b; // A2    		 b = 2; // B1

    y = a; // B2

    Processor A and processor B perform memory access in parallel according to the sequence of the program, and may end up with x = y = 0, as shown in the figure

    Processors A and B simultaneously write the shared variable to their buffers (A1, B1), then read another shared variable from memory (A2, B2), and finally flush the dirty data from the cache to memory (A3, B3). In this case, the program ends up with x = y = 0

So the sequence of instructions from the Java source code to the actual execution goes through one of the following three reorders

The JMM guarantees memory visibility

Thus, the JMM cannot allow reordering to happen, and it must be controlled, or it will cause thread insecurity. To better explain the steps the JMM takes to ensure memory visibility, let’s first introduce some basic concepts

1. Data dependency

If two operations access the same variable, and one of the two operations is a write operation, there is a data dependence between the two operations, as long as the order of the two operations is reordered, the results of the program will be changed. When reordering, the compiler and processor adhere to data dependencies and do not change the order in which two operations with data dependencies are executed. There are three types of data dependencies:

The name of the Code sample instructions
Writing after reading a = 1;

b = a;		 After writing a variable, read the position
Write after a = 1;

a = 2;		 You write a variable, and then you write that variable
Got to write a = b;

b = 1;		 After reading a variable, write the variable

In the above three cases, the result of the program’s execution will be changed simply by reordering the order of the two operations

Data dependencies are only for sequences of instructions executed in a single processor and operations performed in a single thread. Data dependencies between different processors and between different threads are not considered by compilers and processors

2. The as – if – serial semantics

The result of an as-if-serial program cannot be changed, no matter how reordered it is. The compiler, runtime, and processor must comply with the as-if-serial semantics. To comply with the AS-IF-serial semantics, the compiler and processor do not reorder operations that have data dependencies

The as-if-serial semantics protect single-threaded programs, creating the illusion for programmers that single-threaded programs are executed in program order without programmers worrying about reordering interfering with them or memory visibility issues

(3) happens-before principle

Happens-before is the core concept of the JMM, and understanding happens-before is key to understanding the JMM for Java programmers.

Starting with JDK5, Java uses the new JSR-133 memory model, which uses the concept of happens-before to explain memory visibility between operations. In the JMM, if the results of one operation need to be visible to another, there must be a happens-before relationship between the two operations, which can be either within one thread or between different threads

A happens-before B A happens-before B Of course, this is not accurate; there is a happens-before relationship between two operations, which simply requires that the previous action (the result of the execution) be visible to the latter, and that the former action precedes the second in order

The happens-before principle is defined in the JMM as follows:

  • The single-thread happens-before principle: In the same thread, the happens-before action is written after the action
  • Happens-before rule: The unlock operation of a lock happens before the lock operation of the same lock
  • The happens-before principle for volatile: writes to a volatile variable happens-before any writes to that variable (including, of course, writes)
  • The transitive principle of happens-before: If A operates happens-before B and B operates happens-before C, then A operates happens-before C
  • The happens-before principle: the start method of the same thread happens-before other methods of that thread
  • The happens-before principle for thread interrupts: a call to the threadinterrupt method happens-before the code sent by the interrupting thread that detected the interrupt
  • The happens-before principle of thread termination: All operations in a thread are terminated by the happens-before thread
  • The happens-before principle for object creation: an object’s initialization is completed before its Finalize method is called

The realization of each of these principles will not be explained here, but it would be nice to know that there is such a thing

4. Sequential consistent memory model

Sequential consistent memory model is a theoretical reference model idealized by computer scientists, which provides programmers with a strong guarantee of memory visibility. Sequential consistent memory model has two characteristics:

  • All operations in a thread must be executed in program order
  • Regardless of whether the program is synchronized or not, all threads see only a single order of operation execution. In the sequential consistent memory model, every operation must be performed atomically and immediately visible to all threads

The sequential consistent memory model provides the programmer with the following view:

Conceptually, the sequential consistency model has a single global memory that can be connected to any thread by a switch that swings from side to side. At the same time, each thread must perform memory read/write operations in program order. As you can see from the figure above, at most one thread can be connected to memory at any time. When multiple threads execute concurrently, the switch in the figure serializes all memory read/write operations for all threads

For better understanding, let’s use two diagrams to further illustrate the characteristics of the sequential consistency model

Suppose there are two threads A and B executing concurrently. Thread A has three operations in the program order A1 -> A2 -> A3, and thread B also has three operations in the program order B1 -> B2 -> B3

Suppose the two threads use the monitor to synchronize properly: thread A releases the monitor after three operations, and thread B acquires the same monitor. Then the execution effect of the program in the sequential consistency model will be as follows:

Now, assuming that the two threads are not synchronized, here is a schematic of the execution of the unsynchronized program in the sequential consistency model:

In the sequential consistency model of unsynchronized programs, although the overall execution order is unordered, all threads can only see a consistent overall execution order. For example, thread A and thread B see the order of execution: B1->A1->A2->B2->A3->B3. This guarantee is made possible because each operation in the sequential consistent memory model must be immediately visible to any thread

5. To summarize

Because of reordering, it is not possible for the JMM to implement the sequence-consistent memory model, nor is it possible to completely disable reordering because it would affect efficiency. On the one hand, programmers want the memory model to be easy to understand, easy to program, and want to write code based on a strong memory model. Compilers and processors, on the other hand, want the memory model to tie them down as little as possible so that they can do as many optimizations as possible to improve performance. Compilers and processors want to implement a weak memory model. These two factors are at odds with each other, so the key is to find a balance

The key to balance is to optimize reordering rules, which specify when the compiler and processor allow reordering and when they don’t, according to the happens-before principle, data dependencies, and as-if-Serial principle mentioned earlier. The JMM requires the compiler and processor to forbid reordering that alters the results of program execution. What the programmer sees then is a reliable memory model that guarantees memory visibility

Below is a schematic design of the JMM

As you can see from the above figure, the JMM follows a basic principle: the compiler and processor can be optimized as long as the execution results of the program (i.e., single-threaded programs and properly synchronized multithreaded programs) are not changed. For example, if the compiler, after careful analysis, determines that a lock can only be accessed by a single thread, that lock can be eliminated. For example, if the compiler determines, after careful analysis, that a volatile variable can only be accessed by a single thread, the compiler can treat that volatile variable as a normal variable. These optimizations will not change the execution result of the program, but also improve the execution efficiency of the program. From the programmer’s point of view, the programmer doesn’t really care if the reordering actually happens, only that the semantics of the program execution cannot be changed