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.

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.

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-

 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.