Resource Allocation Graph in Operating System
In this tutorial, we will be covering the Resource Allocation Graph in the operating system.
In order to describe deadlocks in a more precise way directed graphs are used that are called system Resource Allocation Graph.
-
This Graph acts as the pictorial representation of the state of the system.
-
The Resource Allocation graph mainly consists of a set of vertices V and a set of Edges E.
-
This graph mainly contains all the information related to the processes that are holding some resources and also contains the information of the processes that are waiting for some more resources in the system.
-
Also, this graph contains all the information that is related to all the instances of the resources which means the information about available resources and the resources which are being used by the process
-
In this graph, the circle is used to represent the process, and the rectangle is used to represent the resource.
Let us now discuss the components of the Resource Allocation Graph(RAG).
Components of Resource Allocation Graph
Given below are the components of RAG:
-
Vertices
-
Edges
1.Vertices
There is two kinds of vertices used in the resource allocation graph and these are:
-
Process Vertices
-
Resource Vertices
Process Vertices
These vertices are used in order to represent process vertices. The circle is used in order to draw the process vertices and the name of the process is mentioned inside the circle.
Resource Vertices
These vertices are used in order to represent resource vertices. The rectangle is used in order to draw the resource vertices and we use dots inside the circle to mention the number of instances of that resource.
In the system, there may exist a number of instances and according to them, there are two types of resource vertices and these are single instances and multiple instances.
Single Instance
In a single instance resource type, there is a single dot inside the box. The single dot mainly indicates that there is one instance of the resource.
Multiple Instance
In multiple instance resource types, there are multiple dots inside the box, and these Multiple dots indicate that there are multiple instances of the resources.
2. Edges
In the Resource Allocation Graph, Edges are further categorized into two:
1. Assign Edges
Assign Edges are mainly used to represent the allocation of resources to the process. We can draw assign edges with the help of an arrow in which mainly the arrowhead points to the process, and the process mainly tail points to the instance of the resource.
In the above Figure, the resource is assigned to the process
2. Request Edges
Request Edge is mainly used to signify the waiting state of the process. Likewise in assigned edge, an arrow is used to draw an arrow edge. But Here the arrowhead points to the instance of a resource, and the tail of the process points to the process.
In the above figure, the process is requesting a resource
Single Instance RAG Example
Suppose there are Four Processes P1, P2, P3, P4, and two resources R1 and R2, where P1 is holding R1 and P2 is holding R2, P3 is waiting for R1 and R2 while P4 is waiting for resource R1.
In the above example, there is no circular dependency so there are no chances for the occurrence of deadlock.
Thus having cycled in single-instance resource type must be the sufficient condition for deadlock.
Multiple Instance RAG Example
Suppose there are four processes P1, P2, P3, P4 and there are two instances of resource R1 and two instances of resource R2:
One instance of R2 is assigned to process P1 and another instance of R2 is assigned to process P4, Process P1 is waiting for resource R1.
One instance of R1 is assigned to Process P2 while another instance of R2 is assigned to process P3, Process P3 is waiting for resource R2.
