Deadlock
The problem
When threads lock resources in different orders, they can end up each holding what the other needs and waiting forever — the system doesn't crash, it just freezes, silently and permanently, which is far harder to diagnose than an outright failure.
Why now
Concurrency and synchronization introduced locks as the fix for race conditions, but locks themselves create a new failure mode when used carelessly. Graph theory already proved that a dependency structure with a cycle has no valid ordering — deadlock is exactly that same cycle, now made of threads waiting on each other's locks instead of tasks waiting on prerequisites.
Mental model
Draw an arrow from each thread to the lock it's waiting for, and from each held lock to the thread holding it — deadlock exists exactly when this graph has a cycle. This is the identical topological-order failure from graph-theory-basics: a DAG always has a valid order, and a cycle means no valid order exists — for threads, 'no valid order' means nobody ever proceeds.
Requires
- Concurrency & SynchronizationOperating Systems
Deadlock is a specific failure mode of locks; you need to understand what a lock is and why threads wait on them before deadlock (threads waiting on each other's locks forever) is meaningful.
- Graph Theory BasicsMathematical Thinking
Deadlock detection is literally cycle detection in a wait-for graph; the exact algorithm and the exact justification (a DAG has a valid order, a cycle doesn't) both come directly from graph theory.
Related
Used in
- Database deadlock detection between competing transactions
- Operating system resource allocation (locks, file handles, devices)
- Distributed lock managers in distributed systems
- Debugging systems that hang under load instead of crashing outright
Projects
- Write a two-thread program that deadlocks by acquiring two locks in opposite orders, then fix it by enforcing a consistent lock ordering
- Draw the wait-for graph for a three-thread, three-lock deadlock scenario and identify the cycle by hand
Examples
- Thread A holds lock 1 and waits for lock 2; Thread B holds lock 2 and waits for lock 1 — neither ever proceeds
- Most production databases detect deadlocks automatically and abort one transaction to break the cycle
Resources
- Deadlock — MIT 6.033course
Mastery checklist
- I can state the four necessary conditions for deadlock
- I can construct a minimal two-thread, two-lock deadlock example
- I can explain deadlock detection as cycle detection in a wait-for graph
- I can prevent deadlock in a real scenario by enforcing a consistent lock acquisition order