Reordering of reads

Question

Suppose there are two threads without synchronization, one sets n = 1 another executes method().

In the following "read" always refers to a read of field n.

public class MyClass {   public int n = 0;    public void method() {     System.out.println(n); //read 1     System.out.println(n); //read 2   } } 

Would the following output be possible?

1 0 

The answer is yes because even though read 1 happens-before read 2, it is nevertheless possible for read 2 to be re-ordered before read 1 because it wouldn't change the semantics of intra-thread execution.

Is this reasoning correct?

Answer 1

Happens-before does not imply the order for two arbitrary operations. To be more precise, the most important thing that happens-before does is tying up writes and reads in happens-before consistency. Notably, it tells what writes can a read observe: the last write in happens-before order, or any other write not ordered in happens-before (race). Note that two consecutive reads may see different values obtained from different (racy) writes, without violating that requirement.

E.g. JLS 17.4.5 says:

It should be noted that the presence of a happens-before relationship between two actions does not necessarily imply that they have to take place in that order in an implementation. If the reordering produces results consistent with a legal execution, it is not illegal.

Data races are creepy like that: racy reads can return surprising data on each read, and Java memory model captures that. So the more precise answer is that an execution that produces (1, 0) is not violating Java Memory Model constraints (sync order consistency, sync order - program order consistency, happens-before consistency, causality requirements), and therefore allowed.

Implementation-wise: on hardware, both loads can be started and/or arrive to memory subsystem at different times, regardless of their "program order", because they are independent; in compilers, instruction scheduling may also disregard the program order for the independent reads, exposing loads to hardware in "counter-intuitive" order.

If you want reads to be observed in the program order, you need a stronger property. JMM gives that property to synchronization actions (in your example, making a variable volatile would make that), which ties the actions in the total synchronization order that is consistent with program order. In that case, (1, 0) would be prohibited.

Illustration on a very special jcstress testcase (see the full source for caveats):

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(IntResult2 r) {     Holder h1 = this.h1;     Holder h2 = this.h2;     h1.trap = 0;     h2.trap = 0;     r.r1 = h1.a;     r.r2 = h2.a; } 

Even on x86 that does not reorder loads, yields (1, 0), oops:

      [OK] o.o.j.t.volatiles.ReadAfterReadTest                                                                                                           (fork: #1, iteration #1, JVM args: [-server])   Observed state   Occurrences              Expectation  Interpretation                                                         [0, 0]    16,736,450               ACCEPTABLE  Doing both reads early.                                                [1, 1]   108,816,262               ACCEPTABLE  Doing both reads late.                                                 [0, 1]         3,941               ACCEPTABLE  Doing first read early, not surprising.                                [1, 0]        84,477   ACCEPTABLE_INTERESTING  First read seen racy value early, and the s... 

Making Holder.a volatile would make (1, 0) to go away.

Answer 2

We have 4 actions, that form the following happens-before graph:

+-------+     ?    +-------+ | n = 0 |   ---->  | n = 1 | +-------+          +-------+     |     |?     v   +---+             +---+   | n |     ---->   | n |   +---+             +---+ 

Since you are not giving the code that initializes n, it is not known whether n=0 happens-before n=1, and whether n=0 happens-before the first read of n.

If these edges do not exist, (n=1, n, n=0, n) is a sequentially consistent execution order, and the output 1 0 is trivially possible.

If it is known that n=0 happens-before n=1, there is no sequentially consistent execution with the output 1 0.

However, the Java Language Specification only guarantees that all executions are sequentially consistent if they are free of data races, which our program is not. Specifically, the spec writes:

More specifically, if two actions share a happens-before relationship, they do not necessarily have to appear to have happened in that order to any code with which they do not share a happens-before relationship. Writes in one thread that are in a data race with reads in another thread may, for example, appear to occur out of order to those reads.

And

We say that a read r of a variable v is allowed to observe a write w to v if, in the happens-before partial order of the execution trace:

• r is not ordered before w (i.e., it is not the case that hb(r, w)), and

• there is no intervening write w' to v (i.e. no write w' to v such that hb(w, w') and hb(w', r)).

In our case, both reads are allowed to observe both 0 and 1, because there is no intervening write.

Therefore, as far as I can tell, the output 1 0 is permitted by the Java Language Specification.