skip to content

What is livelock, and how does it differ from deadlock? Describe the runtime signature of each.

level: middleimportance: must knowfreq 62%

answer

  1. Deadlock = blocked cycle, CPU idle
  2. Livelock = running cycle, CPU hot, zero throughput
  3. Symmetric retry + fixed delay = collision every round
  4. Fix = break symmetry (jitter, tiebreaker) + bound retries
  5. Safety = nothing bad; liveness = something eventually happens

basics

~20 s

Both are liveness failures: no useful work completes. In deadlock the threads are blocked forever waiting on each other, so their states are frozen. In livelock the threads stay runnable and keep changing state (retry, back off, yield) but the pattern repeats and nobody finishes.

solid answer

~60 s

Deadlock and livelock are both **liveness** failures: nothing is computed incorrectly, the system simply stops making progress. They differ in what the threads are doing. - **Deadlock**: threads are *blocked*. Each holds a resource and waits for one another holds, so no participant is runnable and the global state stops changing. Signature: CPU idle, thread dump shows everyone parked, the same wait-for cycle every time you look. - **Livelock**: threads are *runnable and busy*. They detect a conflict, roll back or release, back off, retry — and because the participants behave symmetrically they collide again on the next attempt. State changes constantly but cycles through the same configurations. Signature: CPU pegged, throughput near zero, retry/abort counters climbing, thread dumps that look different every time. Livelock usually comes from politeness or optimism: deadlock-avoidance code that releases held locks and retries, optimistic compare-and-swap or transaction retries, two peers each yielding to the other. The fix is to break symmetry — randomized jitter, a deterministic tiebreaker (thread id, timestamp), or a bounded retry budget that escalates to a queued, blocking acquisition.

code

text · 8 lines
text
loop:
  acquire(A)
  if try_acquire(B, timeout = 10ms):
      do_work(); release(B); release(A); return
  else:
      release(A)          # polite: avoid deadlock
      sleep(10ms)         # SAME fixed delay in both threads
      goto loop           # both wake together and re-collide

go deeper

for a junior

Recall the definitions and the one-line contrast: deadlock is stuck-and-blocked, livelock is busy-but-going-nowhere, both are progress failures rather than wrong answers.

for a middle

Explain the mechanism — the polite release-and-retry that avoids deadlock and creates livelock — and name the runtime signatures (CPU idle vs CPU hot) plus the symmetry-breaking fix.

for a senior

Talk about diagnosis in production: retry/abort counters, repeated stack sampling, throughput-versus-CPU divergence, and the contention threshold at which optimistic retry tips over into collapse.

for a principal

Frame it as a system-design property: choose optimistic or pessimistic concurrency by expected contention, bound optimism with escalation to fair queueing, and add admission control so the system never enters the retry-collapse region.

## Safety versus liveness Concurrent-correctness properties split into two families. A **safety** property says "nothing bad ever happens": no two threads inside the critical section, no torn value, no lost update. A **liveness** property says "something good eventually happens": every request eventually completes, every waiting thread eventually acquires the lock. Safety violations are wrong answers; liveness violations are silence. Deadlock, livelock and starvation are the three classic liveness failures, and the distinction matters because they need different diagnostics and different fixes. ## Deadlock Deadlock is a *blocked* cycle. Thread A holds resource R1 and waits for R2; thread B holds R2 and waits for R1. Neither is runnable, so no state transition is possible from that configuration — the system is permanently stuck in one point of its state space. Formally it needs the four Coffman conditions to hold simultaneously (mutual exclusion, hold-and-wait, no preemption, circular wait). Its operational signature is distinctive: the machine is quiet. Load average drops, CPU utilisation falls, request latency goes to infinity for the affected paths, and repeated stack samples show exactly the same frames, because nothing moves. ## Livelock Livelock is a *running* cycle. Every thread is scheduled, executing instructions, mutating state — and yet the system revisits the same set of configurations forever, so no operation ever reaches completion. Nothing is blocked; the threads are simply not converging. The canonical shapes: - **Symmetric retry.** A thread grabs lock A, fails to get lock B within a timeout, releases A to avoid deadlock, sleeps a fixed interval, and retries. Its partner does the mirror image. Because both use the same fixed delay, they re-collide on every round with high probability. - **Optimistic concurrency under high contention.** Compare-and-swap loops, software-transactional-memory transactions, or optimistic-locking database updates that abort and replay. Under enough contention the abort rate approaches one, and the system burns all its CPU on rollbacks. - **Mutual deference.** Two components each detect the other's activity and back off to be polite — the two-people-in-a-corridor problem, or two nodes that each concede leadership to the other. - **Handoff loops.** A message or task bounces between queues, each stage deciding the other should own it. Crucially, livelock is a *probabilistic* phenomenon in most real systems. Fixed-delay retries do not guarantee a collision forever; they make collision overwhelmingly likely for long stretches. That is why livelock often shows up as a throughput cliff under load rather than a hard hang: below some contention level the retries usually succeed, above it the system tips over and stays down until load drops. ## Telling them apart in production Use three signals. First, **CPU**: deadlock is idle, livelock is hot. Second, **stack sampling over time**: deadlock shows an identical, unchanging wait-for graph; livelock shows threads moving through the retry path repeatedly. Third, **counters**: instrument retries, aborts, lock-acquire timeouts and rollbacks. A retry rate that grows super-linearly with load is the fingerprint of livelock; you can graph it long before it becomes an outage. Many runtimes can also detect a lock cycle automatically, but no runtime can detect livelock for you — only your own progress metrics can, because from the scheduler's point of view a livelocked thread is a perfectly healthy busy thread. ## Fixes Deadlock is fixed structurally: impose a global lock ordering, use a single coarse lock, take locks with a timeout plus a deterministic loser, or eliminate hold-and-wait. Livelock is fixed by **breaking symmetry** and by **bounding optimism**: - Randomize the backoff so colliding parties diverge instead of re-synchronising. - Add a deterministic tiebreaker: the participant with the lower id, older timestamp or larger transaction wins and does not yield; the other one waits. Database engines do this with wound-wait and wait-die schemes. - Bound retries. After N failed optimistic attempts, escalate to a fair queued lock so the operation is guaranteed to make progress even if it is slower. - Shed load or limit concurrency so the contention level never enters the region where the abort rate explodes. ## Where starvation sits Starvation is the third liveness failure and is easily confused with livelock. In starvation the *system* is making progress — throughput is fine — but one particular thread or class of work never gets served. Livelock is global stagnation; starvation is local unfairness. A useful mental test: if you removed all but one thread, would the remaining one complete? Under livelock, yes (the conflict disappears); under deadlock, it was never runnable; under starvation, the victim was always runnable and simply kept losing.

  • How would you confirm livelock rather than deadlock from a running process you cannot attach a debugger to?
    Compare CPU utilisation against completed-operation throughput: livelock burns CPU while completions flatline, deadlock drops both. Then take several stack samples a second apart — under deadlock the same threads sit on the same wait frames every sample; under livelock the same threads cycle through the retry/abort path. Application counters for retries, transaction aborts and lock-acquire timeouts settle it.
  • Is a spin lock under heavy contention livelock?
    Not by itself. Plain spinning is wasteful but the lock is still handed to someone on each release, so the system as a whole progresses — that is contention, and possibly starvation for unlucky spinners. It becomes livelock only when the protocol makes everyone abandon and retry symmetrically, so no acquirer ever completes its critical section.
  • Can livelock exist with a single thread?
    Not in the concurrency sense. A single thread looping forever is an infinite loop; livelock requires two or more parties whose mutual reactions keep resetting each other's progress. That is why removing all but one participant makes livelock disappear, which is a handy diagnostic.

Two people meeting in a narrow corridor. Deadlock is both standing still forever, each waiting for the other to move. Livelock is both stepping aside at the same instant, again and again — lots of motion, no passage.

saying these in an interview costs you the question

  • Saying livelock is just "a deadlock that eventually resolves" — deadlock never resolves and livelock need not either.
  • Claiming the CPU is idle during livelock; livelock is CPU-hot, which is exactly what distinguishes it in monitoring.
  • Assuming the runtime or JVM/OS deadlock detector will also catch livelock — no scheduler can tell a livelocked thread from a busy one.
  • Proposing "just retry longer" or a bigger fixed sleep as the fix, which keeps the symmetry that caused the collisions.
  • Confusing livelock with starvation: livelock means nobody progresses, starvation means the system progresses but one victim never does.

context

resolving links…