Reading a stale value after a newer value was read

Question

Consider this example. We're having:

int var = 0;

Thread A:

System.out.println(var);
System.out.println(var);

Thread B:

var = 1;

The threads run concurrently. Is the following output possible?

1
0

That is, the original value is read after the new value was read. The var isn't volatile. My gut feeling is that it's not possible.

Answer 1

You are using System.out.println that internally does a synchronized(this) {...} that will make things a bit more worse. But even with that, your reader thread can still observe 1, 0, i.e. : a racy read.

I am by far not an expert of this, but after going through lots of videos/examples/blogs from Alexey Shipilev, I think I understand at least something.

JLS states that :

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

Since both reads of var are in program order, we can draw:

                (po) 
firstRead(var) ------> secondRead(var)
// po == program order

That sentence also says that this builds a happens-before order, so:

                (hb) 
firstRead(var) ------> secondRead(var)
// hb == happens before

But that is within "the same thread". If we want to reason about multiple threads, we need to look into synchronization order. We need that because the same paragraph about happens-before order says:

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

So if we build this chain of actions between program order and synchronizes-with order, we can reason about the result. Let's apply that to your code:

            (NO SW)                    (hb)
write(var) ---------> firstRead(var) -------> secondRead(var)

// NO SW == there is "no synchronizes-with order" here
// hb    == happens-before

And this is where happens-before consistency comes at play in the same chapter:

A set of actions A is happens-before consistent if for all reads r in A, where W(r) is the write action seen by r, it is not the case that either hb(r, W(r)) or that there exists a write w in A such that w.v = r.v and hb(W(r), w) and hb(w, r).

In a happens-before consistent set of actions, each read sees a write that it is allowed to see by the happens-before ordering

I admit that I very vaguely understand the first sentence and this is where Alexey has helped me the most, as he puts it:

Reads either see the last write that happened in the happens-before or any other write.

Because there is no synchronizes-with order there, and implicitly there is no happens-before order, the reading thread is allowed to read via a race. and thus get 1, than 0.

---

As soon as you introduce a correct synchronizes-with order, for example one from here

An unlock action on monitor m synchronizes-with all subsequent lock actions on...

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

The graph changes (let's say you chose to make var volatile):

               SW                       PO
write(var) ---------> firstRead(var) -------> secondRead(var)

// SW == there IS "synchronizes-with order" here
// PO == happens-before

PO (program order) gives that HB (happens before) via the first sentence I quoted in this answer from the JLS. And SW gives HB because:

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

As such:

               HB                       HB
write(var) ---------> firstRead(var) -------> secondRead(var)

And now happens-before order says that the reading thread will read the value that was "written in the last HB", or it means that reading 1 then 0 is impossible.

---

I took the example jcstress samples and introduced a small change (just like your System.out.println does):

@JCStressTest
@Outcome(id = "0, 0", expect = Expect.ACCEPTABLE, desc = "Doing both reads early.")
@Outcome(id = "1, 1", expect = Expect.ACCEPTABLE, desc = "Doing both reads late.")
@Outcome(id = "0, 1", expect = Expect.ACCEPTABLE, desc = "Doing first read early, not surprising.")
@Outcome(id = "1, 0", expect = Expect.ACCEPTABLE_INTERESTING, desc = "First read seen racy value early, and the second one did not.")
@State
public class SO64983578 {

    private final Holder h1 = new Holder();
    private final Holder h2 = h1;

    private static class Holder {

        int a;
        int trap;
    }

    @Actor
    public void actor1() {
        h1.a = 1;
    }

    @Actor
    public void actor2(II_Result r) {
        Holder h1 = this.h1;
        Holder h2 = this.h2;
        
        h1.trap = 0;
        h2.trap = 0;

        synchronized (this) {
            r.r1 = h1.a;
        }

        synchronized (this) {
            r.r2 = h2.a;
        }

    }

}

Notice the synchronized(this){....} that is not part of the initial example. Even with synchronization, I still can see that 1, 0 as a result. This is just to prove that even with synchronized (that comes internally from System.out.println), you can still get 1 than 0.

Answer 2

When the value of var is read and it's 1 it won't change back. This output can't happen, neither due to visibility nor reorderings. What can happen is 0 0, 0 1 and 1 1.

The key point to understand here is that println involves synchronization. Look inside that method and you should see a synchronized there. These blocks have the effect that the prints will happen in just that order. While the write can happen anywhen, it's not possible that the first print sees the new value of var but the second print sees the old value. Therefore, the write can only happen before both prints, in-between or after them.

Besides that, there is no guarantee that the write will be visible at all, as var is not marked with volatile nor is the write synchronized in any way.

Answer 3

I think what is missing here is the fact that those threads run on actual physical cores and we have few possible variants here:

1. all threads run on the same core, then the problem is reduced to the order of execution of those 3 instructions, in this case 1,0 is not possible I think, println executions are ordered due to the memory barriers created by synchronisation, so that excludes 1,0

2. A and B runs on 2 different cores, then 1,0 does not look possible either, as as soon the core that runs thread A reads 1, there is no way it will read 0 after, same as above printlns are ordered.

3. Thread A is rescheduled in between those 2 printlns, so the second println is executed on a different core, either the same as B was/will be executed or on a different 3rd core. So when the 2 printlns are executed on a different cores, it depends what value does 2 cores see, if var is not synchronised (it is not clear is var a member of this), then those 2 cores can see different var value, so there is a possibility for 1,0.

So this is a cache coherence problem.

P.S. I'm not a jvm expert, so there might be other things in play here.

Answer 4

Adding to the other answers:

With long and double, writes may not be atomic so the first 32 bits could become visible before the last 32 bits, or viceversa. Therefore completely different values could be output.