Synchronization Primitives • Compare-and-Swap & Atomic OperationsHard⏱️ ~3 min
The ABA Problem
Key Insight
CAS checks if a value equals expected. But what if the value changed from A to B and back to A? CAS sees A and thinks nothing changed, but the underlying data structure may be corrupted.
ABA Problem Timeline
The Classic Example
Lock-free stack. Thread 1 reads head=A, wants to pop. Gets paused. Thread 2 pops A, pops B, pushes a new node reusing A's memory. Thread 1 resumes, CAS(head, A, B) succeeds. But B was already popped! Stack is corrupted.
Solutions
Hazard pointers: Mark which nodes you are looking at. Others cannot free them until you are done.
Versioned CAS: Pair the pointer with a version number. CAS both together. Even if pointer becomes A again, version will differ.
Garbage collection: Let GC handle memory. No use-after-free possible.
When ABA Does Not Matter
Simple counters, flags, values that do not involve memory management. If you are just incrementing an integer, ABA is irrelevant. Only pointer-based lock-free structures need to worry.
Warning: ABA is subtle and dangerous. If building lock-free data structures with pointers, use hazard pointers or GC. Do not reinvent the wheel.
💡 Key Takeaways
✓ABA: value changes A to B to A. CAS sees A, thinks unchanged, but context is different.
✓Happens with memory reuse. Recycled nodes can appear at same address with different meaning.
✓Version counter: pair pointer with monotonic counter. CAS on both together.
✓Hazard pointers: publish which nodes you are examining, defer reclamation until safe.
✓GC prevents ABA: objects are not reused until no references exist. Java/Go do not have ABA.
📌 Examples
1Java AtomicStampedReference: CAS checks both reference and stamp. compareAndSet(expectedRef, newRef, expectedStamp, newStamp)
2C++ atomic with version: pack pointer and version in 128-bit value, use double-width CAS.