Lock Free Stacks and Queues
A lock free data structure lets multiple threads operate on it without any thread holding a lock. The guarantee is that at least one thread always makes progress, so a stalled or descheduled thread cannot block all the others, which is exactly the weakness of lock based designs.
The core tool is the atomic compare and swap, or CAS. A thread reads the current value, computes the new value, and atomically swaps it in only if the value has not changed since the read. If another thread got there first, the CAS fails and the thread simply retries.
- Lock free stack Push and pop swing the head pointer with a CAS retry loop.
- Lock free queue A two pointer design moves head and tail with separate CAS operations.
- Retry loop A failed CAS means contention, so the thread reloads and tries again.
The classic hazard is the ABA problem. A pointer reads value A, another thread changes it to B and back to A, and the original CAS succeeds even though the structure changed underneath. Solutions tag pointers with a version counter so a reused address still looks different.
Lock free code is subtle and easy to get wrong, but it removes the worst tail latencies caused by a thread being suspended while holding a lock. It is most valuable in highly contended hot paths.
Key idea
Lock free stacks and queues use compare and swap retry loops to guarantee progress without locks, while the ABA problem forces version tagging of reused pointers.