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:

 

1. Single Instance of Each Resource Type: 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 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² operations, where n is the number of vertices in the graph.

 

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

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:

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

2. Find an index i such that both
3. Finish[i] =false.
4. Request_i < Work.

If no such i exists, go to step 4.

3. Work := Work + Allocation_i

                       Finish[i] := true

go to step 2.

4. If Finish[i] = false, for some i, 1 < i < n, then the system is in a deadlock state.

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

This algorithm requires an order of m x n² operations to detect whether the system is in a deadlocked state.