Deadlock Detection and Recovery in OS
In this tutorial, we will be covering the concepts of Deadlock detection and recovery.
If a system does not employ either a deadlock-prevention or deadlock-avoidance algorithm, then there are chances of occurrence of a deadlock.
In this case, the system may provide two things:
Thus order to get rid of deadlocks the operating system periodically checks the system for any deadlock. After Finding the deadlock the operating system will recover from it using recovery techniques.
Now, the main task of the operating system is to detect the deadlocks and this is done with the help of Resource Allocation Graph.
Single Instance of Each Resource Type
If all the resources have only a single instance, then a deadlock-detection algorithm can be defined that mainly uses the variant of the resource-allocation graph and is known as a wait-for graph. This wait-for graph is obtained from the resource-allocation graph by removing its resource nodes and collapsing its appropriate edges.
An edge from Pi to Pj in a wait-for graph simply implies that process Pi is basically waiting for process Pj in order to release a resource that it needs. An edge Pi, Pj exists in a wait-for graph if and only if the corresponding resource allocation graph contains two edges Pi,Rq and Rq,Pj for a resource Rq.
A deadlock exists in the system if and only if there is a cycle in the wait-for graph. In order to detect the deadlock, the system needs to maintain the wait-for graph and periodically system invokes an algorithm that searches for the cycle in the wait-for graph.
The algorithm that is used to detect the cycle in the graph mainly requires n² operations; where n indicates the number of vertices in the graph.
Multiple Instances of Each Resource Type
The above scheme that is a wait-for graph is not applicable to the resource-allocation system having multiple instances of each resource type. Now we will move towards a deadlock detection algorithm that is is applicable for such systems.
This algorithm mainly uses several time-varying data structures that are similar to those used in Banker's Algorithm and these are as follows:
1. Available
It is an array of length m. It represents the number of available resources of each type.
2. Allocation
It is an n x m matrix which represents the number of resources of each type currently allocated to each process.
3. Request
It is an n*m matrix that is used to indicate the request of each process; if Request[i][j] equals to k, then process Pi is requesting k more instances of resource type Ri.
Allocation and Request are taken as vectors and referred to as Allocation and Request. The Given detection algorithm is simply used to investigate every possible allocation sequence for the processes that remain to be completed.
1.Let Work and Finish be vectors of length m and n, respectively. Initialize:
Work = Available
Finish[i] =false for i = 0, 1, ... , n - 1.
If Allocationi is not equal to 0,then Finish[i] = false; else Finish[i] = true
2.Find an index i such that both
Finish[i] ==false
Requesti <= Work
If no such i exist then go to step 4.
3.Perform the following:
Work = Work + Allocationi
Finish[i] = true
Go to step 2.
4. If If Finish[i] == false for some i, 0<=i<n, then it means the system is in a deadlocked state.
Moreover,if Finish[i]==false,then process Pi is deadlocked.
This algorithm may require an order of mxn² operations in order to determine whether the system is in a deadlocked state.
Recovery From Deadlock
When a detection algorithm determines that a deadlock exists then there are several available alternatives. There one possibility and that is to inform the operator about the deadlock and let him deal with this problem manually.
Another possibility is to let the system recover from the deadlock automatically. These are two options that are mainly used to break the deadlock.
Now we will cover Process Termination and Resource Preemption
Process Termination
In order to eliminate deadlock by aborting the process, we will use one of two methods given below. In both methods, the system reclaims all resources that are allocated to the terminated processes.
-
Aborting all deadlocked Processes
Clearly, this method is helpful in breaking the cycle of deadlock, but this is an expensive approach. This approach is not suggestable but can be used if the problem becomes very serious. If all the processes are killed then there may occur insufficiency in the system and all processes will execute again from starting.
-
Abort one process at a time until the elimination of the deadlock cycle
This method can be used but we have to decide which process to kill and this method incurs considerable overhead. The process that has done the least amount of work is killed by the Operating system firstly.
Resource Preemption
In order to eliminate the deadlock by using resource preemption, we will successively preempt some resources from processes and will give these resources to some other processes until the deadlock cycle is broken and there is a possibility that the system will recover from deadlock. But there are chances that the system goes into starvation.
