Happens-before reasoning applied to some examples

We will present some examples to show how to apply happens-before reasoning to check that writes are visible to subsequent reads.

Single-threaded code

As you would expect, writes are always visible to subsequent reads in a single-threaded program.

public class SingleThreadExample {
    public int a, b;
    
    public int add() {
       a = 1;         // write(a)
       b = 2;         // write(b)
       return a + b;  // read(a) followed by read(b)
    }
}

By Happens-Before Rule #1:

1. The write(a) action happens-before the write(b) action.
2. The write(b) action happens-before the read(a) action.
3. The read(a) action happens-before the read(a) action.

By Happens-Before Rule #4:

1. write(a) happens-before write(b) AND write(b) happens-before read(a) IMPLIES write(a) happens-before read(a).
2. write(b) happens-before read(a) AND read(a) happens-before read(b) IMPLIES write(b) happens-before read(b).

Summing up:

1. The write(a) happens-before read(a) relation means that the a + b statement is guaranteed to see the correct value of a.
2. The write(b) happens-before read(b) relation means that the a + b statement is guaranteed to see the correct value of b.

Behavior of ‘volatile’ in an example with 2 threads

We will use the following example code to explore some implications of the Memory Model for `volatile.

public class VolatileExample {
    private volatile int a;
    private int b;         // NOT volatile
    
    public void update(int first, int second) {
       b = first;         // write(b)
       a = second;         // write-volatile(a)
    }

    public int observe() {
       return a + b;       // read-volatile(a) followed by read(b)
    }
}

First, consider the following sequence of statements involving 2 threads:

1. A single instance of VolatileExample is created; call it ve,
2. ve.update(1, 2) is called in one thread, and
3. ve.observe() is called in another thread.

By Happens-Before Rule #1:

1. The write(a) action happens-before the volatile-write(a) action.
2. The volatile-read(a) action happens-before the read(b) action.

By Happens-Before Rule #2:

1. The volatile-write(a) action in the first thread happens-before the volatile-read(a) action in the second thread.

By Happens-Before Rule #4:

1. The write(b) action in the first thread happens-before the read(b) action in the second thread.

In other words, for this particular sequence, we are guaranteed that the 2nd thread will see the update to the non-volatile variable b made by the first thread. However, it is should also be clear that if the assignments in the update method were the other way around, or the observe() method read the variable b before a, then the happens-before chain would be broken. The chain would also be broken if volatile-read(a) in the second thread was not subsequent to the volatile-write(a) in the first thread.

When the chain is broken, there is no guarantee that observe() will see the correct value of b.

Volatile with three threads

Suppose we to add a third thread into the previous example:

1. A single instance of VolatileExample is created; call it ve,
2. Two threads call update:

- `ve.update(1, 2)` is called in one thread,
- `ve.update(3, 4)` is called in the second thread,

1. ve.observe() is subsequently called in a third thread.

To analyse this completely, we need to consider all of the possible interleavings of the statements in thread one and thread two. Instead, we will consider just two of them.

Scenario #1 - suppose that update(1, 2) precedes update(3,4) we get this sequence:

write(b, 1), write-volatile(a, 2)     // first thread
write(b, 3), write-volatile(a, 4)     // second thread
read-volatile(a), read(b)             // third thread

In this case, it is easy to see that there is an unbroken happens-before chain from write(b, 3) to read(b). Furthermore there is no intervening write to b. So, for this scenario, the third thread is guaranteed to see b as having value 3.

Scenario #2 - suppose that update(1, 2) and update(3,4) overlap and the ations are interleaved as follows:

write(b, 3)                           // second thread
write(b, 1)                           // first thread
write-volatile(a, 2)                  // first thread
write-volatile(a, 4)                  // second thread
read-volatile(a), read(b)             // third thread

Now, while there is a happens-before chain from write(b, 3) to read(b), there is an intervening write(b, 1) action performed by the other thread. This means we cannot be certain which value read(b) will see.

(Aside: This demonstrates that we cannot rely on volatile for ensuring visibility of non-volatile variables, except in very limited situations.)