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.**