What Is Deadlock Detection?

Learn deadlock detection — wait-for graph cycles and recovery via termination or preemption — with an OS interview question and code.

mediumQ38 of 224 in Operating Systems Est. time: 5 minsLast updated: July 2026

Open Code Lab

Expected Interview Answer

Deadlock detection is a reactive strategy where the OS allows deadlock to potentially occur, periodically checks the system state for it using an algorithm over the resource-allocation graph or wait-for graph, and then recovers by preempting resources or terminating processes once a deadlock is confirmed.

Instead of restricting requests upfront like prevention or checking safety on every grant like avoidance, detection lets processes request and hold resources freely, then periodically (or when CPU utilization drops suspiciously) runs a detection algorithm: for single-instance resource types, it looks for a cycle in the wait-for graph, which is both necessary and sufficient for deadlock; for resources with multiple instances, it uses a Banker’s-Algorithm-like reduction that tries to find a completion order and reports deadlock if some processes remain stuck. Once a deadlock is confirmed among a specific set of processes, recovery involves either terminating one or more processes in the cycle (chosen by cost heuristics like priority, work done, or resources held) or preempting resources from a victim process and rolling it back to a safe checkpoint. This approach maximizes resource utilization and concurrency compared to prevention or avoidance, but pays for it with detection overhead and the disruption of recovery.

Maximizes resource utilization since requests are never proactively restricted
Cycle detection on a wait-for graph is a simple, well-understood algorithm
Scales to complex systems where prevention rules would be too restrictive
Complements monitoring — low CPU utilization is a natural trigger to run detection

AI Mentor Explanation

Deadlock detection is like a tournament organizer who lets teams book grounds and equipment freely without restriction, but periodically checks a whiteboard of who is waiting on whom, and if Team A is waiting on Team B’s net while Team B is waiting on Team A’s bowling machine, that cycle is flagged as a stuck standoff. Once found, the organizer resolves it by forcing one team to release its equipment, even mid-session, so the other can proceed. This is fundamentally different from stopping the double-booking in the first place; it lets it happen and cleans up after spotting the cycle.

Step-by-Step Explanation

Step 1
Allow free requesting
Processes request and hold resources with no upfront restriction, unlike prevention or avoidance.
Step 2
Build the wait-for graph
Track which process is waiting on which other process, derived from the resource-allocation graph.
Step 3
Run detection
Periodically (or when CPU utilization drops) search for a cycle in the wait-for graph, or run a reduction algorithm for multi-instance resources.
Step 4
Recover
If a deadlock is confirmed, terminate or preempt resources from a chosen victim process among the cycle to break it.

What Interviewer Expects

Understanding that detection is reactive: deadlock is allowed to happen, then found and fixed
Knowledge that a cycle in a single-instance wait-for graph is necessary and sufficient for deadlock
Awareness of the two recovery strategies: process termination and resource preemption
Ability to contrast detection’s utilization benefit against prevention/avoidance’s upfront restriction

Common Mistakes

Confusing deadlock detection with deadlock avoidance (avoidance never lets an unsafe state happen)
Thinking a cycle always means deadlock even for multi-instance resource types (it does not by itself)
Forgetting that detection requires choosing a victim process for recovery, which has real cost
Not mentioning when detection typically runs (periodically or triggered by low CPU utilization)

Best Answer (HR Friendly)

“Deadlock detection takes the opposite approach from prevention: it lets processes request resources freely, and only periodically checks whether a group of them has ended up stuck waiting on each other in a circle. If it finds that circular standoff, it fixes it after the fact, usually by forcibly taking a resource back from one process or stopping it altogether. It trades occasional disruptive cleanup for much better day-to-day resource usage.”

Code Example

Cycle detection in a single-instance wait-for graph

#define N 8

int wait_for[N][N];   /* wait_for[i][j] = 1 if process i waits on process j */
int visited[N];
int in_stack[N];

int has_cycle(int node) {
    visited[node]  = 1;
    in_stack[node] = 1;

    for (int j = 0; j < N; j++) {
        if (!wait_for[node][j]) continue;
        if (in_stack[j]) return 1;                 /* back edge: cycle found */
        if (!visited[j] && has_cycle(j)) return 1;  /* recurse into neighbor */
    }

    in_stack[node] = 0;
    return 0;
}

int deadlock_exists(void) {
    for (int i = 0; i < N; i++) { visited[i] = 0; in_stack[i] = 0; }
    for (int i = 0; i < N; i++) {
        if (!visited[i] && has_cycle(i)) return 1;  /* a wait-for cycle means deadlock */
    }
    return 0;
}

Follow-up Questions

Why is a cycle in the wait-for graph sufficient for deadlock only with single-instance resources?
What triggers the OS to run deadlock detection in practice?
How does a system choose which process to terminate during recovery?
What is the difference between resource preemption and process termination as recovery strategies?

MCQ Practice

1. Deadlock detection differs from avoidance because it?

2. For single-instance resource types, what confirms a deadlock in the wait-for graph?

3. Which is a valid recovery action once a deadlock is detected?

Flash Cards

1 / 4

What Is Deadlock Detection?

Expected Interview Answer

AI Mentor Explanation

Step-by-Step Explanation

Allow free requesting

Build the wait-for graph

Run detection

Recover