Deadlocks
Carsten Griwodz
University of
Oslo
(includes slides from T. Plagemann, Kai Li,
A. Tanenbaum and M. van Steen)
Resources
Examples of computer resources
CPU
Memory
Disk drive
Tape drives
Printers
Plotter
Loudspeaker
1
Resources
Processes
Need access to resources in reasonable order
Typical way to use a resource
Request
Use
Release
Suppose a process holds resource A and
requests resource B
At same time another process holds B and requests A
Both are blocked and remain so
Resources
Active resource
Provides a service
E.g. CPU, network adaptor
Passive resource
System capabilities that are required by active resources
E.g. memory, network bandwidth
Exclusive resource
Only one process at a time can use it
E.g. loudspeaker, processor
Shared resource
Can be used by multiple processes
E.g. memory, bandwidth
Resources
Single resource
Exists only once in the system
E.g. loudspeaker
Multiple resource
Exists several time in the system
E.g. processor in a multiprocessor system
Preemptable resource
Resource that can be taken away from a process
E.g. CPU can be taken away from processes in user space
Non-preemptable resource
Taking it away will cause processes to fail
E.g. Disk, files
Resources
Process must wait if request is denied
acquire block
Requesting process may be blocked
May fail with error code
use
Deadlocks acquire
Occur only when processes are granted exclusive access to resources
use
Deadlocks
Formal definition :
A set of processes is deadlocked
if each process in the set is waiting for an event
that only another process in the set can cause
Usually the event is release of a currently
held resource
None of the processes can …
Run
Release resources
Be awakened
Four Conditions for Deadlock
1. Mutual exclusion condition
Each resource assigned to 1 process or is available
2. Hold and wait condition
Process holding resources can request additional
3. No preemption condition
Previously granted resources cannot forcibly taken away
4. Circular wait condition
Must be a circular chain of 2 or more processes
Each is waiting for resource held by next member of
the chain
Deadlock Modeling
Modeled with directed graphs
A S C T
R B U D
Resource R assigned to process A
Process B is requesting/waiting for resource S
Process C and D are in deadlock over resources T and U
Deadlock Example
A utility program A deadlock
Copies a file from a tape to disk
Prints the file to a printer
Resources A
Tape
Disk
Printer tape disk printer
B
Deadlock Modeling
How deadlock occurs
A
Requests R Requests S Releases S A requests R B requests S C requests T A requests S B requests T C req
Releases R Processes A B C
B
Requests S Requests T Releases T Releases S
C
Requests T Requests R Releases R Releases T
Resources R S T
Deadlock Modeling
How deadlock can be avoided
A
Requests R Requests S Releases
A requests S
R C requests T A requests S B requests S B requests T C requests R A releases S A releases R C rele
Releases R Processes A B C
B
Requests S Requests T Releases T Releases S
C
Requests T Requests R Releases R Releases T
Resources R S T
Deadlocks: Strategies
Ignore the problem
It is user’s fault
Detection and recovery
Fix the problem afterwards
Dynamic avoidance
Careful allocation
Prevention
Negate one of the four conditions
The Ostrich Algorithm
Pretend there is no problem
Reasonable if
Deadlocks occur very rarely
Cost of prevention is high
UNIX and Windows take this approach
It is a trade-off between
Convenience
Correctness
Deadlock Detection and Recovery One Resource of Each Type
R A B
C S D T E
F U V
WG
A cycle can be found within the graph, denoting deadlock
Deadlock Detection and Recovery Multiple Resources of Each Type
Existing resources Available resources
E1 , E2 , E3 ,..., Em A1, A2 , A3 ,..., Am
Current allocation matrix Request matrix
C11 C12 C13 ... C1m R11 R12 R13 ... R1m
C 22
... 2m R 22
R
23
R R
... 2m
C
... C23 C ... ...
21
...
21
... ...
... ...
... ...
... nm R ... nm
C
n1 C n2 C n3 C n1 Rn 2 Rn3 R
Process n has these resources Process 2 needs these resources
Data structures needed by deadlock detection algorithm
Deadlock Detection and Recovery Multiple Resources of Each Type
E=( 4231 ) A=( 2100 )
Current allocation matrix Request matrix
0010 2 001
C=2001 R=1 010
0120 2 100
An example for the deadlock detection algorithm
Deadlock Detection and Recovery Multiple Resources of Each Type
E=( 4231 ) A=( 2000 )
Current allocation matrix Request matrix
0010 2 001
C=21001 R=1 010
0120 2 100
An example for the deadlock detection algorithm
Deadlock Detection and Recovery
Recovery
Recovery through preemption
Take a resource from some other process
Depends on nature of the resource
Recovery through rollback
Checkpoint a process periodically
Use this saved state
Restart the process if it is found deadlocked
Recovery through killing processes
Crudest but simplest way to break a deadlock
Kill one of the processes in the deadlock cycle
The other processes get its resources
Choose process that can be rerun from the beginning
Deadlock Avoidance Resource Trajectories
B
release
Safe
release finished
Safe
request
Safe Unreachable
Printer
request
Plotter
Unsafe
SafeSafeSafe
start
A
release
request request release
Two process resource trajectories Printer
Plotter
Deadlock Avoidance Safe and Unsafe States
has max has max has max has max has max
A 3 9 A 3 9 A 3 9 A 3 9 A 3 9
B 2 4 B 4 4 B 0 B 0 B 0
C 2 7 C 2 7 C 2 7 C 7 7 C 0
Free: 3 Free: 1 Free: 5 Free: 0 Free: 7
state is safe
Deadlock Avoidance Safe and Unsafe States
has max has max has max has max
A 3 9 A 4 9 A 4 9 A 3 9
B 2 4 B 2 4 B 4 4 B 0
C 2 7 C 2 7 C 2 7 C 2 7
Free: 3 Free: 2 Free: 0Free: 4
state is unsafe
state is safe
Deadlock Avoidance
Banker’s Algorithm for a Single Resource
Each process has a credit
System knows how many resources a
process requests at most before releasing
resources
Total resources may not satisfy all credits
Keep track of resources assigned and needed
Check on each allocation whether it is safe
Safe: there exists a sequence of other states
that all processes can terminate correctly
Deadlock Avoidance
Banker's Algorithm for a Single Resource
Resource allocation state
has max has max has max
A 60 6- A 63150 6- A 12 6
B 50 5- B 3510 5- B 23 5
C 400 4- C 420 4- C 23 4
D 700 7- D 470 7- D 45 7
Free: 10 Free:
Free:654210 Free: 1
safe
safe unsafe
Deadlock Detection and Recovery Banker’s Algorithm for Multiple Resources
E=() 6 3 4 2
P=() 5 3 2 2
Assigned resources Resources still needed
A=( 1020 )
A 3 0 1 1 A 1 1 0 0
B 0 1 0 0 B 0 1 1 2
C 1 1 1 0 C 3 1 0 0
D 1 1 0 1 D 0 0 1 0
E 0 0 0 0 E 2 1 1 0
An example for the deadlock detection algorithm
Deadlock Detection and Recovery Banker’s Algorithm for Multiple Resources
E=() 6 3 4 2
P=() 4 2 2 1
Assigned resources Resources still needed
A=( 2121 )
A 3 0 1 1 A 1 1 0 0
B 0 1 0 0 B 0 1 1 2
C 1 1 1 0 C 3 1 0 0
D 0 0 0 0 D - - - -
E 0 0 0 0 E 2 1 1 0
An example for the deadlock detection algorithm
Deadlock Detection and Recovery Banker’s Algorithm for Multiple Resources
E=() 6 3 4 2
P=() 1 2 1 0
Assigned resources Resources still needed
A=( 5132 )
A 0 0 0 0 A - - - -
B 0 1 0 0 B 0 1 1 2
C 1 1 1 0 C 3 1 0 0
D 0 0 0 0 D - - - -
E 0 0 0 0 E 2 1 1 0
An example for the deadlock detection algorithm
Deadlock Detection and Recovery Banker’s Algorithm for Multiple Resources
E=() 6 3 4 2
P=() 1 1 1 0
Assigned resources Resources still needed
A=( 5232 )
A 0 0 0 0 A - - - -
B 0 0 0 0 B - - - -
C 1 1 1 0 C 3 1 0 0
D 0 0 0 0 D - - - -
E 0 0 0 0 E 2 1 1 0
An example for the deadlock detection algorithm
Deadlock Detection and Recovery Banker’s Algorithm for Multiple Resources
E=() 6 3 4 2
P=() 0 0 0 0
Assigned resources Resources still needed
A=( 6342 )
A 0 0 0 0 A - - - -
B 0 0 0 0 B - - - -
C 0 0 0 0 C - - - -
D 0 0 0 0 D - - - -
E 0 0 0 0 E 2 1 1 0
An example for the deadlock detection algorithm
Deadlock Detection and Recovery Banker’s Algorithm for Multiple Resources
SAFE E=( 6 3 4 2 )
P=( 5 3 2 2 )
Assigned resources Resources still needed )
A=( 1 0 2 0
A 3 0 1 1 A 1 1 0 0
B 0 1 0 0 B 0 1 1 2
C 1 1 1 0 C 3 1 0 0
D 1 1 0 1 D 0 0 1 0
E 0 0 0 0 E 2 1 1 0
An example for the deadlock detection algorithm
Deadlock Avoidance
Practical Avoidance
Two Phase Locking
Phase I
Process tries to lock all resources it needs, one at a time
If needed resources found locked, start over
(no real work done in phase one)
Phase II
Run
Releasing locks
Note similarity to requesting all resources at once
Algorithm works where programmer can arrange
Deadlock Prevention
R: Conditions for Deadlock
1. Mutual exclusion condition
Each resource assigned to 1 process or is available
2. Hold and wait condition
Process holding resources can request additional
3. No preemption condition
Previously granted resources cannot forcibly taken away
4. Circular wait condition
Must be a circular chain of 2 or more processes
Each is waiting for resource held by next member of
the chain
Deadlock Prevention
Mutual Exclusion Condition
Some resources are not sharable
Printer, tape, etc
Some resources can be made sharable
Some resources can be made virtual
Spooling - Printer
Does spooling apply to all non-sharable resources?
Mixing - Soundcard
Principle:
Avoid assigning resource when not absolutely necessary
A few processes as possible actually claim the resource
Deadlock Prevention
Hold and Wait Condition
Require processes to request resources
before starting
A process never has to wait for what it needs
Telephone companies do this
Problems
May not know required resources at start of run
Also ties up resources other processes could be using
Variation:
Process must give up all resources
Then request all immediately needed
Deadlock Prevention
No Preemption Condition
This is not a viable option
Consider a process given the printer
Halfway through its job
No forcibly take away printer
!!??
Deadlock Prevention Circular Wait Condition
CD Rom drive Tape
1. drive Plotter Scanner Imagesetter A
2.
3.
4.
5.
1 2 3 4 5
Normally ordered resources
A resource graph
Deadlock Prevention
Circular Wait Condition
Impose an order of requests for all resources
Method
Assign a unique id to each resource
All resource requests must be in an
ascending order of the ids
Release resources in a descending order
Can you prove this method has no
circular wait?
Is this generally feasible?
Deadlock Prevention Overview
Condition Approach
Mutual exclusion Spool everything
Hold and wait Request all resource initially
No preemption Take resources away
Circular wait Order resources numerically
Non-resource Deadlocks
Possible for two processes to deadlock
Each is waiting for the other to do some task
Can happen with semaphores
Each process required to do a down() on
two semaphores (mutex and another)
If done in wrong order, deadlock results
Summary
Resource
Introduction to deadlocks
Strategies
Ostrich algorithm
Deadlock detection and recovery
Deadlock avoidance
Deadlock prevention
Non-resource deadlocks