Deadlock Detection
Deadlock detection is a strategy that lets deadlocks happen, periodically checks the system's wait-for graph of processes for a cycle, and recovers when one is found. Recovery breaks the cycle either by terminating one or more of the deadlocked processes or by preempting a resource from one process and rolling that victim back to an earlier safe point.
Deadlock detection takes the opposite philosophy from prevention and avoidance: instead of stopping a deadlock from ever forming, it lets the system run freely, periodically checks whether a deadlock has actually occurred, and recovers if one is found.
The core tool: the wait-for graph
Build a graph where each node is a process, and there's an edge from process A to process B if A is waiting for a resource currently held by B. When every resource has a single instance, a deadlock exists if and only if this graph contains a cycle. (With multiple instances of a resource, a cycle is necessary but not sufficient, and detection uses a Banker's-style algorithm over the available, allocation and request matrices instead.) Detecting a deadlock is exactly the graph problem of cycle detection.
Step-by-step detection algorithm
- Build the current wait-for graph from the system's real resource allocation and request state.
- Run a cycle-detection traversal (a depth-first search tracking the current recursion stack works well here).
- If a cycle is found, every process in that cycle is deadlocked.
- If no cycle exists, the system is currently deadlock-free (this check has to be re-run periodically, since new requests can create a cycle later).
A worked example
Three processes and three resources, single instance each.
- P1 holds R1, and is waiting for R2.
- P2 holds R2, and is waiting for R3.
- P3 holds R3, and is waiting for R1.
Wait-for graph: P1 to P2 (P1 waits on something P2 holds), P2 to P3, P3 to P1. Tracing this: P1 leads to P2 leads to P3 leads back to P1, a cycle. All three processes are deadlocked.
Now suppose instead P3 was waiting for R2 (held by P2) rather than R1. Wait-for graph: P1 to P2, P2 to P3, P3 to P2. There's no cycle back to P1, and P2/P3 alone don't form a cycle either since P2 doesn't wait on P3. No deadlock in this version.
Recovery once a deadlock is detected
Two real strategies: process termination (kill one or more processes in the cycle, freeing their resources so the rest can proceed) or resource preemption (forcibly take a resource away from one process in the cycle and give it to another, then roll the victim process back to a safe earlier point). Choosing which process to terminate usually weighs factors like how much work that process has already done, its priority, and how many resources it holds.
Where this matters in real systems
This is exactly what real relational databases do for row-level locks. PostgreSQL and MySQL both run a background deadlock detector that periodically checks the transaction wait-for graph, and when it finds a cycle, it picks one transaction (often the one that would be cheapest to undo) and forcibly rolls it back with a deadlock error, letting the other transaction proceed. Detecting via a wait-for graph and recovering via "kill a victim" is the same pattern taught here, just applied to database rows instead of OS-level resources.
What interviewers actually ask about deadlock detection
- "How do you detect a deadlock?" Build a wait-for graph from current resource waits and holdings, then check for a cycle; a cycle means a deadlock.
- "What are the two recovery strategies once a deadlock is detected?" Process termination (kill one or more processes in the cycle) and resource preemption (take a resource from one process and roll it back).
- "Why can't you just always terminate every process in the cycle?" That wastes completed work unnecessarily; better recovery strategies pick the minimum number of victims, often based on cost, to free the cycle.
- "How does this relate to what real databases do?" Almost identically, most production databases run a background deadlock detector over their transaction wait-for graph and roll back one transaction to break any detected cycle.
Key takeaways
- Deadlock detection lets the system run and periodically checks for deadlocks rather than preventing them structurally.
- A cycle in the wait-for graph is the formal signature of a deadlock.
- Recovery is either terminating a victim process or preempting a resource and rolling the victim back.
- Real databases implement this exact pattern for row-level locking deadlocks.
More in Deadlocks
Browse all Operating Systems topics
Log in to save which topics you've read across every subject.
Frequently asked questions
How do you detect a deadlock?
Build a wait-for graph from current resource waits and holdings, then check for a cycle; a cycle means a deadlock.
What are the two recovery strategies once a deadlock is detected?
Process termination (kill one or more processes in the cycle) and resource preemption (take a resource from one process and roll it back).
Why can't you just always terminate every process in the cycle?
That wastes completed work unnecessarily; better recovery strategies pick the minimum number of victims, often based on cost, to free the cycle.
How does this relate to what real databases do?
Almost identically, most production databases run a background deadlock detector over their transaction wait-for graph and roll back one transaction to break any detected cycle.