Is it guaranteed that compareAndSwap can NOT fail for ALL the participating threads?

Question

Suppose some "N" number of threads are trying to CAS an AtomicInteger variable, Is it guaranteed that the CAS must succeed for exactly ONE thread?

Is there a possibility that all the "N" threads fail in an attempt?

Answer 1

compareAndSet is intended to be implemented by hardware so the behavior would depend on the particular hardware you're running on. From java.util.concurrent.atomic:

This method (which varies in argument types across different classes) atomically sets a variable to the updateValue if it currently holds the expectedValue, reporting true on success. The classes in this package also contain methods to get and unconditionally set values, as well as a weaker conditional atomic update operation weakCompareAndSet described below.

The specifications of these methods enable implementations to employ efficient machine-level atomic instructions that are available on contemporary processors. However on some platforms, support may entail some form of internal locking. Thus the methods are not strictly guaranteed to be non-blocking -- a thread may block transiently before performing the operation.

Assuming typical hardware, the first thread to reach the underlying hardware instruction will do an atomic CAS (assuming it has the correct initial value) and all other threads will fail.

If the underlying hardware allows all competing threads to fail, there doesn't seem to be anything in the Java API that requires different behavior. However, a CAS that could fail for all threads could lead to live-lock situations and non-deterministic behavior, so any hardware that implements CAS will probably guarantee one thread will succeed.

Answer 2

Maybe worth saying that you asked the question on the concurrency interest list and got the following answer:

Yes, it is guaranteed for AtomicX.compareAndSet.

Really, there is the distinction between "strong" and "weak" CAS, first one can not fail spuriously, and second one can. AtomicX.compareAndSet is the "strong" CAS. AtomicX.weakCompareAndSet is the example of "weak" CAS, and can fails spuriously for all threads without a particular reason.

On hardware that only has LL/SC instead of providing strong CAS directly, the internal implementation of strong CAS requires a retry loop.

So at a Java level, a strong CAS is still strong, but from a livelock / contention / hardware level it's actually retrying.