DEADLOCK

S
In a multiprogramming environment, several processes may compete for a
finite number of resources. A process requests resources; 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.

Operating Systems
2
 A system can be modeled as a collection of limited resources, which can be
partitioned into different categories, to be allocated to a number of processes,
each having different needs. Resource categories may include memory, printers,
CPUs, open files, tape drives, CD-ROMS, etc.

 By definition, all the resources within a category are equivalent, and a request of
this category can be equally satisfied by any one of the resources in that
category. Some categories may have a single resource.

 A process must request a resource before using it and must release the resource
after using it. A process may request as many resources as it requires to carry out
its designated task.

Operating Systems
3
Under the normal mode of operation, a process may utilize a resource in
only the following sequence:
i. Request: The process requests the resource. If the request cannot be
granted immediately (for example, if the resource is being used by
another process), then the requesting process must wait until it can
acquire the resource. For example the system calls open( ), malloc( ),
new( ), and request( ).
ii. Use: The process can operate on the resource (for example, if the
resource is a printer, the process can print on the printer or read from
a file).
iii. Release: The process releases the resource. For example, close( ),
free( ), delete( ), and release( ).
4
 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.
 Application-managed resources can be controlled using mutexes or wait( )
and signal( ) calls, (i.e. binary or counting semaphores.)
 A set of processes is deadlocked when every process in the set is waiting
for a resource that is currently allocated to another process in the set (and
which can only be released when that other waiting process makes
progress.)

Operating Systems
5
A deadlock situation can arise if the following four conditions hold simultaneously in
a system:
1.Mutual exclusion. At least one resource must be held in a nonsharable mode; that is, only
one process at a time can use the resource. If another process requests that resource, the
requesting process must be delayed until the resource has been released.

2.Hold and wait. A process must be holding at least one resource and waiting to acquire
additional resources that are currently being held by other processes.

3.No preemption. Resources cannot be preempted; that is, a resource can be released only
voluntarily by the process holding it, after that process has completed its task.

4.Circular wait. A set {P0, P1, ..., Pn} of waiting processes must exist such that P0 is waiting for
a resource held by P1, P1 is waiting for a resource held by P2, ..., Pn−1 is waiting for a resource
held by Pn, and Pn is waiting for a resource held by P0.
6
In some cases deadlocks can be understood more clearly through the use of
Resource- Allocation Graphs, having the following properties:
• A set of resource categories, { R1, R2, R3, . . ., RN }, which appear 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 } the set consisting of all the processes in the
system
• 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. Pi  Rj
• 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. Rj  Pi
Note that a request edge can be converted into an assignment edge by reversing the direction of the arc
when the request is granted.
Operating Systems
7
R
E
S
O
U
R
C
E
-
A
L
L
O
C
A
T
I
O
N
The sets P, R, and E:
P = {P1, P2, P3}
G
R R = {R1, R2, R3,
A
P R4}
E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 →
H 8
• If a resource-allocation graph contains no cycles, then the system is not deadlocked.
• 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 Resource allocation graph with a cycle but no
deadlock deadlock 9
Deadlock Conditions
1.mutual exclusion: The resources involved must be unshareable; otherwise, the processes would not be prevented
using the resource when necessary.
from

2.hold and wait or partial allocation: The processes must hold the resources they have already been allocated while waiting
for other (requested) resources. If the process had to release its resources when a new resource or resources were
requested, deadlock could not occur because the process would not prevent others from using resources that it controlled.

3.no pre-emption: The processes must not have resources taken away while that resource is being used. Otherwise,
deadlock could not occur since the operating system could simply take enough resources from running processes to enable
any process to finish.

4. resource waiting or circular wait: A circular chain of processes, with each process holding resources which are currently
being requested by the next process in the chain, cannot exist. If it does, the cycle theorem (which states that "a cycle in
resource graph is necessary for deadlock to occur") indicated that deadlock could
the 10
Generally speaking there are three ways of handling
deadlocks:
 Deadlock prevention or avoidance - Do not allow the system to get into a
deadlocked state.
 Deadlock detection and recovery - Abort a process or preempt some
resources when deadlocks are detected.
 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. This is the approach that both
Windows and UNIX take.
11
 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. )

 Deadlock detection is fairly straightforward, but deadlock recovery requires either

aborting processes or preempting resources, neither of which is an attractive
alternative.

 If deadlocks are neither prevented nor detected, then when a deadlock occurs the
system will gradually slow down, as more and more processes become stuck
waiting for resources currently held by the deadlock and by other waiting
processes. Unfortunately this slowdown can be indistinguishable from a general
system slowdown when a real-time process has heavy computing needs.
Operating Systems
12
Deadlocks can be prevented by preventing at least one of the four required conditions:
Mutual Exclusion
• Shared resources such as read-only files do not lead to deadlocks.
• Unfortunately some resources, such as printers and tape drives, require exclusive access by
a
single process.
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:
 Require that all processes request all resources at one time. This can be wasteful of system
resources if a process needs one resource early in its execution and doesn't need some
other resource until much later.
 Require that processes holding resources must release them before requesting new
resources, and then re-acquire the released resources along with the new ones in a single
new request. 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.
 Either of the methods described above can lead to starvation if a process requires one
Operating Systems
13
No
Preemption
Preemption of process resource allocations can prevent this condition of deadlocks, when it is
possible.
• One approach is that if a process is forced to wait when requesting a new resource, then all other
resources previously held by this process are implicitly released, (preempted), forcing this process to
re-acquire the old resources along with the new resources in a single request.
• Another approach is that when a resource is requested and not available, then the system looks to
see what other processes currently have those resources and are themselves blocked waiting for
some other resource. If such a process is found, then some of their resources may get preempted
and added to the list of resources for which the process is waiting.
• 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.
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.
• In other words, in order to request resource Rj, a process must first release all Ri such that i >= j.
One big challenge in this scheme is determining the relative ordering of the different resources
The general idea behind deadlock avoidance is to prevent deadlocks from ever
happening, by preventing at least one of the four conditions.
The system knows the complete sequence of requests and releases for each
process.
The system decides for each request whether or not the process should wait in
order to avoid a deadlock.
Each process declare the maximum number of resources of each type that it may
need.
 A resource allocation state is defined by the number of available and allocated
resources, and the maximum requirements of all processes in the system. The
system should always be at a safe state.
Operating Systems
15
Safe State
 A state is safe if the system can allocate all resources requested by all
processes ( up to their stated maximums ) without entering a deadlock state.
 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. )
 I f 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. )

Operating Systems
16
17
Resource-Allocation Graph Algorithm
• If resource categories have only single instances of their resources, then deadlock states can be detected
by cycles in the resource-allocation graphs.
• In this case, unsafe states can be recognized and avoided by augmenting the resource-allocation graph
with claim edges, noted by dashed lines, which point from a process to a resource that it may request in
the future.
• In order for this technique to work, all claim edges must be added to the graph for any particular process
before that process is allowed to request any resources

A cycle-detection
algorithm is an
algorithm for detecting
a cycle in this graph
requires an order of n2
operations, where n is
the number of processes
in the system.
18
 Banker's Algorithm
 For resource categories that contain more than one instance the resource-allocation graph
mehtod does not work, and more complex ( and less efficient ) methods must be chosen.
 The Banker's Algorithm gets its name because it is a method that bankers could use to
assure h
tat when they lend out resources, they will still be able to satisfy all their clients.
 When a process starts up, it must state in advance the maximum allocation of resources it
may request, up to the amount available on the system.
 When a request is made, the scheduler determines whether granting the request would
leave the system in a safe state. If not, then the process must wait until the request can be granted
safely.
• The banker's algorithm relies on several key data structures:

Operating Systems
19
Let ‘n’ be the number of processes in the system and ‘m’ be the number of resources types.
Available :
It is a 1-d array of size ‘m’ indicating the number of available resources of each type.
Available[ j ] = k means there are ‘k’ instances of resource type Rj
Max :
It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a system.
Max[ i, j ] = k means process Pi may request at most ‘k’ instances of resource type Rj.
Allocation :
It is a 2-d array of size ‘n*m’ that defines the number of resources of each type currently allocated to each
process.
Allocation[ i, j ] = k means process Pi is currently allocated ‘k’ instances of resource type Rj
Need :
It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each process.
Need [ i, j ] = k means process Pi currently allocated ‘k’ instances of resource type Rj
Need [ i, j ] = Max [ i, j ] – Allocation [ i, j ]

• Allocationi specifies the resources currently allocated to process Pi and Needi

specifies the additional
resources that process Pi may still request to complete its task.
• Banker’s algorithm consist of Safety algorithm and Resource request algorithm.
Operating Systems
20
The algorithm for finding out whether or not a system is in a safe state can be described as
follows:

This algorithm may require an order of m × n2 operations to determine whether a state is safe.
21
Operating Systems
Let Requesti be the request array for process Pi. Requesti [j] = k means process Pi wants k
instances of resource type Rj. When a request for resources is made by process Pi, the following
actions are taken:

Operating Systems
22
 Considering a system with five processes P0 through P4 and
three resources types A, B, C. Resource type A has 10 instances, B has 5
instances and type C has 7 instances. Suppose at time t0 following
snapshot of the system has been taken:

Question1. What will be the content of the

Need matrix?
Need [i, j] = Max [i, j] – Allocation [i, j]
So, the content of Need Matrix is:

23
Question2. Is the system in safe state? If Yes, then what is the safe
sequence?

24
Question3. What will happen if process P1 requests one additional instance of resource type
A
and two instances of resource type C?

25
Hence the new system state is safe, so we can immediately grant the request for process P1
when the system is in this state, a request for (3,3,0) by P4 cannot be granted, since the resources are not available.
Furthermore, a request for (0,2,0) by P0 cannot be granted, even though the resources are available, since the
resulting state is unsafe. 26
An operating system uses the Banker’s algorithm for deadlock avoidance when managing the allocation of
three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below presents the
current system state. Here, the Allocation matrix shows the current number of resources of each type
allocated to each process and the Max matrix shows the maximum number of resources of each type
required by each process during its execution.

There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a
safe state. Consider the following independent requests for additional resources in the current state:

REQ1: P0 requests 0 units of X,

0 units of Y and 2 units of Z
REQ2: P1 requests 2 units of X,
0 units of Y and 0 units of Z
Operating Systems
27
 If deadlocks are not avoided, then another approach is to detect when they have
occurred and recover somehow.
 In addition to the performance hit of constantly checking for deadlocks, a policy /
algorithm must be in place for recovering from deadlocks, and there is potential for
lost work when processes must be aborted or have their resources preempted.

 If each resource category has a single instance, then we can use a variation of the
resource-allocation graph known as a
 A wait-for graph can be constructed from a resource-allocation graph by eliminating
the resources and collapsing the associated edges.
 An arc from Pi to Pj in a wait-for graph indicates that process Pi is waiting for
a resource that process Pj is currently holding.
Operating Systems 28
Maintain wait-for graph
Nodes are processes
Pi  P j if Pi is waiting for Pj
Periodically invoke an algorithm that searches for a cycle in the graph. If there is a cycle, there exists a deadlock
An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in
the graph

Resource-Allocation Graph Corresponding wait-for graph 29

 The wait-for graph scheme is not applicable to a resource-allocation system with
multiple instances of each resource type.
 The detection algorithm employs several time-varying data structures that are
similar to those used in the banker’s algorithm.
 Available: A vector of length m indicates the number of available resources of
each type
 Allocation: An n x m matrix defines the number of resources of each type
currently allocated to each process
 Request: An n x m matrix indicates the current request of each process. If
Request [i][j] = k, then process Pi is requesting k more instances of resource
type Rj.

Operating Systems
30
1. Let Work and Finish be vectors of length m and n, respectively
Initialize:
(a) Work = Available
(b) For i = 1,2, …, n, if Allocationi  0, then
Finish[i] = false; otherwise, Finish[i] = true

2. Find an index i such that both:

(a) Finish[i] == false
(b) Requesti  Work

If no such i exists, go to step 4

3. Work = Work + Allocationi

Finish[i] = true
go to step 2

4. If Finish[i] == false, for some i, 1  i n, then the system is in deadlock

state. Moreover, if Finish[i] == false, then Pi is deadlocked

Algorithm requires an order of O(m x n2) operations to detect

whether the system is in deadlocked state 31
Consider, for example, the following state, and determine if it is currently
deadlocked:

Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true for all i
Now suppose that process P2 makes a request for an additional instance of type C, yielding
the state shown below. Is the system now deadlocked?

• Can reclaim resources held by

process P0, but insufficient
resources to fulfill other processes
requests.
• Deadlock exists, consisting of
processes P1, P2, P3, and P4
32
1. In this, Work = [0, 0, 0] &
Finish = [false, false, false, false,
2. i=0 isfalse]
selected as both Finish[0] = false and [0, 0, 0]<=[0, 0,
0]. 3. Work =[0, 0, 0]+[0, 1, 0] =>[0, 1, 0] &
Finish = [true, false, false, false, false].
4. i=2 is selected as both Finish[2] = false and [0, 0, 0]<=[0, 1,
0]. 5. Work =[0, 1, 0]+[3, 0, 3] =>[3, 1, 3] &
Finish = [true, false, true, false, false].
6. i=1 is selected as both Finish[1] = false and [2, 0, 2]<=[3, 1,
3]. 7. Work =[3, 1, 3]+[2, 0, 0] =>[5, 1, 3] &
Finish = [true, true, true, false, false].
8. i=3 is selected as both Finish[3] = false and [1, 0, 0]<=[5, 1,
3]. 9. Work =[5, 1, 3]+[2, 1, 1] =>[7, 2, 4] &
Finish = [true, true, true, true, false].
10. i=3 is selected as both Finish[4] = false and [0, 0, 2]<=[7, 2,
4]. 11. Work =[7, 2, 4]+[0, 0, 2] =>[7, 2, 6] &
Finish = [true, true, true, true, true].
12. Since Finish is a vector of all true it means there is no
deadlock in this example. 33
 When should we invoke the detection algorithm? The answer depends
on two factors:
1. How often is a deadlock likely to occur?
2. How many processes will be affected by deadlock when it
happens?

The answer may depend on how frequently deadlocks are expected to

occur, as well as the possible consequences of not catching them
immediately. (If deadlocks are not removed immediately when they occur,
then more and more processes can "back up" behind the deadlock,
making the eventual task of unblocking the system more difficult and
possibly damaging to more processes. )
Operating Systems 34
 There are two obvious approaches, each with trade-offs:
 Do deadlock detection after every resource allocation which cannot be immediately
granted. This has the advantage of detecting the deadlock right away, while the
minimum number of processes are involved in the deadlock. The down side of this
approach is the extensive overhead and performance hit caused by checking for
Detection-Algorithm

deadlocks so frequently.

 Do deadlock detection only when there is some clue that a deadlock may have
occurred, such as when CPU utilization reduces to 40% or some other magic number.
Usage

The advantage is that deadlock detection is done much less frequently, but the down
side is that it becomes impossible to detect the processes involved in the original
deadlock, and so deadlock recovery can be more complicated and damaging to more
processes.

Operating Systems
35
 When a detection algorithm determines that a deadlock exists,
several alternatives are available.
 One possibility is to inform the operator that a deadlock has occurred
and to let the operator deal with the deadlock manually.
 Another possibility is to let the system recover from the
deadlock
automatically. There are two options for breaking a deadlock.
 One is simply to abort one or more processes to break the circular
wait.
 The other is to preempt some resources from one or more of the
deadlocked processes.
Operating Systems
36
Process Termination
To eliminate deadlocks by aborting a process, we use one of two methods. In both methods, the system
reclaims all resources allocated to the terminated processes
This method clearly will break the deadlock cycle, but at great expense.
The deadlocked processes may have computed for a long time, and the results of these partial
computations must be discarded and probably will have to be
recomputed later.
. This method incurs considerable
overhead, since after each process is aborted, a deadlock-detection algorithm must be invoked to
determine whether any processes are still deadlocked.

Aborting a process may not be easy.

There are many factors that can go into deciding which processes to terminate next:
1. Process priorities.
2. How long the process has been running, and how close it is to finishing.
3. How many and what type of resources is the process holding. ( Are they easy to preempt and restore? )
4. How many more resources does the process need to complete.
5. How many processes will need to be terminated
6. Whether the process is interactive or batch.
Resource Preemption
When preempting resources to relieve deadlock, there are three important issues to be
addressed:
 Selecting a victim - Deciding which resources to preempt from which processes
involves
many of the same decision criteria outlined earlier.
 Rollback - Ideally one would like to roll back a preempted process to a safe state
prior to the point at which that resource was originally allocated to the process.
Unfortunately it can be difficult or impossible to determine what such a safe state
is,
and so the only safe rollback is to roll back all the way back to the beginning. ( I.e.
abort the process and make it start over. )
 Starvation - How do you guarantee that a process won't starve because its resources
are constantly being preempted? One option would be to use a priority system, and
increase the priority of a process every time its resources get preempted. Eventually
Operating Systems
38 it
Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?
A. In deadlock prevention, the request for resources is always granted if the resulting state is
safe
B. In deadlock avoidance, the request for resources is always granted if the result state is
safe
C. Deadlock avoidance is less restrictive than deadlock prevention
D. Deadlock avoidance requires knowledge of resource requirements a priori

 Consider a system consisting of 4 resources of same type that are share by 3

processes each of which needs at most two resources. Show that the system is
deadlock free

 A system contains three programs and each requires three tape units for
its operation. The minimum number of tape units which the system must
that
havedeadlocks
such never arise is 7
. 39
 Practice Problems

Consider the following Snapshot of the

System

Using Banker’s algorithm, answer the following questions:-

i) How many resources of type A, B, C, D are there?

ii) What are the contents of need matrix?
iii) Find if the system is in safe state? If it is, find the safe
sequence 40
Assume that there are three resources, A, B, and C. There are 4 processes P0 to P3. At T0 we have the following snapshot of
the system:

1. Create the need matrix

2. Is the system in a safe state? Why or
why not

Assume that there are 5 processes, P0 through P4,

and 4 types of resources. At T0 we have the
following system state:
1. Create the need matrix (max - allocation)
2. Use the safety algorithm to test if the system is
in a safe state.
3. If the system is in a safe state, can the following
requests be granted, why or why not? Please
also run the safety algorithm on each request as
necessary.
a. P1 requests (2,1,1,0)
b. P1 requests (0,2,1,0) 41
42
43
44
If Available = [0 0 X 1 1], what is the smallest value of X for which is a
safe state?
A. 1
B. 3
C.2
D. 0

45