If a system has no deadlock prevention and no deadlock avoidance scheme, then it needs a deadlock detection scheme with recovery from deadlock capability. For this, information should be kept on the allocation of resources to processes, and on outstanding allocation requests. Then, an algorithm is needed which will determine whether the system has entered a deadlock state. This algorithm must be invoked periodically.
Deadlock Detection Algorithm (Shoshani and Coffman)
Data Structure is as:
Available [m]
Allocation [n,m] as in Banker’s Algorithm
Request [n,m] indicates the current requests of each process.
Let Work and Finish be vectors of length m and n, as in the safety algorithm.
The algorithm is as follows:
1. Initialize Work = Available
For i = 1 to n do
If Allocation(i) = 0 then Finish[i] = true else Finish[i] = false
2. Search an i such that
Finish[i] = false and Request(i) ≤ Work
If no such i can be found, go to step 4.
3. For that i found in step 2 do:
Work = Work + Allocation(i)
Finish[i] = true
Go to step 2.
4. If Finish[i] ≠ true for a some i then the system is in deadlock state else the system is safe
