lock free data structure
**Lock-Free Data Structures** are **concurrent data structures that guarantee system-wide progress without using mutual exclusion locks** — at least one thread makes progress in a finite number of steps, eliminating deadlock and priority inversion.
**Progress Guarantees (Strongest to Weakest)**
- **Wait-Free**: Every thread completes in a bounded number of steps. Strongest guarantee, hardest to implement.
- **Lock-Free**: At least one thread completes in a bounded number of steps. Practical standard.
- **Obstruction-Free**: Thread completes if it runs alone (no contention). Weakest.
**Core Primitive: Compare-and-Swap (CAS)**
```cpp
bool CAS(std::atomic& target, T expected, T desired) {
// Atomic: if target == expected, set target = desired, return true
// Else return false (target unchanged)
return target.compare_exchange_strong(expected, desired);
}
```
- CAS is the fundamental building block for lock-free algorithms.
- Available on all modern hardware (x86: CMPXCHG; ARM: LDREX/STREX, LDXR/STXR).
**Lock-Free Stack (Treiber Stack)**
```
Push: new_node->next = head; while(!CAS(&head, new_node->next, new_node)) {...}
Pop: old_head = head; while(!CAS(&head, old_head, old_head->next)) {...}
```
**ABA Problem**
- CAS pitfall: A→B→A changes look like no change to CAS.
- Thread reads A, context switch, A removed and re-added.
- Solution: Tagged pointer (combine pointer with version counter).
**Hazard Pointers**
- Memory reclamation challenge: Cannot free node until no thread holds reference.
- Hazard pointer: Thread announces which nodes it's reading → other threads defer deletion.
- Alternative: RCU (Read-Copy-Update) — reads are lock-free; updates copy and swap.
**Applications**
- High-performance message queues: LMAX Disruptor, Folly MPMC queue.
- Memory allocators: jemalloc, TCMalloc use lock-free freelists.
- Reference counting: `std::shared_ptr` uses lock-free atomic reference count.
Lock-free data structures are **essential for high-throughput concurrent systems** — they eliminate the latency spikes, deadlocks, and priority inversions that plague lock-based designs in low-latency trading, OS kernels, and real-time systems.