Methods for Handling Deadlocks: Deadlock Detection

 

Deadlock Detection:

 

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

 

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

2.    An algorithm to recover from the deadlock.

 

 

Single Instance of Each Resource Type:

 

If all resources have only single instance, then we can define a deadlock detection algorithm that uses a variant of the resource allocation graph called wait-for graph.

 

We obtain this graph from the resource allocation graph by removing the nodes of type resource and collapsing the appropriate edges.

 

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.

Several Instances of a Resource Type:

 

The wait-for graph scheme is not applicable to a resource allocation system with multiple instances of each resource type.

 

The deadlock detection algorithm described next is applicable to such a system. Algorithm has the following data structures:

 

1.    Available: a vector of length ‘m’ indicates the number of available resources of each type.

 

2.    Allocation: ‘nxm’ matrix defines the number of resources of each type currently allocated to each process.

 

3.    Request: ‘nxm’ matrix indicates the current request of each process. If Request [i,j]=k, then process P_i  requesting ‘k’ more instances of resource type R_j.