Hazard Pointers and the ABA Problem
Recognize the ABA problem and mitigate it with hazard pointers or tagged pointers.
The ABA Problem
In lock-free code with pointers, a value may be A, change to B, then back to A. A CAS comparing only the value cannot tell anything changed in between.
Classic ABA Scenario
Thread 1 reads pointer A and prepares to CAS. Meanwhile Thread 2 deletes A, allocates a new node that happens to reuse A s address, and Thread 1 s CAS incorrectly succeeds.
All lessons in this course
- std::atomic and Memory Orders
- Compare-and-Swap CAS Patterns
- Lock-Free Queue Implementation
- Hazard Pointers and the ABA Problem