Operating System Concepts
Chapter 7 { Deadlocks
Based on the 9th Edition of:
Abraham Silberschatz, Peter B. Galvin and Jreg Gagne:. Operating System
Concepts
Department of Information Technology, College of Business, Law & Governance
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Learning 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
Chapter 7 { Deadlocks Operating System Concepts 2
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Outline
1 System Model
2 Deadlock Characterization
3 Methods for Handling Deadlocks
4 Deadlock Prevention
5 Deadlock Avoidance
6 Deadlock Detection
7 Recovery from Deadlock
Chapter 7 { Deadlocks Operating System Concepts 3
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
System Model
System consists of resources
Resource types R1; R2; : : : ; Rm |CPU cycles, memory space,
I/O devices
Each resource type Ri has Wi instances.
Each process utilizes a resource as follows:
request
use
release
Chapter 7 { Deadlocks Operating System Concepts 4
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously.
1 Mutual exclusion: only one process at a time can use a
resource
2 Hold and wait: a process holding at least one resource is
waiting to acquire additional resources held by other processes
3 No preemption: a resource can be released only voluntarily by
the process holding it, after that process has completed its
task
4 Circular wait: there exists a set fP0; P1; : : : ; Png 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.
Chapter 7 { Deadlocks Operating System Concepts 5
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Characterization
Resource-Allocation Graph
A set of vertices V and a set of edges E.
V is partitioned into two types:
1 P = fP1; P2; : : : ; Png, the set consisting of all the processes in
the system
2 R = fR1; R2; : : : ; Rmg, the set consisting of all resource types
in the system
request edge { directed edge Pi ! Rj
assignment edge { directed edge Rj ! Pi
Chapter 7 { Deadlocks Operating System Concepts 6
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Characterization
Resource-Allocation Graph (Cont.)
Process
Resource Type with 4 instances
Pi requests instance of Rj
Pi
Pi is holding an instance of Rj
Pi
Chapter 7 { Deadlocks Operating System Concepts 7
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Characterization
Example of a Resource-Allocation Graph
R1 R3
R2
R4
P1 P2 P3
Chapter 7 { Deadlocks Operating System Concepts 8
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Characterization
Basic Facts
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
Chapter 7 { Deadlocks Operating System Concepts 9
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Characterization
Resource-Allocation Graph with a Deadlock
R1 R3
R2
R4
P1 P2 P3
Chapter 7 { Deadlocks Operating System Concepts 10
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Characterization
Resource-Allocation Graph with a Cycle But No Deadlock
R2
R1
P3
P4
P2
P1
Chapter 7 { Deadlocks Operating System Concepts 11
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 A deadlocked state occurs whenever .
A. a process is waiting for I/O to a device that does not exist
B. the system has no available free resources
C. every process in a set is waiting for an event that can only be
caused by another process in the set
D. a process is unable to release its request for a resource after use
Answer:
Chapter 7 { Deadlocks Operating System Concepts 12
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 A deadlocked state occurs whenever .
A. a process is waiting for I/O to a device that does not exist
B. the system has no available free resources
C. every process in a set is waiting for an event that can only be
caused by another process in the set
D. a process is unable to release its request for a resource after use
Answer: C
Chapter 7 { Deadlocks Operating System Concepts 12
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 A deadlocked state occurs whenever .
A. a process is waiting for I/O to a device that does not exist
B. the system has no available free resources
C. every process in a set is waiting for an event that can only be
caused by another process in the set
D. a process is unable to release its request for a resource after use
Answer: C
2 One necessary condition for deadlock is , which states
that at least one resource must be held in a nonsharable
mode.
A. hold and wait
B. mutual exclusion
C. circular wait
D. no preemption
Answer:
Chapter 7 { Deadlocks Operating System Concepts 12
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 A deadlocked state occurs whenever .
A. a process is waiting for I/O to a device that does not exist
B. the system has no available free resources
C. every process in a set is waiting for an event that can only be
caused by another process in the set
D. a process is unable to release its request for a resource after use
Answer: C
2 One necessary condition for deadlock is , which states
that at least one resource must be held in a nonsharable
mode.
A. hold and wait
B. mutual exclusion
C. circular wait
D. no preemption
Answer: B
Chapter 7 { Deadlocks Operating System Concepts 12
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 One necessary condition for deadlock is , which states
that a process must be holding one resource and waiting to
acquire additional resources.
A. hold and wait
B. mutual exclusion
C. circular wait
D. no preemption
Answer:
Chapter 7 { Deadlocks Operating System Concepts 13
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 One necessary condition for deadlock is , which states
that a process must be holding one resource and waiting to
acquire additional resources.
A. hold and wait
B. mutual exclusion
C. circular wait
D. no preemption
Answer: A
Chapter 7 { Deadlocks Operating System Concepts 13
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 One necessary condition for deadlock is , which states
that a process must be holding one resource and waiting to
acquire additional resources.
A. hold and wait
B. mutual exclusion
C. circular wait
D. no preemption
Answer: A
2 True or False { The circular-wait condition for a deadlock
implies the hold-and-wait condition.
Answer:
Chapter 7 { Deadlocks Operating System Concepts 13
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 One necessary condition for deadlock is , which states
that a process must be holding one resource and waiting to
acquire additional resources.
A. hold and wait
B. mutual exclusion
C. circular wait
D. no preemption
Answer: A
2 True or False { The circular-wait condition for a deadlock
implies the hold-and-wait condition.
Answer: True
Chapter 7 { Deadlocks Operating System Concepts 13
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 One necessary condition for deadlock is , which states
that a process must be holding one resource and waiting to
acquire additional resources.
A. hold and wait
B. mutual exclusion
C. circular wait
D. no preemption
Answer: A
2 True or False { The circular-wait condition for a deadlock
implies the hold-and-wait condition.
Answer: True
3 True or False { If a resource-allocation graph has a cycle,
the system must be in a deadlocked state.
Answer:
Chapter 7 { Deadlocks Operating System Concepts 13
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 One necessary condition for deadlock is , which states
that a process must be holding one resource and waiting to
acquire additional resources.
A. hold and wait
B. mutual exclusion
C. circular wait
D. no preemption
Answer: A
2 True or False { The circular-wait condition for a deadlock
implies the hold-and-wait condition.
Answer: True
3 True or False { If a resource-allocation graph has a cycle,
the system must be in a deadlocked state.
Answer: False
Chapter 7 { Deadlocks Operating System Concepts 13
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Methods for Handling Deadlocks
Ensure that the system will never enter a deadlock state:
Deadlock prevention
Deadlock avoidence
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
Chapter 7 { Deadlocks Operating System Concepts 14
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Prevention
Restrain the ways request can be made
(a) Mutual Exclusion { not required for sharable resources (e.g.,
read-only files); must hold for non-sharable resources
(b) Hold and Wait { must guarantee that whenever a process
requests a resource, it does not hold any other resources
Require process to request and be allocated all its resources
before it begins execution, or allow process to request
resources only when the process has none allocated to it.
Low resource utilization; starvation possible
Chapter 7 { Deadlocks Operating System Concepts 15
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Prevention
Restrain the ways request can be made (Cont.)
(c) No Preemption {
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
(d) Circular Wait { impose a total ordering of all resource types,
and require that each process requests resources in an
increasing order of enumeration
Chapter 7 { Deadlocks Operating System Concepts 16
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 In a system resource-allocation graph, .
A. a directed edge from a process to a resource is called an
assignment edge
B. a directed edge from a resource to a process is called a request
edge
C. a directed edge from a process to a resource is called a request
edge
D. None of the above
Answer:
Chapter 7 { Deadlocks Operating System Concepts 17
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 In a system resource-allocation graph, .
A. a directed edge from a process to a resource is called an
assignment edge
B. a directed edge from a resource to a process is called a request
edge
C. a directed edge from a process to a resource is called a request
edge
D. None of the above
Answer: C
Chapter 7 { Deadlocks Operating System Concepts 17
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 In a system resource-allocation graph, .
A. a directed edge from a process to a resource is called an
assignment edge
B. a directed edge from a resource to a process is called a request
edge
C. a directed edge from a process to a resource is called a request
edge
D. None of the above
Answer: C
2 True or False { Protocols to prevent hold-and-wait
conditions typically also prevent starvation.
Answer:
Chapter 7 { Deadlocks Operating System Concepts 17
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 In a system resource-allocation graph, .
A. a directed edge from a process to a resource is called an
assignment edge
B. a directed edge from a resource to a process is called a request
edge
C. a directed edge from a process to a resource is called a request
edge
D. None of the above
Answer: C
2 True or False { Protocols to prevent hold-and-wait
conditions typically also prevent starvation.
Answer: False
Chapter 7 { Deadlocks Operating System Concepts 17
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance
Requires that the system has some additional a priori information
available
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
Chapter 7 { Deadlocks Operating System Concepts 18
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance | 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 sequence
< P1; P2; : : : ; Pn > of ALL the processes in the systems such
that 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. That is:
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
Chapter 7 { Deadlocks Operating System Concepts 19
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance | Safe State
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.
Chapter 7 { Deadlocks Operating System Concepts 20
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance | Safe State
Safe, Unsafe, and Deadlock State
deadlock
unsafe
safe
Chapter 7 { Deadlocks Operating System Concepts 21
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance
Avoidance Algorithms
Single instance of a resource type
Use a resource-allocation graph
Multiple instances of a resource type
Use the bankers algorithm
Chapter 7 { Deadlocks Operating System Concepts 22
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance | Avoidance Algorithms
Resource-Allocation Graph Scheme
Claim edge Pi ! Rj indicated that process Pj may request
resource Rj; represented by a dashed line
Claim edge converts to request edge when a process requests
a resource
Request edge converted to an assignment edge when the
resource is allocated to the process
When a resource is released by a process, assignment edge
reconverts to a claim edge
Resources must be claimed a priori in the system
Chapter 7 { Deadlocks Operating System Concepts 23
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance | Avoidance Algorithms
Resource-Allocation Graph
R1
R2
P1 P2
Chapter 7 { Deadlocks Operating System Concepts 24
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance | Avoidance Algorithms
Unsafe State in Resource-Allocation Graph
R1
R2
P1 P2
Chapter 7 { Deadlocks Operating System Concepts 25
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance | Avoidance Algorithms
Resource-Allocation Graph Algorithm
Suppose that process Pi requests a resource Rj
The request can be granted only if converting the request
edge to an assignment edge does not result in the formation
of a cycle in the resource allocation graph
Chapter 7 { Deadlocks Operating System Concepts 26
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance | Avoidance Algorithms
Banker’s Algorithm
Multiple instances
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
Chapter 7 { Deadlocks Operating System Concepts 27
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance | Avoidance Algorithms
Data Structure for the Banker’s Algorithm
Let n = number of processes, and m = number of resources types.
Available: Vector of length m. If available [j] = k, there are k
instances of resource type Rj available
Max: an n × m matrix. If Max[i; j] = k, then process Pi may
request at most k instances of resource type Rj
Allocation: an n × m matrix. If Allocation[i; j] = k then Pi is
currently allocated k instances of Rj
Need: an n × 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]
Chapter 7 { Deadlocks Operating System Concepts 28
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance | Safty Algorithm
(1) Let Work and Finish be vectors of length m and n,
respectively. Initialize:
Work = Available
Finish[i] = false for i = 0; 1; : : : ; n – 1
(2) Find an i such that both:
(a) Finish[i] = false
(b) Needi≤ 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] ==true for all i, then the system is in a safe state
Chapter 7 { Deadlocks Operating System Concepts 29
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance
Resource-Request Algorithm for Process Pi
Notation:
Requesti = request vector for process Pi
If Requesti[j] = k then process Pi wants k instances of resource
type Rj
Chapter 7 { Deadlocks Operating System Concepts 30
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance | Resource-Request Algorithm
(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
Chapter 7 { Deadlocks Operating System Concepts 31
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance
Example of Banker’s Algorithm
5 processes P0; P1; : : : ; P4;
3 resource types:
A (10 instances), B (5 instances), and C (7 instances)
Snapshot at time T0:

Chapter 7 { Deadlocks Operating System Concepts 32
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance
Example of Banker’s Algorithm (Cont.)
The content of the matrix Need is defined as:
Need = Max – Allocation

The system is in a safe state since the sequence
< P1; P3; P4; P2; P0 > satisfies safety criteria
Chapter 7 { Deadlocks Operating System Concepts 33
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Avoidance
Example of Banker’s Algorithm (Cont.) |P1 Request (1, 0, 2)
Check that Request ≤ Available, i.e., (1; 0; 2) ≤ (3; 3; 2)

Executing safety algorithm shows that sequence
< P1; P3; P4; P0; P2 > satisfies safety requirement
Can request for (3,3,0) by P4 be granted?
Can request for (0,2,0) by P0 be granted?
Chapter 7 { Deadlocks Operating System Concepts 34
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 Which of the following statements is true?
A. A safe state is a deadlocked state.
B. A safe state may lead to a deadlocked state.
C. An unsafe state is necessarily, and by definition, always a
deadlocked state.
D. An unsafe state may lead to a deadlocked state.
Answer:
Chapter 7 { Deadlocks Operating System Concepts 35
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 Which of the following statements is true?
A. A safe state is a deadlocked state.
B. A safe state may lead to a deadlocked state.
C. An unsafe state is necessarily, and by definition, always a
deadlocked state.
D. An unsafe state may lead to a deadlocked state.
Answer: D
Chapter 7 { Deadlocks Operating System Concepts 35
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 Which of the following statements is true?
A. A safe state is a deadlocked state.
B. A safe state may lead to a deadlocked state.
C. An unsafe state is necessarily, and by definition, always a
deadlocked state.
D. An unsafe state may lead to a deadlocked state.
Answer: D
2 True or False { The banker’s algorithm is useful in a system
with multiple instances of each resource type.
Answer:
Chapter 7 { Deadlocks Operating System Concepts 35
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 Which of the following statements is true?
A. A safe state is a deadlocked state.
B. A safe state may lead to a deadlocked state.
C. An unsafe state is necessarily, and by definition, always a
deadlocked state.
D. An unsafe state may lead to a deadlocked state.
Answer: D
2 True or False { The banker’s algorithm is useful in a system
with multiple instances of each resource type.
Answer: True
Chapter 7 { Deadlocks Operating System Concepts 35
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 Which of the following statements is true?
A. A safe state is a deadlocked state.
B. A safe state may lead to a deadlocked state.
C. An unsafe state is necessarily, and by definition, always a
deadlocked state.
D. An unsafe state may lead to a deadlocked state.
Answer: D
2 True or False { The banker’s algorithm is useful in a system
with multiple instances of each resource type.
Answer: True
3 True or False { Deadlock prevention and deadlock avoidance
are essentially the same approaches for handling deadlock.
Answer:
Chapter 7 { Deadlocks Operating System Concepts 35
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 Which of the following statements is true?
A. A safe state is a deadlocked state.
B. A safe state may lead to a deadlocked state.
C. An unsafe state is necessarily, and by definition, always a
deadlocked state.
D. An unsafe state may lead to a deadlocked state.
Answer: D
2 True or False { The banker’s algorithm is useful in a system
with multiple instances of each resource type.
Answer: True
3 True or False { Deadlock prevention and deadlock avoidance
are essentially the same approaches for handling deadlock.
Answer: False
Chapter 7 { Deadlocks Operating System Concepts 35
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Detection
Deadloc Detection
Allow system to enter deadlock state
Detection algorithm
Recovery scheme
Chapter 7 { Deadlocks Operating System Concepts 36
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Detection
Deadlock Detection | Single Instance of Each Resource Type
Maintain wait-for graph
Nodes are processes
Pi ! Pj 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
Chapter 7 { Deadlocks Operating System Concepts 37
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Detection
Resource-Allocation graph and Wait-for graph
P3
P5
P4
P1 P2
R2
R1 R3 R4
R5
P3
P5
P4
P1 P2
(a) (b)
Chapter 7 { Deadlocks Operating System Concepts 38
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Detection
Deadlock Detection | Several Instance of a Resource Type
Available: A vector of length m indicates the number of
available resources of each type
Allocation: An n × m matrix defines the number of resources
of each type currently allocated to each process
Request: An n × 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.
Chapter 7 { Deadlocks Operating System Concepts 39
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Detection
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 6= 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
Chapter 7 { Deadlocks Operating System Concepts 40
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Detection
Detection Algorithm (Cont.)
(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
Remark: Algorithm requires an order of O(m × n2) operations to
detect whether the system is in deadlocked state
Chapter 7 { Deadlocks Operating System Concepts 41
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Detection
Example of Detection Algorithm
Five processes P0; P1; : : : ; P4; three resource types
A (7 instances), B (2 instances), and C (6 instances).
Snapshot at time T0:

Sequence < P0; P2; P3; P1; P4 > will result in Finish[i] = true
for all i
Chapter 7 { Deadlocks Operating System Concepts 42
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Detection
Example of Detection Algorithm (Cont.)
P2 requests an additional instance of type C

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
Chapter 7 { Deadlocks Operating System Concepts 43
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Deadlock Detection
Detection Algorithm Usage
When, and how often, to invoke depends on:
How often a deadlock is likely to occur?
How many processes will need to be rolled back? |one for
each disjoint cycle
If detection algorithm is invoked arbitrarily, there may be
many cycles in the resource graph and so we would not be
able to tell which of the many deadlocked processes ’caused’
the deadlock.
Chapter 7 { Deadlocks Operating System Concepts 44
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Recovery from Deadlock
Recovery from Deadlock | Process Termination
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 the process has used
Resources process needs to complete
How many processes will need to be terminated
Is process interactive or batch?
Chapter 7 { Deadlocks Operating System Concepts 45
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Recovery from Deadlock
Recovery from Deadlock | Resource Preemption
Selecting a victim { minimize cost
Rollback { return to some safe state, restart process for that
state
Starvation { same process may always be picked as victim,
include number of rollback in cost factor
Chapter 7 { Deadlocks Operating System Concepts 46
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 Which of the following data structures in the banker’s
algorithm is a vector of length m, where m is the number of
resource types?
A. Need
B. Allocation
C. Max
D. Available
Answer:
Chapter 7 { Deadlocks Operating System Concepts 47
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 Which of the following data structures in the banker’s
algorithm is a vector of length m, where m is the number of
resource types?
A. Need
B. Allocation
C. Max
D. Available
Answer: D
Chapter 7 { Deadlocks Operating System Concepts 47
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 Which of the following data structures in the banker’s
algorithm is a vector of length m, where m is the number of
resource types?
A. Need
B. Allocation
C. Max
D. Available
Answer: D
2 True or False { The wait-for graph scheme is not applicable
to a resource allocation system with multiple instances of each
resource type.
Answer:
Chapter 7 { Deadlocks Operating System Concepts 47
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 Which of the following data structures in the banker’s
algorithm is a vector of length m, where m is the number of
resource types?
A. Need
B. Allocation
C. Max
D. Available
Answer: D
2 True or False { The wait-for graph scheme is not applicable
to a resource allocation system with multiple instances of each
resource type.
Answer: True
Chapter 7 { Deadlocks Operating System Concepts 47
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 Which of the following data structures in the banker’s
algorithm is a vector of length m, where m is the number of
resource types?
A. Need
B. Allocation
C. Max
D. Available
Answer: D
2 True or False { The wait-for graph scheme is not applicable
to a resource allocation system with multiple instances of each
resource type.
Answer: True
3 True or False { A system in an unsafe state will ultimately
deadlock.
Answer:
Chapter 7 { Deadlocks Operating System Concepts 47
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
Quick Quiz
1 Which of the following data structures in the banker’s
algorithm is a vector of length m, where m is the number of
resource types?
A. Need
B. Allocation
C. Max
D. Available
Answer: D
2 True or False { The wait-for graph scheme is not applicable
to a resource allocation system with multiple instances of each
resource type.
Answer: True
3 True or False { A system in an unsafe state will ultimately
deadlock.
Answer: False
Chapter 7 { Deadlocks Operating System Concepts 47
System Model Characterization Handling Prevention Deadlock Avoidance Detection Recovery
End of Chapter 7
Chapter 7 { Deadlocks Operating System Concepts 48