Deadlock and the Four Conditions
Resource deadlock requires mutual exclusion, hold and wait, no preemption, and circular wait. For blocking locks with one holder each, a wait-for cycle identifies deadlock. A shared acquisition order prevents circular wait among those locks; it does not release an existing deadlock.
What a learner can do afterwards
- Draw the wait-for graph of a deadlocked pair of threads and find the cycle
- Break a given deadlock by removing one of the four conditions
- Explain how a global lock ordering prevents the cycle from forming
1 · Read
In a deadlock, a set of threads cannot proceed because each waits for a resource held within the set. Four conditions are necessary: mutual exclusion (one holder per resource), hold and wait (keep a resource while requesting another), no preemption (resources cannot be forcibly reclaimed), and circular wait (a chain returns to its starting thread). We use blocking locks with one holder each and no timeout.
Thread A holds lock 1 and waits for lock 2; B holds lock 2 and waits for lock 1. Neither releases before getting the other. A waits for B, and B waits for A. With exclusive blocking locks and no timeout, this cycle proves deadlock. With multiple interchangeable resource instances, a cycle alone need not prove deadlock.
In a thread-only wait-for graph, threads are nodes. An edge points from the waiting thread to the holder of the requested lock. Record who is waiting for whom, even if the waiter still holds another lock.
Prevent deadlock by ruling out one condition. Request all needed resources together, or release held resources before waiting, to avoid hold and wait. A system that can safely abort a holder, roll back its work and reclaim resources allows preemption. Do not unlock another thread's mutex while its work is incomplete.
Include every waiting relation when checking a wait-for graph. Reversing every arrow in a directed cycle reverses the cycle; it does not remove it. A single thread can also deadlock: if it requests a non-reentrant lock it already holds, it waits for itself. Non-reentrant means the same thread cannot acquire the lock again before releasing it.
A frozen program is not proof of deadlock; it may be waiting for input or slow work. Inspect actual holders and waiters. A new lock-order rule prevents future cycles but cannot free locks already stuck. Existing deadlock needs safe recovery, such as supported abort and rollback.
Deadlock requires all four conditions. A shared lock order prevents circular wait among those locks; an existing deadlock still needs safe recovery.
Original lesson, questions and flashcards about resource deadlock, authored for this dataset.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.