Resource-Allocation Graph

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

• V is partitioned into two types:
  =>FP = {P1, P2, …, Pn}, the set consisting of all the processes in the system.
  =>FR = {R1, R2, …, Rm}, the set consisting of all resource types in the system.
• request edge – directed edge P1 ® Rj.
• assignment edge – directed edge Rj ® Pi
  

Resource-Allocation Graph Algorithm

• Claim edge Pi ® Rj indicated that process Pj may request resource Rj; represented by a dashed line.
• Claim edge converts to request edge when a process requests a resource.
• When a resource is released by a process, assignment edge reconverts to a claim edge.
• Resources must be claimed a priori in the system.
  

Resource-Allocation Graph and Wait-for Graph

Resource-Allocation Graph Corresponding wait-for graph

How did you know if there is a deadlock based on a resource allocation graph?

• In a multiprogramming system, processes request resourceused by other processes then the process enters a processes are also in a waiting state, we have deadlock.