Why are two writes to the same variable conflicting in the Java memory model?

Question

The absence of data races is the prerequisite for sequential consistency. Data races are caused by conflicting accesses. And two accesses to the same variable are conflicting if at least one of the accesses is a write.

See below quotes from the JLS7 for reference.

I understand this definition for the case, where one operation is a read access and the other operation is a write access. However, I do not understand why it is required (for the memory model), if there are two write operations to the same variable.

Question: What's the rationale for not guaranteeing sequential consistency in case of two write operations to the same variable, that are not ordered by a happens-before relationship?

---

§17.4.1: [..] 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.

§17.4.5: [..] When a program contains two conflicting accesses that are not ordered by a happens-before relationship, it is said to contain a data race. [..] A program is correctly synchronized if and only if all sequentially consistent executions are free of data races. If a program is correctly synchronized, then all executions of the program will appear to be sequentially consistent.

Answer 1

If two write accesses are not in a happens-before relationship, it is unspecified which will happen last, i.e. which assignment wins. For instance, the program

static int x;
static int y;

public static void main(String[] args) {
    Thread t1 = new Thread() {
        @Override public void run() {
            x = 1;
            y = 1;
        }
    };
    Thread t2 = new Thread() {
        @Override public void run() {
            y = 2;
            x = 2;
        }
    };
    t1.start();
    t2.start();
    t1.join();
    t2.join();
    System.out.println(x + "" + y);
}

may print 11, 12, 21, or 22, even though the only data races are between writes, and 12 can not be obtained by a sequentially consistent execution.

Answer 2

Consider for example a long variable on a 32 bit architecture. It will take two writes for a long. If two threads try that concurrently there are sequences leaving the variable in an inconsistent state.

thread1:   write high bits                                  write low bits
thread2:                    write high bits, write low bits

This will result in the high bits from thread2 and the low bits from thread1.

Answer 3

Intuitively, sequential consistency means that the execution of the multithreaded program appears as if the program was executed one statement at a time following the original program order, i.e. the actual order of statements in the code that developpers see. Sequential consistency is how people intuitively reason about concurrency.

The main point here is the verb appear. Indeed, the compiler and the VM have the liberty to perform many optimizations behind the hood, as long as they don't break sequential consistency.

According to the memory model, a program will appear sequentially consistent only if it is correctly synchronized. In other words: if a program is not correctly synchronized, its execution at run time might correspond to an execution you cannot reach by executing one statement at a time in the original program order.

Let's consider the original code

T1        T2

a = 3     b = 5
b = 4     a = 6

Sequentially consistent executions can be a=3,b=4,b=5,a=6, or a=3,b=5,a=6,b=4, or b=5,a=6,a=3,b=4 or a=3,b=5,b=4,a=6 or b=5,a=3,b=4,a=6 or b=5,a=3,a=6,b=4 (all the possible interleaving)

To guarantee sequential executions in the JVM, you should wrap each of the four assignments within a synchronized block. Otherwise, the compiler and VM are authorized to do optimizations that could break the intuitive sequential consistency. For instance, they could decide to reorder the statements of T1 to be b=4,a=3. The code will not run in the original program order. With this reordering, the following execution could happen: b=4,b=5,a=6,a=3, resulting in b=5,a=3. This state couldn't be reached with sequential consistency.

The reason why sequential consistency can be broken if the program is not correctly synchronized is that optimizations consider the consistency of individual threads, not the whole program. Here, swapping the assignements in T1 does not compromise the logic of T1 if taken in isolation. However, it compromises the logic of the interleaving of threads T1 and T2, since they mutate the same variables, i.e. they have a data race. If the assignments were wrapped into synchronized blocks, the reordering wouldn't be legal.

There's something true in your observation that if you don't read the heap, you won't actually notice the race that occured. However, it is safe to assume that any variable written to is also read at time, otherwise it has no purpose. As this small example should have examplified, the writes should not race or they could corrupt the heap, which can have unintended consequences later on.

Now, to make the situation worse, reads and writes aren't atomic on the JVM (reading and write doubles need to memory accesses). So if they race, they can corrupt the heap not only in the sense it's not consistent, but also in the sense that it contains value that never really existed.

Finally, the result of the assignment expression is the value of the variable after the assignment has occurred. So x = ( y = z ) is valid. This assumes that the write did not race with a concurrent race and return the value that was written.

To make the story short: if reads and writes are not properly synchronized, it becomes very very hard to guarantee anything about their effect.

Answer 4

see http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.5-500

We want two writes to have an happens-before relationship so that the later one can shadow the earlier one. Consider this example

hb(w1, r1), hb(w2, r1), hb(r1, r2), but not hb(w1, w2) or hb(w2, w1)

    w1   w2
     \   / 
      \ /
       |
       r1  // see w1 or w2
       |
       r2  // see w1 or w2

in a sequentially consistent execution, r2 and r1 must see the same value. However JMM is weakened to not guarantee that. Therefore this program is not "correctly synchronized."

If hb(w1, w2) or hb(w2, w1) JMM does guarantee that r2 and r1 see the same value.

       w1
       |
       w2
       |
       r1  // see w2
       |
       r2  // see w2

The basic idea is to link all writes and reads on one chain, so that each read is deterministic.

P.S. The definition of data race is buggy; two volatile actions should never be considered a data race, see Is volatile read happens-before volatile write?