# Deadlock Detection and Recovery in Operating System (OS)

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.

## 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,

### 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.