Resource Allocation graph technique is used for deadlock avoidance when there is a single instance of every resource. In resource allocation graph for deadlock avoidance we introduce a third kind of edge called the claim edge which is a dotted line from a process towards a resource meaning that the resource can be requested by the process in future.
Whenever a process requests for a resource the claim edge is changed to request edge and if the resource can be granted the request edge is changed to assignment edge. After this change look for a cycle in the graph. If no cycle exists, then the system is in safe state and the deadlock will not occur else the system is in unsafe state and deadlock may or may not occur.
Important to remember
- Applicable if each resource has only one instance.
- Claim edge : ——-> from process to resource
- Process may request resource in future
- When process requests resource change claim edge to request edge.
- Request edge is converted into assignment edge only if the conversion does not lead to the formation of a cycle in the graph.
Example
Consider the scenario in Figure 1. P1 is holding R2 and P2 is requesting R2. P1 and P2 can request for R1 in the future.
Q. Suppose P2 requests for R1. Should the grant this request?
Ans: No, because granting the request will lead to the formation of cycle in the graph.
P2 request for R1, since R1 is free it can be allocated to P1. The resulting graph will be as shown in Figure 2. This results in cycle formation in the resource-allocation graph. Hence, the state is an unsafe state and this request can not be granted.
Q. Suppose P1 requests for R1 (refer Figure 1). Should the system grant this request?
Ans: Discuss your answer in the comments section
PPT on Resource Allocation Graph
Note: Clicking on the “next” slide button will not display any animation. Hence, Click within the slide area for animations.
Video on Resource Allocation Graph
Previous Next Deadlock Avoidance Banker's Algorithm
Suppose P1 requests for R1 (refer Figure 1). Can this request be granted?
and:-Yes because no cycle is formed after granting the request.
Correct