# DEADLOCK DETECTION

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

I really like your blog.. very nice colors& theme. Did you make this website yourself or did you hire someone to do it for you? Plz reply as I’m looking to design my own blog and would like to find out where u got this from.

Yes, I design it myself.