Deadlock detection is the process of actually determining that a deadlock exists and identifying the processes and resources involved in the deadlock. The basic idea is to check allocation against resource availability for all possible allocation sequences to determine if the system is in deadlocked state a. Of course, the deadlock detection algorithm is only half of this strategy. Once a deadlock is detected, there needs to be a way to recover several alternatives exists:

Temporarily prevent resources from deadlocked processes. Back off a process to some check point allowing preemption of a needed resource and restarting the process at the checkpoint later. Successively kill processes until the system is deadlock free. These methods are expensive in the sense that each iteration calls the detection algorithm until the system proves to be deadlock free. The complexity of algorithm is O(N2) where N is the number of proceeds. Another potential problem is starvation; same process killed repeatedly.

1. If resources have single instance:

In this case for Deadlock detection we can run an algorithm to check for cycle in the Resource Allocation Graph. Presence of cycle in the graph is the sufficient condition for deadlock.

In the above diagram, resource 1 and resource 2 have single instances. There is a cycle R1–>P1–>R2–>P2. So Deadlock is Confirmed.

2. If there are multiple instances of resources:

Detection of cycle is necessary but not sufficient condition for deadlock detection, in this case system may or may not be in deadlock varies according to different situations.

A) Let W be an integer array of length m,initialized to array A(Available number of resources)

Let F be a boolean array of length n,initialized to false(determines if process is finished or not)

For all i,if C[i] !=0,then F[i]= False; otherwise F[i]=true.

B) Find an i such that both

F[i] == false // Pi is currently not involved in a deadlock

R[i] <= W

If no such i exists, go to step D

C) // reclaim the resources of process Pi

W = W+C[i]; F[i] = true; go to step B

D) If F[i]== false for some i,

then the system is in a deadlock state. Moreover ,if F[i]==false then Process Pi is deadlocked. Detection algorithm is invoked in following two cases

Extreme : Invoke the algorithm every time a request is denied.

Alternative: Invoke the algorithm at less frequent time intervals.