Happens-before relationships

(The following is a simplified version of what the Java Language Specification says. For a deeper understanding, you need to read the specification itself.)

Happens-before relationships are the part of the Memory Model that allow us to understand and reason about memory visibility. As the JLS says (JLS 17.4.5):

“Two actions can be ordered by a happens-before relationship. If one action happens-before another, then the first is visible to and ordered before the second.”

What does this mean?

Actions

The actions that the above quote refers to are specified in JLS 17.4.2. There are 5 kinds of action listed defined by the spec:

• Read: Reading a non-volatile variable.
• Write: Writing a non-volatile variable.
• Synchronization actions:

- Volatile read: Reading a volatile variable.

- Volatile write: Writing a volatile variable.

- Lock. Locking a monitor

- Unlock. Unlocking a monitor.

- The (synthetic) first and last actions of a thread.

- Actions that start a thread or detect that a thread has terminated.

• External Actions. An action that has a result that depends on the environment in which the program.
• Thread divergence actions. These model the behavior of certain kinds of infinite loop.

Program Order and Synchronization Order

These two orderings ( JLS 17.4.3 and JLS 17.4.4 ) govern the execution of statements in a Java

Program order describes the order of statement execution within a single thread.

Synchronization order describes the order of statement execution for two statements connected by a synchronization:

• An unlock action on monitor synchronizes-with all subsequent lock actions on that monitor.
• A write to a volatile variable synchronizes-with all subsequent reads of the same variable by any thread.
• An action that starts a thread (i.e. the call to Thread.start()) synchronizes-with the first action in the thread it starts (i.e. the call to the thread’s run() method).
• The default initialization of fields synchronizes-with the first action in every thread. (See the JLS for an explanation of this.)
• The final action in a thread synchronizes-with any action in another thread that detects the termination; e.g. the return of a join() call or isTerminated() call that returns true.
• If one thread interrupts another thread, the interrupt call in the first thread synchronizes-with the point where another thread detects that the thread was interrupted.

Happens-before Order

This ordering ( JLS 17.4.5 ) is what determines whether a memory write is guaranteed to be visible to a subsequent memory read.

More specifically, a read of a variable v is guaranteed to observe a write to v if and only if write(v) happens-before read(v) AND there is no intervening write to v. If there are intervening writes, then the read(v) may see the results of them rather than the earlier one.

The rules that define the happens-before ordering are as follows:

• Happens-Before Rule #1 - If x and y are actions of the same thread and x comes before y in program order, then x happens-before y.
• Happens-Before Rule #2 - There is a happens-before edge from the end of a constructor of an object to the start of a finalizer for that object.
• Happens-Before Rule #3 - If an action x synchronizes-with a subsequent action y, then x happens-before y.
• Happens-Before Rule #4 - If x happens-before y and y happens-before z then x happens-before z.

In addition, various classes in the Java standard libraries are specified as defining happens-before relationships. You can interpret this as meaning that it happens somehow, without needing to know exactly how the guarantee is going to be met.