Resource Allocation Graph in OS - Vertices, Edges, Deadlocks
What is a Resource allocation graph?
Resource allocation graph is a directed graph used to indicate how the current set of system resources are allocated to each of the process in software applications.
What is a system resource? A Resource can be:
- a CPU,
- location in memory (RAM),
- location in Cache memory,
- file handle in storage (internal or external hard disk, USB storage),
- I/O device such as keyboard or printer,
- or a network socket
Locations in memory can be contiguous or non-contiguous. Contiguous refers to consecutive neighbour locations.
What is the purpose of a resource allocation graph?
Resource allocation graph is a directed graph that is used to describe a deadlock in operating system more clearly. If the resource allocation graph contains a cycle, then the deadlock may or may not occur. If the graph does not contain a cycle, then there is no deadlock.
Resource states
Resource allocation graph is a directed graph used to represent the set of processes in a software and resources required by the processes. Resources can be:
- already assigned to a process,
- reqested by the process for assignment
- waiting for it to be requested by the process for assignment
Resource allocation graph - Vertices and Edges
Resource allocation graph consists of set of vertices V and set of edges E. The Vertices V is divided into two sets:
- set of all processes in the system
P = {P1, P2, P3...Pn}and - set of all resource types in the system
R = {R1, R2, R3...Rm}
Request edge & Assignment edge
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.
Let us 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}
Let us conside that each Resource has instances as mentioned below:
- R1 has 2 instances
- R2 has 1 instance
- R3 has 1 instance
- R4 has 2 instances
For the processes P1, P2 and P3 and for the resources R1, R2, R3 and R4 considered above, resource allocation graph can be drawn as shown below:
In the above 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 above graph (Fig 1), there is no cycle. So, deadlock cannot occur. Suppose, we assume the Process P3 is going to request an instance of resource type R1 and we add the request edge to the graph. At present, there is no instance available in the system. Hence, two cycle may exist.(Fig 2.)
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.
