Atomics and compare-and-swap question 56 of 180 senior
What is the ABA problem, and how do you avoid it?
- A CAS that fails twice in a row
- Correct: A value changes from A to B and back to A, so a CAS succeeds even though the state it assumed has been replaced
- Two threads reading the same value
- A deadlock between two atomics
CAS compares values, not history. A thread reads A, is descheduled, and meanwhile another thread changes the value to B and back to A. The first thread's CAS succeeds, because A is what it expected, even though everything it inferred from seeing A is now wrong.
With an AtomicInteger counter this is usually harmless. With references it is not: in a lock-free
stack, the node you read may have been popped, reused and pushed again, and your CAS quietly links a
freed node back into the list.
The fix is a version stamp, so the pair (value, counter) never repeats:
AtomicStampedReference for an int stamp, AtomicMarkableReference for a single boolean. Java's
garbage collector removes the worst form of this, which is why ABA bites C++ far harder.
Quiz yourself on Atomics and compare-and-swap Suggest a correction