Deadlock Detection Algorithm

A deadlock detection algorithm examines the state of the system to determine whether deadlock has occurred or not.

There are two algorithms for deadlock detection. The first algorithm deals with the case where there is only one instance of each resource type and other algorithm deals with the situation where there are multiple instances of each resource type.

Deadlock detection algorithm for single instance of each resource type

This algorithm uses a type of resource allocation graph called wait-for graph.

Wait-for graph consists of the nodes or vertices that represent various processes. The wait-for graph has following features :

1. It represents the processes as nodes (circles).
2. An edge from process Pi to process Pj means that a process Pi is waiting for the resource that is held by process Pj.
3. Wait-for graph can be generated from resource allocation graph by removing the nodes that represents the resource (i.e. nodes represented as square) and collapsing the appropriate edges.
4.  An edge Pi → Pj exists in wait for graph if the corresponding resource allocation  graph contains two edges Pi → Rq and Rq → Pj for some resource Rq.
5. After generating a wait for graph, thus algorithm examines it for the existence of cycles.
6. Thus, a deadlock exists in the system if and only if wait for graph contains a cycle.
7. Complexity of algorithm, which detects cycle in a graph, will be n², where n is the number of nodes in the graph.

Deadlock detection algorithm for a multiple instances of each resource type

The wait-for graph cannot be used to detect deadlock in system that has multiple instances of each resource type. This algorithm is almost the same as safety part of the banker’s algorithm with few semantic differences.

It uses almost the same data structures as Banker’s algorithm.

The various steps followed in this algorithm are:

Here number of processes are n and number of resources are m

1. If Allocation [i, j] ≠ 0 then

Set finish [i] false;

Else

Set finish [i] = true;

for all processes i =1 to n

for all resources j= 1 to m

2. Find a process i such that both conditions

Finish [i] = false

And Request [i, j]<= Available [j]

(This means that request of process i for all resources j should be less than the available amount of resources j)

if no such i exists go to step 4

3. Set Available [j] = Available[j] + Allocation [i, jl

Set finish [i] = true;

Go to step 2

4. If finish [i] = false, for some process, then the system is in deadlock state. The process i for which finish [i] = false, is deadlocked.