How does the happen-before property relate to visibility and ordering?

Question

I'd like some clarity on what exactly the happens-before property means.

I've seen explanations for the happens-before property say that updates to global variables (which are not volatile or enclosed in a sync block) are made visible to other threads if they are altered before some other variable which is volatile or altered within a sync block. Is this right? If so, where in the java documentation does it say this?

My understanding was that the happens-before property defines the relationship between shared fields and code execution e.g:

an unlock of a monitor happens-before every subsequent lock of the same monitor.
a write to a volatile field happens-before every subsequent read of that same field.
a call to start on a thread happens-before any action in the started thread.
all actions in a thread happen-before any other thread successfully returns from a join on that thread.

For example:

class Shared {

  private int y = 0;
  private volatile int x = 0;

  public void setOne() {
    y = 1;
    x = 1;
  }

  public int getY() {
    return y;
  }

}

For the code above, given 2 threads:

Shared shared = new Shared();

new Thread(() -> shared.setOne()).start();
new Thread(() -> shared.getY()).start();

Edit Assuming we can guarantee that the first thread has started, would getY() return 0 or 1 here?

I've also seen examples saying that this behavior happens only following a read of a volatile field in a thread. So in that case if one thread reads the value of the volatile field (let's say thread B), then all fields written before that volatile field in thread A are available to thread B. According this, if I modify the getY() method in Shared object from above to be:

  public int getXPlusY() {
    int local = x;
    return local + y;
  }

Is it this action that makes y visible to the other thread?

user_3199595 · Answer

Let's look at your second example first.

class Shared {

  private int y = 0;
  private volatile int x = 0;

  public void setOne() {
    y = 1; //(1)
    x = 1; //(2)
  }

  public int getXPlusY() {
    int local = x; //(3)
    return local + y; //(4)
  }
}

We know that there is a happens-before relationship between (1) and (2) due to program order:

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

Since x is volatile, we know that there's a happens-before relationship between (2) and (3)

A write to a volatile field (§8.3.1.4) happens-before every subsequent read of that field.

And there is a happens-before relationship between (3) and (4) due to program order again:

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

Therefore, we have a happens-before chain (1) → (2), (2) → (3), (3) → (4)

And since happens-before is a transitive relation (if A happens before B and B happens before C, then A happens before C) that means that (1) has a happens-before relation with (4).

Now let's look at the first example:

class Shared {

  private int y = 0;
  private volatile int x = 0;

  public void setOne() {
    y = 1; //(1)
    x = 1; //(2)
  }

  public int getY() {
    return y; //(3)
  }
}

There's again a happens-before relation between (1) and (2), but that's about it. Since x is not read by the second thread, we have no happens-before between (2) and (3). Therefore we have no happens-before relation between (1) and (3).

The quotes were taken from Chapter 17 of the Java Language Specification (JLS)

user_1059372 · Answer

I'll rename the classes to make it clear:

class First {

    private int y = 0;
    private volatile int x = 0;

    public void setOne() {
       y = 1;
       x = 1;
    }

    public int getY() {
       return y;
    }

}

And you pre-condition that:

Assuming we can guarantee that the first thread has started

There are zero guarantees that getY will return 1. Updates to a shared field are guaranteed to be visible to some reading thread only when you respect the happens-before rules of the JLS, none are enforced here. As such getting a 0 from getY is perfectly valid.

Your second example:

class Second {

    private int y = 0;
    private volatile int x = 0;

    public void setOne() {
       y = 1;
       x = 1;
    }

    public int getXPlusY() {
       int local = x;
       return local + y;
    }

}

again with the pre-condition that:

Assuming we can guarantee that the first thread has started

is NOT guaranteed to return 2. For that method to output 2, the reading thread must observe (see) the volatile write. That is it has to be something along these lines:

 public int getXPlusY() {
   int local = x;
   if(local == 1){ // you need to see the write that was done in the other thread
      return local + y;
   }
   return local + y;    
}

if you enter that if statement f(local == 1) you have observed the volatile write that was done in the other thread (x = 1) and, as such, you are guaranteed that everything that was done before that write is visible also. That means that at this point in time, y = 1, for sure, so your method will return 2.

Without this if statement, your read int local = x is a racy read, there is nothing stopping this thread to do int local = x in between the two:

y = 1;
x = 1;

It turns out this is provable also, here is a jcstress test that proves the other answer (at least 1/2 of it) wrong:

// https://stackoverflow.com/questions/58450777/how-does-the-happen-before-property-relate-to-visibility-and-ordering
@JCStressTest
@State
@Outcome(id = "0", expect = Expect.FORBIDDEN, desc = "can not happen")
@Outcome(id = "1", expect = Expect.FORBIDDEN, desc = "can not happen")
@Outcome(id = "2", expect = Expect.ACCEPTABLE, desc = "reader thread was done before writer did anything")
@Outcome(id = "3", expect = Expect.ACCEPTABLE_INTERESTING, desc = "racy read!!!")
@Outcome(id = "4", expect = Expect.ACCEPTABLE, desc = "reader thread sees everything that writer did")
public class VolatileRace {

    // change defaults so that "readerThread" does not output a false positive.
    // it can happen when it runs it's entire method body before "writerThread"
    // does anything at all.
    private int y = 1;
    private volatile int x = 1;

    @Actor
    public void writerThread() {
        y = 2;
        x = 2;
    }

    @Actor
    public void readerThread(I_Result result) {
        int local = x;
        result.r1 = local + y;
    }

}

The point of this test is that, it has such an output:

  0             0                FORBIDDEN  can not happen
  1             0                FORBIDDEN  can not happen
  2     4,616,926               ACCEPTABLE  reader thread was done before writer did anything
  3         6,694   ACCEPTABLE_INTERESTING  racy read!!!
  4     3,107,831               ACCEPTABLE  reader thread sees everything that writer did

Even if you don't understand it, it shows that the reading thread has seen 3 as its result, that means it has read x = 1 and y = 2.

How does the happen-before property relate to visibility and ordering?

2 Answers