// the one-minute version
A deadlock is a cycle of waiting: each task holds a resource and waits for one another holds, so nobody moves. It needs four conditions at once — mutual exclusion, hold-and-wait, no preemption, circular wait — and breaking any one prevents it. Systems handle deadlock four ways: prevent by design, avoid by checking each request (Banker's algorithm), detect-and-recover, or ignore it and reboot.
Two threads, two locks. Thread A grabs lock 1 and reaches for lock 2. Thread B grabbed lock 2 and reaches for lock 1. Both wait. Forever. Nothing crashed — the system is simply, permanently stuck. That's deadlock, one of the nastiest bugs in systems because it depends on exact timing.
01 The four necessary conditions
Deadlock can only happen when all four hold simultaneously. That's good news — remove any one and deadlock is impossible.
Mutual exclusion
At least one resource is non-shareable — only one task can use it at a time.
Hold and wait
A task holds at least one resource while waiting to acquire more.
No preemption
A resource can't be forcibly taken; it's released only voluntarily.
Circular wait
A closed chain of tasks exists, each waiting for a resource the next one holds.
02 Resource-allocation graphs
Draw tasks and resources as nodes; an arrow from a task to a resource means "waiting for it," and from a resource to a task means "held by it." A cycle signals possible deadlock. With one instance of each resource, a cycle is deadlock; with multiple instances, a cycle only means deadlock is possible — you must check further.
Fig 1 — A resource-allocation graph. Solid = waiting-for, dashed = held-by. A cycle here means deadlock.
03 Strategy 1 — Prevention
Prevention designs the system so one condition can never hold. Attack hold-and-wait by requiring a task to request all resources up front (wasteful — it holds things it isn't using yet). Attack circular wait by numbering resources and forcing acquisition in increasing order (the practical favorite). Attack no preemption by allowing the system to take resources back and roll the task back. Prevention is airtight but often hurts utilization or flexibility.
04 Strategy 2 — Avoidance and the Banker's Algorithm
Avoidance is less rigid: allow flexible requests, but before granting each one, check whether it could lead to trouble. This needs advance knowledge of each task's maximum future needs. A state is safe if there's some order in which all tasks can finish; unsafe doesn't mean deadlocked yet, but it risks it. The Banker's Algorithm grants a request only if the resulting state stays safe.
05 Strategy 3 — Detection and recovery
Some systems let deadlocks happen, run a detection algorithm periodically (looking for cycles in the wait-for graph), and recover by force: abort one or more tasks, or preempt their resources and roll them back. Choosing the victim (cheapest to kill, fewest resources held, least work lost) is its own problem, and you must avoid repeatedly killing the same unlucky task (starvation). Databases do exactly this between transactions.
06 Strategy 4 — Ignore it
The blunt option — the "ostrich algorithm": assume deadlocks are rare enough that handling them isn't worth the cost, and reboot if the system hangs. Surprisingly, this is what most general-purpose operating systems actually do for ordinary resources, because prevention/avoidance overhead isn't worth it for a rare event.
07 The practical rule
In everyday multithreaded code you rarely run the Banker's Algorithm. You break circular wait by always acquiring locks in a consistent global order — lock account A before account B by ID, always. Then the cycle that causes deadlock can't form. Simple, cheap, effective, and the one technique you'll genuinely use.
common catches & gotchas
- All four conditions, together — Deadlock needs every one of the four at once; break a single one and it's impossible. Prevention always targets exactly one.
- Unsafe ≠ deadlocked — An unsafe state only risks deadlock; the system may still be fine. The Banker's algorithm conservatively refuses to enter unsafe states.
- Banker's needs max-needs upfront — Its big real-world limitation — general programs don't declare maximum resource needs, so it's seldom used outside specialized systems.
- Deadlock ≠ starvation — Deadlock = a fixed set of tasks permanently blocked in a cycle. Starvation = the system runs but one task never gets served. Different problems.
- Cycle with multi-instance resources — A cycle only guarantees deadlock when each resource has one instance. With multiple instances a cycle may be harmless — check carefully.
08 Questions students actually ask
Do you need all four conditions, or just some?
All four must hold at the same time. That's why prevention works by eliminating just one — break a single link and the chain can't form.
Why not always prevent or avoid deadlocks?
Both cost real performance and flexibility — requesting all resources up front, or checking safety on every request. For rare deadlocks, that overhead often isn't worth it, so many systems just detect-and-recover or ignore.
How do databases handle deadlock?
Detection and recovery: detect a cycle between transactions, then abort and roll back the cheaper one so the other proceeds. The killed transaction is simply retried.
What's the easiest defense in my own code?
Always acquire locks in a consistent global order. This kills the circular-wait condition and prevents the most common multithreaded deadlocks with almost no cost.
What does the Banker's algorithm actually check?
Whether granting a request leaves a safe state — one where some ordering lets every task obtain its declared maximum and finish. If not, it makes the requester wait.
09 Key takeaways
- A deadlock is a cycle of tasks each holding one resource and waiting for another.
- It needs four conditions together: mutual exclusion, hold-and-wait, no preemption, circular wait.
- Break any one and deadlock is impossible.
- Prevention designs it out; avoidance (Banker's) checks each request but needs max-needs upfront; detection+recovery cleans up; ignoring is common.
- Deadlock ≠ starvation; unsafe ≠ deadlocked.
- Practical rule: acquire locks in a consistent global order.
10 Wrapping up
Deadlock closes the process-and-concurrency half of the book: correctness can fail in the interaction between components even when each looks fine alone. Now the focus shifts to the other great resource — memory. Next up: Main Memory.