Transcript Deadlocks

Course Overview
Principles of Operating Systems







Introduction
Computer System
Structures
Operating System
Structures
Processes
Process Synchronization
Deadlocks
CPU Scheduling
© 2000 Franz Kurfess








Memory Management
Virtual Memory
File Management
Security
Networking
Distributed Systems
Case Studies
Conclusions
Deadlocks 1
Chapter Overview
Deadlock and Starvation





Motivation
Objectives
Deadlock Principles
Starvation
Deadlock Conditions




Mutual Exclusion
Hold and Wait
No Preemption
Circular Wait
© 2000 Franz Kurfess

Dealing with Deadlock






Deadlock Prevention
Deadlock Avoidance
Deadlock Detection and
Recovery
Deadlock and Operating
Systems
Important Concepts and
Terms
Chapter Summary
Deadlocks 2
Motivation
 there
is the potential of conflicts for processes who
cooperate or share resources
 deadlock and starvation are the most severe
conflicts, leading to the permanent halting of the
processes affected
 common practice is not satisfactory
 ad
hoc solutions
 neglecting the problem
© 2000 Franz Kurfess
Deadlocks 3
Objectives
 recognize
potential problems with the coordination
of activities for several processes (cooperation or
resource sharing)
 understand the necessary conditions for a formal
deadlock situation
 distinguish deadlocks from other reasons for
“frozen” systems
 analyze the status of a system based on resource
allocation graphs
 apply deadlock prevention, avoidance, and detection
principles and algorithms to sets of processes
© 2000 Franz Kurfess
Deadlocks 4
“Deadlocked” Systems
term “deadlock” is often used casually to indicate
that the computer system doesn’t respond (it is
“frozen”)
 there are other reasons for a system to be in such a
state
 the
 endless
loop
 waiting for an event that may never occur
 synchronization between processes
 deadlock
needs to be defined carefully to distinguish
it from these other reasons
© 2000 Franz Kurfess
Deadlocks 5
Deadlock Principles
 permanent
mutual blocking of a set of resources that
either compete for resources or cooperate on a task
 deadlocked processes don’t make any progress,
and never finish their execution
 deadlocked processes may tie up system resources
© 2000 Franz Kurfess
Deadlocks 6
Starvation
a
process can’t proceed because other processes
always have the resources it needs
 the request of the process is never satisfied
 in principle, it is possible to get the resource, but
doesn’t happen because of
 low
priority of the process
 timing of resource requests
 ill-designed resource allocation or scheduling algorithm
 different
© 2000 Franz Kurfess
from deadlock
Deadlocks 7
Examples Starvation
 batch
processes with low priority in a heavily used
time-sharing system
 crossing a very busy road
 trying to call a very popular phone number
 NJIT
modem pool
 radio station giveaways
 getting
into a very popular course with limited
enrollment
© 2000 Franz Kurfess
Deadlocks 8
Solution Starvation
 fairness:
each process gets its fair share of all
resources it requests
 how
is fair defined?
 how is it enforced?
 aging
 the
priority of a request is increased the longer the
process waits for it
© 2000 Franz Kurfess
Deadlocks 9
Resource Types
 reusable
resources
 can
be used repeatedly by different processes
 does not imply simultaneous use
 OS examples: CPU, main memory, I/O devices, data
structures
 consumable
resources
 are
produced by one entity, and consumed by another
 reuse is not possible, or impractical
 OS examples: messages
© 2000 Franz Kurfess
Deadlocks 10
Example Reusable Resources
 main
memory allocation
 two
processes make successive requests for main
memory
 the overall memory size is 16 MByte
Process A
request 5 MBytes;
request 8 MBytes;
Process B
request 7 MBytes;
request 7 MBytes;
 deadlock
no process can proceed unless one gives up some
memory (preemption)
 frequent solutions: preallocation, virtual memory

© 2000 Franz Kurfess
Deadlocks 11
Example Consumable Resources
 message
passing
 two
processes wait for a message from each other, and
then send one to each other
 receive operation is blocking (process can’t continue)
Process A
receive (B);
send (B);
Process B
receive (A);
send(A);
 deadlock
no process can proceed because it is waiting for a
message from the other
 no easy solution

© 2000 Franz Kurfess
Deadlocks 12
Deadlock on Resources
 usually
based on design or programming errors
 these errors may be difficult or impossible to avoid
 interaction
between different modules
 interaction between independent programs
 very
difficult to detect
 may
not occur during testing
 may occur very infrequently in the field
© 2000 Franz Kurfess
Deadlocks 13
Resource Allocation Graphs
 processes
 hold,
request and release resources
 resources
 resource
types specify a class of resources
 individual instances are identical from the process’
perspective
 resource
assignment
 an
instance of a resource is currently held by a process
 indicated by an assignment edge
 resource
request
a
process wants to acquire another instance of a resource
 indicated by a request edge
© 2000 Franz Kurfess
Deadlocks 14
Resource Allocation Graphs
R1
R2
R3
Assignment
Edge
P1
P2
P3
P4
P5
Request
Edge
R4
© 2000 Franz Kurfess
R5
R6
R7
Deadlocks 15
Resource Allocation Graph
with Cycle

R1

P1
P1 -> R1 -> P2 -> R1,
P1 -> R1 -> P2 -> R3 -> P1
P2


R2
© 2000 Franz Kurfess
there is at least one cycle in
the graph
processes and resources
involved
 e.g.
R3
is there a deadlock?
no, we have enough resources
to satisfy all requests
Deadlocks 16
Resource Allocation Graph
with Deadlock

R1

P1
R2

P2
R3

there must be at least one
cycle in the graph
 cycles are candidates for
deadlock
is there a deadlock?
yes, there are not enough
resources in R2 to satisfy all
requests by P1 and P2
processes and resources
involved

© 2000 Franz Kurfess
P1 -> R2 -> P2 -> R2
Deadlocks 17
Cycles and Deadlocks
 if
there is a cycle in the resource allocation graph,
there may be a deadlock
 cycles
a
without deadlock are possible
deadlock can only occur if there is a cycle
 no
deadlock without a cycle
© 2000 Franz Kurfess
Deadlocks 18
Safe States
a
system is in a safe state if resources can be
allocated to processes without getting into a
deadlock
 the
order in which resources are allocated must be flexible
a
sequence of processes is a safe sequence if the
resources that a process may request are satisfiable
by the currently available resources plus resources
held by other processes
 this
must hold for all processes in the system
 the process may have to wait until other processes are
finished
© 2000 Franz Kurfess
Deadlocks 19
Safe State Space
 if
a system is in a safe state there are no deadlocks
 in an unsafe state, there is a possibility of deadlocks
Deadlock
unsafe
safe
© 2000 Franz Kurfess
Deadlocks 20
Dining Philosophers, Again
var chopstick: array [0..4] of semaphore;
repeat
wait(chopstick[i]);
wait(chopstick[i + 1 mod 5]);
...
-- eat
...
signal(chopstick[i]);
signal(chopstick[i + 1 mod 5]);
...
-- think
...
until false;
R4
R0
P4
P1
R1
R3
P3
© 2000 Franz Kurfess
P0
R2
P2
Deadlocks 21
Why Deadlock?
 reasons
for potential deadlock
 mutual

exclusion
two philosophers cannot use a chopstick simultaneously
 use
a protocol that prevents philosophers from
 picking up their chopsticks simultaneously
 picking up one chopstick if the other is not available
 supervisor


an authority that can tell philosophers what to do
may use preemption of resources
 seating

philosopher
arrangement
don’t seat philosophers around a round table
 may require more n+1 chopsticks for n philosophers
 several
conditions must hold simultaneously
© 2000 Franz Kurfess
Deadlocks 22
Conditions for Deadlock
 all
four conditions must hold simultaneously
 mutual

exclusion
 hold and wait
 no preemption
 circular wait
the term deadlock is often used sloppily in situations that
don’t constitute a formal deadlock as described above
© 2000 Franz Kurfess
Deadlocks 23
Mutual Exclusion
 only
one process can hold a resource at one point
 at least one resource may be used in a mutually
exclusive way only
 requests by other processes are delayed
 usually determined by the needs of the resource, not
under the control of the OS
 examples: CPU, printer, write on files
© 2000 Franz Kurfess
Deadlocks 24
Hold and Wait
 one
process holds a resource and waits to acquire
other resources currently held by other processes
 the processes doesn’t release its current resources
 may be necessary, or a consequence of bad
program design
 examples: memory segments, I/O devices,
chopsticks
© 2000 Franz Kurfess
Deadlocks 25
No Preemption
a
resource is released by a process only voluntarily
 no intervention by the OS or other processes
 examples: “cooperative multitasking” (MacOS)
© 2000 Franz Kurfess
Deadlocks 26
Circular Wait
 each
process holds at least one resources needed
by another process
 the set of processes together with the request and
hold links forms a cycle
 there
must be a set of processes
P0, P1, ..., PN such that
Pi is waiting on Pi+1
and PN is waiting on P0
 examples:
© 2000 Franz Kurfess
dining philosophers, memory requests
Deadlocks 27
Deadlock Examples
 examples
 studying
students
 traffic intersection
 narrow tunnel
 single-track railroad
 airline reservation system
 evaluation
 four
conditions: mutual exclusion, hold and wait, no
preemption, circular wait
© 2000 Franz Kurfess
Deadlocks 28
Studying Students
 studying
students: both students need the textbook
and the course notes to study, but there is only one
copy of each
 consider the following situation:
Student A
get coursenotes
get textbook
study
release textbook
release coursenotes
© 2000 Franz Kurfess
Student B
get textbook
get coursenotes
study
release coursenotes
release textbook
Deadlocks 29
Students Evaluation
 mutual
exclusion
 books

and course notes can be used only by one student
hold and wait
a
student who has the book waits for the course notes, or
vice versa
 no
preemption
 there
is no authority to take away book or course notes
from a student
 circular
wait
 student A waits
for resources held by student B, who waits
for resources held by A
© 2000 Franz Kurfess
Deadlocks 30
Traffic Intersection
 at
a four-way intersection, four cars arrive
simultaneously
 if all proceed, they will be stuck in the middle
© 2000 Franz Kurfess
Deadlocks 31
Traffic Evaluation
 mutual
 cars

exclusion
can’t pass each other in the intersection
hold and wait
 vehicles
proceed to the center, and wait for their path to be
clear
 no
preemption
 there
 circular
is no authority to remove some vehicles
wait
 vehicle
1 waits for vehicle 2 to move, which waits for 3,
which waits for 4, which waits for 1
© 2000 Franz Kurfess
Deadlocks 32
Narrow Tunnel
 in
a narrow tunnel, there is enough room for most
vehicles to pass each other
 if two large trucks arrive simultaneously, they won’t
be able to pass each other
© 2000 Franz Kurfess
Deadlocks 33
Tunnel Evaluation
 mutual
exclusion
 trucks

can’t pass each other in the tunnel
hold and wait
 trucks
occupy part of the tunnel and wait for their path to
become clear
 no
preemption
 there
is no authority to remove the trucks
 circular
 truck
wait
1 waits for truck 2 to move, which waits for 1
© 2000 Franz Kurfess
Deadlocks 34
Single-Track Railroad
 two
trains arrive from different directions on a singletrack section
 railroad evaluation
 mutual


exclusion
trains can’t pass each other on the single track
hold and wait

 no

trains occupy part of the track and wait for their path to become
clear
preemption
there is no authority to remove the trains
 circular

wait
train 1 waits for train 2 to move, which waits for 1
© 2000 Franz Kurfess
Deadlocks 35
Airline Reservation System
 two
agents book flights in from EWR to FRA to MUC
 agent
A books flights EWR to FRA first
 agent B books FRA to MUC first
 flight
records are locked during booking
Agent A
lock EWR-FRA
lock FRA-MUC
-- finalize booking
release FRA-MUC
release EWR-FRA
© 2000 Franz Kurfess
Agent B
lock FRA-MUC
lock EWR-FRA
-- finalize booking
release EWR-FRA
release FRA-MUC
Deadlocks 36
Reservation Evaluation
 mutual
 flight

exclusion
records are locked
hold and wait
 one
agent locks one segment and waits for the other to
become available
 no
preemption
 there
 circular
 agent
is no authority to remove the locks held by an agent
wait
A waits for agent B to unlock a segment, who waits
for A
© 2000 Franz Kurfess
Deadlocks 37
Dealing with Deadlocks
 protocol
 have
strict rules that prevent a deadlock from occurring
 recover
 allow
the system to enter a deadlock
 there must be a way to recover from the deadlock situation
 ignoring
the deadlock
 frequently

used in operating systems
Windows, MacOS, Unix, ...
© 2000 Franz Kurfess
Deadlocks 38
Dealing with Deadlocks
 deadlock
 based
on protocols
 deadlock
 check
avoidance
for safe state
 deadlock
 run
prevention
detection and recovery
into a deadlock, detect it, and recover
© 2000 Franz Kurfess
Deadlocks 39
Deadlock Prevention
 set
of rules ensures that at least one of the four
necessary conditions for deadlock doesn’t hold
 mutual
exclusion
 hold and wait
 no preemption
 circular wait
 may
result in low resource utilization, reduced
system throughput
 example: traffic lights, no trucks in the narrow tunnel
© 2000 Franz Kurfess
Deadlocks 40
Denying Mutual Exclusion
 if
all resources were sharable there would not be
any deadlock
 some resources can be made sharable
 for
example, spooling printer output
 some
 e.g.
resources are intrinsically non-sharable
CPU (at the instruction time scale)
© 2000 Franz Kurfess
Deadlocks 41
Denying Hold And Wait
 prevent
processes that hold resources from waiting
for more resources
 processes
request and are allocated all their resources
before they start executing

low resource utilization rate
 processes

can request resources only if they have none
indefinite postponement
© 2000 Franz Kurfess
Deadlocks 42
Denying No Preemption
 means
that processes may be preempted by the OS
 should


only done when necessary
resources of a process trying to acquire another unavailable
resource may be preempted
preempt resources of processes waiting for additional resources,
and give some to the requesting process
 possible
only for some types of resources
 state
must be easily restorable
 e.g. CPU, memory
 frequently
© 2000 Franz Kurfess
used when applicable
Deadlocks 43
Denying Circular Wait
 break
the cycle of waiting processes
 impose
a total ordering of all resource types
 resources may only requested in increasing order of
enumeration

no process can request a resource with a lower number than what
it is already holding
 ordering
© 2000 Franz Kurfess
should take typical order of usage into account
Deadlocks 44
Safe Philosophers
 solution
based on monitors
 deadlock
prevention is used by designing the program
with certain restrictions
 basic
idea
a
philosopher picks up a chopstick only if the other one is
available as well
 philosophers inform each other when they are done
© 2000 Franz Kurfess
Deadlocks 45
Philosophers with Monitors
type dining-philosophers = monitor
var state: array [0..4] of (thinking, hungry, eating);
var self: array [0..4] of condition;
procedure entry pickup(i: 0..4);
begin
state[i] := hungry;
test(i);
if state[i] <> eating then self[i].wait;
end;
procedure entry putdown(i: 0..4);
begin
state[i] := thinking;
test(i-1 mod 5);
test(i+1 mod 5);
end;
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
Deadlocks 46
Philosophers with Monitors (cont.)
procedure test(k: 0..4);
begin
if (state[k-1] mod 5 <> eating
and state[k] = hungry
and state[k+1] mod 5 <> eating)
then begin
state[k] := eating;
self[k].signal;
end;
end;
begin
for i := 0 to 4
do state[i] := thinking;
end;
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
Deadlocks 47
Deadlock Avoidance
 makes
sure the system stays in a safe state if a
request is satisfied
 prevents circular waits
 requires additional information at the beginning of
the execution of a process
 maximum
number of instances per resource type for each
process
© 2000 Franz Kurfess
Deadlocks 48
Safe State
 A system
is in a safe state when given the current
allocation the system is able to handle any number
of requests, in some order, without getting into a
deadlock.
© 2000 Franz Kurfess
Deadlocks 49
Example
 Bank
gives loans to customers
 maximum
allocation = credit limit
BANK
$10
A
B
C
$5
$7
$3
© 2000 Franz Kurfess
Maximum Allocation
Deadlocks 50
 Safe
State?
 Will
the bank be able to give each customer a loan up to
the full credit limit?



not necessarily all customers simultaneously
order is not important
customers will pay back their loan once their credit limit is reached
BANK
$2
Current Allocation
A $3
$5
© 2000 Franz Kurfess
B $4
$7
Maximum Allocation
C $1
$3
Deadlocks 51
 Still
Safe?
 after
customer B requests and is granted $1, is the bank
still safe?
BANK
$1
Current Allocation
A $3
$5
B $5
$7
C $1
$3
Maximum Allocation
© 2000 Franz Kurfess
Deadlocks 52
Safe State Space
Safe
unsafe
deadlock
© 2000 Franz Kurfess
Deadlocks 53
Bank Safe State Space
unsafe
Safe
(3,4,1)
x
(3,5,1)
x
deadlock
© 2000 Franz Kurfess
Deadlocks 54
Banker’s Algorithm
 before
a request is granted, check the system’s
state
 assume
the request is granted
 if it is still safe, the request can be honored
 otherwise the process has to wait
 overly careful

there are cases when the system is unsafe, but not in a deadlock
© 2000 Franz Kurfess
Deadlocks 55
Example Banker’s Algorithm
 initially
given: current allocation, maximum
allocation, available resources
Process
P0
P1
P2
P3
P4
© 2000 Franz Kurfess
Current
Allocation
A B C D E
1 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 1 1 1
0 0 1 0 0
Maximum
Allocation
A B C D E
2 0 2 1 3
1 2 1 2 2
2 1 3 1 2
0 1 2 1 2
1 1 1 2 2
Available
A B C D E
1 0 1 0 1
Deadlocks 56
 needed
allocation is calculated by subtracting the
current allocation from the maximum allocation
Process
P0
P1
P2
P3
P4
Current
Allocation
A B C D E
1 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 1 1 1
0 0 1 0 0
Needed
Allocation
A B C D E
1 0 1 1 3
0 1 1 1 2
2 1 3 1 1
0 0 1 0 1
1 1 0 2 2
Available
A B C D E
1 0 1 0 1
1 1 2 1 2
<P3>
© 2000 Franz Kurfess
Deadlocks 57
 available
resources are increased because
processes that are finished return their resources
Process
P0
P1
P2
P3
P4
Current
Allocation
A B C D E
1 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 1 1 1
0 0 1 0 0
Needed
Allocation
A B C D E
1 0 1 1 3
0 1 1 1 2
2 1 3 1 1
0 0 1 0 1
1 1 0 2 2
Available
A B C D E
1 0 1 0 1
1 1 2 1 2
2 2 2 2 2
<P3, P1>
© 2000 Franz Kurfess
Deadlocks 58
Process
P0
P1
P2
P3
P4
Current
Allocation
A B C D E
1 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 1 1 1
0 0 1 0 0
Needed
Allocation
A B C D E
1 0 1 1 3
0 1 1 1 2
2 1 3 1 1
0 0 1 0 1
1 1 0 2 2
Available
A B C D E
1 0 1 0 1
1 1 2 1 2
2 2 2 2 2
2 2 3 2 2
<P3, P1, P4>
© 2000 Franz Kurfess
Deadlocks 59
Process
P0
P1
P2
P3
P4
Current
Allocation
A B C D E
1 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 1 1 1
0 0 1 0 0
Needed
Allocation
A B C D E
1 0 1 1 3
0 1 1 1 2
2 1 3 1 1
0 0 1 0 1
1 1 0 2 2
Available
A B C D E
1 0 1 0 1
1 1 2 1 2
2 2 2 2 2
2 2 3 2 2
2 2 3 2 3
<P3, P1, P4, P2>
© 2000 Franz Kurfess
Deadlocks 60
 if
there is a sequence in which all processes get
their needed allocation, the system is in a safe state
Process
P0
P1
P2
P3
P4
Current
Allocation
A B C D E
1 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 1 1 1
0 0 1 0 0
Needed
Allocation
A B C D E
1 0 1 1 3
0 1 1 1 2
2 1 3 1 1
0 0 1 0 1
1 1 0 2 2
Available
A B C D E
1 0 1 0 1
1 1 2 1 2
2 2 2 2 2
2 2 3 2 2
2 2 3 2 3
3 2 4 2 3
<P3, P1, P4, P2, P0>
© 2000 Franz Kurfess
Deadlocks 61
 What
if P0 requests and is granted one instance of
resource A?
 adjust current and needed allocation, available
resources
Process
P0
P1
P2
P3
P4
© 2000 Franz Kurfess
Current
Allocation
A B C D E
2 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 1 1 1
0 0 1 0 0
Needed
Allocation
A B C D E
0 0 1 1 3
0 1 1 1 2
2 1 3 1 1
0 0 1 0 1
1 1 0 2 2
Available
A B C D E
0 0 1 0 1
Deadlocks 62
Process
P0
P1
P2
P3
P4
Current
Allocation
A B C D E
2 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 1 1 1
0 0 1 0 0
Needed
Allocation
A B C D E
0 0 1 1 3
0 1 1 1 2
2 1 3 1 1
0 0 1 0 1
1 1 0 2 2
Available
A B C D E
0 0 1 0 1
0 1 2 1 2
<P3>
© 2000 Franz Kurfess
Deadlocks 63
Process
P0
P1
P2
P3
P4
Current
Allocation
A B C D E
2 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 1 1 1
0 0 1 0 0
Needed
Allocation
A B C D E
0 0 1 1 3
0 1 1 1 2
2 1 3 1 1
0 0 1 0 1
1 1 0 2 2
Available
A B C D E
0 0 1 0 1
0 1 2 1 2
1 2 2 2 2
<P3, P1>
© 2000 Franz Kurfess
Deadlocks 64
Process
P0
P1
P2
P3
P4
Current
Allocation
A B C D E
2 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 1 1 1
0 0 1 0 0
Needed
Allocation
A B C D E
0 0 1 1 3
0 1 1 1 2
2 1 3 1 1
0 0 1 0 1
1 1 0 2 2
Available
A B C D E
0 0 1 0 1
0 1 2 1 2
1 2 2 2 2
1 2 3 2 2
<P3, P1, P4>
© 2000 Franz Kurfess
Deadlocks 65
Process
P0
P1
P2
P3
P4
Current
Allocation
A B C D E
2 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 1 1 1
0 0 1 0 0
Needed
Allocation
A B C D E
0 0 1 1 3
0 1 1 1 2
2 1 3 1 1
0 0 1 0 1
1 1 0 2 2
<P3, P1, P4>
© 2000 Franz Kurfess
Available
A B C D E
0 0 1 0 1
0 1 2 1 2
1 2 2 2 2
1 2 3 2 2
Conflict!
Deadlocks 66
Example 1 Banker’s Algorithm
 initially
given: current allocation, maximum
allocation, available resources
Process
P0
P1
P2
P3
P4
P5
© 2000 Franz Kurfess
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
1 2 0 1
0 0 0 0
1 1 1 1
Maximum
Allocation
A B C D
1 2 0 1
1 2 3 2
0 0 3 0
2 3 0 1
0 0 0 1
3 3 4 1
Available
A B C D
1 0 0 1
Deadlocks 67
Ex. 1 Resource Allocation Graph
B
B
A
Assignment
Edge
P0
P1
P2
P3
P4
P5
Request
Edge
C
© 2000 Franz Kurfess
D
Deadlocks 68
Example 1 (cont.)
 needed
allocation is calculated by subtracting the
current allocation from the maximum allocation
 all
calculations are done for each element of the vector
Process
P0
P1
P2
P3
P4
P5
© 2000 Franz Kurfess
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
1 2 0 1
0 0 0 0
1 1 1 1
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
1 1 0 0
0 0 0 1
2 2 3 0
Available
A B C D
1 0 0 1
Deadlocks 69
Example 1 (cont.)
 select
a process whose request (needed allocation)
could be satisfied with the available resources
 there
may be several candidates (e.g. P0, P4)
Process
P0
P1
P2
P3
P4
P5
© 2000 Franz Kurfess
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
1 2 0 1
0 0 0 0
1 1 1 1
<P0>
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
1 1 0 0
0 0 0 1
2 2 3 0
Available
A B C D
1 0 0 1
Deadlocks 70
Example 1 (cont.)
 the
resources held by this process are added to the
available resources because processes that are
finished return their resources
Process
P0
P1
P2
P3
P4
P5
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
1 2 0 1
0 0 0 0
1 1 1 1
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
1 1 0 0
0 0 0 1
2 2 3 0
Available
A B C D
1 0 0 1
1 2 0 2
<P0>
© 2000 Franz Kurfess
Deadlocks 71
Example 1 (cont.)
 the
next process is selected
 the
previous process is marked as already checked
Process
P0
P1
P2
P3
P4
P5
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
1 2 0 1
0 0 0 0
1 1 1 1
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
1 1 0 0
0 0 0 1
2 2 3 0
Available
A B C D
1 0 0 1
1 2 0 2
<P0, P3>
© 2000 Franz Kurfess
Deadlocks 72
Example 1 (cont.)
 and
its resources are added to the available
resources
Process
P0
P1
P2
P3
P4
P5
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
1 2 0 1
0 0 0 0
1 1 1 1
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
1 1 0 0
0 0 0 1
2 2 3 0
Available
A B C D
1 0 0 1
1 2 0 2
2 4 0 3
<P0, P3>
© 2000 Franz Kurfess
Deadlocks 73
Example 1 (cont.)
 the
next process is selected, and its resources are
added to the available resources
Process
P0
P1
P2
P3
P4
P5
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
1 2 0 1
0 0 0 0
1 1 1 1
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
1 1 0 0
0 0 0 1
2 2 3 0
Available
A B C D
1 0 0 1
1 2 0 2
2 4 0 3
3 5 3 3
<P0, P3, P1>
© 2000 Franz Kurfess
Deadlocks 74
Example 1 (cont.)
 the
next process is selected, and its resources are
added to the available resources
Process
P0
P1
P2
P3
P4
P5
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
1 2 0 1
0 0 0 0
1 1 1 1
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
1 1 0 0
0 0 0 1
2 2 3 0
Available
A B C D
1 0 0 1
1 2 0 2
2 4 0 3
3 5 3 3
3 5 4 3
<P0, P3, P1, P2>
© 2000 Franz Kurfess
Deadlocks 75
Example 1 (cont.)
 the
next process is selected, and its resources are
added to the available resources
Process
P0
P1
P2
P3
P4
P5
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
1 2 0 1
0 0 0 0
1 1 1 1
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
1 1 0 0
0 0 0 1
2 2 3 0
Available
A B C D
1 0 0 1
1 2 0 2
2 4 0 3
3 5 3 3
3 5 4 3
3 5 4 3
<P0, P3, P1, P2, P4>
© 2000 Franz Kurfess
Deadlocks 76
Example 1 (cont.)
 the
last process (P5) is selected, and its resources
are added to the available resources
Process
P0
P1
P2
P3
P4
P5
© 2000 Franz Kurfess
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
1 2 0 1
0 0 0 0
1 1 1 1
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
1 1 0 0
0 0 0 1
2 2 3 0
<P0, P3, P1, P2, P4, P5>
Available
A B C D
1 0 0 1
1 2 0 2
2 4 0 3
3 5 3 3
3 5 4 3
3 5 4 3
4 6 5 4
Deadlocks 77
Outcome Example 1
 all
processes have been checked successfully
 there is at least one sequence in which the requests
of the processes can be satisfied safely
 the final value for the “available” vector indicates the
total number of resources
© 2000 Franz Kurfess
Deadlocks 78
Example 2 Banker’s Algorithm
 slight
modification of the previous example:
holds 2 2 0 1 instead of 1 2 0 1
 this changes Current Allocation, Needed
Allocation, and Available
Current
Maximum
Process Allocation
Allocation
Available
AB C D
A B C D
A B C D
P0
0 2 0 1
1 2 0 1
0 0 0 1
P1
1 1 3 0
1 2 3 2
P2
0 0 1 0
0 0 3 0
P3
2 2 0 1
2 3 0 1
P4
0 0 0 0
0 0 0 1
P5
1 1 1 1
3 3 4 1
 P3
© 2000 Franz Kurfess
Deadlocks 79
Ex. 2 Resource Allocation Graph
B
B
A
Assignment
Edge
P0
P1
P2
P3
P4
P5
Request
Edge
C
© 2000 Franz Kurfess
D
Deadlocks 80
Example 2 (cont.)
 needed
allocation is calculated by subtracting the
current allocation from the maximum allocation
 all
calculations are done for each element of the vector
Process
P0
P1
P2
P3
P4
P5
© 2000 Franz Kurfess
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
2 2 0 1
0 0 0 0
1 1 1 1
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
0 1 0 0
0 0 0 1
2 2 3 0
Available
A B C D
0 0 0 1
Deadlocks 81
Example 2 (cont.)
 select
a process whose request (needed allocation)
could be satisfied with the available resources
Process
P0
P1
P2
P3
P4
P5
© 2000 Franz Kurfess
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
2 2 0 1
0 0 0 0
1 1 1 1
<P4>
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
0 1 0 0
0 0 0 1
2 2 3 0
Available
A B C D
0 0 0 1
Deadlocks 82
Example 2 (cont.)
 the
resources held by this process are added to the
available resources because processes that are
finished return their resources
Process
P0
P1
P2
P3
P4
P5
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
2 2 0 1
0 0 0 0
1 1 1 1
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
0 1 0 0
0 0 0 1
2 2 3 0
Available
A B C D
0 0 0 1
0 0 0 1
<P4>
© 2000 Franz Kurfess
Deadlocks 83
Example 2 (cont.)
 the
next process is selected
 the
previous process is marked as already checked
Process
P0
P1
P2
P3
P4
P5
Current
Allocation
AB C D
0 2 0 1
1 1 3 0
0 0 1 0
2 2 0 1
0 0 0 0
1 1 1 1
Needed
Allocation
A B C D
1 0 0 0
0 1 0 2
0 0 2 0
0 1 0 0
0 0 0 1
2 2 3 0
<P4>
© 2000 Franz Kurfess
Available
A B C D
0 0 0 1
0 0 0 1
Conflict!
Deadlocks 84
Outcome Example 2
 not
all processes could be checked successfully
 there is no sequence in which the requests of the
processes can be satisfied safely
 the system is in an unsafe state involving all
processes except P4
© 2000 Franz Kurfess
Deadlocks 85
Detection and Recovery
 the
system must provide an algorithm to
 examine
whether a deadlock has occurred
 recover from the deadlock
 requires
run-time overhead due to
 maintaining
information and executing a detection
algorithm
 the potential losses inherent in recovery
© 2000 Franz Kurfess
Deadlocks 86
Detection: Single Instance
 all
resource types have only one instance
 a cycle in the resource allocation graph means there
is a deadlock
 a cycle detection algorithm requires an order of
n2 operations for n nodes in the graph
(processes + resources)
© 2000 Franz Kurfess
Deadlocks 87
Resource Allocation Graphs
R1
R2
R3
Assignment
Edge
P1
P2
P3
P4
P5
Request
Edge
R4
© 2000 Franz Kurfess
R5
R6
R7
Deadlocks 88
Detection: Multiple Instances
 there
are several instances for each resource type
 an algorithm similar to deadlock avoidance (banker’s
algorithm) is used to determine whether the system
is deadlocked
order of m * n2 operations
(m = no. of resource types, n = no. of processes)
 requires
 how
often the algorithm is invoked depends on
 the
likelihood for deadlock to occur
 the number of processes affected by deadlock
© 2000 Franz Kurfess
Deadlocks 89
Recovery
 resume
operation after a deadlock has been
detected
 preemption
 rollback
 killing
processes
© 2000 Franz Kurfess
Deadlocks 90
Ignoring the Problem
 simplest
approach
 better performance and less restrictive system
 problem: possibility of occasional deadlocks
 example: Unix
© 2000 Franz Kurfess
Deadlocks 91
Deadlock in Operating Systems
 combined
approach
 resources
are partitioned into hierarchically ordered
classes
 a resource-ordering technique is applied to the classes
 within each class, one particular approach to deadlocks
can be used
 guarantees that a deadlock cannot involve more than one
class, and the whole system is safe
© 2000 Franz Kurfess
Deadlocks 92
Example Combined Approach
 classes
of resources
 system

used by the OS
 user

resources
memory
memory used by a user process
 process

resources
resources available to processes
 devices, files
 swap

space
space for processes on a background storage device
© 2000 Franz Kurfess
Deadlocks 93
Solution Combined Approach
 resource
ordering between the four classes
 individual approaches within each class
 system

prevention: resource ordering within the class
 user

resources
memory
preemption: swap a process to secondary storage
 process

deadlock avoidance: processes inform the OS in advance about
resources to be requested
 swap

resources
space
prevention: all required resources are allocated at the same time
(preallocation)
© 2000 Franz Kurfess
Deadlocks 94
Important Concepts and Terms











Banker’s algorithm
circular wait condition
deadlock
deadlock avoidance
deadlock detection
deadlock prevention
dining philosophers
hold and wait condition
instance
monitor
mutual exclusion condition












© 2000 Franz Kurfess
no preemption condition
process
preemption
recovery
resource
resource allocation
resource allocation graph
resource type
safe state
starvation
synchronization
termination
Deadlocks 95
Summary Deadlocks
 deadlock
is a specific situation characterized by four
criteria
 mutual
exclusion, hold and wait, no preemption, circular
wait
 it
prevents affected processes from continuing their
execution
 deadlock can be dealt with by prevention,
avoidance, detection, or by ignoring the problem
 various algorithms based on resource allocation
graphs
 e.g.
banker’s algorithm
© 2000 Franz Kurfess
Deadlocks 96