Deadlocks
A cycle of waits. Coffman conditions, detection, and the ways out.
Level: intermediate
What is it?
A deadlock is a circular wait: P1 holds A and wants B, P2 holds B and wants A, and nobody will drop what they hold. No progress, no exception — just silence.
Why does it matter?
Locks, database rows, and distributed leases all deadlock. If you cannot name the four conditions, you cannot choose a prevention strategy on purpose.
Mental model
Two people in a corridor, each too polite to step back, each holding a box the other needs. The resource-allocation graph has a cycle.
How it works
- Coffman: mutual exclusion, hold-and-wait, no preemption, circular wait. All four required.
- Prevention: break a condition (lock ordering breaks circular wait; allocate-all-at-once breaks hold-and-wait).
- Avoidance: Banker's algorithm admits a request only if a safe sequence still exists.
- Detection: find a cycle, then abort a victim. Databases do this; OS kernels usually do not for user mutexes.
- Livelock is not deadlock: everyone is running, nobody is progressing.
Steps
- Draw processes and resource instances.
- Add request and assignment edges.
- A cycle in a single-instance graph is a deadlock. Multi-instance needs a more careful reduction.
- Pick a strategy: prevent, avoid, detect-and-recover, or ostrich (common in user-space mutexes).
Real-world usage
- pthread mutexes
- InnoDB row locks
- Distributed lock managers
Common mistakes
- Locking A then B in one thread and B then A in another. Order your locks globally.
- Calling a slow system 'deadlocked' without a cycle. It may be a convoy, an I/O wait, or a leak.
- Using timeouts as the only distributed deadlock strategy without fencing tokens.
Interview questions
Four Coffman conditions?
Mutual exclusion, hold and wait, no preemption, circular wait.
How does lock ordering prevent deadlock?
It makes a cycle impossible: all threads acquire locks in the same global order, so a wait-for cycle cannot form.
Deadlock vs starvation vs livelock?
Deadlock: circular wait, no progress. Starvation: some process never gets the resource. Livelock: activity without progress.