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.
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
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:
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.
This algorithm is similar to Banker’s Algorithm. It uses three data structures:
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.
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.
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
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:
Note: Click within the slide area for animations. Clicking on the “next” slide button will not display any animation
Previous Next Banker's Algorithm Memory Management