Page 117 - DCAP403_Operating System

Operating System

Notes 6.6 Deadlock Characterization

Necessary Conditions

Deadlock situation can arise if the following four conditions hold simultaneously in a system:

1. Resources are used in mutual exclusion.
2. Resources are acquired piecemeal (i.e. not all the resources that are needed to complete an
activity are obtained at the same time in a single indivisible action).
3. Resources are not preempted (i.e. a process does not take away resources being held by
another process).

4. Resources are not spontaneously given up by a process until it has satisfied all its
outstanding requests for resources (i.e. a process, being that it cannot obtain some needed
resource it does not kindly give up the resources that it is currently holding).

Resource Allocation Graphs

Resource Allocation Graphs (RAGs) are directed labeled graphs used to represent, from the point
of view of deadlocks, the current state of a system.

RESOURCE ALLOCATION GRAPHS

Process
[reusable] Resources with multiplicity 2

Request Edge from process Pi
to resource Rj
Pi Rj
Assignment Edge from resource
Rj to process Pi
Pi Rj

R1 P1 P1 holds two copies of
resource R1, and P2 holds
one copy of resource R1 and
P2 requests one copy of R2
R2

State transitions can be represented as transitions between the corresponding resource allocation
graphs. Here are the rules for state transitions:

1. Request: If process Pi has no outstanding request, it can request simultaneously any
number (up to multiplicity) of resources R1, R2, ..Rm. The request is represented by adding
appropriate requests edges to the RAG of the current state.

2. Acquisition: If process Pi has outstanding requests and they can all be simultaneously
satisfied, then the request edges of these requests are replaced by assignment edges in the

RAG of the current state
3. Release: If process Pi has no outstanding request then it can release any of the resources it
is holding, and remove the corresponding assignment edges from the RAG of the current
state.

110 LOVELY PROFESSIONAL UNIVERSITY