Resource Allocation Graph

Resource allocation graph & Wait-for 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




How could you know if theres a deadlock based w/ the Resouce Allocation table?



*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 of deadlock.