Page 145 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes A deadlock exists in the system if and only if the wait-for graph contains a
cycle. To detect deadlocks, the system needs to maintain the wait-for graph
and periodically to invoke an algorithm that searches for a cycle in the graph.

An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the
number of vertices in the graph.

Figure 4.14: (a) Resource-Allocation Graph and (b) Corresponding Wait-for Graph

4.6.17 Several Instances of a Resource Type

The wait-for graph scheme is not applicable to a resource-allocation system with multiple
instances of each resource type. The deadlock-detection algorithm that we describe next is
applicable to such a system. The algorithm employs several time-varying data structures that
are similar to those used in the banker’s algorithm.

Available: A vector of length rn indicates the number of available resources of each type.
Allocation: An n x rn matrix defines the number of resources of each type currently allocated
to each process.
Request: An n x rn matrix indicates the current request of each process. If Request[i,j] = k,
then process Pi is requesting k more instances of resource type Ri. The 5 relation between two
vectors is defined. To simplify notation, we shall again treat the rows in the matrices Allocation
and Request as vectors, and shall refer to them as Allocationi and Requesti, respectively. The
detection algorithm described here simply investigates every possible allocation sequence for
the processes that remain to be completed. Compare this algorithm with the banker’s algorithm.
1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work := Available. For

i = 1, 2, ..., n, if Allocation $0, then Finish[i] :=false;

138 LOVELY PROFESSIONAL UNIVERSITY