Sequential consistency volatile explanation

Question

I am watching video from java jpoint conference.

I have question about following slide from Alexey Shipilev report:

Excuse me for non-english on slide. Actually author says that it is impossible that variable set will be

r1 = 1 (Y)
r2 = 0 (x)
r3 = 1 (x)
r4 = 0 (Y)

According the video he implies that it is obviously.

Can someone clarify why this value set impossible according JMM?

P.S.

If I understand Alexey notation correct it respects the following code:

public class SequentialConsistency {
    static volatile int x;
    static volatile int y;

    public static void main(String[] args) {
        new Thread(new Runnable() {
            @Override
            public void run() {
                x = 1;
            }
        }).start();
        new Thread(new Runnable() {
            @Override
            public void run() {
                y = 1;
            }
        }).start();
        new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println("r1=" + x + ", r2=" + y);
            }
        }).start();
        new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println("r3=" + x + ", r4=" + y);
            }
        }).start();
    }
}

Tellurate

Why would your code correctly represent the slide when your code doesn't have a volatile x,y; and doesn't have r3 and r4? – Jacindajacinta

@Erwin Bolwidt I could not translate you question. Can you rephrase it ? – Tellurate

Where are x, y, r3 and r4 in your code? – Jacindajacinta

oops, excuse me. One moment – Tellurate

@Erwin, I corrected. I haven't create r1-r4 explicitly but I believe it is obviously – Tellurate

Answer 1

You can construct exhaustive list of SC executions for this code, and realize no SC execution yields (1, 0, 1, 0).

Model-wise, it is very easy to argue about. Synchronization order (SO) consistency says that synchronized reads should see the last synchronized write in SO. SO-PO consistency says SO should be consistent with program order.

This allows to sketch the proof by contradiction. Suppose the execution that yields (1, 0, 1, 0) exists. Then, in those executions read that see zeroes must be in this order, due to SO consistency:

(r2 = x):0 --so--> (x = 1)  [1]
(r4 = y):0 --so--> (y = 1)  [2]

...and the other two reads must be in this order with writes to see them (due to SO consistency):

(x = 1) --so--> (r3 = x):1  [3]
(y = 1) --so--> (r1 = y):1  [4]

...and further, due to SO-PO consistency:

(r1 = y):1 --po--> (r2 = x):0  [5]
(r3 = x):1 --po--> (r4 = y):0  [6]

This yields weird transitive SO that is cyclic:

(r2 = x):0 --so--> (r3 = x):1 --so--> (r4 = y):0 --so--> (r1 = y):1 --so--> (r2 = x):0
            [1,3]               [6]               [2,4]               [5]

Notice that for any pair of actions A != B in the execution above, we can say (A --so--> B) and (B --so--> A) -- this is called symmetry. By definition, SO is total order, and total order is antisymmetric, and here we have the symmetric one. We have arrived to contradiction, and therefore such execution does not exist. Q.E.D.

Stokowski

Answer 2

Believe that I understood.

Lets say we have 4 thread. t1-t4(from left to right according the picture)

t3 reads y and then x and we see result

y=1
x=0

It means that sequence was following:

1. t1 writes y
2. t3 reads y
3. t3 reads x
4. t2 writes x

It is the only posiible sequence.

Lets check it for t4 readings:

x=1
y=0

According reasonings as for t3 it means that

t2 write happens before t1 write but it contradicts t3 output thus it is impossible

Tellurate

Because the variable are marked as volatile they are not store in thread local memory, they stay in the jvm main memory. Meaning that y = 1 will be true for all thread, so its impossible for any thread to read y = 0 if the value has been set to 1. If the values where not marked as volatile it would be possible for the thread to have any given sequence of values, because the value would be store in the threads memory. Meaning that every thread could contain a different value for the same variable. This has happen to me a lot of times, local thread memory is a pain. – Cheltenham

@Cheltenham there is no such thing as "JVM main memory", as such, everything that follows in your explanation makes no sense – Matrimony

Okay fair enough. But this is not about how java manages memory in detail. You can find the term "main memory" in all this articles: tutorials.jenkov.com/java-concurrency/volatile.html , baeldung.com/java-volatile ,javamex.com/tutorials/synchronization_volatile.shtml . Just as a reference. – Cheltenham

@Cheltenham two of these articles only refer to “main memory” a single time, when saying how CPUs work. The JMM, however, is not (only) about how CPUs work, but which optimizations a JVM’s JIT compiler is allowed to do. In fact, it even affects what bytecode a compiler can (legally) create for certain source code constructs. Besides that, threads run with an unspecified scheduling behavior and timing. Even if there were no “local memory” you’d get inconsistent results when accessing mutable data without proper synchronization primitives. – Pastoral

Answer 3

You can think about it in a slightly more simple form (though you can't get any more correct than Aleksey put it). volatile in java offers sequential consistency, which means that operations are done like in a global and atomic order. If you write to a field (x = 1), everyone will see that write. To make it more correct according to your example, if there is a ThreadA that does x = 1, both ThreadB (that does r2 = x) and ThreadC (that does r3 = x), will read x to be 1. This is what sequential consistency guarantees.

The slides show that in a SC (sequential consistent) execution: 1, 0, 1, 0 is impossible. Because that would mean that:

ThreadA wrote to x value of 1
ThreadB observed that value to be 1 (via r2 = x)
ThreadC observed that value to be 0 (via r3 = x)

But in a SC world, once a write happens (and we know it happened because ThreadB has observed it), it must be observed by everyone else. Which is not the case here : ThreadC sees x to be 0. As such, this breaks SC.

You have to recall that his point is - "Can we replace every volatile with release/acquire? (it is cheaper after all)". And the answer is no, because SC prohibits 1, 0, 1, 0, while release/acquire allows it.

Matrimony

Is this simplified example accurate? I don't quite understand the 'once a write happens, it must be observed by everyone else' point. The Threads are all independent, right? If in 'real time' ThreadC reads x as 0, then ThreadA writes 1 to x, then ThreadB reads x as 1, how is that sequentially inconsistent? – Effective

@ChristopherNg that’s an oversimplification in this answer. The order proposed in the answer is determined by the values read from y. But you can also use the order proposed in your comment (determined by the values read from x) and then show, that the reads and writes of y are not sequentially consistent with it. – Pastoral