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 ...