Concurrency
Livelock and starvation: interview questions and how to answer them
Livelock is motion without progress — threads repeatedly retry and repeatedly undo each other; starvation is a thread that is ready to run but never gets the resource it needs.
Written and reviewed by Sahil Srivastav
What it actually is
Deadlock, livelock, and starvation are all liveness failures, and they are distinguished by what the threads are doing. In deadlock the threads are blocked and the wait-for graph has a cycle. In livelock the threads are running — burning CPU — and the global state keeps changing without anyone completing. In starvation the system as a whole is making progress but one participant never does.
Livelock classically arises from politeness. Two threads each hold one lock, each detects contention, each releases and retries — and if they retry in lockstep they collide again. The pattern appears in `tryLock`-with-backoff code, in optimistic retry loops on a hot row where every attempt loses to some other attempt, and in distributed leader election where two candidates keep stepping down for each other.
Starvation is usually a consequence of an unfair scheduling policy meeting an unlucky workload. An unfair lock hands the lock to whichever thread asks next, which is fast — the woken thread may not even have to context-switch back in — but it lets a stream of short-lived requesters keep a long-waiting thread queued indefinitely. A lock convoy is the related pathology: a lock held briefly but constantly, so the queue never empties and every acquisition pays a context switch.
Why it matters in production
Because both failure modes present as a performance problem rather than an error, and so get diagnosed wrongly. A livelocked retry loop shows as high CPU and flat throughput, which reads like "we need more instances". Starvation shows as a heavy tail: p50 fine, p99 catastrophic, because a handful of unlucky requests wait behind everyone else. Adding capacity makes both worse, since more contenders means more collisions and a longer queue.
Because optimistic concurrency turns into livelock exactly where it is most tempting. A single hot row updated with a version check under a hundred concurrent writers means almost every writer loses, retries, and loses again. The system is not deadlocked and no request errors — they just all take ten times longer, and the database sees ten times the write attempts.
And because the mitigations have real costs that an interviewer wants you to name. Fair locks eliminate starvation and reduce throughput measurably, because they forbid the barging that makes unfair locks fast. Randomised backoff breaks livelock and adds latency. There is no free option, only a choice about which property you need.
How it works
Livelock is a synchronised retry
Two participants that detect conflict and retry after the same delay collide again with high probability, because their schedules stay aligned. Adding randomised jitter to the backoff desynchronises them, and exponential growth bounds the collision rate as contention rises. A fixed retry delay is the single most common cause of an unbreakable livelock.
Fairness is a queue, and queues cost throughput
`new ReentrantLock(true)` grants the lock in arrival order, so no thread waits forever. The cost is that a releasing thread cannot hand the lock to itself or to an already-running thread; it must wake the head of the queue, which means a context switch per handoff. On a hot lock this can cut throughput by an order of magnitude, which is why the default is unfair.
Lock convoys: short critical sections, permanent queue
If the arrival rate of lock requests exceeds the rate at which the critical section plus the wakeup cost can be completed, the queue never drains. Each thread now pays a park/unpark round trip, so effective throughput drops below what a single thread would achieve. The fix is to remove the shared lock — shard the state, use a read-write lock if most access is read-only, or replace the structure with a concurrent one — not to make the section faster.
Starvation in thread pools comes from nesting
A task submitted to a fixed pool that waits on the result of another task submitted to the same pool can consume every thread with waiters and have nobody left to do the work. Nothing is deadlocked in the lock sense, but no task completes. Separate pools per tier, or a work-stealing pool where a blocked join can help complete the subtask, avoid it.
Priority inversion needs inheritance, not more priority
A low-priority thread holding a lock a high-priority thread needs blocks it indefinitely if a medium-priority thread keeps the CPU. Raising the high thread's priority changes nothing, because it is blocked, not scheduled out. Priority inheritance — temporarily boosting the lock holder — is the mechanism that resolves it, and it is the reason Java thread priorities are nearly useless for this.
Implementing it
Bound every retry loop by attempts and by total elapsed time, and add full jitter to the delay. An unbounded retry with a constant delay is how a transient conflict becomes a permanent livelock.
Reach for a fair lock only when tail latency or a fairness SLA is the requirement, and measure the throughput you gave up. On most server workloads unfair plus a bounded queue is the right trade.
Give distinct workloads distinct pools. A slow downstream and a fast one sharing an executor means the slow one starves the fast one, and no amount of tuning the pool size fixes the coupling.
When an optimistic retry loop starts failing repeatedly, treat it as a signal to change the operation shape — a single atomic statement, a queue that serialises the hot key, or sharded counters — rather than to raise the retry limit.
// Livelock: identical backoff keeps the two threads in lockstep
while (true) {
if (lockA.tryLock()) {
if (lockB.tryLock()) { work(); return; }
lockA.unlock();
}
Thread.sleep(10); // both retry together, forever
}
// Desynchronised: full jitter plus a hard bound
for (int attempt = 0; attempt < 5; attempt++) {
if (tryBoth()) return;
long capMs = Math.min(200, 10L << attempt);
Thread.sleep(ThreadLocalRandom.current().nextLong(capMs + 1));
}
throw new ContentionException("gave up after 5 attempts");
// Fairness costs throughput — make it a deliberate choice
Lock fair = new ReentrantLock(true); // no barging, one context switch per handoffInterview questions and how to answer them
Distinguish deadlock, livelock, and starvation with the symptom you would see in production.
Deadlock: the involved threads are parked, CPU for them is zero, a thread dump shows a cycle, and the affected endpoints hang permanently. Livelock: CPU is high, throughput is flat or falling, retry counters climb, and nothing errors — the threads are working and undoing each other. Starvation: overall throughput looks fine but the tail explodes, because some requests wait behind a stream of others. The reason to be precise is that the fixes differ completely — lock ordering, jittered backoff, and fairness or pool separation respectively.
Your optimistic retry loop on a hot row is spinning. What now?
Accept that optimistic concurrency is the wrong tool for that row. Under high contention nearly every attempt loses the version check, so you pay N attempts to complete one write. The options in order of preference: express the mutation as a single atomic statement so there is no conflict to detect; shard the state so contention spreads across rows, as `LongAdder` does in-process and as sharded counters do in a database; or serialise the hot key through a queue so writes arrive one at a time. Raising the retry cap is the one thing that reliably makes it worse.
When would you use a fair lock?
When an unbounded wait is unacceptable — a per-tenant fairness guarantee, an SLA on p99.9, or a background writer that must not be starved by a flood of readers. I would enable it knowing the cost: fairness forbids barging, so each handoff requires waking the queue head and paying a context switch, and on a hot lock that is a large throughput loss. If the requirement is really "no thread waits forever" I would first ask whether the lock should exist at all, because reducing the shared section usually beats scheduling it more politely.
What is a lock convoy and why does it make things slower than single-threading?
A convoy forms when a lock is held very briefly but requested constantly: the queue never empties, so every acquisition involves parking and unparking a thread. The critical section might be 200 nanoseconds while the handoff costs microseconds, so the system spends most of its time on scheduling overhead — worse than if one thread did all the work with no synchronisation at all. Recognising it matters because the instinct is to optimise the code inside the lock, when the fix is to stop sharing: shard the map, use a read-write lock if reads dominate, or move to a lock-free structure.
A task in a fixed thread pool waits for another task in the same pool. What happens?
With enough concurrency, every thread ends up holding a waiting parent task and there is nobody left to run the children, so the pool stalls. It is starvation, not deadlock — no lock cycle exists — but the outcome is the same and no detector will report it. The fixes are to use separate pools for the two tiers so the dependency cannot exhaust a single one, or a `ForkJoinPool` where `join` can help execute the pending subtask, or to restructure so the parent never blocks on a child.
Answers that lose the round
- Calling a livelock a deadlock, when the CPU profile alone distinguishes them: deadlocked threads are parked, livelocked ones are hot
- Fixing contention by raising the retry limit, which increases load on the contended resource and lengthens the livelock
- Using a fixed backoff delay, so retries stay synchronised and collide again
- Making every lock fair "to be safe", then being unable to explain the throughput regression that follows
- Submitting dependent tasks to the same fixed-size pool and calling the resulting stall a deadlock; it is starvation, and the fix is pool separation
- Treating thread priorities as a starvation fix in Java, where they are advisory and do nothing about a blocked thread waiting on a lock
- Scaling out a livelocked service, which adds contenders and makes the collision rate worse
Practise livelock and starvation in a real repository
Gronex ships this as a runnable repository: a service whose nested task submissions exhaust a shared executor and stall under load. The tests drive enough concurrency to starve the pool, so raising the pool size only moves the cliff — the fix has to change the dependency structure.
FAQ
Does the JVM detect livelock?
No. Deadlock detection works by finding a cycle in a static wait-for graph; a livelock has no cycle and no static state — the threads are running. You find it by noticing high CPU with no throughput, then profiling to see the retry loop at the top of the stack.
Is `synchronized` fair?
No. Java monitors make no fairness guarantee at all, and HotSpot deliberately allows barging because it is faster. If you need fairness you need `ReentrantLock(true)`, and even then only lock acquisition is fair — `Condition.await` wakeups and the underlying OS scheduler have their own policies.
How does backoff jitter actually help?
Because collisions come from correlated timing. Two clients that both retry after exactly 100 ms retry simultaneously forever. Randomising the delay over the interval decorrelates their schedules, so the probability that a given retry collides falls with each round. Exponential growth on top of that keeps the total load bounded as contention rises.