DEADLOCK

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 in the system.

* R = {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

�Process

�Resource Type with 4 instances

�Pi requests instance of Rj

�Pi is holding an instance of Rj

How would you know if there is a deadlock based on the Resource Allocator Graph?

� If graph contains a cycle :

* if only one instance per resource type, then deadlock.
* if several instances per resource type, possibility of deadlock.