The happens-before Relationship and Model

To understand the happens-before relationship we’ll need to grasp few related concepts first.

Total order

You are already familiar with total ordering, the sequence of natural numbers i.e. 1, 2, 3 4, … is a total ordering. Each element is either greater or smaller than any other element in the set of natural numbers (Totality). If 2 < 4 and 4 < 7 then we know that 2 < 7 necessarily (Transitivity). And finally if 3 < 5 then 5 can’t be less than 3 (Asymmetry).

Partial order

Elements of a set will exhibit partial ordering when they possess transitivity and asymmetry but not totality. As an example think about your family tree. Your father is your ancestor, your grandfather is your father's ancestor. By transitivity, your grandfather is also your ancestor. However, your father or grandfather aren't ancestors of your mother and in a sense they are incomparable.

Actions

A program consists of actions which can be any of:

1. reads or writes
2. lock and unlocks of a monitor or other locking constructs
3. start of a thread or detecting a thread’s termination
4. read or write of volatile variables

The last three actions in the above list are categorized as synchronization actions.

Synchronization order

Each execution of a program has a synchronization order. A synchronization order is a total order over all of the synchronization actions of an execution. In terms of synchronization order a data race is defined by JSR-133 as:

A data race occurs in an execution of a program if there are conflicting actions in that execution that are not ordered by synchronization.

Sequential consistency

Sequential consistency says that all actions within a program are atomic and follow a total order, which matches the program order. A program that has no data races will exhibit sequential consistency across all its runs. However, sequential consistency doesn’t imply program correctness. Groups of operations that need to be executed atomically may not execute as such giving rise to errors.

In the sequential memory model a read R of a variable V sees the value written to the variable V by a write W, that occurs before R in the execution order. Furthermore there’s no other write that takes place in-between W and R.

The sequential memory model is too restrictive and doesn’t allow for many of the compiler and hardware optimizations. Quoting JSR-133:

A program is correctly synchronized if and only if all sequentially consistent executions are free of data races.

Happens-before memory model

The happens-before memory model has several requirements and properties. It is mathematically described at great length in JSR-133. For this course, we’ll present a brief gist. From the synchronization order of a program a partial order called the happens-before order is derived. In a happens-before memory model:

• A read R of a variable V sees the write W to the variable V, if W occurs before R in the happens-before partial order of the program execution and there is no other intervening write between W and R.

• A read R of a volatile variable observes the last write W of the variable in the synchronization order.

When a program contains two conflicting accesses that are not ordered by a ...