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.

Unsafe state in Resource Allocation Graph

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.

Leave a Reply

Your email address will not be published. Required fields are marked *