Resource Allocation Graph Algorithm
Q1. What is Resource Allocation Graph Algorithm?
Ans. Suppose that process Pi resource Rj. The request can be granted only if converting the request edge
Pi → Rj
to an assignment edge
Rj → Pi
doesn’t result in the form of a cycle in the resource allocation graph. An algorithm for detecting a cycle in the graph requires that an order of n2 operations, where n=number of processes in the system. If the no cycle exists, then the allocation of the resource will leave the system in safe state. If a cycle is found, then the allocation will put the system in an unsafe state. Therefore, Pi will have to wait for its request to be satisfied.
Figure: An unsafe state in a resource allocation graph
By figure suppose that process P2 request R1 and R1 is assigned to P1, P1 is requesting to R2 and R2 is assigned to P2.
*It is used for single instance.