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 P_i to process P_j exists in a wait-for graph, if and only if, the corresponding resource allocation graph contains two edges, one from process P_i to some resource R_a and the other from the resource R_a to process P_j. This indicates that process P_i is waiting for a resource that is in use by the process P_j.

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 n² operations, where n is the number of vertices in the graph.

Example :

Consider five processes P₁, P₂, P₃, P₄, and P₅, and five resources R₁ to R₅. 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 P_i is deadlocked.

Hence, m × n² 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,

• Process Termination
• Resource Preemption.

Process Termination :

Here one or more processes are terminated to eliminate deadlock. It has two methods as follows,

• Terminate all deadlocked processes which will break deadlock immediately, but it is a bit expensive because there may be some processes that have been executing for a long time consuming considerable CPU time and their termination will result in wasting those CPU cycles.
• In order to overcome the drawback of the above method, this method terminates one process at a time until the deadlock is recovered. However, it has some overhead since, after terminating each process, a detection algorithm has to be executed for deciding to further terminate the processes or not. This method is slower than the first one.

Resource Preemption :

In this method, resources are deallocated or preempted from some processes, and the same is allocated to others until the deadlock is resolved. We have three important issues to implement this scheme. They are,

• Selection of Victim Process – We need to decide which process or resource is to be preempted, the decision is based on cost factor which includes the number of resources, a deadlocked process is holding and CPU time consumed by it, etc.
• Rollback – The process which was preempted cannot continue normal execution, because its resources are taken back. Hence, we need to roll back to some previous checkpoint or total rollback to start it from the beginning.
• Starvation – We should ensure that a particular process should not starve every time preemption is done.