Page 136 - DCAP103_Principle of operating system

Unit 4: Process Management-III

Process States Notes
• Process PI is holding an instance of resource type R2, and is waiting for an instance of
resource type R1.
• Process P2 is holding an instance of R1 and R2, and is waiting for an instance of resource
type R3.
• Process P3 is holding an instance of R3.

Given the definition of a resource-allocation graph, it can be shown that, if the graph contains
no cycles, then no process in the system is deadlocked. If the graph does contain a cycle, then
a deadlock may exist. If each resource type has exactly one instance, then a cycle implies that a
deadlock has occurred. If the cycle involves only a set of resource types, each of which has only
a single instance, then a deadlock has occurred. Each process involved in the cycle is deadlocked.
In this case, a cycle in the graph is both a necessary and a sufficient condition for the existence
of deadlock. If each resource type has several instances, then a cycle does not necessarily imply
that a deadlock has occurred. In this case, a cycle in the graph is a necessary but not a sufficient
condition for the existence of deadlock. To illustrate this concept, let us return to the resource-
allocation graph depicted. Suppose that process P3 requests an instance of resource type R2.
Since no resource instance is currently available, a request edge P3 -+ RL is added to the graph.
At this point, two minimal cycles exist in the system:
P → R → P → R → P → R → P 1
3
2
2
3
1
1
P → R → P → R → P 2
2
3
2
3
Figure 4.11: Resource-Allocation Graph with a Deadlock

LOVELY PROFESSIONAL UNIVERSITY 129