Deadlock, starvation and livelock all mean "some work never finishes," but they look completely different on a running system. Telling them apart tells you where to look: blocked threads, an unfair scheduler or lock, or retry logic that keeps colliding.
Deadlock: frozen forever#
Threads are blocked, waiting on each other in a cycle:
| Thread | Holds | Wants | State |
|---|---|---|---|
| Thread 1 | A | B | Blocked |
| Thread 2 | B | A | Blocked |
Both are asleep. CPU usage is ~0%, and there is no progress.
Analogy: two cars meet on a one-lane bridge from opposite sides. Nobody moves. The four conditions and prevention strategies are covered in Deadlocks.
Starvation: forgotten forever#
A thread is ready to run but never gets the CPU or the lock, because others keep being picked first. The system as a whole is working; just this thread is ignored.
For example, high-priority tasks keep arriving. P1, P2 and P3 (all priority 1) each run in turn, and more keep coming, while P10 (priority 5) sits in the ready queue forever.
Analogy: a polite person at a buffet. Food is being served, but every time they step forward, someone cuts in.
Common causes:
-
Priority scheduling without aging: high-priority work never stops arriving (see CPU scheduling).
-
Unfair mutex: a thread releases the lock and immediately re-acquires it; waiters never get a turn.
-
Writer starvation with read-write locks: readers keep overlapping, so the read lock is never free.
Step Readers Writer 1 Reader 1 reading; Reader 2 starts Waiting 2 Reader 1 finishes; Reader 3 starts Waiting 3 Reader 2 finishes; Reader 4 starts ... Still waiting for a moment with zero readers
Fixes:
- Priority aging: raise a waiting thread's priority over time until it runs.
- Fair locks (FIFO): the longest waiter goes next. Python's
threading.Lockhas no fair mode, so you would build one, for example by handing turns out through aqueue.Queue. - Writer-preferring read-write locks: once a writer is waiting, new readers queue behind it; existing readers finish, then the writer goes.
Livelock: busy forever, going nowhere#
Threads are not blocked. They're running and consuming CPU, but they keep reacting to each other and make no progress.
Analogy: two people in a hallway both step left, then both step right, then both left again. Both are moving, nobody gets past.
How it happens in code: both threads try to avoid deadlock by backing off, but they do it in lockstep:
| Step | Thread 1 | Thread 2 |
|---|---|---|
| 1 | lock(A): OK |
lock(B): OK |
| 2 | tryLock(B): fails |
tryLock(A): fails |
| 3 | unlock(A), retry |
unlock(B), retry |
| 4 | lock(A): OK |
lock(B): OK |
| 5 | tryLock(B): fails |
tryLock(A): fails |
| ... | Forever | Forever |
Fix: random backoff. Each thread waits a random time before retrying, which breaks the symmetry. Say each sleeps a random 1–10 ms after failing:
| Time | Thread 1 | Thread 2 |
|---|---|---|
| 0 ms | Fails, unlock(A), sleeps 7 ms |
Fails, unlock(B), sleeps 3 ms |
| 3 ms | Still sleeping | Takes B, then A: succeeds |
| 7 ms | Takes A, then B: succeeds | Done |
Classic Ethernet resolves collisions the same way, with (binary) exponential random backoff. Retrying network clients use exponential backoff with jitter for the same reason.
Side-by-side#
The quickest way to tell them apart is to look at thread state and CPU usage.
| Deadlock | Starvation | Livelock | |
|---|---|---|---|
| Threads blocked? | Yes | No, ready but skipped | No, actively running |
| CPU usage | ~Zero for those threads | Others use the CPU | High, wasted |
| Progress | None for the threads involved | None for the starved thread | None for the threads involved |
| System overall | Frozen (at least partly) | Working, but unfair | Working, but wasteful |
| Typical cause | Circular lock dependency | Unfair scheduling or locks | Symmetric retry logic |
| Typical fix | Global lock ordering | Priority aging, fair locks | Random backoff |
| How hard to spot | Easier: thread dump shows a wait cycle | Hard: system looks healthy | Hard: threads look busy |
Key takeaways#
- Deadlock: blocked in a cycle, zero CPU. Fix with lock ordering.
- Starvation: ready but always skipped. Fix with aging or fair locks.
- Livelock: running, reacting to each other, no progress. Fix with random backoff.
- A thread dump plus CPU usage usually tells you which one you have.