JMM: Why this outcome is illegal?

Question

I recently stumbled upon this example in jcstress:

@JCStressTest
@State
@Outcome(id = "10",                      expect = ACCEPTABLE,             desc = "Boring")
@Outcome(id = {"0", "1"},                expect = FORBIDDEN,              desc = "Boring")
@Outcome(id = {"9", "8", "7", "6", "5"}, expect = ACCEPTABLE,             desc = "Okay")
@Outcome(                                expect = ACCEPTABLE_INTERESTING, desc = "Whoa")
public static class Volatiles {
    volatile int x;

    @Actor
    void actor1() {
        for (int i = 0; i < 5; i++) {
            x++;
        }
    }

    @Actor
    void actor2() {
        for (int i = 0; i < 5; i++) {
            x++;
        }
    }

    @Arbiter
    public void arbiter(I_Result r) {
        r.r1 = x;
    }
}

The author highlights that since increments are not atomic operations one cannot expect to just "lose" one increment update per loop iteration. So then all outcomes (up to 10) except 0 and 1 are allowed (and indeed happen).

I see why 0 is not allowed: there is an HB edge between the initialization of default values of objects and the first action in every thread as stated in JLS. JLS 17.4.4

The write of the default value (zero, false, or null) to each variable synchronizes-with the first action in every thread.

The author also explains how one might get the result 2:

The most interesting result, "2" can be explained by this interleaving:
        Thread 1: (0 ------ stalled -------> 1)     (1->2)(2->3)(3->4)(4->5)
        Thread 2:   (0->1)(1->2)(2->3)(3->4)    (1 -------- stalled ---------> 2)

I understand that you cannot just "extend" the explanation above like this:

        Thread 1: (0 --------- stalled -----------> 1)     (1->2)(2->3)(3->4)(4->5)
        Thread 2:   (0->1)(1->2)(2->3)(3->4)(4->5)

Because it leads to the result 5. But isn't there an execution that will produce 1? I definitely can't think of any. But why there actually is none?

user19972573 · Answer

Firstly, let's remember how volatile works in Java.

In Java all volatile reads and writes happen in a global order in runtime (i.e. synchronization order in JLS 17.4.4).
Properties of this global order:

it preserves the order of volatile reads/writes of every thread (in terms of JLS 17.4.4 it is consistent with the program order)
it's one per execution: actions from different threads can interleave differently in different executions of the same program

A volatile read always returns the last (in this global order) volatile write to this variable (i.e. synchronizes-with in JLS 17.4.4).

Secondly, let's clarify that "increments are not atomic operations" means x++ consists of 3 atomic actions:

var temp = x;     // volatile read of 'x' to local variable 'temp'
temp = temp + 1;  // increment of local variable 'temp'
x = temp;         // volatile write to `x`

Finally, let's rewrite

The most interesting result, "2" can be explained by this interleaving:
        Thread 1: (0 ------ stalled -------> 1)     (1->2)(2->3)(3->4)(4->5)
        Thread 2:   (0->1)(1->2)(2->3)(3->4)    (1 -------- stalled ---------> 2)

in a way that shows volatile reads and writes to x:

Thread1    Thread2
r₁₀:0                  | global
            r₂₀:0      | order of
            w₂₁:1      | volatile
            r₂₂:1      | reads
            w₂₃:2      | and
            r₂₄:2      | writes
            w₂₅:3      V
            r₂₆:3
            w₂₇:4
w₁₁:1
            r₂₈:1
r₁₂:1
w₁₃:2
r₁₄:2
w₁₅:3
r₁₆:3
w₁₇:4
r₁₈:4
w₁₉:5
            w₂₉:2

On this diagram:

the global order of volatile reads and writes goes from top to bottom
r:1 is a volatile read of x which returns 1
w:1 is a volatile write of 1 to x

Notice that:

w always writes the value of the previous r in the same thread incremented by 1
r always return the value written by the previous w in the global order

Now we can answer your question:

But isn't there an execution that will produce 1? I definitely can't think of any. But why there actually is none?

look at the last write in the global order w₂₉: it always writes (the value read by r₂₈)+1
(BTW the last write in the global order will always be either the last write w₁₉ in Thread1 or the last write w₂₉ in Thread2; in this case it's w₂₉, but for w₁₉ the reasoning is the same)
r₂₈ always reads the previous write in the global order, which is:
- either w₂₇ from the same thread
- or some write w₁ₓ from Thread1 (if w₁ₓ happens in between w₂₇ and r₂₈ in runtime)
In any case r₂₈ always returns some previous non-initial write.
But every non-initial write always writes at least 1.
That means w₂₉ always writes at least 2.

JMM: Why this outcome is illegal?

1 Answers