Resource Allocation Graphs - aryanjoshi0823/5143-Operating-System GitHub Wiki

Introduction to Resource Allocation Graph (RAG)

The Resource Allocation Graph (RAG) is a graphical representation of the state of a system. It contains all the information about the resource allocation to each process and the requests made by each process.

Representation of Resource Allocation Graph (RAG)

Like all other graphs, a Resource Allocation Graph has vertices and edges:

  • Vertices:

    • The vertices represent processes or resources.
    • Process vertices are typically represented as circles.
    • Resource vertices are represented as rectangles.

  • Edges:

    • Assign Edge: Directed from a resource to a process, indicating that a resource has been allocated to a process.
    • Request Edge: Directed from a process to a resource, indicating that a process has made a request for a resource.

Types of Resources:

  1. Single Instance: A resource that has a single instance, represented by a single dot inside the rectangle (resource vertex).

  • 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.
  1. Multiple Instances: A resource that has multiple instances, represented by multiple dots inside the rectangle.

  • 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.
Process Allocation Request
  R1 R2 R3 R1 R2 R3
P1 0 1 0 1 0 0
P2 1 0 0 0 0 1
P3 0 0 1 0 1 0
P4 0 0 1 0 0 0

  • 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

  • First, find the currently available instances of each resource.
  • Check for each process which can be executed using the allocated + available resource.
  • Add the allocated resource of the executable process to the available resources and terminate it.
  • Repeat the 2nd and 3rd steps until the execution of each process.
  • 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.