What is a Deadlock
A deadlock occurs when two or more threads are each waiting for a mutex held by the other, creating a cycle where none can make progress. The program doesn't crash — it just stops, frozen forever.
How it works
The classic scenario involves two mutexes and two threads:
Thread A: lock(mutex_1) // holds mutex_1
Thread B: lock(mutex_2) // holds mutex_2
Thread A: lock(mutex_2) // waits for mutex_2 (held by B)
Thread B: lock(mutex_1) // waits for mutex_1 (held by A)
// Both threads are stuck forever
Thread A cannot release mutex_1 until it acquires mutex_2. Thread B cannot release mutex_2 until it acquires mutex_1. Neither can proceed.
Four conditions must all be true for a deadlock to occur (the Coffman conditions):
- Mutual exclusion — resources can't be shared (that's what a mutex does).
- Hold and wait — a thread holds one resource while waiting for another.
- No preemption — locks can't be forcibly taken from a thread.
- Circular wait — a cycle exists in the wait graph (A waits for B, B waits for A).
Breaking any one of these prevents deadlocks. The most practical approach is breaking circular wait: always acquire locks in the same global order. If every thread locks mutex_1 before mutex_2, the cycle cannot form.
Other strategies:
- Try-lock with timeout — attempt to acquire the lock but give up after a deadline, then release all held locks and retry.
- Lock-free algorithms — avoid mutexes entirely using atomic operations.
- Single-lock designs — use one coarse lock instead of multiple fine-grained ones (trading parallelism for simplicity).
Why it matters
Deadlocks are the flip side of race conditions. You add locks to prevent races, but too many locks — acquired in inconsistent order — create deadlocks. The tension between "not enough synchronization" (races) and "too much synchronization" (deadlocks) is the central challenge of concurrent programming. Understanding the Coffman conditions tells you exactly what to avoid.
See How Threads Work for patterns that avoid both races and deadlocks.