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?

Hexahedron

I need a clarification on the example... If for both threads the assignment is before the read, there is at least one value changed before they reach the reading. How can both threads see 0? – Slinkman

seriously, what does left number mean? – Laticialaticiferous

Answer 1

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.

Originative

Thanks a lot about your answer. May I consider that all my two understanding are correct? And still two questions: what does "w.v = r.v" mean? what does left number mean? Thanks again. – Hexahedron

According to my understanding, I find that if a program is correctly synchronized then it still allows data race existed in program. So what is your opinion about this opinion? – Hexahedron

I have start a new question: Does a correctly synchronized program still allow data race?(Part I) to continue this discussion. You are welcome to join new question. – Hexahedron

synchronized ensures all memory at the entry and exit of a the block occurs in a predictable order, even things you didn§t access in the block. synchronized components allow different race conditions e.g. a Vector or Collections.syncrhonizedList accessed multiple times can have race condition between a read and a write to that collection. – Originative

Answer 2

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]

Jilljillana

On the topic of ordering, it's not just the compiler that changes ordering or perceived ordering (instructions may execute in order but their effect on memory may not be seen in the same order by other cores/cpus). CPUs' pipelining architectures can and do also change the ordering of instructions that do not depend on each other's output. – Keitel

@Jilljillana I understand your comment. But follow code why is not infinite loop. public class HB { public static Boolean flag = true; public static void main(String[] args) throws InterruptedException { Thread t = new Thread(() -> { while (flag) { System.out.println( "do=====>"); } System.out.println(Thread.currentThread().getName() + " " + "end"); }, "server"); t.start(); Thread.sleep(1000); System.out.println("parent"); flag = false; } } – Horney

Answer 3

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

Indignation

Thanks a lot about your answer. May I consider that all my two understanding are correct? And still two questions: what does "w.v = r.v" mean? what does left number mean? Thanks again. – Hexahedron

@newman:r.v means: read of a variable v and and w.v means: write to variable v.It is explained in the same paragraph: We say that a read r of a variable v is allowed to observe a write w to v if, in the happens-before partial order of the execution trace – Indignation

@Hexahedron You might be interested in this discussion which shows how you can use that paragraph to prove a concurrent code correct (i.e. free of data race). – Rideout

Thanks a lot for all your reply. I have understood what means w.v and r.v, but what means w.v = r.v, in other words, what does "=" mean? I think it does not mean "equals" because "equals" is "==". So would you please explain one step more. – Hexahedron

@Hexahedron It means that the read and the write are about the same variable - it does not say anything about the value of the variable written / seen by w / r. – Rideout

@newman:Please choose the answer that helped you most and mark it as accepted (if you think that you understood your problem) – Indignation

Thanks for your reminder. I have done it. You are welcome to join further discussion. – Hexahedron

I have start a new question: Does a correctly synchronized program still allow data race?(Part I) to continue this discussion. You are welcome to join new question. – Hexahedron

Answer 4

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.

Rideout

Thanks a lot about your answer. May I consider that all my two understanding are correct? And still two questions: what does "w.v = r.v" mean? what does left number mean? Thanks again. – Hexahedron

According to my understanding, I find that if a program is correctly synchronized then it still allows data race existed in program. So what is your opinion about this opinion? – Hexahedron

@Hexahedron I am not sure => I prefer to keep it simple and avoid data races. – Rideout

Thanks a lot. I will continue this topic tomorrow. See you next day. – Hexahedron

There are two conclusions from JLS: C1:If a program has no data races, then all executions of the program will appear to be sequentially consistent. C2:If a program is correctly synchronized, then all executions of the program will appear to be sequentially consistent. If another direction of C1 is true,then we get following conclusion: C3:If a program is correctly synchronized,then this problem has no data race. But unfortunately,there is not such a direction in JLS, so I get the that conclusion: – Hexahedron

if a program is correctly synchronized then it still allows data race existed in program. But I think this is not enough, I want get same conclusion in other solid ways, or proof of false of this conclusion,even in informal way. First of all, I think a code sample that shows a sequential consistent execution of a multiple-threaded program in which it contains data race is helpful to understand and resolve this question. After serious consideration, I still can not find a proper sample. So would you please give me a code sample. – Hexahedron

To be honest that is becoming very theoretical and I m not the best person to answer those questions. – Rideout

I have start a new question: Does a correctly synchronized program still allow data race?(Part I) to continue this discussion. You are welcome to join new question. – Hexahedron

I feel a bit strange resurrecting this, but you say ...that a read that comes after a write in your program order..., while happens before consistency has nothing to do with program order. It is the rule that says that a read observes either the write in happens-before or any other read (racy). This rule defines the connection between synchronizes-with order, that builds the happens-before order among multiple threads. – Effluence

Answer 5

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"

Bemock