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 indicate that is waiting for a resource held by . 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
5Working / How It Works
- Cycle Detection Algorithm (for Single Instance Systems):
- Construct Wait-For Graph (WFG) by collapsing resource nodes from Resource Allocation Graph.
- Run Depth-First Search (DFS) or Tarjan's cycle detection routine periodically.
- If cycle exists in WFG, flag system state as Deadlocked.
- Deadlock Recovery Options:
- Option A: Process Termination:
- Abort all deadlocked processes: Clears deadlock instantly, but discards all partial work.
- Abort one process at a time: Abort process -> Re-check WFG for cycles -> Repeat until cycle broken.
- Option B: Resource Preemption:
- Select a victim: Determine which process holds resources with lowest cost to preempt.
- Rollback: Revert victim process state to safe checkpoint.
- Starvation Prevention: Ensure the same process is not repeatedly selected as a victim.
- Option A: Process Termination:
6Types / Components / Characteristics
- Wait-For Graph Rules:
- Nodes: Only Processes .
- Edge : Process is waiting for Process 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
- 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. - Conceptual Question: Describe the step-by-step procedure for handling deadlock recovery via Resource Preemption.
- Application Question: Convert a Resource Allocation Graph containing 4 processes and 4 resources into its corresponding Wait-For Graph and evaluate cycle presence.
