Resource Allocation Graph Algorithm
In this graph a new type of edge has been introduced is known as claim edge. Claim edge Pi→Rj indicates that process Pj may request resource Rj; represented by a dashed line.Claim edge converts to request edge when a process requests a resource.Request edge converted to an assignment edge when the resource is allocated to the process.When a resource is released by a process, assignment edge reconverts to a claim edge.Resources must be claimed a priori in the system.
- P2 requesting R1, but R1 is already allocated to P1.
- Both processes have a claim on resource R2
- What happens if P2 now requests resource R2
- Cannot allocate resource R2 to process P2
- Why? Because resulting state is unsafe
- P1 could request R2, thereby creating deadlock!
Use only when there is a single instance of each resource type
- Suppose that process Pi requests a resource Rj
- The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph.
- Here we check for safety by using cycle-detection algorithm.