Deadlocks

Chapter Objectives

 To develop a description of deadlocks, which prevent

sets of concurrent processes from completing their tasks
 To present a number of different methods for preventing
or avoiding deadlocks in a computer system.

Operating System Concepts 7.2 Silberschatz, Galvin and Gagne ©

 The Deadlock Problem

 A set of blocked processes

 each holding a resource and waiting to acquire a resource held
by another process in the resource set.
 Example 1
 A system has 2 disk drives.
 P1 and P2 each hold one disk drive and each needs another
one.
 Example 2

 semaphores A and B, initialized to 1

P0 P1
wait (A); wait (B)
wait (B); wait (A)

Operating System Concepts 7.3 Silberschatz, Galvin and Gagne ©

 Bridge Crossing Example

 Traffic only in one direction possible.

 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).
 In some cases, several cars may have to be backed up if a deadlock occurs.
 Observation
 Need checking mechanism whether the car that want to go exist or not.
 Giving priority in one direction  simply deadlock problem resolved.
 Starvation is possible.

Operating System Concepts 7.4 Silberschatz, Galvin and Gagne ©

 Bridge Crossing Example

Operating System Concepts 7.5 Silberschatz, Galvin and Gagne ©

 In OS inside

Operating System Concepts 7.6 Silberschatz, Galvin and Gagne ©

 System Model

 Resource types R1, R2, . . ., Rm

CPU cycles, memory space, files, I/O devices
 Each resource type Ri has Wi instances.

 Each process utilizes a resource as follows:

 request
 e.g., request device, open file, allocate memory
 use
 release
 e.g., release device, close file, free memory

 This sequence should always be followed.

Operating System Concepts 7.7 Silberschatz, Galvin and Gagne ©

 Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously.
Necessary conditions for Deadlock are followings.
 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 a

process that is holding it, after the 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 Pn, and Pn is waiting for
a resource that is held by P0.

Operating System Concepts 7.8 Silberschatz, Galvin and Gagne ©

 Deadlock Characterization

 This is a Necessary Condition

 e.g., not all accesses of mutual exclusion result in
deadlock, but in case of deadlock, mutual exclusion
happens.
 e.g., not all circular wait results in deadlock, but in case
of deadlock, circular wait happens.

 However, when deadlock happens, these four conditions

are satisfied simultaneously.

Operating System Concepts 7.9 Silberschatz, Galvin and Gagne ©

 Resource-Allocation Graph

A set of vertices V and a set of edges E.

 V is partitioned into two types:

 P = {P1, P2, …, Pn}, the set consisting of all processes in the
system.

 R = {R1, R2, …, Rm}, the set consisting of all resources types

in the system.

 request edge – directed edge Pi  Rj

 assignment edge – directed edge Rj  Pi

Operating System Concepts 7.10 Silberschatz, Galvin and Gagne ©

 Resource-Allocation Graph (Cont.)

 Process

 Resource Type with 4 instances

 Pi requests instance of Rj
 Request edge
Pi
Rj
 Pi is holding an instance of Rj

 Assignment edge
Pi
Rj

Operating System Concepts 7.11 Silberschatz, Galvin and Gagne ©

 Example of a Resource Allocation Graph

Operating System Concepts 7.12 Silberschatz, Galvin and Gagne ©

 Resource Allocation Graph With A Deadlock

2 cycles

Operating System Concepts 7.13 Silberschatz, Galvin and Gagne ©

 Resource Allocation Graph With A Cycle But No Deadlock

Observations
After P4 release the resource R2,
P3 can obtain resource R2.

: No cycles  No deadlock
: Cycles  may have deadlock

i.e., Cycle in graph is necessary

condition, not sufficient condition,
for deadlock.

Operating System Concepts 7.14 Silberschatz, Galvin and Gagne ©

 Basic Facts

 If a graph contains no cycles  no deadlock.

 If a graph contains a cycle 

 if only one instance per resource type, then deadlock.
 if several instances per resource type, the possibility of deadlock.

Operating System Concepts 7.15 Silberschatz, Galvin and Gagne ©

 Methods for Handling Deadlocks

 Ensure that the system will never enter a deadlock state.

 Prevention or avoidance

 Allow the system to enter a deadlock state and then recover.

 Detection and recovery

 Ignore the deadlock and pretend that deadlocks never occur in the
system.
 used by most operating systems, including UNIX.
 It is then up to the application developer to write the program that
handle deadlocks.

Operating System Concepts 7.16 Silberschatz, Galvin and Gagne ©

 Methods for Handling Deadlocks

 Deadlock Prevention

 Deadlock Avoidance

 Deadlock Detection and Recovery

Operating System Concepts 7.17 Silberschatz, Galvin and Gagne ©

 Deadlock Prevention
Ensure that at least one of the necessary conditions is false at all time.

 Mutual Exclusion
 This condition is inherently not allowed for nonsharable
resources
 Mutual exclusion must hold at all times
 e.g., printer can not be simultaneously shared by several
processes.
 i.e., must always hold this condition in case of nonsharable
resources.

cf. sharable resource  all requestor can share (request),

thus no deadlock at all.

Operating System Concepts 7.18 Silberschatz, Galvin and Gagne ©

 Deadlock Prevention
Ensure that at least one of the necessary conditions is false at all time.

 Hold and Wait – must guarantee that whenever a process requests a

resource, it does not hold any other resources.
 Method 1
 Only before execution, process can request and be allocated its
resources in one shot method execution (only before starting)
 i.e., after all resources are obtained, the process can execute its
very first start.
 Method 2
 Method 1 is too much inefficient because of “before execution”
 Allow process to request resources only when the process has no
resource at all (even in the middle of executing).
 Problems
 Low resource utilization
 Starvation is also possible
– Repeated requests but cannot eventually acquire all resources
at one time
Operating System Concepts 7.19 Silberschatz, Galvin and Gagne ©
 Deadlock Prevention (Cont.)
Ensure that at least one of the necessary conditions is false at all time.

 No Preemption
 If a process, that is holding some resources, requests another
resource that cannot be immediately allocated to it, then all
currently allocated resources are released.
 That is, preempted.

 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.
 i.e., re-request all its resources again and re-start.

Operating System Concepts 7.20 Silberschatz, Galvin and Gagne ©

 Deadlock Prevention (Cont.)
Ensure that at least one of the necessary conditions is false at all time.

 Circular Wait – impose a total ordering into all resource types, and
each process requests its resources in an increasing order of
enumeration.
 Impose the sequence of resource request
 e.g., F(card drive) = 1, F(disk drive) = 5, F(tape drive) = 7,
F(printer drive) = 12
 If Ri can be requested, then new resource Rj can only be
requested F(Rj) > F(Ri).

 Proof by contradiction
 In this total ordering, there is no circular wait.
 However, let’s assume that there exists circular wait. Then,
F(r0) < F(r1)< … < F(rn) < F(r0). But F(r0) < F(r0) is wrong
because of wrong assumption. So there is no circular wait.

Operating System Concepts 7.21 Silberschatz, Galvin and Gagne ©

 Deadlock Prevention (Cont.)
Ensure that at least one of the necessary conditions is false at all time.

 E.g., dining philosophers problem

 Hold and wait : picking up chopsticks only if both chopsticks are

available

 No Preemption : if other chopstick is not available, release

chopsticks.

 Circular wait : chopstick ordering 1 to 5, with requesting 1-2, 2-3,

3-4, 4-5, 1-5

Operating System Concepts 7.22 Silberschatz, Galvin and Gagne ©

 Deadlock Avoidance
 Deadlock Prevention is implemented by imposing Restriction on
Resource Request.
 e.g., request all before execution, request in total orders, and etc
 Although cycle exists, no deadlock is possible.
 Therefore, low device utilization and low system throughput.
 Possibility of starvation

 Deadlock Avoidance requires that the system has some additional

priori information
 With the knowledge of the complete sequence of requests and
releases for each process, system can avoid a possible future
deadlock

 Deadlock avoidance allows deadlock necessary conditions but it avoid

properly. (e.g., hold and wait is allowed in avoidance)
 Thus avoidance allows better resource utilization than prevention.

Operating System Concepts 7.23 Silberschatz, Galvin and Gagne ©

 Deadlock Avoidance
 Simplest and most useful model
 Each process declare the maximum number of resources of each
type that it may need.
 Not by incremental method, but one shot decision method

Operating System Concepts 7.24 Silberschatz, Galvin and Gagne ©

 Safe State

 When a process requests an available resource, system must

decide if immediate allocation leaves the system in a safe state.

 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 request, can be satisfied by currently available resources +
resources held by all the Pj, with j<i (i.e., previous processes).
 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 7.25 Silberschatz, Galvin and Gagne ©

 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.

Operating System Concepts 7.26 Silberschatz, Galvin and Gagne ©

 Safe, Unsafe, Deadlock State

Operating System Concepts 7.27 Silberschatz, Galvin and Gagne ©

 Resource-Allocation Graph Algorithm

 Claim edge
 Pi  Rj indicated that process Pi may (in the near future)
request resource Rj ; represented by a dashed (dotted) line.
 Maintain total all priori knowledge of resource request.

 Claim edge converts to request edge when a process actually

requests a resource.

 When a resource is released by a process, assignment edge

reconverts to a claim edge.
 i.e., Rj  Pi to Pi --> Rj
 What is the reasoning to keep the claim edge after the
resource is used? (next slide)

Operating System Concepts 7.28 Silberschatz, Galvin and Gagne ©

 Resource-Allocation Graph Algorithm

 What is the reasoning to keep the claim edge after the resource
is used?
 For the same reason it was there in the first place, to tell the
operating system that the process may request this resource.
 Even if the process released the resource, it still might
request it again in the future.

 Resources must be claimed a priori in the system.

 Before Pi starts executing, all claim edges must appear in graph.

 Resource Allocation Graph method is only applicable in case of

single resource instance.
 In case of multiple resource instances  banker’s algorithm

Operating System Concepts 7.29 Silberschatz, Galvin and Gagne ©

 Resource-Allocation Graph For Deadlock Avoidance

Operating System Concepts 7.30 Silberschatz, Galvin and Gagne ©

 Unsafe State In Resource-Allocation Graph

Although R2 is currently free,

we can not allocate it to P2
because it will create a cycle
in a near future by P1

This allocation may lead

unsafe state. But not all
unsafe state lead a deadlock.
P1 may request it later after
Cannot allocate
P2 release R2.
 unsafe vs. deadlock
 Resource utilization of
avoidance is also low.

Operating System Concepts 7.31 Silberschatz, Galvin and Gagne ©

 Banker’s Algorithm

 Proposed by Dijkstra

 Previous policy is not applicable in case of multiple instances of

resource.
 Cycle detection in multiple instance of resource is different domain
 That is, the graph is composed of the nodes which have multiple
sub nodes?  require different algorithm!

 Here is Banker’s Algorithm for multiple instances of resource.

 Deadlock Avoidance algorithm with multiple instances of resource
 Guess why is it called as banking system?

 Less efficient due to the complicated algorithm

Operating System Concepts 7.32 Silberschatz, Galvin and Gagne ©

 Banker’s Algorithm

 Assumption for Banker’s algorithm

 The number of processes in the system is fixed.
 The number of resources in the system is fixed.
 Each process must claim the maximum use.
 When a process gets all its resources, it must return them in a finite
amount of time.

 When processes request resources, they have to wait to evaluate the

safe check.

Operating System Concepts 7.33 Silberschatz, Galvin and Gagne ©

 Data Structures for the Banker’s Algorithm

Let n = the number of processes, and m = the number of resources

 Available: Vector of length m. If available [j] = k, there are k

instances of resource type Rj which is available.
 Max: n x m matrix. If Max [i,j] = k, then process Pi may
request at most k instances of resource type Rj.
 Allocation: n x m matrix. If Allocation[i,j] = k then Pi is
currently allocated k instances of Rj.
 Need: n x m matrix. 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 7.34 Silberschatz, Galvin and Gagne ©

 Resource-Request Algorithm

Request = request vector for process Pi. If Requesti [j] = k then process Pi
wants k instances of resource type Rj.
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;
 Safety check algorithm is applied  next slide.
 If safe  the resources are allocated to Pi.
 If unsafe  Pi must wait, and the old resource-allocation state
is restored

Operating System Concepts 7.35 Silberschatz, Galvin and Gagne ©

 Safety Algorithm

1. Let Work and Finish be vectors of length m and n,

respectively. Initialize:
Work = Available
Finish [i] = false for i - 1,2, …, n.
2. Find i such that both:
(a) Finish [i] = false
(b) Needi  Work // work is available
If no such i exists, go to step 4.

(Virtually, allocate/release Needi )

3. Work = Work + Allocationi //Return the resources

Finish[i] = true
go to step 2.
4. If Finish [i] == true for all i, then the system is in a safe
state. If not, system is unsafe state.
Operating System Concepts 7.36 Silberschatz, Galvin and Gagne ©
 Example of Banker’s Algorithm

 5 processes P0 through P4
 3 resource types
 A (10 instances), B (5instances), and C (7 instances).

 Snapshot at time T0:

Allocation Max Available
ABC ABC ABC
P0 010 753 332
P1 200 322
P2 302 902
P3 211 222
P4 002 433

Operating System Concepts 7.37 Silberschatz, Galvin and Gagne ©

 Example (Cont.)

 The content of the matrix Need is defined to be Max – Allocation.

Need
ABC
P0 743
P1 122
P2 600
P3 011
P4 431

 The system is in a safe state since executing safety algorithm

produce the safe sequence < P1, P3, P4, P2, P0>, which satisfies
safety criteria.

Operating System Concepts 7.38 Silberschatz, Galvin and Gagne ©

 Example: P1 additional request (1,0,2)
allocation of P1 (2,0,0) + (1,0,2)  (3,0,2)

 Check that the additional request (1,0,2) for P1  Available (3,3,2)  true.
 Allocation : (2,0,0)  (3,0,2), Available (3,3,2)  (2,3,0), Need (1,2,2)  (0,2,0)

Allocation Need Available

ABC ABC ABC
P0 010 743 230
P1 302 020
P2 301 600
P3 211 011
P4 002 431

 Executing safety algorithm shows that sequence <P1, P3, P4, P0, P2> satisfies
safety requirement.
 P1 : (2,3,0) > (0,2,0) then (2,3,0)+(3,0,2)=(5,3,2) // work (allocation) + allocation
 P3 : (5,3,2,) > (0,1,1) then (5,3,2)+(2,1,1)=(7,4,3)
 And so on..

Operating System Concepts 7.39 Silberschatz, Galvin and Gagne ©

 Example : P4 additional request (3,3,0)

Allocation Need Available

ABC ABC ABC
P0 010 743 230
P1 302 020
P2 301 600
P3 211 011
P4 002 431

 Can additional request for (3,3,0) by P4 be granted?

 Resource is not available
 Request4 (3,3,0) > Available (2,3,0)

Operating System Concepts 7.40 Silberschatz, Galvin and Gagne ©

 Example : P0 additional request (0,2,0)

Allocation Need Available

ABC ABC ABC
P0 010 743 230
P1 302 020
P2 301 600
P3 211 011
P4 002 431

 Can additional request for (0,2,0) by P0 be granted?

 Resource is available, but no safety sequence
 P0 (0,3,0) (7,2,3) (2,1,0) (2,1,0) can not be satisfied in any one of Need
 Red number in Need

Operating System Concepts 7.41 Silberschatz, Galvin and Gagne ©

 Evaluation

 Evaluation of Banker’s algorithm

 System overhead to execute avoidance algorithm

 No dynamic method
 All resources and users are fixed before executing.
 Can not be applied in dynamic environment

 1st and 3rd assumption is difficult to preserve in real world. (Slide 7.33)
 Therefore, theoretical approach
 If the assumptions are satisfied, banker’s algorithm (deadlock
avoidance) can start its execution.
– Deadlock prevention can not even start its execution(because
one shot allocation, no hold and wait, etc), so it allows better
resource utilization than deadlock prevention.

Operating System Concepts 7.42 Silberschatz, Galvin and Gagne ©

 Deadlock Detection

 Deadlock Detection & Recovery allows system to enter deadlock

state
 Overhead for the execution of deadlock detection algorithm.
 Overhead for recovery

 Detection algorithm
 Single instance resource
Use wait-for graph

 Multiple instance resource
 Detection algorithm proposed by Shoshani and Coffman
 Similar data structure, compared to Banker Algorithm.
 Algorithm for multiple instance resource type

 It requires recovery schemes

Operating System Concepts 7.43 Silberschatz, Galvin and Gagne ©

 Single Instance of Resource Type

 Maintain wait-for graph (see next slide first)

 Nodes are only processes.
 Pi  Pj if Pi is waiting for Pj.

 The number of nodes are reduced, so the overhead of cycle

detection algorithm could be reduced.

 Periodically invoke an algorithm that searches for a cycle in the

graph.

 An algorithm to detect a cycle in a wait-for graph

 requires an order of n2 operations, where n is the number of
vertices in the graph.
 Only allowed in a single instance of resource type

Operating System Concepts 7.44 Silberschatz, Galvin and Gagne ©

 Resource-Allocation Graph and Wait-for Graph

Resource-Allocation Graph Corresponding wait-for graph

Operating System Concepts 7.45 Silberschatz, Galvin and Gagne ©

 Several Instances of Resource Type
proposed by Shoshani and Coffman

 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.

 No Max and No Need, But Request

 No priori information, i.e., No Max, required, and thus No Need
 c.f., Need : future request  Deadlock avoidance
 Instead, required current request

Operating System Concepts 7.46 Silberschatz, Galvin and Gagne ©

 Detection Algorithm
1. Let Work and Finish be vectors of length m and n, respectively Initialize:
(a) Work = Available
For i = 1,2, …, n,
if Allocationi  0, then Finish[i] = false;
otherwise, Finish[i] = true. //zero allocation means Pi is finished?
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.

Operating System Concepts 7.47 Silberschatz, Galvin and Gagne ©

 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:

Allocation Request Available
ABC ABC ABC
P0 010 000 000
P1 200 202
P2 303 000
P3 211 100
P4 002 002

 Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true for all i.

Operating System Concepts 7.48 Silberschatz, Galvin and Gagne ©

 Example (Cont.)

 P2 requests an additional instance of type C. P2 request (0,0,0)(0,0,1)

Request
ABC
P0 000
P1 202
P2 001
P3 100
P4 002
 State of system?
 We can reclaim resources held by process P0 , then available is (0,0,0) 
(0,1,0), but still insufficient resources to fulfill at least one of all other
processes requests.
 Deadlock exists, consisting of processes P1, P2, P3, and P4
 With request (0,0,1) for P2, it can not be allocated to remained
processes.

Operating System Concepts 7.49 Silberschatz, Galvin and Gagne ©

 Detection-Algorithm Usage

 When, and how often, to invoke detection algorithm depends on:

 How often a deadlock is likely to occur?

 Simple and idle system vs. large and busy system

 How many processes will need to be rolled back?

 Each time deadlock occurs, the complex cycle exists 
then frequent detection execution required.
 One deadlock for each disjoint cycle

Operating System Concepts 7.50 Silberschatz, Galvin and Gagne ©

 Recovery from Deadlock

 After deadlock is detected, recovery algorithm should be executed

 Two general approach for recovery from deadlock

 Process Termination
 Resource Preemption

Operating System Concepts 7.51 Silberschatz, Galvin and Gagne ©

 Recovery from Deadlock:
Process Termination
 Two solutions
 Abort all deadlocked processes.
 Abort one process at a time until the deadlock cycle is
eliminated.

 In which order should we choose to abort?

 Priority of the process.
 How long process has computed, and how much longer to
completion.
 Resources that the process has used.
 Resources that process needs to complete.
 How many processes will need to be terminated.
 Is process interactive or batch?

Operating System Concepts 7.52 Silberschatz, Galvin and Gagne ©

 Recovery from Deadlock:
Resource Preemption

 Selecting a victim – minimize cost.

 Rollback – return to a safe state, restart process from that state.

 Checkpoint and restart method
 Return to the latest (known safe state) checkpoint and restart it.

 Starvation – sometimes, same process may always be picked as

victim.
 include the number of rollbacks as a cost factor.

Operating System Concepts 7.53 Silberschatz, Galvin and Gagne ©

Thank You