Tag: Resource Allocation Graph

Resource Allocation Graph | Deadlock Detection

Operating System

Resource Allocation Graph-

 

Before you go through this article, make sure that you have gone through the previous article on Resource Allocation Graph.

 

We have discussed-

  • Resource Allocation Graph (RAG) is a graph that represents the state of a system pictorially.
  • There are two components of RAG- Vertices and Edges.

 

 

Deadlock Detection-

 

Using Resource Allocation Graph, it can be easily detected whether system is in a Deadlock state or not.

The rules are-

 

Rule-01:

 

In a Resource Allocation Graph where all the resources are single instance,

  • If a cycle is being formed, then system is in a deadlock state.
  • If no cycle is being formed, then system is not in a deadlock state.

 

Rule-02:

 

In a Resource Allocation Graph where all the resources are NOT single instance,

  • If a cycle is being formed, then system may be in a deadlock state.
  • Banker’s Algorithm is applied to confirm whether system is in a deadlock state or not.
  • If no cycle is being formed, then system is not in a deadlock state.
  • Presence of a cycle is a necessary but not a sufficient condition for the occurrence of deadlock.

 

Also Read- Deadlock Handling Strategies

 

PRACTICE PROBLEMS BASED ON DETECTING DEADLOCK USING RAG-

 

Problem-01:

 

Consider the resource allocation graph in the figure-

 

 

Find if the system is in a deadlock state otherwise find a safe sequence.

 

Solution-

 

Method-01:

 

  • The given resource allocation graph is single instance with a cycle contained in it.
  • Thus, the system is definitely in a deadlock state.

 

Method-02:

 

Using the given resource allocation graph, we have-

 

Allocation Need
R1 R2 R1 R2
Process P1 1 0 0 1
Process P2 0 1 1 0

Available = [ R1 R2 ] = [ 0 0 ]

 

Now,

  • There are no instances available currently and both the processes require a resource to execute.
  • Therefore, none of the process can be executed and both keeps waiting infinitely.
  • Thus, the system is in a deadlock state.

 

Problem-02:

 

Consider the resource allocation graph in the figure-

 

 

Find if the system is in a deadlock state otherwise find a safe sequence.

 

Solution-

 

  • The given resource allocation graph is multi instance with a cycle contained in it.
  • So, the system may or may not be in a deadlock state.

 

Using the given resource allocation graph, we have-

 

Allocation Need
R1 R2 R1 R2
Process P1 1 0 0 1
Process P2 0 1 1 0
Process P3 0 1 0 0

Available = [ R1 R2 ] = [ 0 0 ]

 

Step-01:

 

  • Since process P3 does not need any resource, so it executes.
  • After execution, process P3 release its resources.

 

Then,

Available

= [ 0 0 ] + [ 0 1 ]

= [ 0 1 ]

 

Step-02:

 

  • With the instances available currently, only the requirement of the process P1 can be satisfied.
  • So, process P1 is allocated the requested resources.
  • It completes its execution and then free up the instances of resources held by it.

 

Then-

Available

= [ 0 1 ] + [ 1 0 ]

= [ 1 1 ]

 

Step-03:

 

  • With the instances available currently, the requirement of the process P2 can be satisfied.
  • So, process P2 is allocated the requested resources.
  • It completes its execution and then free up the instances of resources held by it.

 

Then-

Available

= [ 1 1 ] + [ 0 1 ]

= [ 1 2 ]

 

Thus,

  • There exists a safe sequence P3, P1, P2 in which all the processes can be executed.
  • So, the system is in a safe state.

 

Problem-03:

 

Consider the resource allocation graph in the figure-

 

 

Find if the system is in a deadlock state otherwise find a safe sequence.

 

Solution-

 

  • The given resource allocation graph is multi instance with a cycle contained in it.
  • So, the system may or may not be in a deadlock state.

 

Using the given resource allocation graph, we have-

 

Allocation Need
R1 R2 R3 R1 R2 R3
Process P0 1 0 1 0 1 1
Process P1 1 1 0 1 0 0
Process P2 0 1 0 0 0 1
Process P3 0 1 0 0 2 0

Available = [ R1 R2 R3 ] = [ 0 0 1 ]

 

Step-01:

 

  • With the instances available currently, only the requirement of the process P2 can be satisfied.
  • So, process P2 is allocated the requested resources.
  • It completes its execution and then free up the instances of resources held by it.

 

Then-

Available

= [ 0 0 1 ] + [ 0 1 0 ]

= [ 0 1 1 ]

 

Step-02:

 

  • With the instances available currently, only the requirement of the process P0 can be satisfied.
  • So, process P0 is allocated the requested resources.
  • It completes its execution and then free up the instances of resources held by it.

 

Then-

Available

= [ 0 1 1 ] + [ 1 0 1 ]

= [ 1 1 2 ]

 

Step-03:

 

  • With the instances available currently, only the requirement of the process P1 can be satisfied.
  • So, process P1 is allocated the requested resources.
  • It completes its execution and then free up the instances of resources held by it.

 

Then-

Available

= [ 1 1 2 ] + [ 1 1 0 ]

= [ 2 2 2 ]

 

Step-04:

 

  • With the instances available currently, the requirement of the process P3 can be satisfied.
  • So, process P3 is allocated the requested resources.
  • It completes its execution and then free up the instances of resources held by it.

 

Then-

Available

= [ 2 2 2 ] + [ 0 1 0 ]

= [ 2 3 2 ]

 

Thus,

  • There exists a safe sequence P2, P0, P1, P3 in which all the processes can be executed.
  • So, the system is in a safe state.

 

To watch video solutions and practice other problems,

Watch this Video Lecture

 

Next Article- Contiguous Memory Allocation

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Resource Allocation Graph | Operating System

Operating System

Resource Allocation Graph-

 

Resource Allocation Graph (RAG) is a graph that represents the state of a system pictorially.

 

It gives complete information about the state of a system such as-

  • How many processes exist in the system?
  • How many instances of each resource type exist?
  • How many instances of each resource type are allocated?
  • How many instances of each resource type are still available?
  • How many instances of each resource type are held by each process?
  • How many instances of each resource type does each process need for execution?

 

Components Of RAG-

 

There are two major components of a Resource Allocation Graph-

  1. Vertices
  2. Edges

 

Vertices-

 

There are following types of vertices in a Resource Allocation Graph-

 

 

  1. Process Vertices
  2. Resource Vertices

 

Process Vertices-

 

  • Process vertices represent the processes.
  • They are drawn as a circle by mentioning the name of process inside the circle.

 

Resource Vertices-

 

  • Resource vertices represent the resources.
  • Depending on the number of instances that exists in the system, resource vertices may be single instance or multiple instance.
  • They are drawn as a rectangle by mentioning the dots inside the rectangle.
  • The number of dots inside the rectangle indicates the number of instances of that resource existing in the system.

 

Edges-

 

There are two types of edges in a Resource Allocation Graph-

 

 

  1. Assign Edges
  2. Request Edges

 

Assign Edges-

 

  • Assign edges represent the assignment of resources to the processes.
  • They are drawn as an arrow where the head of the arrow points to the process and tail of the process points to the instance of the resource.

 

Request Edges-

 

  • Request edges represent the waiting state of processes for the resources.
  • They are drawn as an arrow where the head of the arrow points to the instance of the resource and tail of the process points to the process.
  • If a process requires ‘n’ instances of a resource type, then ‘n’ assign edges will be drawn.

 

Example Of RAG-

 

The following diagram represents a Resource Allocation Graph-

 

 

It gives the following information-

  • There exist three processes in the system namely P1, P2 and P3.
  • There exist two resources in the system namely R1 and R2.
  • There exists a single instance of resource R1 and two instances of resource R2.
  • Process P1 holds one instance of resource R1 and is waiting for an instance of resource R2.
  • Process P2 holds one instance of resource R2 and is waiting for an instance of resource R1.
  • Process P3 holds one instance of resource R2 and is not waiting for anything.

 

To gain better understanding about Resource Allocation Graph,

Watch this Video Lecture

 

Next Article- Practice Problems On Resource Allocation Graph

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.