Instruction reordering & happens-before relationship

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.

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.