In computer operating systems, RAG stands for Resource Allocation Graph. RAG is a directed graph that can be used to illustrate the state of a system graphically. A directed graph can be used to describe deadlocks more precisely.
In this article, we will look more into the Deadlock Detection Using RAG according to the GATE Syllabus for (Computer Science Engineering) CSE. Read ahead to find out more about it.
Table of Contents
How Do We Perform Deadlock Detection Using RAG?
The system gets stalled if a loop forms in a RAG in which all resources have the same instance. The cycle is a required but not sufficient condition of deadlock in a RAG (Resource allocation graph) with multi-instanced resource types.
Three processes, namely P1, P2, and P3 and three resources, namely R1, R2, and R3, are shown in the following example. There is only one instance of each resource.
When we examine the graph, we can see that a cycle has developed because the system meets all four deadlock conditions.
Allocation Matrix
The resource allocation graph in a system can be used to create an allocation matrix. Each resource assigned will have its own entry in the allocation matrix. Because R3 is allocated to P1, an entry is made in front of P1 or below R3 in the following matrix.
Request Matrix
Each resource requested will have its own entry in the request matrix. P1 requires R1 in the following example; thus, an entry is made in front of P1 or below R1.
Avial = (0,0,0)
We don’t have any resources in the system, and no processes are about to start. Because each process requires at least one resource to complete, they will be held indefinitely.
We can’t meet the demand of at least a single process with the resources we have; hence the system is blocked, as we discovered when we noticed a cycle in the graph earlier.
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.
