Card 03/ 08
The Four Conditions for Deadlock
All four must hold at the same time, and one of them can be removed for free.
A deadlock can only happen when four conditions hold at the same time: mutual exclusion, hold and wait, no preemption, and circular wait. Removing any one of them makes deadlock impossible, which turns a mysterious failure into a design decision.
| Condition | Means | Removing it would mean |
|---|---|---|
| Mutual exclusion | A lock is held by one thread at a time | Not using locks at all |
| Hold and wait | A thread holding one lock asks for another | Taking every lock at once, or none |
| No preemption | A lock cannot be taken away from its holder | A timeout that makes a thread let go |
| Circular wait | Each thread waits for a lock the next one holds, closing a cycle | A fixed order every thread takes locks in |
The first is the point of a lock and is not going anywhere. The second is hard to avoid when an operation really spans two objects. The third is what a timeout removes, and it turns a hang into a failure rather than into success.
The fourth is the one to attack, and the only one you can remove without giving up something you wanted. If every thread in the program takes locks in the same order, a cycle cannot form, because no thread can be waiting for a lock that comes earlier in the order than one it holds.
So the practical rule from a four-part theory is one sentence: decide a global order for your locks, and take them in that order, everywhere.
← → move through sections and cards