Chapter 8: Deadlocks

System Model
Deadlock Characterization
Methods for Handling Deadlocks
Deadlock Prevention
Deadlock Avoidance
Deadlock Detection
Recovery from Deadlock

Operating System Concepts

8.1

Bridge Crossing Example

Traffic only in one direction.

Each section of a bridge can be viewed as a resource.
If a deadlock occurs, it can be resolved if one car backs up
(preempt resources and rollback).
Several cars may have to be backed up if a deadlock occurs.
Starvation is possible.

Operating System Concepts

8.2

1
 System Model
A set of blocked processes each holding a resource and waiting to
acquire a resource held by another process in the set.
Example of a deadlock problem:
System has 2 tape drives.
Process P1 and process P2 each hold one tape drive and each
needs another one.
A system consists of a finite number of resources to be distributed
among a number of competing processes.
Resource types R1, R2, . . ., Rm
CPU cycles, memory space, I/O devices
The resources may be either physical (printers, tape drives, memory
space, and CPU cycles) or logical (files and semaphores).
A process must request a resource before using it, and must release
the resource after using it.

Operating System Concepts

8.3

System Model
A process may utilize a resource in only the following
sequence:
1. Request: If the request cannot be granted immediately,
then the requesting process must wait until it can
acquire the resource.
2. Use: The process can operate on the resource (ex., print
on printer).
3. Release: The process releases the resource.
The request and release of resources are system calls
(examples: request and release device, open and close file,
and allocate and free memory system calls).
Request and release of other resources can be
accomplished through the wait and signal operations on
semaphores.

Operating System Concepts

8.4

2
 Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously.
Mutual exclusion: only one process at a time can use a
resource. If another process requests that resource, the
requesting process must be delayed until the resource has
been released.
Hold and wait: a process is holding at least one resource and
is waiting to acquire additional resources held by other
processes (i.e., you hold a resource and wait for another one).
No preemption: a resource can be released only voluntarily
by the process holding it, after that process has completed its
task (ex., in FCFS a process use the CPU until it terminates).
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, , Pn1 is
waiting for a resource that is held by Pn, and P0 is waiting for a
resource that is held by P0.
Operating System Concepts
8.5

Resource-Allocation Graph

A deadlock can be described in terms of a directed graph

called system resource-allocation graph.
A set of vertices V and a set of edges E.
V is partitioned into two types:
7 P = {P1, P2, , Pn}, the set consisting of all the
processes in the system.
7 R = {R1, R2, , Rm}, the set consisting of all resource
types in the system.
request edge directed edge Pi Rj
assignment edge directed edge Rj Pi

Operating System Concepts

8.6

3
 Resource-Allocation Graph (Cont.)

Process:
Resource type with 4 instances of same type:
For example four printers

Pi requests instance of Rj Pi
Rj

Pi is holding an instance of Rj
Pi
Rj

Operating System Concepts

8.7

Example of a Resource Allocation Graph

Process State:
P1 is holding an instance
of R2 and waiting for an
instance of R1.
P2 is holding an instance
of R1 and R2, and is waiting
for an instance of R3.
P3 is holding an instance
of R3.
The graph does not contain any
cycles. What does that mean?

Operating System Concepts

8.8

4
 Resource Allocation Graph With A Deadlock
Two minimal cycles exist in the
system:
P1 R1 P2 R3 P3 R2 P1
P2 R3 P3 R2 P2
Processes P1, P2, P3 are
deadlocked.
P2 is waiting for R3, which is held
by P3.
P3 is waiting for P1 or P2 to
release R2.
P1 is waiting for P2 to release R1.

Operating System Concepts

8.9

Resource Allocation Graph With A Cycle But No Deadlock

We have a cycle:
P1 R1 P3 R2 P1
There is no deadlock.
P4 may release its instance of
R2 and that resource can then
be allocated to P3 breaking the
cycle.
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.
Operating System Concepts
8.10

5
 Methods for Handling Deadlocks
Ensure that the system will never enter a deadlock
state.
The system can use either a deadlock prevention
or avoidance.
Allow the system to enter a deadlock state and then
recover.
Ignore the problem and pretend that deadlocks never
occur in the system; used by most operating systems,
including UNIX (need to restart your computer if a
deadlock occur).

Operating System Concepts

8.11

Deadlock Prevention
For a deadlock to occur, each of the four necessary conditions
must hold.
By ensuring that at least one of these conditions cannot hold, we
can prevent the occurrence of a deadlock.
1. Mutual Exclusion not required for sharable resources; must
hold for non-sharable resources.
For example, a printer cannot be simultaneously shared by
several processes.
A process never needs to wait for a sharable resource.
2. Hold and Wait must guarantee that whenever a process
requests a resource, it does not hold any other resources.
One protocol requires each process to request and be
allocated all its resources before it begins execution,
Or another protocol allows a process to request resources
only when the process has none. So, before it can request
any additional resources, it must release all the resources
that it is currently allocated.
Operating System Concepts
8.12

6
 Deadlock Prevention (Cont.)

Example to illustrate the difference between the

two protocols: A process copies data from a tape
drive to a disk file, sorts the disk file, and then
prints the results to a printer.

Tape Disk Printer

Protocol 1: request all tape, disk, printer and hold

for entire execution; note printer will be idle for a
long time.
Protocol 2: request tape and disk only after
copying release both then request disk and printer
after printing release both.

Operating System Concepts

8.13

Deadlock Prevention (Cont.)

Tow main disadvantages to these protocols:

1. Low resource utilization: since many of the
resources may be allocated but unused for a long
time.
2. starvation possible: A process that needs several
popular resources may have to wait indefinitely,
because at least one of the resources that it
needs is always allocated to some other process.

Operating System Concepts

8.14

7
 Deadlock Prevention (Cont.)
3. No Preemption To ensure that this condition does
not hold, we can use the following protocol:
If a process that is holding some resources requests
another resource that cannot be immediately
allocated to it, then all resources currently being
held are released.
Preempted resources are added to the list of
resources for which the process is waiting.
Process will be restarted only when it can regain its
old resources, as well as the new ones that it is
requesting.

Operating System Concepts

8.15

Deadlock Prevention (Cont.)

4. Circular Wait To ensure that the circular-wait condition
never holds is to determine a total ordering of all resource
types, and to require that each process requests resources
in an increasing order of enumeration.
Example: Let R={R1, R2, , Rm} be the set of resource
types.
Assign to each resource type a unique integer number to
compare two resources and to determine whether one
proceeds another in ordering.
For example: If the set of resource types R includes tape
drives, disk drives, and printers, then a function F might
be defined as follows:
F(tape drive)= 1; F(disk drive)= 5; F(Printer)= 12.

Operating System Concepts

8.16

8
 Deadlock Prevention (Cont.)
A protocol to prevent deadlocks: Each process can
request resources only in an increasing order of
enumeration.
A process can initially request any number of instances
of a resource type Ri.
1. That process can request instances of resource type
Rj if and only if F(Rj)>F(Ri).
From the previous example; a process wants to use
the tape drive and printer at the same time, must first
request the tape drive and then the printer.
2. When a process requests an instance of resource type
Rj, it has released any resources Ri such that
F(Ri)>=F(Rj).
By applying 1 and 2 then the circular-wait condition
cannot hold.

Operating System Concepts

8.17

Deadlock Avoidance

Requires that the system has some additional a priori

information about how resources are to be requested.
Simplest and most useful model requires that each
process declare the maximum number of resources of
each type that it may need.
The deadlock-avoidance algorithm dynamically
examines the resource-allocation state to ensure that
there can never be a circular-wait condition.
Resource-allocation state is defined by the number of
available and allocated resources, and the maximum
demands of the processes.

Operating System Concepts

8.18

9
 Safe State
A state is safe if the system can allocate resources to each process
(up to its maximum) in some order and still avoid a deadlock.
System is in safe state if there exists a safe sequence of all
processes.
Sequence <P1, P2, , Pn> is safe if for each Pi, the resources that
Pi can still request can be satisfied by currently available resources
+ resources held by all the Pj, with j<i.
If Pi resource needs are not immediately available, then Pi can
wait until all Pj have finished.
When Pj is finished, Pi can obtain needed resources, execute,
return allocated resources, and terminate.
When Pi terminates, Pi+1 can obtain its needed resources, and
so on.

Operating System Concepts

8.19

Safe State Example

A system with 12 tape drives and 3 processes; P0, P1, P2.
The following Table at state t0.
Process Max Need Current hold 9 tape drives
total at t0 been
P0 10 5
held, so a total of
P1 4 2 3 tape drives are
P2 9 2 free available.
Release 4 Release 10 Release 9

P1 P0 P2

Hold 2 Request 2 Hold 5 Request 5 Hold 2 Request 7

At t0 the system is in a safe state, because the sequence
<P1, P0, P2> satisfies the safety condition.

Operating System Concepts

8.20

10
 Safe State Example (Cont.)

For unsafe state suppose at t1, P2 requests and is holding

one more tape drive as shown below:

Process Max Need Current hold 10 tape drives

total at t1 been
P0 10 5
held, so a total of
P1 4 2 2 tape drives are
P2 9 3 free available.

This sequence <P1, P0, P2> is unsafe; only P1 can be

satisfied. P0 and P2 must waits yielding to a deadlock.

Operating System Concepts

8.21

Basic Facts
If a system is in safe state
no deadlocks.
If a system is in unsafe
state possibility of
deadlock.
Avoidance ensure that
a system will never enter
an unsafe state.
Safe, unsafe , deadlock
state spaces.

Operating System Concepts

8.22

11
 Resource-Allocation Graph Algorithm
Claim edge Pi Rj indicated that process Pi may request
resource Rj; represented by a dashed line.
Claim edge converts to request edge when a process
requests a resource.
When a resource is released by a process, assignment edge
reconverts to a claim edge.
Resources must be claimed a priori in the system.
If a cycle is found in a graph, then the allocation will put the
system in an unsafe state.
If no cycle exists, then the allocation of the resource will
leave the system in a safe state.

Operating System Concepts

8.23

Resource-Allocation Graph For Deadlock Avoidance

Figure 1: Figure 2:

Figure 2 shows an unsafe state in a resource-allocation graph, because

there is a cycle in the graph.
The resource-allocation graph algorithm is not applicable to a resource-
allocation system with multiple instances of each resource type.

Operating System Concepts

8.24

12
 Bankers Algorithm
Bankers algorithm is applicable to a resource-allocation
system with multiple instances of each type.
From its name, it could be used in a banking system to
ensure that the bank never allocates its available cash
such that it can no longer satisfy the needs of all
customers.
Each process must a priori claim maximum use.
When a process requests a resource it may have to
wait.
When a process gets all its resources it must return
them in a finite amount of time.

Operating System Concepts

8.25

Data Structures for the Bankers Algorithm

Let n = number of processes, and m = number of resource types.
Available: Vector of length m indicates the number of
available resources of each type. If available [j] = k, there are
k instances of resource type Rj available.
Max: n x m matrix defines the maximum demand of each
process. If Max [i,j] = k, then process Pi may request at most
k instances of resource type Rj.
Allocation: n x m matrix defines the number of resources of
each type currently allocated to each process. If Allocation[i,j]
= k then Pi is currently allocated k instances of of resource
type Rj.
Need: n x m matrix indicates the remaining resource need of
each process. If Need[i,j] = k, then Pi may need k more
instances of Rj to complete its task.
Need [i,j] = Max[i,j] Allocation [i,j].

Operating System Concepts

8.26

13
 Safety Algorithm (Bankers Algorithm)
1. Let Work and Finish be vectors of length m and n, respectively.
Initialize:
Work := Available
Finish [i] = false for i - 1,3, , n.
2. Find an i such that both:
(a) Finish [i] = false
(b) Needi Work
If no such i (no process) exists, go to step 4.
3. Work := Work + Allocationi
Finish[i] := true
go to step 2.
4. If Finish [i] = true for all i, then the system is in a safe state.

Operating System Concepts

8.27

Resource-Request Algorithm for Process Pi

Requesti = request vector for process Pi. If Requesti [j] = k then process Pi
wants k instances of resource type Rj.
When a request for resources is made by process Pi, the following actions
are taken:
1. If Requesti Needi go to step 2. Otherwise, raise error condition,
since process has exceeded its maximum claim.
2. If Requesti Available, go to step 3. Otherwise Pi must wait, since
resources are not available.
3. Pretend to allocate requested resources to Pi by modifying the state
as follows:
Available := Available - Requesti;
Allocationi := Allocationi + Requesti;
Needi := Needi Requesti;;
If safe the resources are allocated to Pi.
If unsafe Pi must wait, and the old resource-allocation state is
restored

Operating System Concepts

8.28

14
 Example of Bankers Algorithm
5 processes P0 through P4; 3 resource types A (10 instances),
B (5 instances, and C (7 instances).
Snapshot at time T0: (Need= Max - Allocation)
The system is in a safe state since the sequence
< P1, P3, P4, P0, P2> satisfies safety criteria.
Process Allocation Max Available Need Available after
Release
A B C A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2 7 4 3 7 5 5

P1 2 0 0 3 2 2 1 2 2 5 3 2

P2 3 0 2 9 0 2 6 0 0 10 5 7

P3 2 1 1 2 2 2 0 1 1 7 4 3

P4 0 0 2 4 3 3 4 3 1 7 4 5

Operating System Concepts

8.29

Example (Cont.): P1 request (1,0,2)

Check that Request Need (that is, (1,0,2) (1,2,2) is true).
Check that Request Available (that is, (1,0,2) (3,3,2) is true).
Allocation Need Available Available After Release
ABC ABC ABC ABC
P0 010 743 230 755
P1 302 020 532
P2 302 600 10 5 7 (finish)
P3 211 011 743
P4 002 431 745
Executing safety algorithm shows that sequence <P1, P3, P4, P0, P2>
satisfies safety requirement.

Operating System Concepts

8.30

15
 Example (Cont.)
Can request for (3,3,0) by P4 be granted?
Check Request Need (that is, (3,3,0) (4,3,1)) is true).
Check Request Available (that is, (3,3,0) (2,3,0) is
not true).
So, the request for (3,3,0) by P4 can not be granted.
Can request for (0,2,0) by P0 be granted?
Check Request Need (that is, (0,2,0) (7,4,3) is true).
Check Request Available (that is, (0,2,0) (2,3,0) is
true).
However, since Available becomes 2 for A, 1 for B, and 0
for C, we can not find a sequence to satisfy the safety
requirements. Therefore, the resulting state is unsafe
and the request for (0,2,0) by P0 can not be granted.

Operating System Concepts

8.31

Deadlock Detection
If a system does not employ a deadlock prevention algorithm or
a deadlock avoidance algorithm, then a deadlock situation may
occur.
Therefore, the system must provide:
Detection: an algorithm that examines the state of the
system to determine whether a deadlock has occurred.
Recovery: an algorithm to recover from the deadlock.
A detection and recovery scheme requires overhead that
includes:
Run-time costs of maintaining the necessary information.
Executing the detection algorithm.
The potential losses inherent in recovering from a deadlock.

Operating System Concepts

8.32

16
 Single Instance of Each Resource Type
A deadlock detection algorithm uses a variant of the resource-
allocation graph called wait-for graph.
An edge from Pi to Pj in a wait-for graph implies that process Pi is
waiting for process Pj to release a resource that Pi needs.
An edge Pi Pj exists in a wait-for graph if and only if the
corresponding resource-allocation graph contains two edges
Pi Rq and Rq Pj for some resource Rq.
A deadlock exists in the system if and only if the wait-for graph
contains a cycle.
To detect deadlocks, the system needs to:
Maintain the wait-for graph.
Periodically invoke an algorithm that searches for a cycle in the
graph.
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.

Operating System Concepts

8.33

Resource-Allocation Graph And Wait-for Graph

Resource-Allocation Graph Corresponding wait-for graph

The wait-for graph scheme is not applicable to a resource-
allocation system with multiple instances of each resource type.
Operating System Concepts
8.34

17
 Several Instances of a Resource Type

The algorithm employs several time-varying data structures

that are similar to those used in the bankers algorithm:
Note: n is number of processes in the system and m is the
number of resource types.
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 System Concepts

8.35

Detection Algorithm

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 (Pi not involved in deadlock)
If no such i exists, go to step 4.

Operating System Concepts

8.36

18
 Detection Algorithm (Cont.)
3. Work := Work + Allocationi
Finish[i] := true (Assume Pi will require no more
resources to complete).
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 m x n2 operations to
detect whether the system is in deadlocked state.

Operating System Concepts

8.37

Example of Detection Algorithm

Five processes P0 through P4; three resource types
A (7 instances), B (2 instances), and C (6 instances).
Snapshot at time T0:
Ava-New Allocation Request Available Request (New)
ABC ABC ABC ABC
010 P0 010 000 000 000
724 P1 200 202 202
313 P2 303 000 001
524 P3 211 100 100
726 P4 002 002 002
We claim that the system is not in a deadlock state.
Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true for all i.
Operating System Concepts
8.38

19
 Example (Cont.)
Suppose P2 requests an additional instance of type C.
The Request matrix is modified as shown in the
previous slide (New Request).
State of system?
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.

Operating System Concepts

8.39

Recovery from Deadlock

There are two options for breaking a deadlock:

To abort one or more processes to break the
circular wait (Process Termination).
To preempt some resources from one or more of
deadlock processes (Resource Preemption).

Operating System Concepts

8.40

20
 Recovery from Deadlock: Process Termination
Two methods to eliminate deadlocks by aborting a process. In both
methods, the system reclaims all resources allocated to the
terminated processes:
Abort all deadlocked processes: It will break the deadlock
cycle, but a great expense.
Abort one process at a time until the deadlock cycle is
eliminated: Overhead, since, after each process aborted a
deadlock-detection algorithm must be invoked to determine
whether any processes are still deadlocked.
In which order should we choose to abort?
Priority of the process.
How long process has computed, and how much longer to
completion.
Resources the process has used.
Resources process needs to complete.
How many processes will need to be terminated.
Is process interactive or batch?
Operating System Concepts
8.41

Recovery from Deadlock: Resource Preemption

If preemption is required to deal with deadlocks, then

three issues need to be addressed:
Selecting a victim which resources and which
processes are to be preempted? (minimize cost)
Rollback If we preempt a resource from a process,
what should be done with that process? We must roll
back the process to some safe state, and restart it
from that state.
Starvation That is same process may always be
picked as victim, include number of rollback is cost
factor. Insure that a starvation will not occur. That is
Guarantee that resources will not always be
preempted from the same process.
Operating System Concepts
8.42

21
 Combined Approach to Deadlock Handling
Combine the three basic approaches
prevention
avoidance
detection
allowing the use of the optimal approach for each of
resources in the system.
Partition resources into hierarchically ordered classes.
Use most appropriate technique for handling deadlocks
within each class.

Operating System Concepts

8.43

22