Lock-Free Algorithms

2 articles

Software Engineering 23 Sep 2026 6 min read

Hazard Pointers Delay Reclamation Until Readers Release References

Removing a node from a lock-free data structure does not make its memory immediately safe to reuse. Another thread may already hold the node’s address and may still dereference it. If the remover frees that allocation too early, an otherwise correct atomic update can be followed by a use-after-free. Hazard pointers separate logical removal from physical reclamation. A reader publishes the address it intends to access in a designated hazard slot. A remover can unlink a node and place it on a retired list, but reclamation waits until a scan confirms that no hazard slot protects that address.

Software Engineering Concurrency

Software Engineering 12 Sep 2026 8 min read

The ABA Problem Behind Successful Compare-and-Swap

A compare-and-swap operation answers a narrow question: does a memory location contain the expected bit pattern at the instant of the atomic operation? If it does, the replacement can proceed. The operation does not establish that the location remained unchanged between an earlier read and the later comparison. That distinction creates the ABA problem. A thread observes value A, pauses, and later performs a compare-and-swap expecting A. During the pause, other work changes the location from A to B and then back to A. The comparison succeeds because the current representation matches the expected representation, even though the shared state passed through a transition that may invalidate assumptions attached to the first observation.

Software Engineering Concurrency