Lock Free Concurrent Data Structures

Lock-Free Concurrent Data Structures — Lock-free data structures guarantee system-wide progress without using mutual exclusion locks, ensuring that at least one thread makes progress in a finite number of steps even when other threads are delayed, suspended, or fail entirely.

Lock-Free Fundamentals — Progress guarantees define the hierarchy of non-blocking algorithms:
- Obstruction-Free — a thread makes progress if it eventually executes in isolation, the weakest non-blocking guarantee that still prevents deadlock
- Lock-Free — at least one thread among all concurrent threads makes progress in a finite number of steps, preventing both deadlock and livelock at the system level
- Wait-Free — every thread completes its operation in a bounded number of steps regardless of other threads' behavior, the strongest guarantee but often with higher overhead
- Compare-And-Swap Foundation — most lock-free algorithms rely on the CAS atomic primitive, which atomically compares a memory location to an expected value and updates it only if they match

Lock-Free Stack Implementation — The Treiber stack is the canonical example:
- Push Operation — creates a new node, reads the current top pointer, sets the new node's next to the current top, and uses CAS to atomically update the top pointer
- Pop Operation — reads the current top and its next pointer, then uses CAS to swing the top pointer to the next node, retrying if another thread modified the top concurrently
- ABA Problem — a thread may read value A, be preempted while another thread changes the value to B and back to A, causing the first thread's CAS to succeed incorrectly
- Tagged Pointers — appending a monotonically increasing counter to pointers prevents ABA by ensuring that even if the pointer value recurs, the tag will differ

Lock-Free Queue Design — The Michael-Scott queue enables concurrent enqueue and dequeue:
- Two-Pointer Structure — separate head and tail pointers allow enqueue and dequeue operations to proceed concurrently on different ends of the queue
- Helping Mechanism — if a thread observes that the tail pointer lags behind the actual tail, it helps advance the tail pointer before proceeding with its own operation
- Sentinel Node — a dummy node separates the head and tail, preventing the special case where the queue contains exactly one element from creating contention between enqueue and dequeue
- Memory Ordering — careful use of acquire and release memory ordering on atomic operations ensures visibility of node contents without requiring expensive sequential consistency

Memory Reclamation Challenges — Safely freeing memory in lock-free structures is notoriously difficult:
- Hazard Pointers — each thread publishes pointers to nodes it is currently accessing, and memory reclamation checks these hazard pointers before freeing any node
- Epoch-Based Reclamation — threads register entry and exit from critical regions, with memory freed only when all threads have passed through at least one epoch boundary
- Read-Copy-Update — RCU allows readers to access data without synchronization while writers create new versions and defer reclamation until all pre-existing readers complete
- Reference Counting — atomic reference counts track the number of threads accessing each node, with the last thread to release a reference responsible for freeing the memory

Lock-free data structures are essential for building high-performance concurrent systems where blocking is unacceptable, trading algorithmic complexity for guaranteed progress and elimination of priority inversion and convoying effects.