Page 144 - DCAP103_Principle of operating system

Unit 4: Process Management-III

We claim that the system is currently in a safe state. Indeed, the sequence Notes
<PI, P3/ P4, P2/ Po> satisfies the safety criteria. Suppose now that process
PI requests one additional instance of resource type A and two instances
of resource type C, so Requestl = (1,0,2). To decide whether this request
can be immediately granted, we first check that Requestl 5 Available (that
is, (1,0,2) 5 (3,3,2)), which is true. We then pretend that this request has
been fulfilled, and we arrive at the following new state:

Allocation Need Available
A B C A B C A B C
P 0 0 1 0 7 4 3 2 3 0
P 1 3 0 2 0 2 0
P 2 3 0 2 6 0 0
P 3 2 1 1 0 1 1
P 4 0 0 2 4 3 1

We must determine whether this new system state is safe. To do so, we
execute our safety algorithm and find that the sequence <PI, P3, P4, POI
P2> satisfies our safety requirement. Hence, we can immediately grant
the request of process PI. You should be able to see, however, that when
the system is in ths state, a request for (3,3,0) by P4 cannot be granted,
since the resources are not available. A request for (0,2,0) by Po cannot
be granted, even though the resources are available, since the resulting
state is unsafe.

4.6.15 Deadlock Detection

If a system does not employ either a deadlock-prevention or a deadlock-avoidance algorithm,
then a deadlock situation may occur. In this environment, the system must provide: An
algorithm that examines the state of the system to determine whether a deadlock has occurred.
An algorithm to recover from the deadlock. In the following discussion, we elaborate on these
two requirements as they pertain to systems with only a single instance of each resource type,
as well as to systems with several instances of each resource type. At this point, however, let us
note that a detection-and-recovery scheme requires overhead that includes not only the run-time
costs of maintaining the necessary information and executing the detection algorithm, but also
the potential losses inherent in recovering from a deadlock.
4.6.16 Single Instance of Each Resource Type

If all resources have only a single instance, then we can define a deadlock detection algorithm
that uses a variant of the resource-allocation graph, called a wait-for graph. We obtain this graph
from the resource-allocation graph by removing the nodes of type resource and collapsing the
appropriate edges. More precisely, an edge from Pi to Pi in a wait-for graph implies that process
Pi is waiting for process Pi to release a resource that Pi needs. An edge Pi -t Pi exists in a wait-
for graph if and only if the corresponding resource allocation graph contains two edges Pi -+
Rq and Rq + Pj for some resource Rq. For example, we present a resource-allocation graph and
the corresponding wait-for graph.

LOVELY PROFESSIONAL UNIVERSITY 137