Synchronization Algorithms
and Concurrent Programming
Gadi Taubenfeld
Chapter 7
Multiple resources
The dinning philosophers problem
Version: June 2014
Chapter 7 Synchronization Algorithms and Concurrent Programming 1
Gadi Taubenfeld © 2014
Synchronization Algorithms
and Concurrent Programming
ISBN: 0131972596, 1st edition
A note on the use of these ppt slides:
I am making these slides freely available to all (faculty, students, readers).
They are in PowerPoint form so you can add, modify, and delete slides and slide
content to suit your needs. They obviously represent a lot of work on my part.
In return for use, I only ask the following:
q That you mention their source, after all, I would like people to use my book!
q That you note that they are adapted from (or perhaps identical to)
my slides, and note my copyright of this material.
Thanks and enjoy!
Gadi Taubenfeld
All material copyright 2014
Gadi Taubenfeld, All Rights Reserved
To get the most updated version of these slides go to:
http://www.faculty.idc.ac.il/gadi/book.htm
Chapter 7 Synchronization Algorithms and Concurrent Programming 2
Gadi Taubenfeld © 2014
Chapter 7
Multiple Resources
2.1 Deadlocks
2.2 Deadlock Prevention
2.3 Deadlock Avoidance
2.4 The Dining Philosophers
2.5 Hold and Wait Strategy
2.5 Wait and Release Strategy
2.6 Randomized algorithms
Chapter 7 Synchronization Algorithms and Concurrent Programming 3
Gadi Taubenfeld © 2014
Deadlocks
Section 7.1
Chapter 7 Synchronization Algorithms and Concurrent Programming 4
Gadi Taubenfeld © 2014
Deadlocks
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.
Chapter 7 Synchronization Algorithms and Concurrent Programming 5
Gadi Taubenfeld © 2014
Multiple resources
How to avoid deadlock?
account A account B
Transferring money between two bank accounts
semaphores A and B, initialized to 1
P0 P1
down(A); down(B)
deadlock
down(B); down(A)
Chapter 7 Synchronization Algorithms and Concurrent Programming 6
Gadi Taubenfeld © 2014
Multiple resources
How to avoid deadlock?
Bridge crossing
q On the bridge traffic only in one direction.
q The resources are the two entrances.
Chapter 7 Synchronization Algorithms and Concurrent Programming 7
Gadi Taubenfeld © 2014
Two Simple Questions
Question: A system has 2 processes and 3
identical resources. Each process needs a No
maximum of 2 resources. Is deadlock possible?
Question: Consider a system with X identical
resources. The system has 15 processes each
needing a maximum of 15 resources. What is the
smallest value for X which makes the system
deadlock-free (without the need to use a
deadlock avoidance algorithm)?
15×14+1 = 211
Chapter 7 Synchronization Algorithms and Concurrent Programming 8
Gadi Taubenfeld © 2014
Question
Question: Two processes, P1 and P2 each need to hold
five records 1,2,3,4 and 5 in a database to complete. If
P1 asks for them in the order 1,2,3,4,5 and P2 asks
them in the same order, deadlock is not possible.
However, if P2 asks for them in the order 5,4,3,2,1
then deadlock is possible. With five resources, there
are 5! or 120 possible combinations each process can
request the resources. Hence there are 5!×5! different
algorithms. What is the exact number of algorithms
(out of 5!×5!) that is guaranteed to be deadlock free?
5!(4!×4!) = (5!×5!)/5
Chapter 7 Synchronization Algorithms and Concurrent Programming 9
Gadi Taubenfeld © 2014
Strategies for dealing with Deadlocks
q Just ignore the problem altogether
m UNIX and Windows take this approach.
q Detection and recovery
m Allow the system to enter a deadlock state and then
recover.
q Avoidance
m By careful resource allocation, ensure that the
system will never enter a deadlock state.
q Prevention
m The programmer should write programs that never
deadlock. This is achieved by negating one of the
four necessary conditions for deadlock to occur
(mentioned in the next slide.)
Chapter 7 Synchronization Algorithms and Concurrent Programming 10
Gadi Taubenfeld © 2014
Deadlock Prevention
Section 7.2
Chapter 7 Synchronization Algorithms and Concurrent Programming 11
Gadi Taubenfeld © 2014
Deadlock Prevention
Attacking one of the following conditions for deadlock
q Mutual exclusion condition
m one process at a time can use the resource.
q Hold and wait condition
m a process can request (and wait for) a resource
while holding another resource.
q No preemption condition
m A resource can be released only voluntarily by
the process holding it.
q Circular wait condition
m must be a cycle involving several processes, each
waiting for a resource held by the next one.
Chapter 7 Synchronization Algorithms and Concurrent Programming 12
Gadi Taubenfeld © 2014
Attacking the mutual Attacking the no
exclusion condition preemption condition
q Some devices (such as q Many resources (such as
printer) can be spooled printer) should not be
m only the printer preempted
daemon uses printer m can not take the
resource, thus
deadlock for printer printer from a process
eliminated that has not finished
q Not all devices can be
printing yet
spooled
è attack is not useful in è attack is not useful in
general general
Chapter 7 Synchronization Algorithms and Concurrent Programming 13
Gadi Taubenfeld © 2014
Attacking the Hold and Wait Condition
Processes may request all the resources they need in advance.
q Problems
m May not know all required resources in advance.
m Inefficient : ties up resources other processes
could be using.
m Starvation is possible.
Chapter 7 Synchronization Algorithms and Concurrent Programming 14
Gadi Taubenfeld © 2014
Two-Phase Locking
(Notice similarity to requesting all resources at once)
q Phase one
mThe process tries to lock all the resources it
currently needs, one at a time
m if needed record is not avaliable, release
and start over
q Phase two: when phase one succeeds,
m performing updates
m releasing locks
“livelock” is possible.
Chapter 7 Synchronization Algorithms and Concurrent Programming 15
Gadi Taubenfeld © 2014
The time-stamping ordering technique
Time stamps:
q Before a process starts locking a unique new
timestamp is associated with that process.
q If a process has been assigned timestamp Ti
and later a new process has assigned
timestamp Tj then Ti <Tj.
q We associate with each resource a
timestamp value, which is the timestamp of
the process that is currently holding that
resource.
Chapter 7 Synchronization Algorithms and Concurrent Programming 16
Gadi Taubenfeld © 2014
The time-stamping ordering technique
Phase one: the process tries to lock all the resources it
currently needs, one at a time.
q If a needed resource is not available and the
timestamp value is smaller than that of the process,
m release all the resources,
m waits until the resource with the smaller
timestamp is released,
m and starts over.
q Otherwise, if the timestamp of the resource is not
smaller,
m waits until the resource is released and locks it.
Phase two: when phase one succeeds,
q performing updates; releasing locks.
Prevents deadlock and starvation.
Chapter 7 Synchronization Algorithms and Concurrent Programming 17
Gadi Taubenfeld © 2014
Attacking the Circular Wait Condition
Impose a total ordering of all resource types, and
require that each process requests resources in
an increasing order of enumeration.
1 2 3 4 5 6 7
time
account A account B
Solves transferring money between two bank accounts
Chapter 7 We will see other interesting usage of this observation
Synchronization Algorithms and Concurrent Programming
Gadi Taubenfeld © 2014
18
Deadlock Avoidance
Section 7.3
Chapter 7 Synchronization Algorithms and Concurrent Programming 19
Gadi Taubenfeld © 2014
Deadlock Avoidance
Safe and Unsafe States
safe
unsafe
time
deadlock
All terminated!
Chapter 7 Synchronization Algorithms and Concurrent Programming 20
Gadi Taubenfeld © 2014
Basic Facts
q If a system is in safe state è no deadlock.
q If a system is in unsafe state è deadlock
now or in the future.
q Deadlock Avoidance è ensure that a system
will never enter an unsafe state.
Chapter 7 Synchronization Algorithms and Concurrent Programming 21
Gadi Taubenfeld © 2014
Example: Prove that the state below is safe
Allocation
Maximum
P1 1 9
P2 4 5
P3 2 8
available : 2
Chapter 7 Synchronization Algorithms and Concurrent Programming 22
Gadi Taubenfeld © 2014
Proof
Allocation
Allocation
Allocation
Allocation
Allocation
Maximum
Maximum
Maximum
Maximum
Maximum
P1 1 9 P1 1 9 P1 1 9 P1 1 9 P1 1 9
P2 4 5 P2 5 5 P2 0 - P2 0 - P2 0 -
P3 2 8 P3 2 8 P3 2 8 P3 8 8 P3 0 -
available : 2 available : 1 available : 6 available : 0 available : 8
P1 9 9 P1 0 --
P2 0 -- P2 0 --
P3 0 -- P3 0 --
available : 0 available : 9
time
Chapter 7 Synchronization Algorithms and Concurrent Programming 23
Gadi Taubenfeld © 2014
Example: safe and unsafe
Allocation
Maximum
P1 1 9
q If process P1 requests one (out of the 2 avaliable),
P2 4 5
resources the Banker will not allocated it.
P3 2 8
available : 2
P1 2 9 unsafe
state
P2 4 5
P3 2 8
available : 1
Chapter 7 Synchronization Algorithms and Concurrent Programming 24
Gadi Taubenfeld © 2014
The Banker’s Algorithm
q When there is a request q A state is safe if there
for an available resource, exists a sequence of all
the banker must decide if processes <P1, P2, …, Pn>
immediate allocation leaves such that for each Pi, the
the system in a safe state. resources that Pi can still
request can be satisfied by
q If the answer is positive,
currently available
the resource is allocated, resources + resources held
by all the Pj, with j < i.
otherwise the request is
temporarily denied.
Chapter 7 Synchronization Algorithms and Concurrent Programming 25
Gadi Taubenfeld © 2014
The Banker’s Algorithm: commensts
q Can handle Multiple instances.
q Each process must a priori claim maximum
use -- a disadvantage.
q When a process requests a resource it may
have to wait.
q When a process gets all its resources it must
return them in a finite amount of time.
Chapter 7 Synchronization Algorithms and Concurrent Programming 26
Gadi Taubenfeld © 2014
The Dinning Philosophers Problem
Section 7.4
Chapter 7 Synchronization Algorithms and Concurrent Programming 27
Gadi Taubenfeld © 2014
Dining Philosophers
q Philosophers
think
m
m take forks
m eat
m put forks
q Eating needs 2
forks
q Pick one fork at a
time
q How to prevent
deadlock
Chapter 7 Synchronization Algorithms and Concurrent Programming 28
Gadi Taubenfeld © 2014
An incorrect solution
( means “waiting for this forks”)
L L
L L
Chapter 7 Synchronization Algorithms and Concurrent Programming 29
Gadi Taubenfeld © 2014
An inefficient solution
using mutual exclusion
Chapter 7 Synchronization Algorithms and Concurrent Programming 30
Gadi Taubenfeld © 2014
Proving deadlock-freedom & starvation-freedom
Impose a total ordering of all forks, and require that
each philosopher requests resources in an increasing order.
1 2
R
L R
6 3
R R
R
5 4
Chapter 7 Synchronization Algorithms and Concurrent Programming 31
Gadi Taubenfeld © 2014
The Hold and Wait Strategy
Section 7.5
Chapter 7 Synchronization Algorithms and Concurrent Programming 32
Gadi Taubenfeld © 2014
The LR Solution
R R
L L
Chapter 7 Synchronization Algorithms and Concurrent Programming 33
Gadi Taubenfeld © 2014
The LR Solution
Proving deadlock-freedom & starvation-freedom
1 4
R
L L
6 2
R R
L
3 5
Chapter 7 Synchronization Algorithms and Concurrent Programming 34
Gadi Taubenfeld © 2014
Concurrency
How many can eat simultaneously?
Chapter 7 Synchronization Algorithms and Concurrent Programming 35
Gadi Taubenfeld © 2014
At most half can eat simultaneously
Chapter 7 Synchronization Algorithms and Concurrent Programming 36
Gadi Taubenfeld © 2014
Only one third can eat simultaneously
Any algorithm is at most én/3ù-concurrent
Chapter 7 Synchronization Algorithms and Concurrent Programming 37
Gadi Taubenfeld © 2014
In LR only one forth can eat simultaneously
The LR algorithm is at most én/4ù-concurrent
Chapter 7 Synchronization Algorithms and Concurrent Programming 38
Gadi Taubenfeld © 2014
LR
If all want to eat, there is a case where only én/4ù
will be able to eat simultaneously.
( means “waiting for this forks”)
R L
L R
free
Chapter 7 Synchronization Algorithms and Concurrent Programming 39
Gadi Taubenfeld © 2014
Robustness
k-robust: if all except k consecutive
philosophers fail, then one will not
starve.
q Any algorithm is at most
én/3ù-robust.
q The LR algorithm is not 4-robust.
q The LR algorithm is 5-robust iff
n is even.
q There is no 4-robust algorithm
using a hold and wait strategy.
Chapter 7 Synchronization Algorithms and Concurrent Programming 40
Gadi Taubenfeld © 2014
The LLR Solution
R L
L R
Chapter 7 Synchronization Algorithms and Concurrent Programming 41
Gadi Taubenfeld © 2014
LLR
Proving deadlock-freedom & starvation-freedom
3 2
L
R L
0 1
L R
L
5 6
Chapter 7 Synchronization Algorithms and Concurrent Programming 42
Gadi Taubenfeld © 2014
In LLR one third can eat simultaneously
The LLR algorithm is én/3ù-concurrent
A tight bound
Chapter 7 Synchronization Algorithms and Concurrent Programming 43
Gadi Taubenfeld © 2014
Robustness
k-robust: if all except k consecutive
philosophers fail, then one will not
starve.
q The LLR algorithm is not 4-
robust.
q The LLR algorithm is 5-robust iff
n º 0 mod 3.
Chapter 7 Synchronization Algorithms and Concurrent Programming 44
Gadi Taubenfeld © 2014
The Hold and Release Strategy
Section 7.6
Chapter 7 Synchronization Algorithms and Concurrent Programming 45
Gadi Taubenfeld © 2014
The LR wait/release Algorithm
The LR wait/release algorithm is:
q deadlock-free but not L
starvation-free.
R R
q ën/3û-concurrent.
q 3-robust iff n is even.
L L
q Recall: There is no 4-robust
algorithm using a hold and wait R
strategy.
Chapter 7 Synchronization Algorithms and Concurrent Programming 46
Gadi Taubenfeld © 2014
Randomized Algorithms
Section 7.7
Chapter 7 Synchronization Algorithms and Concurrent Programming 47
Gadi Taubenfeld © 2014
Two Randomized Algorithms
The Free Philosophers algorithm is:
q deadlock-free with probability 1,
but is not starvation-free and is
not 2-concurrent.
q 3-robust with probability 1.
The Courteous Philosophers
algorithm is:
q starvation-free with probability
1, but is not 2-concurrent and is
not (n-1)-robust.
Chapter 7 Synchronization Algorithms and Concurrent Programming 48
Gadi Taubenfeld © 2014
