The Dining Philosophers Problem
The Dining Philosophers Problem
The dining philosophers problem is a classic concurrency problem dealing with synchronization. Gather round and I'll tell you how it goes:
Five philosophers are sitting at a table.
Now, each philosopher has two forks: left fork and right fork. If a Swanson gets two forks, he can eat!
If he only has one fork he can't eat :(
So the Swansons need to learn to share forks:
The dining philosophers problem is: how do you make sure every Swanson gets to eat?
Deadlock
Don't get me wrong, I love Swansons. But damn they are competitive. As soon as I told them to start eating, every Swanson grabbed a fork:
And then they waited for someone to give up their fork so they could eat. But of course, "a Swanson never gives up his fork!" sigh So they waited forever and eventually died in their stupid log cabin. Great job, guys. When all Swansons are stuck, that is called deadlock.
Livelock
Alright Rons. I'm going to set a time limit. If you have been waiting for a fork for 10 minutes, you need to give up your fork. And wait 10 minutes before you try to pick up a fork again. By then, someone else will be done and you can use his fork:
Now you can't have deadlock. But if all Swansons do these actions at the exact same time, you now have livelock:
Yay! Nothing can go wrong now! Right?
30 minutes later
So let me get this straight...
- You all picked up your fork at the exact same time.
- 10 minutes later, you all put down your forks.
- 10 minutes later, you just picked up your forks again! This will go on forever!
What do, nephew? You Swansons will starve!
Resource Hierarchy
Let's number the forks:
Now Rons, the rule is, if you're using two forks, you need to pick up the lower numbered fork first.
Now let's see what happens:
- Ron #1 picks up fork #1
- Ron #2 picks up fork #2
- Ron #3 picks up fork #3
- Ron #4 picks up fork #4
- Ron #5 can't pick up fork #5! Because he will need two forks and he needs to pick up the lower numbered fork first!
So fork #5 goes to Ron #4 – no deadlock!
Cool, resource hierarchy avoids deadlocks! But it is slow. Suppose you have forks #3 and #5. Then you decide you need fork #2. Well forks #3 and #5 are larger numbers. So you'll have to:
- put down fork #5
- put down fork #3 (the order you put these down in doesn't matter)
- pick up fork #2
- pick up fork #3
- pick up fork #5
Ugh, what a waste of time!
Semaphores
Here's an easier solution: if there are 5 forks, only 4 Swansons should be allowed at the table. We'll have a waiter control access to the table:
If there are < 4 Swansons on the table, you can join. Otherwise you have to wait until there are < 4 Swansons!
Ok, this prevents deadlock, but you can still have starvation...a Swanson could wait forever and never get to sit at the table. Unless he kills off one of the other Swansons.
Chandy/Misra
Now I've got it. All forks can be clean or dirty:
Initially all forks are dirty:
Now:
-
Number all the Swansons
-
For every pair of Swansons, give the fork to the guy with the smaller id:
- When a Swanson needs a fork, he asks his neighbor for his fork. When his neighbor gets the request:
- if his fork is clean, he keeps it.
- if his fork is dirty, he cleans it and sends it over.
When a Swanson has eaten, all his forks become dirty.
Bam! Starvation problem solved! The guys who are starving get a higher priority than the guys who are eating!
Q. Swansons 3 and 4 both only have one fork. Suppose Swanson #3 requests a second fork from Swanson #4. Will Swanson #4 give up his fork even though he didn't eat?
A. YES. According to the rules of Chandy-Misra, Swanson #4 would have to clean his fork and send it over to Swanson #3.
