Topic 6.3 · Deadlocks

Deadlock Detection, Wait-For Graphs & Recovery Strategies

3 min read1 question to test yourself

1Definition

Deadlock Detection is the process of periodically executing kernel routines to inspect resource allocation states and identify existing cycles or deadlocks. A Wait-For Graph (WFG) is a directed graph variant used for single-instance resource systems where nodes represent processes and directed edges Pi→PjP_i\rightarrow P_j indicate that PiP_i is waiting for a resource held by PjP_j. Deadlock Recovery is the operational strategy used to restore a deadlocked system to normal execution.

2Simple Explanation

If an operating system does not prevent or avoid deadlocks, deadlocks will occasionally happen. Detection works like a background system diagnostic. For single-instance resources, the OS constructs a simplified map called a Wait-For Graph. It removes the resource nodes and draws arrows directly from Process A to Process B if A is waiting for B to release something. If the graph contains a closed loop (Cycle), a deadlock exists! Once detected, the OS executes Recovery: it either forcibly terminates deadlocked processes or preempts their resources.

3Real-Life Example / Analogy

A Traffic Intersection Gridlock Specialist: A police drone flies over a gridlocked city intersection. It maps out which cars are blocking which cars. If Car 1 blocks Car 2, Car 2 blocks Car 3, and Car 3 blocks Car 1 (Wait-For Graph Cycle detected!), the officer uses a tow truck to haul Car 1 away (Process Termination / Preemption), unblocking the rest of the traffic loop.

4Diagram / Visual Representation

WAIT-FOR GRAPH

Process P1

Process P2

RESOURCE ALLOCATION GRAPH

Resource R1

Process P1

Resource R2

Process P2

5Working / How It Works

  • Cycle Detection Algorithm (for Single Instance Systems):
    1. Construct Wait-For Graph (WFG) by collapsing resource nodes from Resource Allocation Graph.
    2. Run Depth-First Search (DFS) or Tarjan's cycle detection routine periodically.
    3. If cycle exists in WFG, flag system state as Deadlocked.
  • Deadlock Recovery Options:
    • Option A: Process Termination:
      1. Abort all deadlocked processes: Clears deadlock instantly, but discards all partial work.
      2. Abort one process at a time: Abort process PkP_k -> Re-check WFG for cycles -> Repeat until cycle broken.
    • Option B: Resource Preemption:
      1. Select a victim: Determine which process holds resources with lowest cost to preempt.
      2. Rollback: Revert victim process state to safe checkpoint.
      3. Starvation Prevention: Ensure the same process is not repeatedly selected as a victim.

6Types / Components / Characteristics

  • Wait-For Graph Rules:
    • Nodes: Only Processes P1,P2,…,Pn{P_1, P_2, \dots, P_n}.
    • Edge Pi→PjP_i\rightarrow P_j: Process PiP_i is waiting for Process PjP_j to release a resource.
    • Deadlock Theorem: In a Wait-For Graph (single-instance resources), a cycle exists if and only if a deadlock exists.

7Solved Examples / Problems

Problem: Contrast Process Termination vs Resource Preemption in deadlock recovery. Solution:

  • Process Termination kills the process outright (kill -9), discarding all uncommitted memory state and requiring a complete application restart.
  • Resource Preemption forcibly revokes a resource lock from a process, saves its execution context to a checkpoint, allocates the resource to a waiting process, and later rolls back the victim process to resume execution from its last checkpoint without restarting from scratch.

8Advantages, Disadvantages & Applications

  • Detection Advantages: Allows maximum system concurrency without upfront allocation restrictions.
  • Disadvantages: Periodically running cycle detection algorithms consumes CPU cycles; process termination can lead to corrupted disk files.

9Important Points to Remember

  • In a single-instance resource system, a cycle in the Wait-For Graph is a necessary and sufficient condition for a deadlock.
  • In multi-instance resource systems, a cycle in a Resource Allocation Graph is a necessary condition, but not a sufficient condition.

10Test Your Understanding

  1. MCQ: In a single-instance resource system, what does a cycle in the Wait-For Graph signify?
    • A) The system is in a safe state.
    • B) A deadlock definitely exists in the system.
    • C) System memory is thrashing.
    • D) A race condition has occurred.
    Show answer
    B.
  2. Conceptual Question: Describe the step-by-step procedure for handling deadlock recovery via Resource Preemption.
  3. Application Question: Convert a Resource Allocation Graph containing 4 processes and 4 resources into its corresponding Wait-For Graph and evaluate cycle presence.

Finished this topic?

0 of 27 topics read in Operating Systems

Handwritten notes for the exam

Unit-wise SPPU notes and PYQs for this subject.

Helpful? Share it with your class

Free for everyone, no login needed.

Share topic