In-depth analysis of Java memory model: reordering

Data dependency

If two operations access the same variable, and one of the two operations is a write operation, there is a data dependency between the two operations. Data dependencies are divided into the following three types:
Name
Code example
Description
Read after writing
a = 1;b = a;
After writing a variable, read this location .
Write after writing
a = 1;a = 2;
After writing a variable, write this variable again.
Write after reading
a = b;b = 1;
After reading a variable, write the variable again.
In the above three cases, as long as the execution order of the two operations is reordered, the execution result of the program will be changed.

As mentioned earlier, the compiler and processor may reorder operations. The compiler and processor will respect data dependencies when reordering, and the compiler and processor will not change the execution order of two operations that have data dependencies.

Note that the data dependencies mentioned here only refer to the instruction sequence executed in a single processor and the operations executed in a single thread. Data dependencies between different processors and different threads are not compiled. processors and processors.

as-if-serial semantics

as-if-serial semantics means: no matter how you reorder (compilers and processors in order to improve parallelism), the (single-threaded) program The execution results cannot be changed. The compiler, runtime, and processor all must adhere to as-if-serial semantics.

In order to comply with as-if-serial semantics, the compiler and processor will not reorder operations with data dependencies, because such reordering will change the execution results. However, if there are no data dependencies between operations, these operations may be reordered by the compiler and processor. For specific explanation, please look at the following code example for calculating the area of ​​a circle:

double pi  = 3.14;    //A
double r   = 1.0;     //B
double area = pi * r * r; //C

The data dependencies of the above three operations are shown in the figure below:

As above As shown in the figure, there is a data dependency relationship between A and C, and there is also a data dependency relationship between B and C. Therefore, in the instruction sequence that is finally executed, C cannot be reordered before A and B (C is placed in front of A and B, and the result of the program will be changed). But there is no data dependency between A and B, and the compiler and processor can reorder the execution order between A and B. The following figure shows the two execution sequences of the program:

as-if-serial semantics protect single-threaded programs and comply with The as-if-serial semantics of the compiler, runtime, and processor work together to create the illusion for programmers writing single-threaded programs that single-threaded programs are executed in program order. as-if-serial semantics save single-threaded programmers from having to worry about reordering interfering with them, and they don't have to worry about memory visibility issues.

Program sequence rules

According to the happens-before program sequence rules, the above example code for calculating the area of ​​a circle has three happens-before relationships:
A happens- before B;
B happens- before C;
A happens- before C;

The third happens-before relationship here is derived based on the transitivity of happens-before.

Here A happens- before B, but in actual execution, B can be executed before A (see the reordered execution order above). As mentioned in Chapter 1, if A happens- before B, JMM does not require that A must be executed before B. JMM only requires that the previous operation (result of execution) be visible to the following operation, and that the previous operation precedes the second operation in order. Here, the execution result of operation A does not need to be visible to operation B; and the execution result after reordering operation A and operation B is consistent with the result of executing operation A and operation B in the happens-before order. In this case, JMM will consider that this reordering is not illegal (not illegal), and JMM allows this reordering.

In computers, software technology and hardware technology have a common goal: to develop as much parallelism as possible without changing the execution results of the program. Compilers and processors adhere to this goal. From the definition of happens-before, we can see that JMM also adheres to this goal.

The impact of reordering on multi-threading

Now let us see whether reordering will change the execution results of multi-threaded programs. Please look at the following sample code:

class ReorderExample {
int a = 0;
boolean flag = false;

public void writer() {
    a = 1;                   //1
    flag = true;             //2
}

Public void reader() {
    if (flag) {                //3
        int i =  a * a;        //4
        ……
    }
}
}

The flag variable is a flag used to identify whether variable a has been written. Assume here that there are two threads A and B. A first executes the writer() method, and then B thread executes the reader() method. When thread B performs operation 4, can it see thread A writing to shared variable a in operation 1?

The answer is: not necessarily visible.

Since operation 1 and operation 2 have no data dependency, the compiler and processor can reorder these two operations; similarly, operation 3 and operation 4 have no data dependency, and the compiler and processor can also Reorder these two operations. Let's first take a look at what might happen when operation 1 and operation 2 are reordered? Please look at the program execution timing diagram below:

As shown in the figure above, operation 1 and operation 2 are reordered. When the program is executed, thread A first writes the flag variable flag, and then thread B reads this variable. Since the condition is true, thread B will read variable a. At this time, variable a has not been written by thread A at all, and the semantics of the multi-threaded program here are destroyed by reordering!

※Note: This article uses red dotted arrow lines to indicate incorrect read operations, and green dotted arrow lines to indicate correct read operations.

Let's take a look at what will happen when operations 3 and 4 are reordered (with the help of this reordering, we can also explain the control dependencies). The following is the execution sequence diagram of the program after operations 3 and 4 are reordered:

## In the program, there is a control dependency between operation 3 and operation 4. When there are control dependencies in the code, it affects the degree of parallelism in the execution of the instruction sequence. To this end, compilers and processors use speculation execution to overcome the impact of control dependencies on parallelism. Taking the speculative execution of the processor as an example, the processor executing thread B can read and calculate a*a in advance, and then temporarily save the calculation results to a hardware cache called the reorder buffer ROB. When the condition of the next operation 3 is judged to be true, the calculation result is written into the variable i.

We can see from the figure that guessing execution essentially reorders operations 3 and 4. Reordering breaks the semantics of multi-threaded programs here!

In a single-threaded program, reordering operations with control dependencies will not change the execution results (this is why as-if-serial semantics allows reordering operations with control dependencies); but In a multi-threaded program, reordering operations that have control dependencies may change the execution results of the program.

The above is an in-depth analysis of the Java memory model: reordering content. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!