Page 141 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes
Maximum Needs Current Needs
P0 10 5
P1 4 2

P2 9 2

At time t0, the system is in a safe state. The sequence <PI, PO, P2> satisfies the safety condition,
since process PI can immediately be allocated all its tape drives and then return them (the system
will then have 5 available tape drives), then process Po can get all its tape drives and return
them (the system will then have 10 available tape drives), and finally process P2 could get all its
tape drives and return them (the system will then have all 12 tape drives available). A system
may go from a safe state to an unsafe state. Suppose that, at time t1, process Pp requests and is
allocated 1 more tape drive. The system is no longer in a safe state. At this point, only process PI
can be allocated all its tape drives. When it returns them, the system will have only 4 available
tape drives. Since process Po is allocated 5 tape drives, but has a maximum of 10, it may then
request 5 more tape drives. Since they are unavailable, process Po must wait. Similarly, process
P2 may request an additional 6 tape drives and have to wait, resulting in a deadlock. Our mistake
was in granting the request from process P2 for 1 more tape drive. If we had made P2 wait
until either of the other processes had finished and released its resources, then we could have
avoided the deadlock. Given the concept of a safe state, we can define avoidance algorithms
that ensure that the system will never deadlock. The idea is simply to ensure that the system
will always remain in a safe state. Initially, the system is in a safe state. Whenever a process
requests a resource that is currently available, the system must decide whether the resource can
be allocated immediately or whether the process must wait. The request is granted only if the
allocation leaves the system in a safe state. In this scheme, if a process requests a resource that
is currently available, it may still have to wait. Thus, resource utilization may be lower than it
would be without a deadlock-avoidance algorithm.

4.6.12 Resource-Allocation Graph Algorithm

If we have a resource-allocation system with only one instance of each resource type, a variant
of the resource-allocation graph can be used for deadlock avoidance. In addition to the request
and assignment edges, we introduce a new type of edge, called a claim edge. A claim edge Pi
-+ Rj indicates that process Pi may request resource Rj at some time in the future. This edge
resembles a request edge in direction, but is represented by a dashed line. When process Pi
requests resource Rj, the claim edge Pi -+ Rj is converted to a request edge. Similarly, when a
resource Rj is released by Pi, the assignment edge Rj -+ Pi is reconverted to a claim edge Pi -+
Xi. We note that the resources must be claimed a priori in the system. That is, before process
Pi starts executing, all its claim edges must already appear in the resource-allocation graph.
We can relax this condition by allowing a claim edge Pi + Rj to be added to the graph only
if all the edges associated with process Pi are claim edges. Suppose that process Pi requests
resource Rj. The request can be granted only if converting the request edge Pi -+ Rj to an
assignment edge Rj + Pi does not result in the formation of a cycle in the resource-allocation
graph. Note that we check for safety by using a cycle-detection algorithm. An algorithm for
detecting a cycle in this graph requires an order of n2 operations, where n is the number of
processes in the system.

134 LOVELY PROFESSIONAL UNIVERSITY