Write an algorithm for deadlock detection.

An algorithm for deadlock detection:

1. Assume that Work and Finish be vectors of length m and n, correspondingly.

Initialize:

(a) Work = Available

(b) For i = 1,2, ..., n, if Allocation i ¹≠  0, then

Finish[i] = false; otherwise, Finish[i] = true.

2. Determine an index i such as both:

(a) Finish[i] == false

i.  (b)  Requesti ≤  Work

If no such i exists, go to step 4.

3.  Work = Work + Allocationi

Finish[i] = true go to step 2.

4. If Finish[i] == false, for some i, 1 ≤  i ≤  n, then the system is in deadlock state. Furthermore, if Finish[i] == false, then Pi is deadlocked.