The question this answers
Both threads are runnable and neither is blocked, so why has nothing finished?
Two import workers, each of which must hold both the schema lock and the staging-table lock, using try-lock with release-on-failure and a fixed 50 ms retry delay.
Two mutexes, L_schema and L_stage. The workers were written this way deliberately, to avoid the deadlock that a blocking double-acquire would have caused.
Some thread makes progress. This is the weakest liveness property there is — not fairness, not bounded waiting, just "the system as a whole advances". Deadlock breaks it with everyone blocked; livelock breaks it with everyone running, and the second is worse because every health signal says the system is fine.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The retry loop that never resolves
The setup is what a careful engineer writes after being burned by Deadlock. Do not block on the second lock — try it, and if it fails, release the first, wait a moment, and start over. That reasoning is correct. The implementation has one flaw: both workers wait the *same* moment.
Follow the trace. At t=0 both workers grab their first lock, both fail the second, both release, both sleep exactly 50 ms, and both wake at t=50 in exactly the state they were in at t=0. The system has performed six operations, burned two cores, and returned precisely to its starting configuration. The loop is a fixed point, and it will iterate until the deploy that changes the timing.
The critical observation is the violates step: nothing breaks. No invariant on the *data* is harmed, no lock is held improperly, no exception is thrown. What breaks is the progress property, and the only way to see it break is to notice that the state after the cycle equals the state before it. That is why livelock is diagnosed by comparing two snapshots, never by reading one.
| # | Worker 1 — wants L_schema then L_stage | Worker 2 — wants L_stage then L_schema | State |
|---|---|---|---|
| 1 | try_lock(L_schema) — ok | · | t=0 ms L_schema=W1 L_stage=free imports=0 |
| 2 | · | try_lock(L_stage) — ok | t=0 ms L_schema=W1 L_stage=W2 imports=0 |
| 3 | try_lock(L_stage) — FAILS | · | t=1 ms L_schema=W1 L_stage=W2 imports=0 |
| 4 | · | try_lock(L_schema) — FAILS | t=1 ms L_schema=W1 L_stage=W2 imports=0 |
| 5 | unlock(L_schema); sleep(50 ms) | · | t=1 ms L_schema=free L_stage=W2 imports=0 |
| 6 | · | unlock(L_stage); sleep(50 ms) | t=1 ms L_schema=free L_stage=free imports=0 |
| 7 | wake at t=50, try_lock(L_schema) — ok | · | t=50 ms L_schema=W1 L_stage=free imports=0 |
| 8 | · | wake at t=50, try_lock(L_stage) — ok | t=50 ms L_schema=W1 L_stage=W2 imports=0 ✕ Progress: the state is bit-for-bit identical to step 2, fifty milliseconds later, with two cores fully occupied. The loop is a fixed point and will repeat indefinitely. |
| 9 | ... cycle repeats: 1 200 iterations per minute, zero imports | · |
Contrast with deadlock: same outcome, opposite signature
Deadlock and livelock produce the same business result — nothing gets done — and completely opposite evidence. A deadlocked thread is in the OS blocked state, off the run queue, consuming no CPU, with an identical stack on every dump. A livelocked thread is running, on the CPU, with a stack that moves. See Process States for the state machine underneath.
That difference matters operationally because it inverts every heuristic. "CPU is at 100%, so the service is working hard" is the reasonable inference that hides a livelock for hours. Meanwhile the deadlock heuristic — "CPU at zero and no errors" — fires immediately. Livelock is under-diagnosed precisely because it produces the metric shape everyone associates with health.
The timeline makes the shape visible. Every segment is running; there is not a single blocked segment in the picture. The two lanes are busy, symmetric, and permanently unproductive. If you saw only the CPU lane you would conclude the workers were saturated with import work.
Jitter is not a nicety; it is the fix
The realistic livelock in production is not two mutexes — it is retry policy. A dependency returns 503, every client retries after exactly one second, and one second later the dependency receives the entire fleet simultaneously and returns 503 again. That is the same fixed point with more actors, and it has a name: a synchronised retry storm, closely related to the Thundering Herd.
The fix in both cases is randomisation. Exponential backoff alone does not break symmetry — if both actors double their wait, they stay in phase forever, just slower. Jitter is the part that matters, because it makes the two waits unequal, and unequal waits mean one actor arrives first and wins. Full jitter — sleeping a uniform random amount in [0, cap) — is the well-studied choice, and the difference between it and fixed backoff is the difference between resolving in one round and never resolving.
Two more guards belong in the same loop. A bounded retry budget turns an unresolvable conflict into a visible failure instead of an infinite loop, and a per-attempt counter exported as a metric turns "the service is busy" into "the service has attempted this 4 000 times". Without those two, a livelock is invisible; with them it is a graph.
1async function withBothLocks<T>(fn: () => Promise<T>): Promise<T> {2 let delay = 503 for (;;) { // no budget: loops forever4 if (schema.tryLock()) {5 if (stage.tryLock()) { try { return await fn() } finally { stage.unlock(); schema.unlock() } }6 schema.unlock()7 }8 await sleep(delay) // both workers sleep the SAME amount9 delay = Math.min(delay * 2, 2000) // doubling keeps them in phase, just slower10 }11}1async function withBothLocks<T>(fn: () => Promise<T>, maxAttempts = 8): Promise<T> {2 let cap = 503 for (let attempt = 1; attempt <= maxAttempts; attempt++) {4 if (schema.tryLock()) {5 if (stage.tryLock()) { try { return await fn() } finally { stage.unlock(); schema.unlock() } }6 schema.unlock()7 }8 lockRetries.inc({ resource: 'import' }) // the metric that reveals a livelock9 await sleep(Math.random() * cap) // full jitter: unequal waits break the symmetry10 cap = Math.min(cap * 2, 2000)11 }12 throw new ContentionError('gave up after 8 attempts') // a visible failure beats an invisible loop13}Exponential backoff controls *load*; jitter controls *phase*. Only the second one fixes a livelock, because the failure is that two actors do the same thing at the same time. The retry budget is orthogonal and equally important: it converts an unbounded loop into an error a human can see. Note that ordering both locks by rank (Lock Ordering) removes the need for this loop entirely — this is the fallback for when ordering is not available, not the preferred design.
Key points
- Livelock: every thread is running and executing real code, and the global state after each cycle is identical to the state before it.
- It is a symmetry bug — two actors reacting to conflict identically at the same time reproduce the conflict.
- Its metric signature (high CPU, no errors, no blocked threads) is the shape people read as "healthy and busy", which is why it hides.
- Exponential backoff does not fix it; jitter does. Doubling in lockstep is still lockstep.
- A bounded retry budget plus a retry counter converts an invisible infinite loop into a visible failure.
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.
- • Each worker acquires its first resource and attempts the second with a non-blocking try.
- • The attempt fails because the peer holds it, so the worker releases what it holds — correctly avoiding hold-and-wait.
- • The worker waits a delay computed by a deterministic policy identical to its peer's.
- • Both workers wake simultaneously into the same starting configuration and repeat, having consumed CPU and elapsed time and changed nothing.
- • With jitter, the two delays differ; one worker arrives while the other is still sleeping, takes both resources uncontended, and completes.
- • W1 tries schema (ok), W2 tries stage (ok), both fail the second, both release, both sleep 50 ms, both wake at t=50 — identical state, cycle repeats forever.
- • With jitter: W1 sleeps 12 ms, W2 sleeps 41 ms. W1 wakes alone at t=12, takes both, completes at t=20, releases. W2 wakes at t=41 into an uncontended system. Resolved in one round.
- • Asymmetric arrival without jitter: W2 is delayed 3 ms by a page fault, wakes 3 ms later, and the system resolves by accident. This is why the bug is intermittent and why it disappears under a debugger.
- • Three workers, fixed backoff: the fixed point is even stickier, because resolution now requires one worker to be alone rather than merely ahead.
- • Retry storm variant: 400 clients, one dependency, all retrying at exactly 1 s. The dependency sees 400 concurrent requests every second, sheds them all, and every client retries again — a fleet-scale livelock. See Thundering Herd.
- • Try-lock guarantees you will not block. It explicitly does not guarantee you will ever acquire — that gap is the entire lesson.
- • Releasing on failure guarantees no hold-and-wait, and therefore no deadlock. It says nothing about progress.
- • Randomised backoff guarantees progress only *probabilistically*: the chance of another full collision decays geometrically, so the expected number of rounds is small, but there is no bound.
- • A retry budget guarantees termination. It converts a liveness failure into a returned error, which someone must then handle.
- • None of this guarantees fairness: with jitter, a worker can lose several rounds in a row purely by chance. See Fairness.
- • Livelock is contention that costs CPU instead of parking it. Two blocked threads cost nothing; two livelocked threads cost two cores.
- • Every retry re-touches the same cache lines for the lock words, so a livelock across many cores also generates coherence traffic — a small effect for two workers, a real one for thirty. See What a Shared Write Costs.
- • The retry rate is a load multiplier on whatever the retry re-does. If each attempt re-reads a row or re-issues a query, the downstream sees traffic proportional to the retry rate, not to the request rate.
- • Livelock under load is self-reinforcing: more workers means more collisions means more retries means longer collision windows.
- • Classic symmetric livelock: identical backoff, permanent fixed point.
- • Synchronised retry storm: many clients retrying a failing dependency on the same schedule, keeping it failing.
- • Optimistic-concurrency livelock: high-contention compare-and-swap retry loops where every attempt is invalidated by another writer, so throughput collapses toward zero as writers increase. See Optimistic Concurrency Control and Compare-and-Swap and the Retry Loop.
- • Starvation dressed as livelock: one worker always loses the retry race while others progress. The system advances, one participant does not — that is Starvation, and the fix is different.
- • Budget exhaustion cascade: adding a retry budget without a fallback turns the livelock into a wave of 500s at exactly the moment contention peaks.
- • The try-and-release structure genuinely helps where a lock hierarchy cannot be established — for example when one of the locks lives inside a library you do not control.
- • It helps for genuinely rare conflicts, where the expected number of retries is close to one and the loop is cheaper than an ordering convention.
- • It is the natural structure for optimistic concurrency, where the retry is fundamental to the model rather than a workaround.
- • Under sustained contention, where retries dominate useful work and throughput falls as you add workers.
- • When the retried operation is expensive — re-reading a large object or re-issuing a query multiplies downstream load by the retry factor.
- • Whenever a lock ordering was available and this was chosen instead: you took on an unbounded loop to avoid a comparison.
- • Retry-attempts-per-successful-operation. A ratio above ~2 is contention; a ratio that grows without bound while throughput is flat is livelock. This single metric is the highest-value instrument in the lesson.
- • CPU high, completed-operations counter flat. Compare a business counter (imports finished) against CPU, not against request rate.
- • Two thread dumps thirty seconds apart showing *different* stacks in the same retry function — the mirror image of the deadlock signature.
- • A CPU profile (Off-CPU Time: The Thing a CPU Profiler Cannot See,
flame-graphs) dominated by the try-lock/backoff path rather than by application work. - • Backoff sleep durations as a histogram: a single spike at one value means no jitter, which is the bug.
- • A retry loop is a state machine that must be idempotent — the work may be partially done before the conflict is detected, and the next attempt must tolerate that.
- • Backoff policy becomes a tunable with real consequences and no obvious right value; cap, base and jitter distribution all interact with contention level.
- • The budget introduces a new error path at every call site, and a fallback decision (fail, degrade, queue) that did not exist before.
- • Retry loops interact badly with layering: a retry at three levels of the stack multiplies into 8× the attempts nobody intended. See Retries and Timeouts as Contract Guidance.
- • Impose a lock order and block. Bounded waiting, no loop, no tuning — the right answer whenever the lock set is rankable. See Lock Ordering.
- • Queue the work to a single owner so conflicts cannot occur. See Producer / Consumer and The Actor Model.
- • Coalesce duplicate attempts so only one runs and the rest await its result, which is the direct fix for the retry-storm variant. See Single-Flight Coalescing.
- • Reduce the conflict rate rather than handling conflicts better — partition the data so two workers rarely want the same pair.
Both polite, neither progressing
The lost update, step by step
| # | Task A — counter++ | Task B — counter++ | State |
|---|---|---|---|
| 1 | rA ← counter | · | counter=0 rA=0 rB=— |
| 2 | · | rB ← counter | counter=0 rA=0 rB=0 |
| 3 | rA ← rA + 1 | · | counter=0 rA=1 rB=0 |
| 4 | counter ← rA | · | counter=1 rA=1 rB=0 |
| 5 | · | rB ← rB + 1 | counter=1 rA=1 rB=1 |
| 6 | · | counter ← rB | counter=1 rA=1 rB=1 ✕ 2 increments completed, counter = 1 |
Thundering herd: 10,000 waiters
no mitigation 10K requests in one 100 ms bucket vs a capacity of 90/bucket → 9,640 shed this setting 10K requests spread over one instant → peak 10K/bucket, 9,640 shed jitter sleep(base + random() * window) — decorrelates wakeups; costs a little latency batching one call serves N waiters — cuts the request count, not the wakeup count both are cheaper than the capacity you would otherwise have to buy for one instant per hour
What people believe, and what is true
Livelock is just a slow deadlock.
They are opposites in every observable. Deadlocked threads are blocked, off-CPU, with frozen stacks; livelocked threads are running, on-CPU, with moving stacks. The only thing they share is that no work completes.
Exponential backoff prevents livelock.
Exponential backoff reduces load. If both actors use the same deterministic schedule they remain perfectly in phase at every level, and the fixed point survives. Jitter is what breaks the symmetry.
The system is fine because CPU is high and nothing is erroring.
That is the livelock signature. Always compare a completed-work counter against CPU; utilisation without completions is the definition of the failure.
Go deeper
Overview
Two threads keep politely getting out of each other's way, at exactly the same time, forever. Everything runs, nothing finishes.
Practical
If a retry loop has fixed or purely exponential backoff, add full jitter and a bounded budget today. Export retries-per-success — that ratio is how you will ever notice this.
Advanced
Livelock is a symmetry problem, and every fix is a way of breaking symmetry: random jitter, priority by thread id, a rotating restart point (which is how std::lock avoids it deterministically), or a designated leader. Recognising it as symmetry rather than as "retries" tells you which fixes can possibly work.
Internals
Optimistic and lock-free algorithms live with this permanently: lock-freedom guarantees that *some* thread makes progress system-wide, which is precisely a guarantee against livelock, but it says nothing about any individual thread. Wait-freedom is the stronger property that bounds every thread's steps. See Wait-Free vs Lock-Free: Whose Progress Is Guaranteed — and note that neither property says anything about speed.