compareAndSet memory effects of unsuccessful operations

Question

Java exposes the CAS operation through its atomic classes, e.g.

boolean compareAndSet(expected,update)

The JavaDocs specifies the memory effects of a compareAndSet operation as follows:

compareAndSet and all other read-and-update operations such as getAndIncrement have the memory effects of both reading and writing volatile variables.

This definitely holds for successful compareAndSet invocations. But do the memory effects also hold if compareAndSet returns false?

I would say that an unsuccessful compareAndSet corresponds to a volatile read (as the current value of the atomic instance has to be accessed in this case), but I do not see why an CAS should perform special memory barrier instructions in the unsuccessful case.

The question actually is, whether an unsuccessful CAS also establishes a happens-before relationship. Consider the following program:

public class Atomics {
    private static AtomicInteger ai = new AtomicInteger(5);
    private static int x = 0;

    public static void main(String[] args) {
        new Thread(() -> {
            while (x == 0) {
                ai.compareAndSet(0, 0); // returns false
            }
        }, "T1").start();

        new Thread(() -> {
            x = 1;
            ai.compareAndSet(0, 0); // returns false
        }, "T2").start();
    }
}

Will thread T2 (and the program) definitely terminate?

Answer 1

The problem with establishing a happens-before relationship using volatile reads and writes is that such a relationship exists only for a write and a subsequent read. If one thread T1 writes to a shared volatile variable and another thread T2 reads from the same variable, there can’t be a happens-before relationship if T2 read the variable before T1 wrote to it. If all that determines whether T1 writes before T2 reads is the thread scheduling, we don’t have any guarantees.

A practical way of dealing with it without additional synchronization is to evaluate the actual value, T2 has read. If this value makes it apparent that T1 has already written the new value, we have a valid happens-before relationship. This is how it works when using a volatile boolean fooIsInitialized flag or a volatile int currentPhase counter. It’s obvious that this can’t work if the value written is the same as the old value or if the new value was never actually written.

The problem with your example program is that it speculates about the thread scheduling. It assumes that T2 eventually performs the cas action and that there will be a subsequent iteration in T1 in which the next cas will create a happens-before relationship. But this is not guaranteed. It might not be intuitively understandable but without synchronization all iterations of T1 could happen before the actions of T2, even if the loop is infinite. It is even a valid thread scheduling behavior, letting T1 running forever consuming 100% CPU time before ever assigning CPU time to T2 as preemptive thread switching between threads of equal priority is not guaranteed.

But even if the underlying system does assign CPU time to T2, which will eventually perform the actions, there is no need for the JVM to make this apparent to T1 as it’s not observable to T1 that T2 has ever ran. It’s unlikely to ever spot this in a real life implementation but the answer still is that there is no guaranty. Things change when there is a chain of actions that will make it observable to T1 that T2 ran (i.e. changed its status) but of course, that chain of actions would make the cas obsolete.