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

Try Now – Operating Systems MCQs

Practice Now – Operating System Online Test