5

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.

Community
  • 1
  • 1
nosid
  • 48,932
  • 13
  • 112
  • 139
  • Can you be more clear on your question "What's the rationale for not guaranteeing sequential consistency in case of two write operations to the same variable" ? do you mean the guarantee from the underlying JVM or OS? – Algorithmist Sep 01 '13 at 15:50
  • How non-java models are free of conflict? How ever you can be free of conflict when one commander makes order whereas another commands another? "Am am loosing ground here" (George Carlin tm) – Val Sep 01 '13 at 16:17

4 Answers4

3

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.

Henry
  • 42,982
  • 7
  • 68
  • 84
  • This case is already covered by §17.7 in the JLS7. That means it is irrelevant for my question. – nosid Sep 01 '13 at 21:13
  • @nosid I can't follow you there. You are asking why two writes are not considered acceptable sequential behavior and this is the perfect example: Multiple writes to a variable without synchronization between result in undefined behavior for lots of CPUs. – Voo Sep 01 '13 at 23:03
  • @Voo: §17.7 states that **for the purpose** of the Java memory model, a single write to a non-volatile `long` or `double` value is treated as two separate writes: one to each 32-bit half. That means, the above example contains four write operations to two different variables. And there is a _sequentially consistent_ execution, with the "inconsistent" result. – nosid Sep 02 '13 at 11:03
  • @nosid Ah that's your problem. Well then just imagine writing to an int across a cacheline or page. Exactly same problem. – Voo Sep 02 '13 at 11:04
  • @Voo: I have the impression that we are talking past each other. I am not talking about the hardware architecture. I am talking about the abstract machine defined by the JLS. I have accepted meriton's answer, because it contains a full example that shows, why _ordered_ write operations are required for _sequential consistency_. – nosid Sep 02 '13 at 16:12
3

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.

meriton
  • 68,356
  • 14
  • 108
  • 175
  • Have to downvote that because the "may print " part is misleading. If you have conflicting writes the result is undefined and can be everything from 0 to all 1s. Just assuming "one random write will win" is not correct. – Voo Sep 01 '13 at 17:20
  • 1
    Thanks. This example makes it very clear why write operations are conflicting. – nosid Sep 01 '13 at 21:08
  • Your example is misleading, since the states 11,12,21,22 are all states that can be reached with sequentially consistent executions. The point is, without proper synchronization, you can have executions that *aren't* sequentially consistent, and your example fails to show that. As @Voo said, it's not only about "which write wins". – ewernli Sep 02 '13 at 07:09
  • Actually, even if all four assignements were wrapped in individual synchronized blocks, the end state could still be 11,12,21, or 22. – ewernli Sep 02 '13 at 07:13
  • 1
    The idea is good, but you have to swap the write operations in `t2`. Then `12` is not possible in _sequentially consistent_ executions. – nosid Sep 02 '13 at 08:07
  • @nosid: Right you are, fixed. Now, 12 is a possible outcome, but not sequentially consistent. – meriton Sep 02 '13 at 15:56
  • @Voo: I disagree. The Java Tutorial [writes](http://docs.oracle.com/javase/tutorial/essential/concurrency/atomic.html): "Reads and writes are atomic for reference variables and for most primitive variables (all types except long and double)." and "An atomic action cannot stop in the middle: it either happens completely, or it doesn't happen at all." And since the main thread joins both t1 and t2, the writes happen-before the println, and happens-before consistency requires that a write has occured, and the field therefore no longer contains the initial value. – meriton Sep 02 '13 at 16:24
2

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.

Community
  • 1
  • 1
ewernli
  • 38,045
  • 5
  • 92
  • 123
  • I can't imagine that's the reason. Do you have a reference showing that write operations are read operations at the same time? – nosid Sep 01 '13 at 21:00
  • @nosid Rewritten. The key point is sequential consistency, i.e preserving the natural program order, not "which write wins" or "writes are not atomic". – ewernli Sep 02 '13 at 07:11
  • Thanks for the explanation. Regarding my question, the important part is the one with the variables `a` and `b`. I upvoted your answer. However, I have accepted meriton's answer, because it contains a full example. – nosid Sep 02 '13 at 16:07
  • @ewernli Sorry to bring back this topic,but in your answer you have the execution b=5,a=3,b=4,a=6 twice. It is confusing,since the number of interleavings is 6 not 7. – notArefill Aug 27 '14 at 09:57
1

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?

Community
  • 1
  • 1
ZhongYu
  • 19,446
  • 5
  • 33
  • 61
  • Sorry, I didn't get it. Do you have an example with these _happens-before_ relationships? – nosid Sep 02 '13 at 16:37
  • 2 threads write to a variable. main thread joins the two threads, then reads the variable twice. – ZhongYu Sep 02 '13 at 18:18