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)

bool CAS(std::atomic<T>& 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.