Deadlocks

In a multiprogramming environment, several processes may compete for a finite number of

resources. A process requests resources; and if the resources are not available at that time,
the process enters a waiting state. Sometimes a waiting process is never again able to change
state, because the resources it has requested are held by other waiting processes. This
situation is called a deadlock.

Resource types can be Memory space, CPU cycles, files, and I/O devices (such as printers
and DVD drives)
Resource types can be Identical or not Identical
If a system has two CPUs, then the resource type CPU has two instances. If a process
requests an instance of a resource type, the allocation of any instance of the type will satisfy
the request. If it will not, then the instances are not identical

In normal operation a process must request a resource before using it, and release it when it
is done, in the following sequence: (request →use→ release)

1. Request - If the request cannot be immediately granted, then the process must wait
until the resource(s) it needs become available. For example the system calls open( ),
malloc( ), new( ), and request( ).
2. Use - The process uses the resource, e.g. prints to the printer or reads from the file.
3. Release - The process relinquishes the resource. so that it becomes available for other
processes.

• A process cannot request a number more than the total number of resources available
in the system.
• For all kernel-managed resources, the kernel keeps track of what resources are free
and which are allocated, to which process they are allocated, and a queue of
processes waiting for this resource to become available.

Deadlock Characterization
Necessary conditions:
A deadlock occurs if and only if the following four conditions hold in a system
Simultaneously:
1. Mutual Exclusion: At least one of the resources is non-sharable (that is only a
limited number of processes can use it at a time and if it is requested by a process
 while it is being used by another one, the requesting process has to wait until the
resource is released.)
2. Hold and Wait: There must be at least one process that is holding at least one
resource and waiting for other resources that are being hold by other processes.
3. No Preemption: No resource can be preempted before the holding process
completes its task with that resource.
4. Circular Wait: There exists a set of processes: {P1, P2, ..., Pn} such that
P1 is waiting for a resource held by P2
P2 is waiting for a resource held by P3 ...
Pn-1 is waiting for a resource held by Pn Pn is waiting for a resource held by P1
Four Conditions are not completely Independent

Resource-Allocation Graph
Deadlocks can be understood more clearly through the use of Resource-Allocation
Graphs, having the following properties:
A set of resource { R1, R2, R3, . . ., RN } are represented as square nodes on the
graph.
Dots inside the resource nodes indicate specific instances of the resource. ( E.g.
two dots might represent two laser printers. )
A set of processes, { P1, P2, P3, . . ., PN } represented as Circles
Edges:
Request Edges - A set of directed arcs from Pi to Rj, indicating that process Pi
has requested Rj, and is currently waiting for that resource to become available.

Assignment Edges - A set of directed arcs from Rj to Pi indicating that resource

Rj has been allocated to process Pi, and that Pi is currently holding resource Rj.

Once the process requests for the resource a request edge is inserted with the arrow
pointing towards the resource .
Note that a request edge can be converted into an assignment edge by reversing the
direction of the arrow when the request is granted. ( However note also that request
edges point to the category box, whereas assignment edges emanate from a particular
instance dot within the box. )
Once the process utilizes and no longer access the resource the assignment edge is
deleted
 For example: Resource allocation graph depicts the following:

Process states:
• Process P1 is holding an instance of resource type R2 and
is waiting for an instance of resource type R1.
• Process P2 is holding an instance of R1 and an instance of
R2 and is waiting for an instance of R3.
• Process P3 is holding an instance of R3.

When can p1 complete? ……when p2 releases R1.

When can p2 complete?........when p3 releases R3.
So deadlock doesn’t occur

Process states:
o Process P\ is holding an instance of resource type R2 and is waiting for
an instance of resource type R|.
o Process Pn is holding an instance of R\ and an instance of R2 and is
waiting for an instance of R3.
o Process P3 is holding an instance of R3.
• If a resource-allocation graph contains no cycles, then the system is not deadlocked. (
When looking for cycles, remember that these are directed graphs. ) See the above
example.
• If a resource-allocation graph does contain cycles AND each resource category
contains only a single instance, then a deadlock exists.
• If a resource category contains more than one instance, then the presence of a cycle
in the resource-allocation graph indicates the possibility of a deadlock, but does not
guarantee one

Resource allocation graph with a

deadlock

Resource allocation graph with a cycle but no deadlock

 3. Methods for Handling Deadlocks

There are three ways of handling deadlocks:

1. Deadlock prevention or avoidance - Do not allow the system to get into a

deadlocked state.
2. Deadlock detection and recovery - Abort a process or pre-empt some
resources when deadlocks are detected.
3. Ignore the problem all together - If deadlocks only occur once a year or so,
it may be better to simply let them happen and reboot as necessary than to incur
the constant overhead and system performance penalties associated with
deadlock prevention or detection
• Deadlock can be prevented by ensuring that at least one of the necessary conditions
cannot hold (Mutual Exclusion, Hold and Wait, No Pre-emption, Circular Wait)
• In order to avoid deadlocks, the system must have additional information about all
processes. In particular, the system must know what resources a process will or may
request in the future. (Ranging from a simple worst-case maximum to a complete
resource request and release plan for each process, depending on the particular
algorithm.)

7.4 Deadlock Prevention

• Deadlocks can be prevented by ensuring that at least one of the following four cannot
hold.

7.4.1 Mutual Exclusion

• Shared resources such as read-only files do not lead to deadlocks.

• Certain resources, such as printers and tape drives, require exclusive access by a single
process.
• We cannot prevent deadlocks by denying mutual exclusion condition, because some
resources are intrinsically non sharable

7.4.2 Hold and Wait

• To prevent this condition processes must be prevented from holding one or more
resources while simultaneously waiting for one or more others. There are several
possibilities for this:
o Require that all processes request and be allocated all resources before it
begins. Leads to lower resource Utilization.
o Require that processes to request resources only when it has none. This can
be a problem if a process has partially completed an operation using a resource
and then fails to get it re-allocated after releasing it, may also leads to
starvation.
7.4.3 No Pre-emption

Pre-emption of process resource allocations can prevent this condition of deadlocks,

when it is possible.

One approach is that if a process is holding some resource and requests another
which cannot be granted immediately, then all other resources previously held
by this process are implicitly released, (pre-empted), forcing this process to re-
acquire the old resources along with the new resources in a single request.

Second approach is that when a resource is requested and not available, then
the system looks to see whether they are allocated to a certain process which
is waiting for additional resources. If so, the resource is pre-empted by the
waiting process and allocated to the requesting process.

If p1 requests r1 and r2, and if r1(available) and r2 held by p2

If p2 holds r2 and waiting for r3 ,but r3 is unavailable then r2 is pre-empted so that

p1 can complete.

Either of these approaches may be applicable for resources whose states are easily
saved and restored, such as registers and memory, but are generally not applicable
to other devices such as printers and tape drives.

7.4.4 Circular Wait

One way to avoid circular wait is to number all resources, and to require that
processes request resources only in strictly increasing ( or decreasing ) order.
i) Process can initially request any number of instances of a resource type say, Ri.
After that, the process can request instances of resource type Rj. If several
instances of the same resource type are needed, a single request for all of them
must be issued.
ii) In order to request resource Rj, a process must first release all Ri such that i >= j.
If these two protocols are used, then the circular-wait condition cannot hold.

7.5 Deadlock Avoidance

Deadlock-prevention algorithms prevent deadlocks by ensuring that at least
one of the necessary conditions for deadlock cannot occur, but results in low
device utilization and reduced system throughput.

Deadlock avoidance: when a request is made knowledge of the complete

sequence of requests (total instances of resources) and releases for each
process is required, so that the system can decide for each request whether or not
the process should wait in order to avoid a possible future deadlock.
 Each request requires that in making this decision the system considers the
resources currently available, the resources currently allocated to each process, and
the future requests and releases of each process.
If a scheduler finds that starting a process or granting resource requests may lead
to future deadlocks, then that process is just not started or the request is not granted.

7.5.1 Safe State

A state is safe if the system can allocate resources to each process in some order and
can still avoid deadlock.
A deadlock state is an unsafe state.

More formally, a state is safe if there exists a safe sequence of processes { P0, P1, P2,
..., PN } such that all of the resource requests for Pi can be granted using the resources
currently allocated to Pi and all processes Pj where j < i. ( I.e. if all the processes prior
to Pi finish and free up their resources, then Pi will be able to finish also, using the
resources that they have freed up.)
If a safe sequence does not exist, then the system is in an unsafe state, which MAY lead to
deadlock. ( All safe states are deadlock free, but not all unsafe states lead to deadlocks. )

Consider a system with 12 tape drives. Assume there are three processes : p0, p1, p2.
Assume we know the maximum number of tape drives that each process may request:

Maximum Current
Needs Allocation
P0 10 5
P1 4 2
P2 9 2
Example: