Resource Allocation Graph | Deadlock Detection

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-

 

AllocationNeed
R1R2R1R2
Process P11001
Process P20110

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-

 

AllocationNeed
R1R2R1R2
Process P11001
Process P20110
Process P30100

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-

 

AllocationNeed
R1R2R3R1R2R3
Process P0101011
Process P1110100
Process P2010001
Process P3010020

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.

Summary
Resource Allocation Graph | Deadlock Detection
Article Name
Resource Allocation Graph | Deadlock Detection
Description
Practice Problems based on Resource Allocation Graph. In OS, Resource Allocation Graph (RAG) is a graph that represents the state of a system pictorially. Whether the system is in a deadlock state or not can be predicted using Resource Allocation Graph.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-