Resource-Allocation Graph

• Deadlocks can be described more precisely 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_i$s and $R_i$s.
  • A directed edge from process $P_i$ to resource type $R_j$ is denoted by $P_i \rightarrow R_j$; it signifies that process $P_i$ has requested an instance of resource type $R_j$ and is currently waiting for that resource (request edge).
  • A directed edge from resource type $R_j$ to process $P_i$ is denoted by $R_j \rightarrow P_i$; it signifies that an instance of resource type $R_j$ has been allocated to process $P_i$ (assignment edge).
• Pictorially, each process $P_i$ is represented as a circle and each resource type $R_j$ as a rectangle.

  Figure 4: Resource allocation graphs. (a) Holding a resource. (b) Requesting a resource. (c) Deadlock.

  
• An arc from a resource node (square) to a process node (circle) means that the resource has previously been requested by, granted to, and is currently held by that process (see Fig. 4).
• Since resource type $R_j$ may have more than one instance, each such instance is represented as a dot within the rectangle.

  Figure 5: Left: Resource-allocation graph. Middle: Resource-allocation graph with a deadlock. Right: Resource-allocation graph with a cycle but no deadlock
• The resource-allocation graph shown in Fig. 5left depicts the following situation. The sets $P$, $R$, and $E$:
  • $P = \{P_1, P_2, P_3\}$
  • $P = \{R_1, R_2, R_3, R_4 \}$
  • $E = \{P_1 \rightarrow R_1, P_2 \rightarrow R_3, R_1 \rightarrow P_2, R_2 \rightarrow P_2, R_2 \rightarrow P_1, R_3 \rightarrow P_3\}$
• 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.
• A cycle in the graph is a necessary but not a sufficient condition for the existence of deadlock with resource types of several instances. A knot must exist; a cycle with no non-cycle outgoing path from any involved node
• Suppose that process $P_3$ requests an instance of resource type $R_2$. Since no resource instance is currently available, a request edge $P_3 \rightarrow R_2$ is is added to the graph (see Fig. 5middle).
• At this point, two minimal cycles exist in the system.
• Now consider the resource-allocation graph in Fig. 5right.
  • In this case, we also have a cycle. However, there is no deadlock.
  • Observe that process $P_4$ may release its instance of resource type $R_2$.
  • That resource can then be allocated to $P_3$ , breaking the cycle.
• In summary, if a resource-allocation graph does not have a cycle, then the system is not in a deadlocked state. If there is a cycle, then the system may or may not be in a deadlocked state.
• An example of resource allocation graphs (see Fig. 6);

  Figure 6: Resource Allocation Graphs. Lower; either $P_2$ or $P_4$ could relinquish (release) a resource allowing $P_1$ or $P_3$ (which are currently blocked) to continue.

  

  
• Another example of how resource graphs can be used; three processes, $A$, $B$, and $C$, and three resources $R$, $S$, and $T$ (see Fig. 7);.

  Figure 7: An example of how deadlock occurs and how it can be avoided.