Deadlock Detection and Recovery Techniques in Operating Systems

1. What is the Deadlock Detection and Recovery Approach?

If an Operating System does neither Deadlock Prevention nor Deadlock Avoidance, then a Deadlock may eventually occur in the system.

In such systems, the OS uses a two-step strategy:

1. Deadlock Detection Algorithm: Periodically examines the state of the system to determine whether a deadlock has occurred (and which specific processes and resources are involved).
2. Deadlock Recovery Algorithm: Once a deadlock is detected, executes a recovery mechanism to break the deadlock and restore normal system operation.

2. Deadlock Detection Techniques

How the OS detects a deadlock depends on whether each resource type has a Single Instance or Multiple Instances:

Case 1: Single Instance of Each Resource Type (Wait-For Graph)

• If all resources have only 1 instance (e.g., 1 Printer, 1 Scanner, 1 Plotter), we can simplify the Resource-Allocation Graph into a Wait-For Graph (WFG) by removing the resource boxes and collapsing the edges:
  • If Pi → Rq (Pi is waiting for Rq) and Rq → Pj (Rq is held by Pj), we draw a direct arrow Pi → Pj (meaning “Process Pi is waiting for Process Pj”).
• Detection Rule: The OS periodically runs a cycle-detection algorithm on the Wait-For Graph. A deadlock exists in the system if and only if the Wait-For Graph contains a Cycle (e.g., P1 → P2 → P3 → P1).

Case 2: Multiple Instances of Each Resource Type

• When resource types have multiple instances, a Wait-For Graph cannot be used. Instead, the OS uses a time-varying Detection Algorithm (very similar to the Banker’s Algorithm) that tracks:
  • Available: Vector of length m indicating available resources.
  • Allocation: Matrix defining resources currently allocated to each process.
  • Request: Matrix defining the current request of each process (instead of lifetime Max need!).
• Any process Pi for which Finish[i] == false at the end of the algorithm is Deadlocked!

How Often Should the OS Run the Detection Algorithm?

Running deadlock detection after every single resource request wastes a lot of CPU time. Therefore, the OS invokes detection based on two factors:

1. At fixed time intervals (e.g., once every 30 minutes), OR
2. Whenever CPU Utilization drops below a threshold (e.g., if CPU utilization suddenly drops below 40%, it strongly indicates several processes are stuck in a deadlock!).

3. Recovery from Deadlock

Once the Detection Algorithm discovers that a deadlock exists, how does the Operating System break the deadlock? Apart from informing the system operator to deal with it manually, there are two automatic methods for breaking a deadlock:

1. Process Termination (Killing Deadlocked Processes)
2. Resource Preemption (Snatching Resources Away)

Method 1: Process Termination (Killing Processes)

To eliminate the deadlock by terminating processes, the OS uses one of two strategies:

1. Abort ALL Deadlocked Processes:
   • How it works: Immediately kills every single process involved in the deadlock cycle and reclaims all their resources.
   • Pros & Cons: Guaranteed to break the deadlock immediately, but it is very expensive—if a process had been calculating for 5 hours and was 99% complete, all of its work is thrown away and must be recomputed from scratch!
2. Abort ONE Process at a Time Until the Deadlock Cycle is Eliminated:
   • How it works: Kills one single victim process from the cycle, releases its resources, and re-runs the Deadlock Detection algorithm to check if the remaining processes can now finish. If still deadlocked, it aborts one more process.
   • Pros & Cons: Saves maximum work, but incurs high overhead because the detection algorithm must be invoked after every single termination!
   • Factors for Choosing Which Process to Kill First:
     • Priority of the process (kill low-priority process first).
     • How long the process has executed and how much time is left to finish.
     • Number of resources the process is currently holding.

Method 2: Resource Preemption (Taking Resources Away)

Instead of killing processes completely, the OS forcibly preempts (takes away) certain resources from one or more processes and gives them to other deadlocked processes until the deadlock cycle is broken!

When implementing Resource Preemption, the OS must handle 3 critical issues:

1. Selecting a Victim: Which process and which resources should be preempted? The OS chooses a “Victim” process that minimizes cost (based on the number of resources held and CPU time consumed so far).
2. Rollback: If we snatch a resource away from a running Victim process, that process cannot continue from its current state! We must roll back the process to a previously saved Safe Checkpoint and restart it from that state later (or do a total rollback and restart the process from the beginning).
3. Starvation (Ensuring the Same Victim Isn’t Picked Every Time): How do we ensure that the exact same process isn’t chosen as the Victim again and again every time a deadlock occurs?
   • Solution: Include the number of rollbacks in the cost factor so a process can only be chosen as a victim a finite number of times!

💡 Exam Preparation Tips for DAVV BCA

• “Explain Deadlock Detection and Recovery techniques in detail” is one of the most repeated 8-mark questions in Unit 3 of DAVV BCA exams!
• Always structure your Recovery answer clearly into Method 1: Process Termination (Abort all vs Abort one at a time) and Method 2: Resource Preemption (1. Selecting a Victim, 2. Rollback, 3. Starvation).