When a deadlock forms
A deadlock occurs when threads wait on each other in a cycle so none can proceed. The classic case is two threads grabbing two locks in opposite order.
The wait for graph
A runtime detector maintains a wait for graph:
- each node is a thread
- an edge from thread A to thread B means A is blocked waiting for a lock B holds
- a cycle in this graph means a deadlock
The detector adds an edge when a thread blocks and removes it when the thread acquires, checking for cycles after each change.
Detect versus prevent
Detection catches a deadlock that already happened so the system can break it, often by aborting a victim. It does not prevent deadlock, unlike disciplines that enforce a fixed lock order.
Key idea
Runtime deadlock detection models blocking as a wait for graph and reports a deadlock when a cycle forms, then recovers by breaking the cycle rather than preventing it.