Deadlock Detection: An Overview

Deadlock detection is the process of determining whether a deadlock currently exists in the system. Unlike prevention and avoidance, detection allows the system to enter deadlock states — but then detects them and takes corrective action.

When to use detection:

• Prevention is too costly or restrictive.
• Avoidance is impossible because maximum resource needs are unknown.
• The system is a general-purpose OS (like Linux or Windows) with unpredictable workloads.

Detection methods depend on resource type:

Detection for Single-Instance Resources: Wait-for Graph

For systems where each resource type has exactly one instance, a deadlock can be detected by constructing a Wait-for Graph (WFG) from the Resource-Allocation Graph (RAG).

Transforming RAG to WFG

The WFG is derived from the RAG by removing resource nodes and connecting processes directly:

1. For each pair (Pᵢ, Rₖ, Pⱼ) where Pᵢ is waiting for Rₖ (request edge Pᵢ → Rₖ) and Rₖ is allocated to Pⱼ (assignment edge Rₖ → Pⱼ), draw a wait-for edge from Pᵢ → Pⱼ.
2. Remove all resource nodes from the graph.
3. The resulting graph has only process nodes and directed edges representing "is waiting for".

Before (RAG): The Resource-Allocation Graph shows processes connected through resources.

After (WFG): The Wait-for Graph removes resource nodes and connects processes directly.

The cycle P₁ → P₂ → P₁ in the WFG indicates a deadlock.

Cycle Detection

Example Transformation:

Detection Algorithm (DFS-Based)

1. For each process Pᵢ in the WFG, start a Depth-First Search (DFS).
2. Mark nodes as: White (unvisited), Gray (in current DFS path), Black (fully explored).
3. If during DFS from Pᵢ we encounter a node that is already Gray, a cycle (deadlock) has been detected.
4. If no Gray node is encountered during any DFS, no deadlock exists.

Detection for Multi-Instance Resources: Banker's Detection Algorithm

When resource types have multiple instances, the Wait-for Graph approach is insufficient (a cycle does not guarantee deadlock). Instead, we use the Banker's Detection Algorithm, which is similar to the Safety Algorithm but uses current request information rather than maximum need.

Data Structures

The Detection Algorithm

1. Let Work[m] = Available[m]   // Temporary copy
2. Let Finish[n] = false for all processes
3. For each process Pᵢ where Finish[i] == false:
      if Request[i] ≤ Work, then:
         Work = Work + Allocation[i]   // Pretend Pᵢ finishes and releases
         Finish[i] = true
         Go to step 3 and restart
4. After scanning all processes:
      if Finish[i] == false for any process, then Pᵢ is deadlocked.

Result Interpretation

Example: 3 Processes, 2 Resources

Given:

• Available = (0, 0)
• Allocation = P₀: (0, 1), P₁: (2, 0), P₂: (3, 0)
• Request = P₀: (0, 0), P₁: (2, 0), P₂: (0, 1)

Execution:

1. Work = (0, 0). P₀: Request (0,0) ≤ (0,0) ✓ → P₀ finishes → Work = (0+0, 0+1) = (0, 1). Finish[0] = true.
2. P₁: Request (2,0) ≤ (0,1) ✗ → P₁ blocked.
3. P₂: Request (0,1) ≤ (0,1) ✓ → P₂ finishes → Work = (0+3, 1+0) = (3, 1). Finish[2] = true.
4. P₁: Request (2,0) ≤ (3,1) ✓ → P₁ finishes → Work = (3+2, 1+0) = (5, 1). Finish[1] = true.
5. All Finish[i] == true → No deadlock. Sequence: <P₀, P₂, P₁>.

PYQ Variation: Detection Using Allocation + Request Only (No Max) [2022 Q4b]

Some exam problems provide Allocation and Request matrices directly without a Max matrix. In this case, you use the same detection algorithm but treat Request as the current outstanding needs. Let's solve the 2022 PYQ.

Problem [2022 Q4b]: Single processor system, 3 resource types (X, Y, Z) with 5 units each, 3 processes. Find which process finishes first and last.

Step 1: Calculate Available = Total − Sum(Allocation) = (5,5,5) − (1+2+2, 2+0+2, 1+1+1) = (5,5,5) − (5,4,3) = (0, 1, 2).

Step 2: Apply Detection Algorithm. Work = (0, 1, 2).

• P₁: Request (0,1,2) ≤ Work (0,1,2) ✓ → P₁ finishes → Work = (0+2, 1+0, 2+1) = (2, 1, 3). P₁ finishes first.
• P₀: Request (1,0,3) ≤ Work (2,1,3) ✓ → P₀ finishes → Work = (2+1, 1+2, 3+1) = (3, 3, 4).
• P₂: Request (1,2,0) ≤ Work (3,3,4) ✓ → P₂ finishes → Work = (3+2, 3+2, 4+1) = (5, 5, 5). P₂ finishes last.

Result: All processes complete. Safe sequence: <P₁, P₀, P₂>. P₁ finishes first, P₂ finishes last.

Detection Frequency: When to Run Detection

Running deadlock detection is not free — it consumes CPU time and can degrade system performance. The frequency of detection involves a trade-off.

Guidelines:

• If deadlocks are rare → run detection infrequently (e.g., every hour or on admin request).
• If deadlocks are frequent → run detection more often (e.g., every few seconds or on each block).
• The cost of detection must be weighed against the cost of the deadlock (tied-up resources, frustrated users).

Deadlock Recovery: What to Do After Detection

Once a deadlock is detected, the system must recover — break the deadlock and allow processes to continue. There are two main approaches:

---

Option 1: Process Termination

Selection factors for choosing which process to abort:

1. Priority of the process (lower priority → kill first).
2. Runtime — how long the process has been running (more runtime → more work lost).
3. Resources held — how many and what type of resources the process holds (more resources → more expensive to restart).
4. Resources still needed — how many more resources the process needs to complete.
5. Number of processes that will need to be terminated.

---

Option 2: Resource Preemption

Comparison: Termination vs. Preemption