Java Memory Model: a JLS statement about sequential consistency seems incorrect

Question

I'm reading Chapter 17. Threads and Locks of JLS and the following statement about sequential consistency in Java seems incorrect to me:

If a program has no data races, then all executions of the program will appear to be sequentially consistent.

They define a data race as:

When a program contains two conflicting accesses (§17.4.1) that are not ordered by a happens-before relationship, it is said to contain a data race.

They define conflicted accesses as:

Two accesses to (reads of or writes to) the same variable are said to be conflicting if at least one of the accesses is a write.

And finally they have following about happens-before relationship:

A write to a volatile field (§8.3.1.4) happens-before every subsequent read of that field.

My problem with the 1st statement is that I think I can come up with a Java program which has no data races and allows sequentially inconsistent executions:

// Shared code
volatile int vv = 0;
int v1 = 0;
int v2 = 0;


// Thread1       Thread2
   v1 = 1;
   v2 = 2;
   vv = 10;      while(vv == 0) {;}
                 int r1 = v1;
                 int r2 = v2;
                 System.out.println("v1=" + r1 + " v2=" + r2);
   v1 = 3;
   v2 = 4;
   vv = 20;

In the code above I also showed with indentation how the threads' code is interleaved in runtime.

So, as I understand, this program:

has no data races: reads of v1 and v2 in Thread2 are synchronized-with writes in Thread1
can output v1=1 v2=4 (which violates sequential consistency).

As a result, the initial statement from JLS

If a program has no data races, then all executions of the program will appear to be sequentially consistent.

seems incorrect to me.

Am I missing something or did I make a mistake somewhere?

EDIT: user chrylis-cautiouslyoptimistic correctly pointed out that the code I gave can output v1=1 v2=4 with sequential consistency — the lines in threads' code simply should be interleaved a little bit differently.

So here is the slightly modified code (I've changed the order of reads) for which sequential consistency cannot output v1=1 v2=4, but everything still applies.

// Shared code
volatile int vv = 0;
int v1 = 0;
int v2 = 0;


// Thread1       Thread2
   v1 = 1;
   v2 = 2;
   vv = 10;      while(vv == 0) {;}
                 int r2 = v2;
                 int r1 = v1;
                 System.out.println("v1=" + r1 + " v2=" + r2);
   v1 = 3;
   v2 = 4;
   vv = 20;

user_1189885 · Answer

Your error is in bullet point #1: The reads of v1 and v2 are not synchronized-with.

There are happens-before relationships created only by the interactions with vv, so for example in this case, if you added vv to the beginning of your print statement, you would be guaranteed not to see vv=20,v2=4. Since you busy-wait on vv becoming nonzero but then don't interact with it again, the only guarantee is that you will see all of the effects that happened before it became nonzero (the assignments of 1 and 2). You may also see future effects, because you don't have any further happens-befores.

Even if you declare all of the variables as volatile, it is still possible for you to output v1=1,v2=4 because the multithreaded accesses of the variables do not have a defined order, and the global sequence can go like this:

T1: write v1=1
T1: write v2=2
T1: write vv=10 (Thread 2 cannot exit the while loop before here and is guaranteed to see all of these effects.)
T2: read vv=10
T2: read v1=1
T1: write v1=3
T1: write v2=4
T2: read v2=4

After each of these steps, the memory model guarantees that all threads will see the same values of the volatile variables, but you have a data race, and that is because the accesses are not atomic (grouped). In order to assure that you see them in a group, you need to use some other means, such as executing in a synchronized block or putting all of the values into a record class and using volatile or AtomicReference to swap out the entire record.

Formally, the data race as defined by the JLS consists of the operations T1(write v1=3) and T2(read v1) (and a second data race on v2). These are conflicting accesses (because the T1 access is a write), but while both of these events happen after T2(read vv), they are not ordered in relation to each other.

user_1059372 · Answer

It's actually much easier to prove you are wrong than you think. Actions between two independent threads are "synchronized-with" under very special rules, all of them defined in the proper chapter in the JSL. The accepted answer says that synchronizes-with is not an actual term, but that is wrong. (unless I miss-understood the intent or there is a mistake in it).

Since you have no such special actions to establish the synchronized-with order (SW for short), between Thread1 and Thread2, everything that follows falls like a castle of cards and makes no sense anymore.

You mention volatile, but be careful at the same time what subsequent means in that:

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

It means a read that will observe the write.

If you change your code and establish a synchronizes-with relationship and implicitly thus a happens-before like so:

  v1 = 1;
  v2 = 2;
  vv = 10; 

             if(vv == 10) {
                int r1 = v1;
                int r2 = v2;
                // What are you allowed to see here?
             }

You can start reasoning of what it is possible to be seen inside the if block. You start simple, from here:

If x and y are actions of the same thread and x comes before y in program order, then hb(x, y).

OK, so v1 = 1 happens-before v2 = 2 and happens-before vv = 10. This way we establish hb between actions in the same thread.

We can "sync" different threads via synchronizes-with order, via the proper chapter and the proper rule:

A write to a volatile variable v synchronizes-with all subsequent reads of v by any thread

This way we have established a SW order between two independent threads. This, in turn, allows us to build a HB (happens before) now, because of the proper chapter and yet another proper rule:

If an action x synchronizes-with a following action y, then we also have hb(x, y).

So now you have a chain:

        (HB)          (HB)            (HB)                (HB)
v1 = 1 -----> v2 = 2 -----> vv = 10 ------> if(vv == 10) -----> r1 = v1 ....

So only now, you have proof that that if block will read r1 = 1 and r2 = 2. And because volatile offers sequential consistency (no data races), every thread that will read vv to be 10 will, for sure, also read v1 to be 1 and v2 to be 2.

Java Memory Model: a JLS statement about sequential consistency seems incorrect

2 Answers