Deadlock refers to a situation in an operating system in which one process is waiting for a resource that is currently under the control of some other process. This may result in the permanent blocking of the processes. The entry of deadlock in the operating system can be avoided by the deadlock prevention and avoidance technique.
If either of the above two techniques is not applied then a deadlock may occur and a system must provide,
- An algorithm that can monitor the state of the system to detect the occurrence of a deadlock.
- A recovery algorithm to regain from the deadlocks state.
This can be done by implementing various deadlock detection and recovery techniques.
Deadlock Detection in a System Containing a Single Instance of Each Resource Type :
A deadlock detection algorithm that makes use of a variant of the resource allocation graph, called the Wait-For graph is defined for a system containing only a single instance for all the resources.
An edge from a process Pi to process Pj exists in a wait-for graph, if and only if, the corresponding resource allocation graph contains two edges, one from process Pi to some resource Ra and the other from the resource Ra to process Pj. This indicates that process Pi is waiting for a resource that is in use by the process Pj.
The presence of a cycle in the wait-for graph indicates the existence of a deadlock. An algorithm that is used to detect a cycle in the graph requires a total of n2 operations, where n is the number of vertices in the graph.
Example :
Consider five processes P1, P2, P3, P4, and P5, and five resources R1 to R5. The Resource Allocation Graph (RAG) for such a system is shown in the below figure.
Deadlock Detection in a System Containing Multiple Instance of a Resource Type :
The wait-for graph can’t be used for a resource allocation system containing multiple instances of each resource type. Hence, a different algorithm is employed which carries certain data structures. The data structures in the algorithm are,
- Available – It is a vector of length ‘m’ that can specify the number of resources of each type that are available.
- Allocation – It is an ‘n × m’ matrix that is used to define the number of resources of each type presently assigned to each process in a system.
- Request – It is an ‘n × m’ matrix which specifies the current request made by each process.
If Request [i, j] = k, then process ‘i’ is currently requesting for ‘k’ additional instances of resource ‘j’. The deadlock detection algorithm for every possible resource allocation sequence is given by considering two vectors work and finish whose lengths are ‘m’ and ‘n’ respectively.
- Initialize Work = Available.
- Determine allocation for each ‘i’, where i = 1, 2,…n. If allocation i ≠0 then set Finish[i] to false else, Finish [i] is assigned a value true.
- Determine an index ‘i’ for which both Finish[i] = false and Request i ≤ Work. If no such ‘i’ value is available then jump directly to step 5.
- Set Work = Work + Allocation and Finish[i] = true and iterate through step 2.
- If Finish[i] false, for some i, 1 ≤ i ≤ n then the system is in a deadlock state, and the process Pi is deadlocked.
Hence, m × n2 operations are required to determine whether the system is in a deadlocked state.
Usage of Deadlock Detection Algorithm :
The usage of deadlock detection algorithm depends on the following factors,
- Frequent occurrence of deadlocks,
- Effects of deadlock on other processes.
The invocation of the deadlock detection algorithm highly depends on how frequently deadlocks occur. In case the deadlocks occur frequently, algorithm must be used as frequently as their occurrence. This is done because when a process is affected by deadlock all its allocated resources can not be released and hence, can not be used by other processes. In addition to this, it is possible the processes in the ready queue might increase.
In the second case, the detection algorithm is used every time a process is requested for a resource and it is not allowed immediately. By implementing this, it is possible to grab the process with which a deadlock occurred and the set of processes associated with it. However, using the algorithm on every process request takes a lot of time for computing overall processes.
One method to overcome the above drawback is to use the detection algorithm on certain regular custom time intervals (for example, every 30 minutes). However, with this method, it is difficult to identify the process with which a deadlock occurred. This is because, within that time interval, the resource graph might carry many deadlock cycles.
The deadlock detection algorithm only finds a process whose requests for the resources can be satisfied with the available resources and it is assumed that those resources are allocated to it and the process completes its execution thereby releasing all its resources. Another process is then looked up by the algorithm and the whole process is repeated. This algorithm does not assure deadlock prevention but instead, it determines the existence of deadlock.
Deadlock Recovery :
When a deadlock has been detected in the system by deadlock detection algorithms, then it has to be recovered by using some recovery mechanism. The brute force approach is to reboot the computer, but it is inefficient because it may lose complete data and waste computing time. Hence, other techniques are used to recover from deadlock. They are broadly classified into two types. They are,