Operating System - Resource Allocation Graph


Next >>

Resource allocation graph is a directed graph that is used to describe the deadlock more clearly. If the resource allocation graph contains a cycle, then the deadlock may occur. If the graph does not contain a cycle, then there is no deadlock.

The graph consists of set of vertices V and set of edges E. The Vertices V is divided into two form: set of all process in the system        P = {P1, P2, P3...Pn} and set of all resource types in the system R = {R1, R2, R3...Rm}

  • P→Rj -----indicates that process P has requested an instance of resource type Rj and is waiting for that.This directed edge is called request edge.
  • Rj→P -----indicates that an resource instance Rj has been allocated to the process Pi. This edge is called assignment edge.

When the process pi requests the instance of resource type Rj, then request edge is added into the graph. Suppose that request can be fulfilled, then this request edge is instantaneously transformed into assignment edge. Once the process has completed their task, it releases the resource instance and delete the assignment edge.

Lets consider the sets P,R and £ :

  • P = {P1, P2, P3}
  • R = {R1, R2, R3, R4}
  • £ = {P1→R2, R2→P2, P2→R3, R3→P3, R1→P1, R1→P2}

Resource instances:

  • R1 has two instances
  • R2 has one instance
  • R3 has one instance
  • R4 has two instance
Fig 1.Resource allocation Graph Function

Process state:

  • P1 is holding an instance of resource type R1 and waiting for an instance R2.
  • P2 is holding and instance of resource type R1, R2 and waiting for an instance R3.
  • P3 is holding instance of resource type R3.

In the given graph(Fig 1.), there is no cycle so that the deadlock can not be occurred. Suppose, we assume that the Process P3 is going to request an instance of resource type R1 and add the request edge to the graph. At present there is no instance available in the system because of that two cycle may exist.(Fig 2.)

Fig 2.Resource allocation Graph with deadlock

The Two cycles are:

  • P1→R2→P2→R3→P3→R1→P1
  • P2→R3→P3→R1→P2

Now all the three processes are deadlocked. In short, If the resource allocation graph contains no cycle, then there is no deadlock. If it contains a cycle, the deadlock may exist.


Next >>