# 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.

Canonical: https://devsunite.com/resources/core-subjects/operating-systems/deadlock-detection
Last updated: 2026-11-22

Subject: Operating Systems · Category: Deadlocks · 4 min read

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

1. Build the current wait-for graph from the system's real resource allocation and request state.
2. Run a cycle-detection traversal (a depth-first search tracking the current recursion stack works well here).
3. If a cycle is found, every process in that cycle is deadlocked.
4. 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.

## Related

- [Previous: Banker's Algorithm](https://devsunite.com/resources/core-subjects/operating-systems/bankers-algorithm)
- [Next: Deadlock Ignorance (The Ostrich Algorithm)](https://devsunite.com/resources/core-subjects/operating-systems/deadlock-ignorance)
- [More in Deadlocks: Deadlocks in Operating Systems](https://devsunite.com/resources/core-subjects/operating-systems/deadlocks-in-os)
- [More in Deadlocks: Deadlock Prevention](https://devsunite.com/resources/core-subjects/operating-systems/deadlock-prevention)
- [More in Deadlocks: Deadlock Avoidance](https://devsunite.com/resources/core-subjects/operating-systems/deadlock-avoidance)
- [More in Deadlocks: Starvation in Operating Systems](https://devsunite.com/resources/core-subjects/operating-systems/starvation)
- [All 205 OS interview questions](https://devsunite.com/resources/core-subjects/operating-systems)
