Lock Free Data Structures
A lock free data structure lets multiple threads operate on it concurrently while guaranteeing that at least one thread always makes progress, even if others stall or are descheduled. No thread ever holds a lock that could block the rest.
This sits in a hierarchy of progress guarantees:
- Blocking A stalled thread holding a lock halts everyone. Locks live here.
- Lock free The system as a whole always advances, though an individual thread may be starved.
- Wait free Every thread finishes its operation in a bounded number of steps, the strongest and hardest guarantee.
Lock free structures are built from atomic primitives, most often compare and swap. An operation reads the current state, computes a new state, and atomically swaps it in only if nothing changed underneath. If another thread won the race, it retries.
Why bother:
- No deadlock With no locks there is nothing to deadlock on.
- Fault tolerance A thread paused mid operation cannot block others.
- Lower latency No waiting on a contended lock under light contention.
The costs are real. Lock free code is notoriously hard to get right, must handle subtle memory reclamation, and can suffer livelock as threads retry. It also needs careful attention to memory ordering.
Key idea
Lock free structures guarantee system wide progress without locks by using atomic swaps and retries, trading simplicity for deadlock freedom and resilience.