Deadlock Detection and Recovery

If a system neither uses deadlock prevention nor a deadlock avoidance strategy then it might enter into a deadlock. Thus, it becomes important to use deadlock detection and recovery policy. A Deadlock detection algorithm, determines whether the system is in deadlock state or not? If yes, then the system uses a deadlock recovery method to break the deadlock.

1. Deadlock Detection

There are two deadlock detection methods depending upon the number of instances of each resource:
1. Single instance of each resource
2. Multiple instance of each resource

1.1 Single Instance of Each Resource: wait-for-graph

When there is a single instance of each resource the system can use wait-for-graph for deadlock detection. The key points about the wait-for-graph are:

1. Obtained from resource allocation graph
2. Remove the resource nodes – from the resource allocation graph remove the resource nodes
3. Collapse the corresponding edges

Working of wait-for-graph

An Edge from Pi to Pj means that process Pi is waiting for a resource held by process Pj. Now, if there are two edges Pi -> Rq and Rq -> Pj in resource allocation graph, for some resource Rq the collapse these into one single edge from Pi -> Pj to make the wait-for-graph. Finally, if there is a cycle in wait-for-graph, then the system is in deadlock else not.
For example, in the above figure, P2 is requesting R3 which is held by P5. Hence, we remove the resource R3 and collapse the edge between P2 and P5. wait-for-graph reflects this change. Similarly, the collapse of edges between P4 and P1 and all other processes is done.

1.2 Multiple Instance of Each Resource

This algorithm is similar to Banker’s Algorithm. It uses three data structures:

1. Available: A vector of length m indicates the number of available resources of each type.
2. Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process
3. Request: An n x m matrix indicates the current request of each process. For example, if Request [ij] = k, then process Pi is requesting k more instances of the resource type. Rj.

The algorithm is as below: (Refernce: Silberschatz, Abraham, et al. Operating system concepts. Edition-8. Reading: Addison-Wesley.)

1. Let Work and Finish be vectors of length m and n, respectively
Initialize:
(a) Work = Available
(b) For i = 1,2, …, n, if Allocationi ≠ 0, then
Finish[i] = false; otherwise, Finish[i] = true.
2. Find an index i such that both:
(a) Finish[i] == false
(b) Requesti <= Work
If no such i exists, go to step 4.
3. Work = Work + Allocationi
Finish[i] = true
go to step 2.
4. If Finish[i] == false, for some i, 1 <= i <= n, then the system is in deadlock state.
Moreover, if Finish[i] == false, then Pi is deadlocked.

Algorithm requires an order of O(m x n2) operations to detect whether the system is in deadlocked state.

Example of deadlock detection

Is the system in deadlocked state?
No. Safe sequence is <P0,P2,P3,P1,P4>
P0 request can be satisfied with the Available resources. Hence, the first process in safe sequence is P0.
Next, update the Available using
Available=Available + Allocation of P0
So, the new Available is <0,1,0>
The next process whose Request can be satisfied with updated Available is P2. So, the updated safe frequencies is <P0,P2>
Available=Available + Allocation of P2
So, the new Available is <3,1,3>
Next, in the same manner find a process whose request can be satisfied. So, the final sequence is <P0,P2,P3,P1,P4>

Note: There can be multiple safe-sequence. As long as there is one safe-sequence, the system is not in deadlock state.

2. When to invoke detection algorithm?

1. Every time a process requests for a resource
   • Advantages
     • It is easy to identify the processes involved in the deadlock
     • Also, the process which caused the deadlock is known. This is possible because the system invokes the algorithm after each request.
   • Disadvantage
     • Overhead in computation time
2. After fixed-interval of time
   • Disadvantage
     • Can not tell which process caused the deadlock

3. Deadlock Recover

If a deadlock is detected in the system, the next step is to recover from it. There are two methods to do so:
1. Process termination
2. Preempt resources from some of the deadlocked processes

3.1 Process Termination

1. Terminate all the deadlocked processes.
2. Terminate processes one by one until the deadlock is broken. However, the issue is to decide which process to terminate. Certain factors that can be used are:
   • How long the process has computed?
   • How much the process has finished its working?
   • What is the priority of the process?
   • How many resources are being used by the process?
   • How many total processes will be required to be terminated?

3.2 Resource preemption

In resource preemption some resources are preempted from certain processes and these resources can then be allocated to other process. But, certain issues that should be addressed are:

1. Select a victim – which process to select for preempting the resources.
2. Rollback – the process whose resources are preempted, can not continue execution. So, a process
   • must be rolled back to some safe state.
   • Or abort the process and restart
3. Starvation – it must be ensured that the same process does not get selected for resource preemption, as this will lead to starvation.

Previous                                   Next
Banker's Algorithm                Memory Management