# Resource-Allocation Graph

Deadlocks can be described in terms of a directed graph called a system resource-allocation graph.

This graph consists of a set of vertices V and a set of edges E. The set of vertices V is partitioned into two different types of nodes P = {PI, P2, …, Pn}, the set consisting of all the active processes in the system, and R = {R1, R2, …, Rm}, the set consisting of all resource types in the system.

A directed edge from process Pi to resource type Rj is denoted by PiàRj; it signifies that process Pi requested an instance of resource type Rj and is currently waiting for that resource. A directed edge Pi -> Rj is called a request edge.

A directed edge from resource type Rj to process Pi is denoted by RjàPi; it signifies that an instance of resource type Rj has been allocated to process Pi. A directed edge RjàPi is called an assignment edge.

Pictorially, we represent each process Pi as a circle and each resource type Rj as a square. Since resource type Rj may have more than one instance, we represent each such instance as a dot within the square. A request edge points to only the square Rj, whereas an assignment edge must designate one of the dots in the square. The resource-allocation graph shown below depicts the following situation.

The sets P, R, and E:

P={P1,P2,P3}

R={R1,R2,R3,R4}

E={P1®R1, P2®R3, R1®P2, R2®P2, R2®P1, R3®P3}

Resource instances:

• One instance of resource type R1
• Two instances of resource type R2
• One instance of resource type R3
• Three instances of resource type R4

Process states:

• 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. ### Example of a Resource Allocation Graph

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 the 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 the deadlock.

To illustrate this concept, let us return to the resource-allocation graph depicted in Figure. Suppose that process P3 requests an instance of resource type R2. Since no resource instance is currently available, a request edge P3® R2 is added to the graph. At this point, two minimal cycles exist in the system: P1®R1® P2® R3® P3® R2® P1

P2® R3 ® P3® R2® P2

Processes PI, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is held by process P3. Process P3, on the other hand, is waiting for either process PI or process P2 to release resource R2. In addition, process PI is waiting for process P2 to release resource R1.