6.2 Deadlock characterization

A deadlock situation can arise if the following four necessary conditions hold simultaneously in a system:

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

Hold and wait: A process holding at least one resource is waiting to acquire additional resources

held by other processes.

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

has completed its task.

Circular wait: There exists a set {P0, P1, ..., Pn} 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 P0.

The system resource-allocation graph is a directed graph that is used to describe deadlocks. The graph consists of a set of vertices V and a set of edges E. Vertices V is partitioned into two types:

P = {P1, P2, ..., Pn}, the set consisting of all the processes in the system. Each process is represented

as a circle.

R = {R1, R2, ..., Rm}, the set consisting of all resource types in the system. Each resource is

represented as a rectangle. Each resource can have more than an instance. Each instance is

represented as a dot.

6.2 Deadlock characterization

The graph has two types of edges:

Request edge: It is directed edge from process Pi to resource Rj (Pi –› Rj).

Assignment edge: It is directed edge from resource Rj to process Pi (Rj –› Pi).

If the graph contains no cycles, then there is no deadlock. If the graph contains a cycle, then there is a deadlock if each resource has only one instance. If the resources have several instances, then a cycle in the graph means there is a possibility of deadlock.