Deadlock Characterization

   1.  Mutual exclusion: only one process at a time can use a resource.

   2.  Hold and wait: a process holding at least one resource is waiting to acquire additional resources held

        by other processes.

   3.  No preemption: a resource can be released only voluntarily by the process holding it, after that

        process has Completed its task.

   4. Circular wait: there exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a

        resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a 

        resource that is held by Pn, and P0 is waiting for a resource that is held by P0.

        Deadlock can arise if four conditions hold simultaneously.

Resource-Allocation Graph

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

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

Process

Resource Type with 4 instances

   Pi requests instance of Rj

  Pi is holding an instance of Rj

          Pi

          Pi

          Rj

          Rj   

Example of a Resource Allocation Graph

Resource Allocation Graph With A Deadlock

Resource Allocation Graph With A Cycle But No Deadlock

Basic Facts

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.