Concurrency
Lock-free programming: interview questions and how to answer them
A lock-free algorithm guarantees system-wide progress: even if threads are delayed, some operation completes, usually through atomic compare-and-set loops.
Written and reviewed by Sahil Srivastav
What it actually is
Lock-free is a progress guarantee, not a promise that no instruction blocks. A thread can starve while other threads continue to complete operations. Wait-free is stronger: every operation finishes in a bounded number of its own steps.
Most lock-free structures use atomic read-modify-write operations and retry when another thread wins. Correctness depends on linearisation points, memory ordering, and safe reclamation of nodes that another thread may still hold.
Why it matters in production
Locks can convoy, deadlock, or block a high-priority thread behind a paused owner. Lock-free structures keep global progress during a stalled thread, which is valuable in queues and allocators.
They are easy to get subtly wrong. ABA, reclamation races, cache-line contention, and retry storms can make a “lock-free” queue slower and less reliable than a short mutex.
How it works
CAS loop
Read the current value, compute a new one, and compare-and-set only if the value is unchanged. A failed CAS means retry from a fresh read.
Linearisation point
Identify the single atomic operation at which each method takes effect. If no such point can be named, the proof is usually incomplete.
ABA
A pointer can change A→B→A while a CAS sees A and succeeds incorrectly. Version tags or hazard-aware designs distinguish the instances.
Memory reclamation
Removing a node does not mean it can be freed: another reader may still dereference it. Hazard pointers, epochs, or garbage collection provide reclamation safety.
Implementing it
Prefer a tested concurrent collection unless latency and contention data justify custom code. Benchmark under the same core count and contention shape as production.
Bound retries or collect contention metrics. A lock-free loop that burns a core under contention is still an outage.
Separate algorithmic progress from memory reclamation in the design and review both.
for (;;) {
Node oldHead = head.get();
Node next = new Node(value, oldHead);
if (head.compareAndSet(oldHead, next)) return;
}Interview questions and how to answer them
What progress guarantee does lock-free provide?
In a finite number of steps, some thread completes an operation. One unlucky thread may starve; wait-free is the per-thread bounded guarantee.
What is the linearisation point in a CAS push?
The successful CAS that changes the shared head. Before it, the operation has not taken effect; after it, readers can observe it.
How does ABA break a stack?
A thread reads head A, pauses, another pops A and pushes a different node, then the address returns to A. The first CAS sees the same address and can overwrite a changed next pointer.
When would you choose a lock?
When critical sections are short, contention is modest, and a well-tested mutex meets the latency target. Simpler correctness is often the higher-throughput choice.
Answers that lose the round
- Calling any atomic variable lock-free
- Forgetting ABA
- Reclaiming removed nodes immediately
- Ignoring memory ordering
- Assuming lock-free means wait-free
- Benchmarking only one producer and one consumer
FAQ
Does lock-free avoid blocking I/O?
No. It concerns coordination among threads; an operation can still block on I/O.
Are atomic counters lock-free?
The implementation may be lock-free on a given architecture, but the algorithm’s overall progress depends on every operation it composes.
Why are retries expensive?
Each failed CAS repeats reads and computation and can invalidate cache lines across cores.