Instruction reordering & happens-before relationship

Question

In the book Java Concurrency In Practice, we are told several time that the instructions of our program can be reordered, either by the compiler, by the JVM at runtime, or even by the processor. So we should assume that the executed program will not have its instructions executed in exactly the same order than what we specified in the source code.

However, the last chapter discussing Java Memory Model provides a listing of happens-before rules indicating which instruction ordering are preserved by the JVM. The first of these rules is:

• "Program order rule. Each action in a thread happens before every action in that thread that comes later in the program order."

I believe "program order" refers to the source code.

My question: assuming this rule, I wonder what instruction may be actually reordered.

"Action" is defined as follow:

The Java Memory Model is specified in terms of actions, which include reads and writes to variables, locks and unlocks of monitors, and starting and joining with threads. The JMM defines a partial ordering called happens before on all actions within the program. To guarantee that the thread executing action B can see the results of action A (whether or not A and B occur in different threads), there must be a happens before relationship between A and B. In the absence of a happens before ordering between two operations, the JVM is free to reorder them as it pleases.

Other order rules mentionned are:

• Monitor lock rule. An unlock on a monitor lock happens before every subsequent lock on that same monitor lock.
• Volatile variable rule. A write to a volatile field happens before every subsequent read of that same field.
• Thread start rule. A call to Thread.start on a thread happens before every action in the started thread.
• Thread termination rule. Any action in a thread happens before any other thread detects that thread has terminated, either by successfully return from Thread.join or by Thread.isAlive returning false.
• Interruption rule. A thread calling interrupt on another thread happens before the interrupted thread detects the interrupt (either by having InterruptedException thrown, or invoking isInterrupted or interrupted).
• Finalizer rule. The end of a constructor for an object happens before the start of the finalizer for that object.
• Transitivity. If A happens before B, and B happens before C, then A happens before C.

Solution

The key point of the program order rule is: in a thread.

Imagine this simple program (all variables initially 0):

T1:

x = 5;
y = 6;

T2:

if (y == 6) System.out.println(x);

From T1's perspective, an execution must be consistent with y being assigned after x (program order). However from T2's perspective this does not have to be the case and T2 might print 0.

T1 is actually allowed to assign y first as the 2 assignements are independent and swapping them does not affect T1's execution.

With proper synchronization, T2 will always print 5 or nothing.

EDIT

You seem to be misinterpreting the meaning of program order. The program order rule boils down to:

If x and y are actions of the same thread and x comes before y in program order, then hb(x, y) (i.e. x happens-before y).

happens-before has a very specific meaning in the JMM. In particular, it does not mean that y=6 must be subsequent to x=5 in T1 from a wall clock perspective. It only means that the sequence of actions executed by T1 must be consistent with that order. You can also refer to JLS 17.4.5:

It should be noted that the presence of a happens-before relationship between two actions does not necessarily imply that they have to take place in that order in an implementation. If the reordering produces results consistent with a legal execution, it is not illegal.

In the example I gave above, you will agree that from T1's perspective (i.e. in a single threaded program), x=5;y=6; is consistent with y=6;x=5; since you don't read the values. A statement on the next line is guaranteed, in T1, to see those 2 actions, regardless of the order in which they were performed.

Comments

[Martin]

Thank you. But still missing something: if the program order rule really holds, then y should always be assigned after x in T1 whatever the "perspective" (T1 or T2), isn't it? Thus T2 should always display the appropriate x value. The example you provide is definitly true, I am rather discussing the accuracy of the program order rule in itself ("Each action in a thread happens before every action in that thread that comes later in the program order").

[Ian Roberts]

@Martin the point is that happens-before is only a partial order - while x=5 happens-before y=6 due to the program order rule, there is no happens-before relationship at all between either of those instructions and anything that happens in T2, so it is OK for T2 to see the result of y=6 but not the result of x=5. If y were volatile then that would enforce a happens-before relation between y=6 in T1 and if(y==6) in T2, in the sense that if T2 sees y=6 then it must also see x=5.

[Soner from The Ottoman Empire]

Just to boot, Instruction reordering is when the execution order of the code is changed by the JVM at compile time or run time. This is done to optimize the code. Instruction reordering guarantees program order execution. This means that two statements which are related will have a happens-before relation, but two unrelated statements can be executed out-of-order. The context where this can cause problems is in a multithreaded environment.

[Soner from The Ottoman Empire]

There is no program order between threads, so there should be no assumptions on execution order following the code order. To avoid reordering problems, threads need to be synchronized properly. Code that needs code order execution should be placed in synchronized blocks.