Dinning philosopher problem cs 603 format.ppt

Dining philosopher problem

1. CS 603
Dining Philosopher’s Problem
February 15, 2002

2. Project 2 Starts Today
•The winner:
–NTP Client
•Basic: Program that accepts NTP server as
argument, gets and returns time from that server
–Three points for well document and tested solution
•Extras (worth one additional point):
–Fault Tolerant averaging solution: Accepts up to four
servers and gives average after throwing away “bad”
servers
–Class library: Initialize sets offset from local clock,
“get time” returns local + offset without sending
message

3. Dining Philosopher’s Problem
(Dijkstra ’71)

4. Dining Philosophers: Solutions
•Simple: “waiting” state
–Enter waiting state when neighbors eating
–When neighbors done, get forks
–Neighbors can’t enter waiting state if neighbor
waiting
•Problem:
–Doesn’t prevent starvation
–Requires checking both neighbors at once
•Race condition

5. Fully Distributed Solution
(Lehman and Rabin ’81)
•Problem with previous solutions
–Not truly distributed: Requires some sort of central coordination
or global state
–Non-Symmetric: Different philosophers run different algorithms
•Additional properties:
–Deadlock free: Eventually someone new gets to eat
–Lockout free: Eventually every hungry philosopher gets to eat
–Adversary: One philosopher may try to starve another
•Can’t just hold the fork indefinitely
–Communication only between adjacent philosophers
•No global state
•Can’t communicate with both at same time

6. No Deterministic Solution
•Proof: Assume solution for philosophers
1..n
–Philosophers don’t know their number!
•Philosophers “activated” in order from 1..n
–Each takes one step
•Claim: If symmetric at beginning of round,
will be symmetric at end of round
–If anyone eating, all would be!

7. Probabilistic Solution
•Assume Random “coin
toss”
–Guaranteed with probability
1 to break symmetry
•Idea: Try to get one first
–Then get other
–If can’t get other, put first
down and try again
•But don’t go for the same
fork first every time
Think
trying= true or die
While trying
s= random(left,right)
Wait for fork sthen take it
If fork ~savailable take it
else drop fork s
Eat
drop s=random(left,right)
drop fork ~s

8. Lemmas: Assume Plato sitting
to left of Aristotle
1.If Plato picks up fork infinite number of times, Aristotle
finite number, then
–P(Plato eats infinite number of times)=1
2.If deadlocked, every philosopher picks up fork infinite
number of times with probability 1
3.If after tsteps, both trying to eat, tried to get same fork.
Then with probability ½,
–One picks up fork only finite number of times in future, or
–One gets to eat in next two draws
4.If at time tthe last set of random draws is A, then with
probability 1 there is a later configuration B ≠ A where
two neighbors try to get the same fork first

9. Theorem: P(Deadlock) = 0
•Assume P(Deadlock) > 0
–By Lemma 2, if deadlocked everyone performs infinite
draws
–By Lemma 4, with probability 1 there will be infinite
sequenceof configuration of last draws A
0, A
1, …
satisfying condition of Lemma 3
–By Lemma 3, nsome philosopher eats between A
n
and A
n+2with probability 1
•Therefore if deadlocked, non-deadlocked
condition will occur with probability 1

10. Problem: Not Lockout-free
Courteous Philosophers
•Possible for all but one to
starve
•Solution: If eating and
neighbor trying to eat, once
done wait until neighbor has
eaten before trying again
•Requires more shared
variables
–“signal” to neighbor: On/Off
–Share “last” with neighbor:
Left, Neutral, Right
•Initialized to Neutral
Only need mutual exclusion with
one neighbor at a time
Think
trying= true; left_signal= right_signal
= on
s= random(left,right)
Wait until sdown and
(s-neighbor-signal= off or
s-last= neutral or s-last= s)
then lift fork s
If ~sdown then
lift ~s; trying = false
else drop s
Eat
left-signal= right-signal= off
left-last= right; right-last= left
Drop forks

11. Lesson: Non-Determinism
Gives Additional Power
•In fully distributed system, random variable
solves problems that can’t otherwise be
solved
•Used in practice
–Ethernet: Random backoff if collision
•Makes proving correctness harder
Consider such solutions when building
distributed systems!