187
A deadlock detection algorithm
nMakes use of previous resource-allocation matrices and
vectors
nMarks each process not deadlocked. Initially all processes are
unmarked. Then perform:
uMark each process j for which: A(j,i) = 0 for all resource type i.
(since these are not deadlocked)
uInitialize
work vector: W(i) = V(i) for all i
uREPEAT:
Find a unmarked process j such that Q(j,i) <= W(i) for all i. Stop if such
j does not exists.
uIf such j exists: mark process j and set W(i) = W(i)
+ A(j,i) for all i. Goto REPEAT
uAt
the end: each unmarked process is deadlocked