Resource Allocation Graph (RAG) | Operating Systems (OS) | Core CS

Introduction to Resource Allocation Graph (RAG)

The Resource Allocation Graph, also known as RAG is a graphical representation of the state of a system. It has all the information about the resource allocation to each process and the request of each process. 

In Banker's Algorithm, we have table-like data that suggests all the information about the allocation of resources to the processes and their requests. We determine the state of a system using those data from the table. But, RAG summarises all the information in its pictorial or graphical form.

In some cases, we can determine there is a deadlock in the system or not, just after looking at the Resource Allocation Graph or (RAG), but it is not possible by just looking at the table. This is one of the advantages of the Resource Allocation Graph.

Representation of Resource Allocation Graph (RAG)

• Like all other graphs, it also has vertices and edges.
• The vertices of the RAG represent the process or the resource, and the edges represent the allocation or request of any resource.
• As both the process and resource are the vertices of the graph, generally, the process vertex will be represented using the circle and the resource vertex using the rectangle.
• The resource can be of two types:

1. Single Instance - It contains the single instance of the resource, and is represented by a single dot inside the rectangle which is the resource vertex.
2. Multiple Instance - It contains the multiple instances of the resource, and is represented by multiple (more than one) dots inside the rectangle.

• Edges also can be of two types:

1. Assign Edge - This edge directing from the resource towards the process represents the allocation of the resource to the process.
2. Request Edge - This edge directing from the process towards the resource represents the request of the resource by the process.

Example of Single Instances RAG

In the above single instances RAG example, it can be seen that P2 is holding the R1 and waiting for R3. P1 is waiting for R1 and holding R2 and, P3 is holding the R3 and waiting for R2. So, it can be concluded that none of the processes will get executed.

It can also be concluded by writing it in the form of an allocation and request matrix.

Here, from the matrix above, the available instance of R1 is 0, R2 is 0 and R3 is 0, and each of the processes is waiting for any one resource. So, none of the processes will get executed and there will be a deadlock.

Note: If there is a cycle in a single instance RAG then the processes will be in a deadlock.

Example of Multiple Instances RAG

In the case of Multiple Instances RAG, it becomes difficult to analyze from the RAG that the system is in a safe state or not.

To determine the state of the system we will write it in the form of an allocation and request matrix.

The above matrix is filled from the given Multiple Instance RAG.

As R2 is allocated to P1, write 1 in the Allocation Matrix corresponding to P1 and R1 and others 0 and similarly for all others. P1 is waiting for R1 so, write 1 in the Request Matrix corresponding to P1 and R1 and others 0 and similarly for all others. 

Now, to find the state of the system we will use the following algorithm. 

Algorithm to check deadlock

1. First, find the currently available instances of each resource.
2. Check for each process which can be executed using the allocated + available resource.
3. Add the allocated resource of the executable process to the available resources and terminate it.
4. Repeat the 2^nd and 3^rd steps until the execution of each process.
5. If at any step, none of the processes can be executed then there is a deadlock in the system.

Using the above algorithm, we will get that there is no deadlock in the above-given example, and their sequence of execution can be P4 → P2 → P1 → P3.

Note: Unlike Singles Instances RAG, a cycle in a Multiple Instances RAG does not guarantee that the processes are in deadlock.