lock free data structure

**Lock-Free Data Structures** are the **concurrent data structures that guarantee system-wide progress — at least one thread makes progress in a bounded number of steps regardless of the scheduling of other threads — using atomic hardware primitives (compare-and-swap, load-linked/store-conditional, fetch-and-add) instead of locks, eliminating the deadlock, priority inversion, and convoying problems inherent in lock-based synchronization while providing higher throughput under contention for the concurrent queues, stacks, and lists that are fundamental building blocks of parallel systems**. **Why Lock-Free** Lock-based data structures have failure modes: - **Deadlock**: Thread A holds lock 1, waits for lock 2; Thread B holds lock 2, waits for lock 1. - **Priority Inversion**: Low-priority thread holds a lock needed by high-priority thread, which is blocked indefinitely. - **Convoying**: Thread holding a lock is descheduled — all other threads waiting on that lock stall until it is rescheduled. Lock-free structures guarantee that some thread is always making progress, even if others are stalled, suspended, or arbitrarily delayed by the OS scheduler. **Atomic Primitives** - **CAS (Compare-And-Swap)**: Atomically compares *ptr with expected value; if equal, writes new value and returns true. Otherwise returns false (and updates expected with current value). The foundation of most lock-free algorithms. - **LL/SC (Load-Linked/Store-Conditional)**: ARM/RISC-V alternative to CAS. LL reads a value; SC writes a new value only if no other write to that address occurred since the LL. Avoids the ABA problem inherent in CAS. - **FAA (Fetch-And-Add)**: Atomically increments *ptr by a value and returns the old value. Used for counters, ticket locks, and queue index management. **Classic Lock-Free Data Structures** - **Michael-Scott Queue (FIFO)**: Linked-list-based queue with separate head and tail pointers. Enqueue: CAS tail→next to the new node, then CAS tail to the new node. Dequeue: CAS head to head→next. Linearizable and lock-free. Used in Java's ConcurrentLinkedQueue. - **Treiber Stack (LIFO)**: Linked list with a CAS on the head pointer. Push: new_node→next = head; CAS(head, old_head, new_node). Pop: CAS(head, old_head, old_head→next). Simple and efficient. - **Harris Linked List (Sorted)**: Lock-free sorted linked list using mark-and-sweep deletion. Logical deletion marks a node (sets a flag in the next pointer), then physical removal CASes the predecessor's next pointer. Foundation for lock-free skip lists and sets. **The ABA Problem** CAS cannot distinguish between "value unchanged" and "value changed to something else and then back." If Thread A reads value X, is preempted, Thread B changes X→Y→X, Thread A's CAS succeeds incorrectly. Solutions: - **Tagged pointers**: Append a version counter to the pointer (128-bit CAS on x86 with CMPXCHG16B). - **Hazard Pointers**: Publish pointers that threads are currently reading — prevents premature reclamation. - **Epoch-Based Reclamation (EBR)**: Defer memory reclamation until all threads have passed through a grace period. Simple and fast but requires cooperative epoch advancement. **Wait-Free vs. Lock-Free** - **Lock-Free**: At least one thread progresses. Individual threads may starve under pathological scheduling. - **Wait-Free**: Every thread progresses in bounded steps. Stronger guarantee but typically higher overhead. Universal constructions exist but are impractical; practical wait-free algorithms are designed per data structure. Lock-Free Data Structures are **the concurrency primitives that enable maximum throughput under contention** — providing progress guarantees that lock-based approaches cannot match, at the cost of algorithmic complexity that demands careful reasoning about atomic operations, memory ordering, and safe memory reclamation.