**DEADLOCK DETECTION**

Deadlock detection, If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm, then a deadlock situation may occur. In this environment, the system must provide:

- An algorithm that examines the state of the system to determine whether a deadlock has occurred.
- An algorithm to recover from the deadlock.

According to a number of instances in each resource type, the Deadlock Detection algorithm can be classified into two categories as follows:

If all resources have only a single instance, then it can define a deadlock detection algorithm that uses a variant of the resource-allocation graph (is called a__Single Instance of Each Resource Type:__*wait-for*graph). A wait–for the graph can be draw by removing the nodes of type resource and collapsing the appropriate edges from the resource-allocation graph.

An edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj to release a resource that Pi 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 some resource Rq. For Example:

((a) Resource-allocation graph. (b) Corresponding wait-for graph)

A deadlock exists in the system if and only if the wait-for graph contains a cycle. To detect deadlocks, the system needs to maintain the wait-for graph and periodically to invoke an algorithm that searches for a cycle in the graph. An algorithm to detect a cycle in a graph requires an order of n^{2 }operations, where *n *is the number of vertices in the graph.

The following deadlock-detection algorithm is applicable to several instance of a resource type. The algorithm employs several time-varying data structures:__Several Instances of a Resource Type:__

**Available:** **A **vector of length m indicates the number of available resources of each type.

**Allocation:** An n x m matrix defines the number of resources of each type currently allocated to each process.

**Request:** An n x m matrix indicates the current request of each process. If Request[i,j] = k, then process *Pi *is requesting *k *more instances of resource type Rj*.*

The detection algorithm is described as follows:

- Let
*Work*and*Finish*be vectors of length*m*and*n,*

Initialize, Work := Available*. *For *i *= 1, 2, …, *n,*

* *if *Allocation _{i} *!= 0, then

*Finish[i] :=false;*otherwise,

*Finish[i]*:=

*true.*

- Find an index
*i*such that both *Finish[i] =false.**Request*_{i}__<__Work.

If no such *i *exists, go to step 4.

*Work*:=*Work*+*Allocation*_{i}

* Finish[i] *:= *true*

go to step 2.

- If
*Finish[i]*= false, for some*i,*1__<__*i*then the system is in a deadlock state.__<__n,

if *Finish[i] =false, *then process *Pi *is deadlocked.

This algorithm requires an order of *m *x *n ^{2 }*operations to detect whether the system is in a deadlocked state.