Lock-Free Structures
Lock-free data structures guarantee that at least one thread makes progress in a bounded number of steps, so the system never freezes from a thread being preempted while holding a lock, at the.
Definition
A lock-free data structure is one where at least one thread is guaranteed to complete an operation in a bounded number of steps regardless of what other threads do, so that a single preempted or crashed thread cannot block the whole structure, implemented with compare-and-swap loops and verified with linearizability arguments.
Context and scope
Applied in high-throughput queues, shared counters, and kernel data structures where blocking on a held lock is unacceptable and the contention is high enough to justify the complexity.
Common misconceptions
- Lock-free is always faster than lock-based — it is faster under contention; at low contention the CAS overhead and the lost optimization opportunities make it slower
- Lock-free means wait-free — lock-free guarantees system-wide progress; wait-free guarantees per-operation progress, which is strictly stronger and harder
Anti-patterns
- Using a lock-free queue where a mutex queue would do, paying CAS retry overhead and ABA-proofing complexity for no contention benefit
- Implementing a lock-free structure without an ABA solution, producing the classic pop-pop-push ABA corruption
Related concepts
Authoritative source
What it is
A lock-free data structure is one where at least one thread is guaranteed to complete an operation in a bounded number of steps regardless of what other threads do, so that a single preempted or crashed thread cannot block the whole structure, implemented with compare-and-swap loops and verified with linearizability arguments. Applied in high-throughput queues, shared counters, and kernel data structures where blocking on a held lock is unacceptable and the contention is high enough to justify the complexity. The central difficulty is that interleaving is nondeterministic: the set of possible executions grows super-exponentially with the number of operations, and testing samples a vanishing fraction.
How it works
Correctness is established by reasoning about happens-before relationships, not by running more tests. Synchronization primitives are chosen for the specific guarantee needed — mutual exclusion, publication, or ordering — and composed only with a documented proof of absence of deadlock. Bounded resources apply backpressure rather than unbounded queuing that hides overload until memory exhausts.
When to apply and pitfalls
Apply whenever multiple flows share mutable state or resources. The dominant pitfall is reasoning sequentially about concurrent code — “this can’t happen because A finishes before B” — when in fact the scheduler can interleave at any instruction boundary. The second is using a coarse lock for simplicity and turning parallelism back into serialization.