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.