Detailed semantics of volatile regarding timeliness of visibility

Question

Consider a volatile int sharedVar. We know that the JLS gives us the following guarantees:

1. every action of a writing thread w preceding its write of value i to sharedVar in program order happens-before the write action;
2. the write of value i by w happens-before the successful read of i from sharedVar by a reading thread r;
3. the successful read of i from sharedVar by the reading thread r happens-before all subsequent actions of r in program order.

However, there is still no wall-clock time guarantee given as to when the reading thread will observe the value i. An implementation that simply never lets the reading thread see that value still complies with this contract.

I have thought about this for a while and I can't see any loopholes, but I assume there must be. Please, point out the loophole in my reasoning.

Answer 1

Turns out that the answers and the ensuing discussions only consolidated my original reasoning. I now have something in the way of a proof:

1. take the case where the reading thread executes in full before the writing thread starts executing;
2. note the synchronization order that this particular run created;
3. now shift the threads in wall-clock time so they execute in parallel, but maintain the same synchronization order.

Since the Java Memory Model makes no reference to wall-clock time, there will be no obstructions to this. You now have two threads executing in parallel with the reading thread observing no actions done by the writing thread. QED.

Example 1: One writing, one reading thread

To make this finding maximally poignant and real, consider the following program:

static volatile int sharedVar;

public static void main(String[] args) throws Exception {
  final long startTime = System.currentTimeMillis();
  final long[] aTimes = new long[5], bTimes = new long[5];
  final Thread
    a = new Thread() { public void run() {
      for (int i = 0; i < 5; i++) {
        sharedVar = 1;
        aTimes[i] = System.currentTimeMillis()-startTime;
        briefPause();
      }
    }},
    b = new Thread() { public void run() {
      for (int i = 0; i < 5; i++) {
        bTimes[i] = sharedVar == 0?
            System.currentTimeMillis()-startTime : -1;
        briefPause();
      }
    }};
  a.start(); b.start();
  a.join(); b.join();
  System.out.println("Thread A wrote 1 at: " + Arrays.toString(aTimes));
  System.out.println("Thread B read 0 at: " + Arrays.toString(bTimes));
}
static void briefPause() {
  try { Thread.sleep(3); }
  catch (InterruptedException e) {throw new RuntimeException(e);}
}

As far as JLS is concerned, this is a legal output:

Thread A wrote 1 at: [0, 2, 5, 7, 9]
Thread B read 0 at: [0, 2, 5, 7, 9]

Note that I don't rely on any malfunctioning reports by currentTimeMillis. The times reported are real. The implementation did choose, however, to make all actions of the writing thread visible only after all the actions of the reading thread.

Example 2: Two threads both reading and writing

Now @StephenC argues, and many would agree with him, that happens-before, even though not explicitly mentioning it, still implies a time ordering. Therefore I present my second program that demonstrates the exact extent to which this may be so.

public static void main(String[] args) throws Exception {
  final long startTime = System.currentTimeMillis();
  final long[] aTimes = new long[5], bTimes = new long[5];
  final int[] aVals = new int[5], bVals = new int[5];
  final Thread
    a = new Thread() { public void run() {
      for (int i = 0; i < 5; i++) {
        aVals[i] = sharedVar++;
        aTimes[i] = System.currentTimeMillis()-startTime;
        briefPause();
      }
    }},
    b = new Thread() { public void run() {
      for (int i = 0; i < 5; i++) {
        bVals[i] = sharedVar++;
        bTimes[i] = System.currentTimeMillis()-startTime;
        briefPause();
      }
    }};
  a.start(); b.start();
  a.join(); b.join();
  System.out.format("Thread A read %s at %s\n",
      Arrays.toString(aVals), Arrays.toString(aTimes));
  System.out.format("Thread B read %s at %s\n",
      Arrays.toString(bVals), Arrays.toString(bTimes));
}

Just to help understanding the code, this would be a typical, real-world result:

Thread A read [0, 2, 3, 6, 8] at [1, 4, 8, 11, 14]
Thread B read [1, 2, 4, 5, 7] at [1, 4, 8, 11, 14]

On the other hand, you'd never expect to see anything like this, but it is still legit by the standards of the JMM:

Thread A read [0, 1, 2, 3, 4] at [1, 4, 8, 11, 14]
Thread B read [5, 6, 7, 8, 9] at [1, 4, 8, 11, 14]

The JVM would actually have to predict what Thread A will write at time 14 in order to know what to let the Thread B read at time 1. The plausibility and even feasibility of this is quite dubious.

From this we can define the following, realistic liberty that a JVM implementation can take:

The visibility of any uninterrupted sequence of release actions by a thread can be safely postponed until before the acquire action that interrupts it.

The terms release and acquire are defined in JLS §17.4.4.

A corrollary to this rule is that the actions of a thread which only writes and never reads anything can be postponed indefinitely without violating the happens-before relationship.

Clearing up the volatile concept

The volatile modifier is actually about two distinct concepts:

1. The hard guarantee that actions on it will respect the happens-before ordering;
2. The soft promise of a runtime's best effort towards a timely publishing of writes.

Note the point 2. is not specified by the JLS in any way, it just kind of arises by general expectation. An implementation that breaks the promise is still compliant, obviously. With time, as we move to massively parallel architectures, that promise may indeed prove to be quite flexible. Therefore I expect that in the future the conflation of the guarantee with the promise will prove to be insufficient: depending on requirement, we'll need one without the other, one with a different flavor of the other, or any number of other combinations.

Answer 2

You are partly correct. My understanding is that this would be legal though if and only if thread r did not engage in any other operations that had a happens-before relationship relative to thread w.

So there's no guarantee of when in terms of wall-clock time; but there is a guarantee in terms of other synchronisation points within the program.

(If this bothers you, consider that in a more fundamental sense, there is no guarantee that the JVM will ever actually execute any bytecode in a timely fashion. A JVM that simply stalled forever would almost certainly be legal, because it's essentially impossible to provide hard timing guarantees on execution.)

Answer 3

Please see this section (17.4.4). you have twisted the specification a bit, which is what is confusing you. the read/write specification for volatile variables says nothing about specific values, specifically:

• A write to a volatile variable (§8.3.1.4) v synchronizes-with all subsequent reads of v by any thread (where subsequent is defined according to the synchronization order).

UPDATE:

As @AndrzejDoyle mentions, you could conceivably have thread r read a stale value as long as nothing else that thread does after that point establishes a synchronization point with thread w at some later point in the execution (as then you would be in violation of the spec). So yes, there is some wiggle room there, but thread r would be very restricted in what it could do (for instance, writing to System.out would establish a later sync point as most stream impls are synchronized).

Answer 4

I don't believe any of the below anymore. It all comes down to the meaning of "subsequent," which is undefined except for two mentions in 17.4.4, where it's tautologically "defined according to the synchronization order".)

The only thing we really have to go on is in section 17.4.3:

Sequential consistency is a very strong guarantee that is made about visibility and ordering in an execution of a program. Within a sequentially consistent execution, there is a total order over all individual actions (such as reads and writes) which is consistent with the order of the program, and each individual action is atomic and is immediately visible to every thread. (emphasis added)

I think there is such a real-time guarantee, but you have to piece it together from various sections of JLS chapter 17.

1. According to section 17.4.5, "the happens-before relation defines when data races take place." It doesn't seem to be explicitly stated, but I assume that this means that if an action a happens-before another action a', there is no data race between them.
2. According to 17.4.3: "A set of actions is sequentially consistent if ... each read r of a variable v sees the value written by the write w to v such that w comes before r in the execution order ... If a program has no data races, then all executions of the program will appear to be sequentially consistent."

If you write to a volatile variable v and subsequently read from it in another thread, that means that the writes happens-before the read. That means that there is no data race between the write and the read, which means they must be sequentially consistent. That means the read r must see the value written by the write w (or a subsequent write).

Answer 5

I think the volatile in Java is expressed in terms of "if you see A you will also see B".

To be more explicit, Java promises that when you thread reads a volatile variable foo and sees value A, you have some guarantees as to what you will see when you read other variables later on the same thread. If the same thread that wrote A to foo also wrote B to bar (before writing A to foo), you're guaranteed to see at least B in bar.

Of course, if you never get to see A, you can't be guaranteed to see B either. And if you see B in bar, that says nothing about the visibility of A in foo. Also, the time that elapses between the thread writing A to foo and another thread seeing A in foo is not guaranteed.