Java CAS and the ABA Problem Explained

CAS is a hardware atomic instruction — compare-and-swap — with the semantic "if memory at address X currently equals expected value E, atomically replace it with new value N and return success; otherwise leave it alone and return failure." It's the building block of non-blocking concurrency. In Java you touch it through Unsafe or VarHandle, and AtomicInteger, AtomicLong, and even ConcurrentHashMap's bucket CAS are all built on it. The typical usage pattern is a retry loop: read current, compute new value, CAS; if someone else modified the field between the read and the CAS, CAS fails and you retry. The ABA problem is CAS's fundamental weakness. Thread T1 reads value A intending to CAS. Before T1 gets to execute the CAS, thread T2 changes A to B and then back to A. When T1 finally executes its CAS, it sees A and succeeds — but the underlying state has moved through an intermediate value and may be semantically different than it was when T1 first observed A. For primitive counters this rarely matters. For reference-based lock-free structures it's disastrous. Classic example: a lock-free stack where head is an AtomicReference. T1 reads head=A, plans to CAS head from A to A.next. Meanwhile T2 pops A (head becomes B), pops B (head becomes null), allocates a new node that happens to reuse A's memory, and pushes it (head becomes A again). T1's CAS sees A and succeeds, setting head to A.next — but A.next from the original view is pointing at B, which has since been freed/popped. Now the stack's head points into invalid memory. The fix is AtomicStampedReference: it wraps value + int stamp. Every set bumps the stamp, and compareAndSet checks both value and stamp match. Any intermediate write, even if the value returns to A, changes the stamp so the CAS fails and retry kicks in. AtomicMarkableReference is similar with a boolean mark, useful for "deleted" flags. In practice, primitive atomic counters don't need this; it's reference-based lock-free data structures where ABA bites.