Lock-free basics — every question, written out
Compare-and-swap, the retry loop, what lock-free actually guarantees, and the value that left and came back.
What does compare-and-swap do?
Explain it plainly
Three arguments: an address, the value you expect, and the value you want. It writes only if the current value matches the expected one, and tells you whether the swap happened. The whole thing is atomic, so the check cannot go stale before the write — which is what makes it the fix for check-then-act.
It writes a new value to a location only if the location still holds the value you expected, and reports whether it did — all indivisibly. The check and the write are one operation, so nothing can intervene between them.
See every interleaving — The retry loop, and what a successful swap proves.
Why is a CAS retry loop correct rather than merely hopeful?
Invariant identification
A successful swap proves nothing intervened between the read and the write.
The value being what you expected is the evidence. An update can only be installed on top of a value the thread actually observed, so re-reading after a failure is not hope — it is starting again from a known state.
What does "lock-free" actually guarantee?
Comparison
The system always progresses — no thread’s suspension can block the others.
A CAS only fails when somebody else succeeded, so the system as a whole cannot stall. One unlucky thread can retry indefinitely while others make progress, which is why lock-free is not wait-free.
Is a lock-free structure always faster than a mutex?
Trade-off & selection
No — under heavy contention a spinning thread generates coherence traffic that a blocked one does not.
Below roughly four to eight contending threads on a short operation, CAS loops win. Above that, every failed attempt has still acquired the cache line exclusively and then thrown its work away.
What is the ABA problem?
Edge case reasoning
A value changes to something else and back, so a CAS sees what it expected and succeeds anyway.
CAS compares values, not histories, so two changes are indistinguishable from none. Harmless for a counter, and for a pointer it means the address is the same while the structure underneath has been rearranged.
See every interleaving — 11 of 120 interleavings corrupt the stack.
How is ABA fixed?
Trade-off & selection
Pack a monotonically increasing tag into the same word as the pointer.
The pointer and its version must swap in one instruction, so returning to the same pointer never means returning to the same word. This is the tagged pointer that every real lock-free structure ships.
See every interleaving — 0 of 126 interleavings corrupt it once tagged.
A tagged pointer uses 16 bits for the tag. Is ABA now impossible?
Edge case reasoning
No — the tag wraps after about 65,000 operations on that slot.
It makes ABA 65,536 times less likely rather than impossible, which at millions of operations a second is a real exposure. High-throughput implementations use double-width CAS and a full 64-bit counter.
You popped a node from a lock-free stack. When is it safe to free it?
Edge case reasoning
Only once no other thread can still be holding a reference — which needs hazard pointers or epochs.
Writing the algorithm is an afternoon; safe reclamation is the actual problem. This is why lock-free code is far easier on a garbage-collected runtime, where a live reference prevents collection.
Why is lock-free programming easier in Java or Go than in C++?
Comparison
The collector solves reclamation: a node cannot be freed while any thread can still reach it.
Use-after-free is the hardest part of hand-written lock-free code, and a collector removes it entirely. ABA survives, which is why `AtomicStampedReference` exists in a garbage-collected language.
Does using CAS make a data structure thread-safe?
Invariant identification
Only if every invariant is maintained by a single one of those operations.
CAS makes one word’s update safe. If the structure’s correctness depends on two words changing together, you need double-width CAS, a different algorithm, or a lock.
Why does C++ offer both `compare_exchange_weak` and `_strong`?
Comparison
The weak form may fail spuriously, which maps directly onto ARM’s load-exclusive pair and is faster in a loop.
ARM’s reservation can be lost by an unrelated event, so a faithful mapping must be allowed to fail without the value having changed. Inside a loop that is free; outside one it would be a bug.
Sixteen threads run a CAS loop on the same location. What happens?
Complexity derivation
Most attempts fail, each having taken the line exclusively and discarded its work.
This is the pathological case for lock-free code: maximum coherence traffic, minimum useful work. The fix is to stop sharing the location — per-thread cells summed on read.
See every interleaving — The same coherence cost, arriving on purpose.
Where do you use compare-and-swap without writing it yourself?
Explain it plainly
Taking an uncontended lock is a CAS on the lock word — that is why it costs tens of nanoseconds rather than microseconds. Reference counting uses it for the count, `ConcurrentHashMap` for bin updates, `LongAdder` per cell, and every atomic increment is built on it. Writing one by hand is rare; depending on one is constant.
Every uncontended mutex acquisition is a CAS on the lock word, and reference counts, concurrent maps and striped counters all use it internally. When people say the fast path is uncontended, the fast path is one successful CAS.
When should you write a lock-free data structure by hand?
Trade-off & selection
Almost never — use the library, because these are subtle enough that published papers had bugs.
Reach for an atomic before a CAS loop, and a lock before a hand-written structure. `ConcurrentLinkedQueue`, crossbeam and their equivalents were written by people who found errors in the literature.
What is an optimistic read, as in Java’s `StampedLock`?
Comparison
Take a stamp, read without locking, then validate the stamp is unchanged.
It is the CAS idea applied to a read: verify nothing changed rather than prevent change. The win is that the read side writes nothing, removing the contended reader count that makes ordinary RW locks disappointing.
What is the simplest alternative to a lock-free structure for read-heavy shared state?
Trade-off & selection
An immutable snapshot behind an atomic reference, swapped on update.
Readers perform one load and hold a consistent view for as long as they like; writers build a new version and publish it with one store. For configuration read constantly and updated rarely, this beats every lock.
See every interleaving — 0 torn reads across 2,772 interleavings.