Resource-Allocation Graph

A set of vertices V and a set of edges E.



V is partitioned into two types:

• P = {P1, P2, …, Pn}, the set consisting of all the processes inthe system.


• R = {R1, R2, …, Rm}, the set consisting of all resource typesin the system.

request edge – directed edge P1 → Rj

assignment edge – directed edge Rj → Pi

If graph contains no cycles
no deadlock.

If graph contains a cycle

• ✦ if only one instance per resource type, then deadlock.
• ✦ if several instances per resource type, possibility ofdeadlock.
  

Resource-Allocation Graph Algorithm

Claim edge Pi → Rj indicated that process Pj may requestresource Rj; represented by a dashed line.

Claim edge converts to request edge when a processrequests a resource.

When a resource is released by a process, assignmentedge reconverts to a claim edge.

Resources must be claimed a priori in the system.