Deadlock and livelock

Deadlock is a state where a set of threads each wait for a resource held by another thread in the set. No one can move, so the program hangs. Unlike a race, deadlock is usually repeatable once the wrong timing happens, and the program stays frozen rather than giving a wrong answer.

The classic case is two threads and two locks. Thread 1 holds lock A and waits for lock B. Thread 2 holds lock B and waits for lock A. Neither can proceed.

The four conditions

Deadlock needs all four of these conditions at once. Edward Coffman named them in 1971, and removing any one prevents deadlock.

The most practical fix is the last one. Lock ordering means every thread takes locks in the same global order. If every path takes A before B, the cycle can't form. Document the order next to the locks, and enforce it in code review.

Timeouts break the no-preemption condition in practice. A thread that can't get its second lock within, say, 500 ms releases its first lock and retries. The timeout value matters: too short causes thrashing, and too long hides the bug.

Livelock

Livelock is the opposite failure. The threads are not blocked. They keep running, but they keep yielding to each other, so no real work happens. Two people in a hallway each step aside in the same direction, again and again.

Livelock often comes from retry logic. Two workers both back off on conflict, then retry at the same moment and conflict again. The fix is randomized backoff: each retry waits a random interval, so the workers stop colliding in lockstep.

Starvation

A related failure is starvation, where a thread never gets its turn because others keep going first. A fair lock, which grants access in arrival order, prevents it at some cost in throughput.

Common mistakes

• Taking locks in different orders on different code paths.
• Holding a lock while calling a function that takes another lock you can't see.
• Retrying on conflict without randomized backoff, which creates livelock under load.
• Setting lock timeouts so long that a deadlock looks like a slow service.

Check yourself

• Which Coffman condition does lock ordering break? Answer: circular wait. Every thread takes locks in the same order, so no cycle can form.
• Why does randomized backoff stop livelock? Answer: retries are spread out in time, so two workers stop colliding in lockstep.

Key takeaways

• Deadlock needs mutual exclusion, hold and wait, no preemption, and circular wait. Breaking any one prevents it.
• Lock ordering is the most practical fix, because it removes circular wait.
• Livelock means threads keep running without progress, usually from synchronized retries.
• Add randomized backoff to retries, and use thread dumps to diagnose hangs.

Further learning

Next, see shared state without locks for designs that avoid this risk by not sharing mutable state.