05-Deadlocks
Peter R. Pietzuch
prp@doc.ic.ac.uk
Deadlocks
What is deadlock & how it occurs
Detecting potential deadlocks
– resource allocation graphs
Recovery techniques
Prevention techniques
Livelock and starvation
22
Deadlocks
Example: two processes want to scan a document,
and then save it on a CD
down(scanner);
down(cd_writer);
scan_and_record();
up(cd_writer);
up(scanner);
down(cd_writer);
down(scanner);
scan_and_record();
up(scanner);
up(cd_writer);
P0 P1
Deadlock?
33
Dining Philosophers
Each philosopher
needs 2 chopsticks
in order to eat
44
Dining Philosophers
Does this work?
What if everybody takes
chopstick[i] at same time?
55
Deadlock
Set of processes is deadlocked if each process is waiting for
an event that only another process can cause
Resource deadlock is most common, 4 conditions must hold:
1. Mutual exclusion: each resource is either available
or assigned to exactly one process
2. Hold and wait : process can request resources while
it holds other resources, requested earlier
3. No preemption: resources given to a process cannot
be forcibly revoked
4. Circular wait: two or more processes in a circular
chain, each waiting for a resource held by the next
process
66
Resource Allocation Graphs
Directed graph models resource allocation
– Directed arc from resource to process means that the
process is currently owning that resource
– Directed arc from process to resource means that the
process is currently blocked waiting for that resource
Cycle = deadlock
77
Dining Philosophers – Deadlock Cycle
Owns chopstick
Waiting for
chopstick
88
Strategies For Dealing With Deadlock
Ignore it
– “The Ostrich Algorithm”
– Contention for resources is low à deadlocks infrequent
Detection and recovery
Dynamic avoidance by careful resource allocation
Prevention by negating 1 of the 4 conditions
99
Detection and Recovery
Detects deadlock and recovers after the fact
Dynamically builds resource ownership graph and looks for cycles
When an arc has been inspected it is marked and not visited again
We are doing a depth-
first search from each
node in the graph,
checking for cycles.
1. For each node do:
2. Initialise L to the empty list
3. Add the current node to L and check if it
appears in L two times. Yes: cycle!
4. From current node check if any unmarked
outgoing arc
Yes: goto 5, No: goto 6
5. Pick unmarked outgoing arc, mark it, follow it
to new current node and goto 3
6. If this is initial node then no cycles detected,
terminate
else reached dead end, remove it, go back
to previous node and make it current and
goto 3
[Tanenbaum, MOS 6.4.1]
A
S
B
DC T
U
E
VGF
W
R
Detection – Example
§ A holds R and wants S
§ B holds nothing wants T
§ C holds nothing wants S
§ D holds U wants S and T
§ E holds T and wants V
§ F holds W and wants S
§ G holds V and wants U
Cycle?
• Starting at R, initialise L = [ ]
• Add R to list and move to A
(only possibility)
• Add A giving L = [R,A]
• Go to S so L = [R,A,S]
• S has not outgoing arcs à dead end,
backtrack to A
• A has no outgoing arcs, backtrack to R
• Restart at A, add A to L à dead end
• Restart at B, follow outgoing arcs until
D, now L = [B,T,E,V,G,U,D]
• Make random choice:
– S à dead end and backtrack to D
– Pick T update L = [B,T,E,V,G,U,D,T]
• Cycle: Deadlock found, STOP
R
Detection – Example (2)
A
S
B
DC
T
U
E
VGF
W
1212
Recovery
Pre-emption:
– Temporarily take resource from owner and give to
another
Rollback:
– Processes are periodically checkpointed (memory
image, state)
– On a deadlock, roll back to previous state
Killing processes:
– Select random process in cycle and kill it!
• OK for compile jobs, not so good for database, why?
1313
Circular Chain Deadlock Question
Suppose that there is a resource deadlock in a system. Can
the set of processes deadlocked include processes that are
not in the circular chain in the corresponding resource
allocation graph?
Menti.com Q1 99 89 93
1515
Strategies For Dealing With Deadlock
Ignore it
Detection and recovery
Dynamic avoidance
– System grants resources when it knows that it is safe to
do so
Prevention
1616
Banker’s Algorithm (Dijkstra 1965)
Four customers A, B, C and D
– Credit unit = £1K
Banker knows that all customers don’t
need max credit
– So reserves only 10 (instead of 22)
units
Each customer randomly asks for credit
• Four customers A, B, C and D
§ Credit unit = £1K
• Banker knows that all customers don’t
need max credit
§ So reserves only 10 (instead of 22) units
• Each customer randomly asks for credit
• For each process A-D,
§ Has = number of resource items allocated
§ Max = number of items required.
1717
Banker’s Algorithm – Save vs. Unsafe States
Safe state:
– Are there enough resources to satisfy any (maximum) request
from some customer?
– Assume that customer repays loan, and then check next
customer closest to the limit, etc.
A state is safe iff there exists a sequence of allocations that
guarantees that all customers can be satisfied
SAFE UNSAFE
1818
Banker’s Algorithm – Safe vs. Unsafe States
SAFE
UNSAFE
A state is safe iff there exists a sequence of
allocations that guarantees all customers can be satisfied
1919
Banker’s Algorithm – Safe vs. Unsafe States
Request granted only if it leads to a safe state
Unsafe state does not have to lead to deadlock, but
banker cannot rely on this behaviour
Algorithm can be generalized to handle multiple
resource types
SA
FE
U
N
SA
FE
2020
Bankers Algorithm Question
A system has 12 magnetic tape drives and 3 processes :
P0, P1, and P2.
What is a safe sequence for running the processes?
Process Has Max Need
P0 5 10
P1 2 4
P2 2 9
Menti.com Q2 99 89 93
2121
Strategies For Dealing With Deadlock
Ignore it
Detection and recovery
Dynamic avoidance
Prevention
– Attack one of the four deadlock conditions:
• Mutual exclusion,
• Hold and wait
• No preemption
• Circular wait
2222
Deadlock Prevention
Attacking the Mutual Exclusion Condition
– E.g., share the resource
Attacking the Hold and Wait Condition
– Require all processes to request resources before start
• If not all available then wait
– Issue: need to know what you need in advance
Attacking the No-Preemption condition
– E.g., forcing a process to give up printer half way through.
Usually not good
Attacking Circular Wait Problem
– Force single resource per process, if needs second, must release
first.
• Optimality issues
– Number resources, processes must ask for resources in this order
• Issue: large number of resources…can be difficult to
organise
2323
Dining Philosophers – Ordering Resources
1
2
3
4
5
• Request resources in specific
order
• Philosopher gets chopstick 4
and can then ask for 5, but if
he gets 5 first he cannot ask
for chopstick 4.
• The process holding the
highest resource will never ask
for a resource already
assigned.
2424
Communication Deadlock
E.g., process A sends message to B and blocks waiting on
B’s reply
B didn’t get A’s message then A is blocked and B is
blocked waiting on message è deadlock!
Ordering resources, careful scheduling not useful here
What should we use?
– Communication protocol based on timeouts
2525
Livelock
process_A process_B
{ {
Enter_region (resource1) Enter_region (resource2)
Enter_region (resource2) Enter_region (resource1)
Use(resource1, resource2) Use(resource1, resource2)
Leave_region (resource2) Leave_region (resource1)
Leave_region (resource1) Leave_region (resource2)
} }
• Example 2: System receiving and processing incoming messages.
Processing thread has lower priority and never gets a chance to run
under high load (receive livelock)
• Example 1: Enter_region() tests mutex then either grabs resource or
reports failure. If attempt fails, it tries again. Processes loop after
gaining first resource but failing second.
• Livelock: Processes/threads are not blocked, but they or the system
as a whole does not make progress
2626
Starvation
Concerns policy
Who gets what resource when
Many jobs want printer, who gets it?
– Smallest file? Suits majority, fast turnaround, but
what about occasional large job?
– FCFS is more fair in this case
2727
Single Processor Deadlock?
Can a single-processor system have no processes ready
and no process running?
Is this a deadlocked system? Explain your answer.
2929
Deadlock Question
Two processes, A and B, each need three records, 1, 2,
and 3, in a database. If A asks for them in the order 1, 2,
3, and B asks for them in the same order, deadlock is not
possible. However, if B asks for them in the order 3, 2, 1,
then deadlock is possible. With three resources, there are
3! = 6 possible combinations each process can request
resources.
What fraction of all combinations is guaranteed to be
deadlock free?
Menti.com Q3 99 89 93
3131
Deadlock Summary
Deadlocks occur from:
§ Accessing limited resources – not enough to go round
§ Incorrect programming of synchronisation
Resource allocation graphs can detect potential cyclic
deadlock
Recovery: pre-emption, rollback, kill process
Prevention
§ Use safe resource allocation strategy
§ Avoid unnecessary mutual exclusion – share instead
§ Ordered resource allocation
Livelock: no progress – incorrect programming?
Starvation: often due to priority