How to understand happens-before consistent

Question

In chapter 17 of JLS, it introduce a concept: happens-before consistent.

A set of actions A is happens-before consistent if for all reads r in A, where W(r) is the write action seen by r, it is not the case that either hb(r, W(r)) or that there exists a write w in A such that w.v = r.v and hb(W(r), w) and hb(w, r)"

In my understanding, it equals to following words: ..., it is the case that neither ... nor ...

So my first two questions are:

• is my understanding right?
• what does "w.v = r.v" mean?

It also gives an Example: 17.4.5-1

Thread 1 Thread 2

B = 1; A = 2; 

r2 = A; r1 = B; 

In first execution order:

1: B = 1;

3: A = 2;

2: r2 = A;  // sees initial write of 0

4: r1 = B;  // sees initial write of 0

The order itself has already told us that two threads are executed alternately, so my third question is: what does left number mean?

In my understanding, the reason of both r2 and r1 can see initial write of 0 is both A and B are not volatile field. So my fourth quesiton is: whether my understanding is right?

In second execution order:

1: r2 = A;  // sees write of A = 2

3: r1 = B;  // sees write of B = 1

2: B = 1;

4: A = 2;

According to definition of happens-before consistency, it is not difficult to understand this execution order is happens-before consistent(if my first understanding is correct). So my fifth and sixth questions are: does it exist this situation (reads see writes that occur later) in real world? If it does, could you give me a real example?

Answer 1

happens-before

Let's take a look at definitions in concurrency theory:

Atomicity - is a property of operation that can be executed completely as a single transaction and can not be executed partially. For example Atomic operations^[Example]

Visibility - if one thread made changes they are visible for other threads. volatile before Java 5 with happens-before

Ordering - compiler is able to change an ordering of operations/instructions of source code to make some optimisations.

For example happens-before which is a kind of memory barrier which helps to solve Visibility and Ordering issue. Good examples of happens-before are volatile^[About], synchronized monitor^[About]

A good example of atomicity is Compare and swap(CAS) realization of check then act(CTA) pattern which should be atomic and allows to change a variable in multithreading envirompment. You can write your own implementation if CTA:

• volatile + synchronized
• java.util.concurrent.atomic with sun.misc.Unsafe(memory allocation, instantiating without constructor call...) from Java 5 which uses JNI and CPU advantages.

CAS algoritm has thee parameters(A(address), O(old value), N(new value)).

If value by A(address) == O(old value) then put N(new value) into A(address), 
else O(old value) = value from A(address) and repeat this actions again

Happens-before

Official doc

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.

volatile^[About] as an example

A write to a volatile field happens-before every subsequent read of that field.

Let's take a look at the example:

// Definitions
int a = 1;
int b = 2;
volatile boolean myVolatile = false;

// Thread A. Program order
{
    a = 5;
    b = 6;
    myVolatile = true; // <-- write
}

//Thread B. Program order
{
    //Thread.sleep(1000); //just to show that writing into `myVolatile`(Thread A) was executed before

    System.out.println(myVolatile); // <-- read
    System.out.println(a);  //prints 5, not 1
    System.out.println(b);  //prints 6, not 2
}

Visibility - When Thread A changes/writes a volatile variable it also pushes all previous changes into RAM - Main Memory as a result all not volatile variable will be up to date and visible for another threads

Ordering:

• All operations before writing into volatile variable in Thread A will be called before. JVM is able to reorder them but guarantees that no one operation before writing into volatile variable in Thread A will be called after it.

• All operations after reading the volatile variable in Thread B will be called after. JVM is able to reorder them but guarantees that no one operation after reading a volatile variable in Thread B will be called before it.

[Concurrency vs Parallelism]

Answer 2

Q1: is my understanding right?

A: Yes

Q2: what does "w.v = r.v" mean?

A: The value of w.v is same as that of r.v

Q3: What does left number mean?

A: I think it is statement ID like shown in "Table 17.4-A. Surprising results caused by statement reordering - original code". But you can ignore it because it does not apply to the conent of "Another execution order that is happens-before consistent is: " So the left number is shit completely. Do not stick to it.

Q4: In my understanding, the reason of both r2 and r1 can see initial write of 0 is both A and B are not volatile field. So my fourth quesiton is: whether my understanding is right?

A: That is one reason. re-order can also make it. "A program must be correctly synchronized to avoid the kinds of counterintuitive behaviors that can be observed when code is reordered."

Q5&6: In second execution order ... So my fifth and sixth questions are: does it exist this situation (reads see writes that occur later) in real world? If it does, could you give me a real example?

A: Yes. no synchronization in code, each thread read can see either the write of the initial value or the write by the other thread.

time 1: Thread 2: A=2

time 2: Thread 1: B=1 // Without synchronization, B=1 of Thread 1 can be interleaved here

time 3: Thread 2: r1=B // r1 value is 1

time 4: Thread 1: r2=A // r2 value is 2

Note "An execution is happens-before consistent if its set of actions is happens-before consistent"

Answer 3

Each thread can be on a different core with its own private registers which Java can use to hold values of variables, unless you force access to coherent shared memory. This means that one thread can write to a value storing in a register, and this value is not visible to another thread for some time, like the duration of a loop or whole function. (milli-seconds is not uncommon)

A more extreme example is that the reading thread's code is optimised with the assumption that since it never changes the value, it doesn't need to read it from memory. In this case the optimised code never sees the change performed by another thread.

In both cases, the use of volatile ensures that reads and write occur in a consistent order and both threads see the same value. This is sometimes described as always reading from main memory, though it doesn't have to be the case because the caches can talk to each other directly. (So the performance hit is much smaller than you might expect).

On normal CPUs, caches are "coherent" (can't hold stale / conflicting values) and transparent, not managed manually. Making data visible between threads just means doing an actual load or store instruction in asm to access memory (through the data caches), and optionally waiting for the store buffer to drain to give ordering wrt. other later operations.

Answer 4

The Java Memory Model defines a partial ordering of all your actions of your program which is called happens-before.
To guarantee that a thread Y is able to see the side-effects of action X (irrelevant if X occurred in different thread or not) a happens-before relationship is defined between X and Y.
If such a relationship is not present the JVM may re-order the operations of the program.
Now, if a variable is shared and accessed by many threads, and written by (at least) one thread if the reads and writes are not ordered by the happens before relationship, then you have a data race.
In a correct program there are no data races.
Example is 2 threads A and B synchronized on lock X.
Thread A acquires lock (now Thread B is blocked) and does the write operations and then releases lock X. Now Thread B acquires lock X and since all the actions of Thread A were done before releasing the lock X, they are ordered before the actions of Thread B which acquired the lock X after thread A (and also visible to Thread B).
Note that this occurs on actions synchronized on the same lock. There is no happens before relationship among threads synchronized on different locks

Answer 5

In substance that is correct. The main thing to take out of this is: unless you use some form of synchronization, there is no guarantee that a read that comes after a write in your program order sees the effect of that write, as the statements might have been reodered.

does it exist this situation (reads see writes that occur later) in real world? If it does, could you give me a real example?

From a wall clock's perspective, obviously, a read can't see the effect of a write that has not happened yet.

From a program order's perspective, because statements can be reordered if there isn't a proper synchronization (happens before relationship), a read that comes before a write in your program, could see the effect of that write during execution because it has been executed after the write by the JVM.