Lock-Free and Wait-Free Data Structures
A lock has a dark secret: if the thread holding it is pre-empted, crashes, or is simply slow, every
other thread that wants the lock stops dead. One stalled thread freezes the whole structure. For a
kernel data path or a real-time system, that is unacceptable. Lock-free programming throws
the lock away entirely and coordinates with nothing but atomic
read-modify-write
instructions — usually compare-and-swap (CAS) — so that the failure or delay of any one
thread can never block the others.
This is some of the hardest code humans write. It lives in kernels, garbage collectors, database engines,
and lock-free queues between threads. To reason about it you need a precise vocabulary of
progress guarantees, two canonical algorithms (the Treiber stack and the
Michael–Scott queue), and a healthy fear of the ABA problem and of
memory
ordering. Get any of them wrong and the bug appears once a week, on one machine, under load.
Three progress guarantees, nested
"Non-blocking" is not one property but a hierarchy of increasingly strong promises about which
threads are guaranteed to make progress, and when. They nest: every wait-free algorithm is
lock-free, and every lock-free algorithm is obstruction-free — but not the reverse.
- Obstruction-free — a thread makes progress if it runs alone for long
enough (all others paused). The weakest promise; concurrent threads may repeatedly abort each other
(livelock) but no locks are held;
- Lock-free — some thread always makes progress in a bounded number of
system-wide steps. The system as a whole never stalls, though an individual unlucky thread may
starve, retrying forever while others succeed;
- Wait-free — every thread completes its operation in a bounded number of
its own steps, regardless of what others do. The strongest promise: no starvation, no
unbounded retries — and the hardest and usually slowest to build.
The distinction is about the system versus the individual. Lock-free guarantees the machine keeps
moving; wait-free guarantees you personally keep moving. Most practical structures aim for
lock-free — it captures the crucial "one stalled thread can't freeze everyone" property at a reasonable
cost — and reserve wait-free for hard real-time paths where a per-operation bound is mandatory.
The Treiber stack: a lock-free push and pop
The classic lock-free structure is the Treiber stack (1986). A stack is a single
\texttt{head} pointer to a chain of nodes. The whole trick is the
optimistic CAS loop: read the current head, prepare your change, and CAS the head from the
value-you-read to your new value. If someone else changed the head in between, the CAS fails, you re-read,
and retry. To push:
- read h = \texttt{head};
- set your new node's \texttt{next} = h;
- \texttt{CAS(head, } h\texttt{, newNode)} — succeed and you're done; fail and
loop from step 1.
Pop is symmetric: read h, read h.\texttt{next}, then
\texttt{CAS(head, } h, h.\texttt{next)}. No lock is ever held; if your CAS fails
it's only because someone else made progress, which is exactly the lock-free promise. It is not
wait-free — a very unlucky thread could lose the CAS race indefinitely — but the stack as a whole never
stalls.
Watch a CAS race play out
Let's run a Treiber stack against interference. The simulation pushes and pops, and deliberately injects a
concurrent modification between a pop's read and its CAS so you can see the CAS fail and retry —
the heartbeat of every lock-free algorithm. Nothing blocks; the loser simply loops and tries again.
// A lock-free (Treiber) stack. The only synchronisation is compareAndSwap on `head`.
interface Node { value: number; next: Node | null; }
class AtomicRef {
private ref: Node | null = null;
load(): Node | null { return this.ref; }
// Atomic CAS: if head === expected, set to next and report success.
cas(expected: Node | null, next: Node | null): boolean {
if (this.ref === expected) { this.ref = next; return true; }
return false;
}
}
const head = new AtomicRef();
let casAttempts = 0, casFailures = 0;
function push(value: number): void {
const node: Node = { value, next: null };
for (;;) {
const h = head.load(); // 1. read current head
node.next = h; // 2. point new node at it
casAttempts++;
if (head.cas(h, node)) return; // 3. swing head -> success
casFailures++; // someone beat us: retry
}
}
function pop(interfere?: () => void): number | null {
for (;;) {
const h = head.load();
if (h === null) return null;
const next = h.next;
if (interfere) interfere(); // simulate another thread acting between read and CAS
casAttempts++;
if (head.cas(h, next)) return h.value;
casFailures++; // head moved under us: retry
}
}
push(10); push(20); push(30);
console.log("pushed 10, 20, 30");
// Pop, but between our read and our CAS another thread pushes 99 -> our CAS fails once, then retries.
let once = true;
const v = pop(() => { if (once) { once = false; push(99); } });
console.log(`pop returned ${v} (retried after interference)`);
console.log(`remaining top = ${head.load()?.value}`);
console.log(`CAS attempts=${casAttempts}, failures(retries)=${casFailures}`);
The Michael–Scott queue
A stack touches one pointer; a FIFO queue touches two (head and tail) and is far subtler.
The Michael–Scott queue (1996) is the lock-free queue — it is what Java's
\texttt{ConcurrentLinkedQueue} and countless kernels use. Its cleverness is a
dummy head node (so head and tail never alias even when empty) and a two-step enqueue:
first CAS the last node's \texttt{next} to point at the newcomer, then CAS the
tail forward. Because those two steps aren't atomic together, a thread may find the tail
"lagging" — pointing at a node that already has a successor — and any thread that notices this
helps by swinging the tail forward before proceeding. This helping is the
signature of lock-free design: instead of waiting for a stalled thread, you finish its job for it, so the
structure never blocks.
| Structure | Pointers | Guarantee | Used in |
|---|
| Treiber stack | 1 (head) | lock-free | free-lists, memory allocators |
| Michael–Scott queue | 2 (head, tail) | lock-free (with helping) | Java ConcurrentLinkedQueue |
| Wait-free queue (Kogan–Petrank) | 2 + per-thread state | wait-free | hard real-time paths |
The ABA problem: when "unchanged" is a lie
Here is the trap that has bitten every lock-free programmer. CAS checks a value, not a
history. Your pop reads \texttt{head} = A and plans to CAS it to
A.\texttt{next} = B. Before your CAS runs, another thread pops
A, pops B, frees them, then pushes a
recycled node that reuses A's address back on top. Your CAS sees
\texttt{head} == A, concludes "nothing changed," and succeeds — installing a
stale B that has since been freed. The structure is now corrupt. The value went
A \to B \to A, and CAS could not tell.
// The ABA problem: CAS on a bare value cannot see A -> B -> A.
// A version-tagged pointer fixes it: the counter changes even when the pointer returns to A.
interface Tagged { ptr: string; tag: number; }
class TaggedRef {
private cur: Tagged;
constructor(ptr: string) { this.cur = { ptr, tag: 0 }; }
load(): Tagged { return { ...this.cur }; }
cas(exp: Tagged, nextPtr: string): boolean {
if (this.cur.ptr === exp.ptr && this.cur.tag === exp.tag) {
this.cur = { ptr: nextPtr, tag: exp.tag + 1 }; // bump the tag on every change
return true;
}
return false;
}
}
// --- Naive CAS on the bare pointer: ABA slips through ---
let head = "A"; // bare pointer
const myView = head; // reader observes A, plans CAS(A -> B)
head = "B"; head = "A"; // another thread: A -> B -> A (recycled address!)
const naiveSucceeds = (head === myView);
console.log(`naive CAS sees head==A -> succeeds? ${naiveSucceeds} <-- WRONG, world changed`);
// --- Tagged pointer: the same A->B->A now carries a different tag ---
const ref = new TaggedRef("A");
const view = ref.load(); // {ptr:'A', tag:0}
ref.cas(ref.load(), "B"); // A -> B, tag 1
ref.cas(ref.load(), "A"); // B -> A, tag 2 (pointer back to A, tag moved!)
const taggedSucceeds = ref.cas(view, "Z"); // expects {A,0} but current is {A,2}
console.log(`tagged CAS with stale {A,0} -> succeeds? ${taggedSucceeds} <-- correctly REJECTED`);
Two standard fixes. Tagged (versioned) pointers: glue a counter to the pointer and bump it
on every change, so a recycled A carries a different tag and the CAS fails
(this needs a double-width CAS, e.g. x86's \texttt{CMPXCHG16B}).
Hazard pointers: each thread publishes the pointers it is currently using, and memory is
not reclaimed until no hazard pointer references it — so A can never be freed
and reused underneath you in the first place. Linux's
RCU
is a third, deferred-reclamation answer to the same underlying question: when is it safe to free?
Why memory ordering is not optional here
Lock-free code lives or dies by the
memory
consistency model. When you push a node, you write its \texttt{value}
and \texttt{next} fields and then publish it by CAS-ing the head. On a
weakly-ordered CPU (ARM, POWER), another core can see the new head pointer before it sees the
node's field writes — reading uninitialised garbage. A lock hid this from you, because acquiring and
releasing a lock imply full memory barriers. Strip the lock away and you must place the fences yourself: a
release on the publishing CAS (so the field writes are visible before the pointer) paired
with an acquire on the reader's load. "Lock-free" never means "fence-free" — it means
you are now responsible for the ordering the lock used to guarantee.
The word "lock-free" sells the wrong dream. Its guarantee is about progress — one stalled thread
can't freeze the rest — not about speed. Under heavy contention a Treiber stack's CAS loop can
thrash worse than a well-tuned lock, because every failed CAS still paid for a coherence transaction on the
head's cache line (the same ping-pong that plagues spinlocks). Benchmarks routinely show a good MCS lock or
a flat-combining design beating a naive lock-free structure at high core counts. Reach for lock-free when
you genuinely need its fault-tolerance and progress properties — real-time deadlines, signal
handlers, code that runs where a thread might be paused arbitrarily — not as a reflexive "locks are slow"
optimisation. The correct question is never "lock or lock-free?" but "what progress property does this path
actually require?"
A common conflation: "my structure is lock-free, so no thread can starve." False. Lock-free guarantees only
that the system makes progress — some thread completes each round. A specific unlucky
thread can lose the CAS race again and again, retrying forever while faster threads keep succeeding; that
is starvation, and it is perfectly compatible with lock-freedom. Only wait-free rules it
out, by bounding every thread's own step count. If you have a per-operation latency requirement — a
packet that must be processed within a deadline no matter what — lock-free is not enough; you need
wait-free (and will pay for it in complexity and average-case throughput). Know which one your problem
demands before you write a line.