The question this answers
What does calling an algorithm lock-free actually promise, and what does it deliberately not promise?
A shared work counter updated by every thread in a pool, implemented once with a mutex and once with a CAS loop.
One atomic word that every thread reads and conditionally writes.
The structure is never in a state where no thread can complete an operation — a thread suspended mid-operation never prevents another thread from finishing.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The ladder of progress guarantees
There are four rungs and they are about *who is guaranteed to finish*, not about how fast anything runs. Blocking: a thread that holds the lock and stops running blocks everyone waiting for it. Obstruction-free: a thread finishes if it runs alone for long enough. Lock-free: at least one thread completes in a bounded number of system-wide steps, so the system always advances. Wait-free: every thread completes in a bounded number of its own steps.
The difference that matters in practice is what happens when a participant stops. A thread holding a mutex that gets descheduled, page-faults, or is killed by the OOM killer takes every waiter with it. A thread halfway through a CAS loop that stops running takes nobody with it, because the loop never left the structure in a state another thread cannot complete from. That immunity is the actual product.
This is why lock-free matters in signal handlers, in interrupt contexts, in shared-memory regions spanning processes where one process can crash, and in real-time paths where a priority inversion is unacceptable. It is also why it usually does not matter in an ordinary application server: there, a descheduled thread comes back in microseconds and the mutex was fine.
| Guarantee | Who is guaranteed to finish | If a participant is suspended mid-operation | Typical cost |
|---|---|---|---|
| Blocking (mutex) | Nobody, absent scheduler fairness | Everyone waiting on that lock stops until it resumes | Cheapest and simplest when uncontended |
| Obstruction-free | A thread running in isolation | Others may livelock retrying against each other | Rarely used alone; a stepping stone in proofs |
| Lock-free | At least one thread, system-wide | Everyone else continues; the suspended thread simply has not committed | CAS loops, retries, and a much harder correctness argument |
| Wait-free | Every thread, in bounded steps of its own | Everyone continues, including the slowest thread | Helping mechanisms and per-thread state; usually the most expensive |
Immunity to a stalled participant, drawn out
The timeline below is the whole argument. Two threads are updating a shared structure; one of them is descheduled at the worst possible moment. Under a mutex, that moment is "while holding the lock", and the other thread is blocked for the entire duration — not because the work is long, but because the holder is not running. This is the mechanism behind Priority Inversion and behind Lock Convoys.
Under a CAS loop, the descheduled thread has not modified the structure at all — it read a value and has not yet attempted its write. The other thread proceeds, commits, and finishes. When the first thread resumes, its CAS fails, it re-reads, and it retries. Total time lost by the second thread: nothing.
Read what this does *not* show. It does not show the lock-free version doing more work per second. Under the same schedule with no descheduling, the mutex version may well finish sooner. The lock-free version bought insurance against a specific failure, and insurance has a premium. Whether you need it is a question about your environment, and answering "we want it to be fast" means you have not asked the question.
What contention does to both of them
The most persistent myth in this area is that lock-free is faster. It is not a claim the definition supports, and it is frequently false. Both a mutex and a CAS loop over the same hot location contend for the same thing: exclusive ownership of one cache line. Adding cores adds contention for that line under either implementation.
The differences that do show up are real but narrower than the myth. An uncontended mutex is very cheap — often a single atomic and no system call — so the lock-free version wins less than people expect at low contention. Under heavy contention a mutex parks waiters, which stops them burning CPU, while a CAS loop keeps them spinning and generating coherence traffic. Which effect dominates is a measurement on your hardware with your loop body, not a rule.
The reliable statement is the negative one: if the reason for going lock-free is performance, the change needs a benchmark on the real workload before and after, and Microbenchmark or End-to-End: Why p99 Did Not Move explains why the microbenchmark you are about to write will probably say the wrong thing. If the reason is the progress guarantee — a signal handler, a shared-memory ring between processes, a hard real-time deadline — you do not need the benchmark to justify the choice, only to size it.
Key points
- Lock-free means at least one thread completes in a bounded number of system-wide steps. It is a statement about progress, not about speed.
- The property you actually buy is immunity to a stalled participant: a suspended, page-faulting or crashed thread cannot block the others.
- It permits individual starvation. Your thread may retry indefinitely while the system as a whole advances.
- A CAS loop and a mutex over the same hot location contend for the same cache line, and neither reliably beats the other.
- Choosing lock-free for performance requires a measurement. Choosing it for the progress guarantee requires only that you name the participant that can stall.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Every operation is expressed so that the structure is in a valid state at every instant an observer could look — there is no window during which it is "being modified".
- • A thread computes its intended change locally, then attempts to commit it with a single atomic operation, usually a CAS.
- • Failure to commit means another thread committed, so the system advanced; the failing thread re-reads and recomputes.
- • Because no thread ever holds a resource others must wait for, no thread's suspension can prevent another's completion.
- • The absence of a held resource is also why there is no wait-for graph and therefore no deadlock — see The Four Conditions.
- • A loads head; A is descheduled for 20ms; B loads head, CAS succeeds, completes; C loads head, CAS succeeds, completes; A resumes, CAS fails, reloads, CAS succeeds. Everyone finished; A merely finished later.
- • Mutex version, same schedule: A acquires; A is descheduled holding the lock; B and C block for the full 20ms doing nothing. Same work, one participant stalled, four times the wall clock.
- • A, B and C all CAS the same word in a tight loop. Every round exactly one succeeds; the other two retry. System progress is continuous; C, being slowest to recompute, may never win — lock-free holds, wait-freedom does not. See Wait-Free vs Lock-Free: Whose Progress Is Guaranteed.
- • A is killed mid-operation (process crash in a shared-memory ring). Lock-free: the structure is consistent and B and C continue. Mutex in shared memory: the lock is held by a dead process and the ring is unusable without a recovery protocol.
- • Promises: system-wide progress. At any point, some thread that is running will complete its operation.
- • Promises: no deadlock. There is no held resource, so there is no circular wait.
- • Promises: no priority inversion of the classic form, since a low-priority thread holds nothing a high-priority thread needs.
- • Does NOT promise: per-thread progress. Starvation is explicitly permitted, and is the difference from wait-free.
- • Does NOT promise: higher throughput or lower latency than a lock. That is a separate, empirical question.
- • Does NOT promise: simplicity. The correctness argument is substantially harder and the failure modes are subtler.
- • Does NOT promise: safe memory reclamation. Knowing when it is safe to free a node another thread may still be reading is a whole separate problem — see The ABA Problem: The Value Came Back and A Lock-Free Stack, and What the Teaching Version Omits.
- • All threads contend for the same cache line on every attempt, so the contended resource is identical to the mutex version; only the waiting strategy differs.
- • Retries are self-amplifying: a losing thread immediately re-attempts, increasing the chance the next thread loses. Exponential backoff damps this and adds a tuning parameter with no universal value.
- • A mutex parks its waiters, which frees their cores for other work; a spinning CAS loop does not, so on an oversubscribed machine the lock-free version can be the worse citizen. See Oversubscription and Busy Waiting.
- • Livelock — all threads retrying, none committing usefully. Progress is technically preserved and practically absent. See Livelock.
- • Starvation — one thread consistently loses every race, with no bound on how long.
- • ABA — a CAS succeeding on a value that left and returned, corrupting the structure. See The ABA Problem: The Value Came Back.
- • Use-after-free — reclaiming a node another thread still holds a pointer to. The single most common way a hand-written lock-free structure is actually wrong.
- • Memory-ordering bugs — the CAS is correct and a surrounding relaxed load lets a reader see a node before its fields are written. See Safe Publication: Handing Over a Finished Object.
- • Throughput collapse under contention that looks like a CPU problem, because the CPU is genuinely 100% busy — retrying.
- • Any context where a participant can stop and not come back promptly: signal handlers, shared memory between processes, kernel and driver code, a thread that may be killed.
- • Hard real-time paths where the tail latency introduced by blocking on a descheduled holder is unacceptable — audio callbacks are the canonical example.
- • Read-mostly structures where readers must never block writers or each other, and the read path can be made to touch nothing exclusively.
- • Very short operations under moderate contention, where the parking and waking cost of a mutex is a large fraction of the work.
- • Ordinary application code where a mutex is correct, readable, and fast enough — which is most code.
- • Long or expensive operations, where every lost race discards real computation.
- • Teams without someone who can maintain the correctness argument. A lock-free structure nobody on the team fully understands is a liability with a good reputation.
- • Anywhere a library already provides the structure. Hand-written lock-free code is a well-known source of production bugs that survive years of testing.
- • Instrument attempts versus commits. A retry ratio that grows with load is the contention signal, and it appears long before latency moves.
- • Measure the tail, not the mean. The progress guarantee is a tail-latency property, so a mean that looks fine proves nothing about the thing you bought.
- • Compare against the mutex version under the production workload, on production-shaped hardware. See Benchmarking: Does This Number Answer My Question? and Microbenchmark or End-to-End: Why p99 Did Not Move.
- • Watch CPU utilisation alongside throughput: high CPU with flat throughput is spin-retry, not work. CPU Saturation: When Cores Become the Queue covers reading that pair.
- • Run it under a race detector and, if the language has one, a model checker. Testing alone does not explore the schedules that break these structures. See Race Detectors: What They Find, and What They Structurally Cannot.
- • The correctness argument stops being "the lock is held here" and becomes a linearizability argument over every possible interleaving, which is genuinely hard to review.
- • Memory reclamation becomes an explicit design problem requiring hazard pointers, epochs or a garbage collector.
- • Memory ordering becomes part of the API contract of the structure.
- • The failure modes are performance cliffs and rare corruption rather than exceptions, so they need dedicated metrics and stress testing to be visible at all.
- • Debugging is worse than with locks: no held-lock state to inspect, and Reading a Thread Dump shows only threads that look busy.
- • A mutex. The correct default, and the right answer far more often than the surrounding literature implies. See Mutexes: What They Protect and What They Do Not.
- • A lock-free structure from a well-reviewed library rather than a hand-written one — the guarantee without the maintenance burden.
- • Removing the sharing: per-thread state combined at the end, or a single owning thread fed by a queue. See Copy or Share? and The Actor Model.
- • A read-write lock or an immutable snapshot pointer, when the workload is read-mostly. See Read/Write Locks, Honestly and Immutability as a Concurrency Strategy.
- • Sharding the hot location, which usually beats both implementations because it removes the contention instead of managing it.
A lock-free stack, one head pointer
push(node): pop():
do { do {
t = head; t = head; if (t == null) return null;
node.next = t; n = t.next;
} while (!CAS(&head, t, node)); } while (!CAS(&head, t, n));| # | Pusher 1 — push(X) | Pusher 2 — push(Y) | Popper — pop() | State |
|---|---|---|---|---|
| 1 | t ← head (= A) | · | · | head=A stack=A→∅ |
| 2 | · | t ← head (= A) | · | head=A stack=A→∅ |
| 3 | X.next ← t (= A) | · | · | head=A stack=A→∅ |
| 4 | · | Y.next ← t (= A) | · | head=A stack=A→∅ |
compare_exchange in a loop — retries, and the pointer that lied
do {
old = counter.load(); # 1 read
next = old + 1; # compute off to the side
} while (!counter.compare_exchange(old, next)); # swap only if unchanged| # | T1 — pop() via CAS | T2 — another thread | State |
|---|---|---|---|
| 1 | old ← head (= A) | · | head=A stack=A→B→C |
| 2 | · | pop() → A | head=B stack=B→C |
| 3 | · | pop() → B | head=C stack=C |
| 4 | · | push(A) | head=A stack=A→C |
| 5 | CAS(head, A, B) → SUCCESS | · | head=B stack=B→ freed ✕ head now points at B, which was popped and freed. Node C has vanished from the stack and T1 returned a node it never observed being on top. |
| 6 | return A to the caller | · | head=B stack=corrupt |
Eight threads, one lock
What people believe, and what is true
Lock-free means faster.
It means the system always progresses. Throughput is a separate, empirical question, and an uncontended mutex is very cheap.
Lock-free means no waiting.
No thread blocks, but a thread can retry indefinitely. Time spent retrying is time spent waiting with the CPU on.
Lock-free means no locks anywhere, so it is simpler.
It replaces one explicit, inspectable mechanism with an invariant that must hold across every interleaving, plus a memory-reclamation scheme. It is strictly more complex.
Go deeper
Overview
Lock-free means one thread going to sleep cannot stop the others. It is about who is guaranteed to finish, not about how fast.
Practical
Ask which participant can stall and why that matters here. If you can name it — a signal handler, another process, a real-time deadline — lock-free is justified. If the answer is "it should be faster", write the benchmark first.
Advanced
Linearizability is the correctness condition that usually accompanies the progress guarantee: every operation appears to take effect at a single instant between its invocation and its return. Progress and linearizability are independent — you must argue both.
Internals
Herlihy's consensus hierarchy says CAS has unbounded consensus number, which is why any object has a lock-free (indeed wait-free) implementation given CAS. That is an existence result about what is possible, not advice about what to build.