Dining PhilosophersPosted: January 31, 2009
The Dining Philosophers problem is probably the most famous of the classic synchronization problems. Posed and solved by Edsger Dijkstra in 1965, it became famous not because it is practical, but because it demonstrate in a nicely visual way some of the dangers inherent in careless sharing of resources.
Five philosophers are sitting around a round (oak) table. Each of the five philosophers has a bowl of rice, and between every two bowls there is a single chopstick. As illustrated in the following diagram:
Philosophers never talk to each other. They spend their time thinking. When a philosopher becomes hungry, she attempts to pick up the two chopsticks closest to her (the ones that are shared between her and her left and right neighbors). Each philosopher can only pick up one chopstick at a time. Then she eats, without putting down the chopsticks. When she is done, she puts both chopsticks down and resumes thinking.
We must find a method that will allow the five philosophers to share five chopsticks and eat without letting any philosopher starve from prolonged lack of access to chopsticks.
As I wrote above, this is a very famous and non-practical concurrency problem. Surprisingly, no one demonstrated it in PL/SQL on Oracle database yet.
The code you’ll find in the link contains several sections:
- Setup code to create the tables with the philosophers and their chopsticks.
- set_status procedure that allows the philosopher to announce their status (eating, hungry) to us, so we can monitor their progress. This is an autonomous transaction, because we don’t want the philosophers to drop their chopsticks while announcing that they are eating.
- Three different eating functions, representing the three typical solutions to shared resource problems.
- add_philosopher code that will allow us to add philosophers to the table and watch them compete for chopsticks.
Now, some explanation about the three eating procedures.
- The first one is the most trivial one. A philosopher grabs the right chopstick, then the left one and then eat. If any stick is busy, we wait. Note that for some time efficiency (and CPU killing) the philosophers eat very very fast in this version. Run this version and very soon, all philosophers will simultaneously pick up their right sticks and wait for the left to become free. They could wait a long time, but Oracle will soon choose one of them as the deadlock victim and allow the other four to proceed eating in peace.
- An attempt of avoiding deadlocks – Each philosopher picks up her right stick, and if she sees the left one is taken, she drops her right stick and tries all over again. This will ensure no deadlocks (since waiting philosophers will not hold their sticks), but we are likely to encounter a situation where a philosopher keeps picking up and dropping his right stick without ever getting to eat. It is unlikely that this will continue forever, but it may continue enough to make our philosopher very unhappy with her response times. Since each philosopher should be able to eat on average 400ms every second, if a philosopher did not eat for an entire second we will consider her dead from starvation. If you run this example, you should see at least one philosopher dead from starvation.
- At last a good solution! We avoid starvation by not dropping the stick we are already holding, and avoid deadlocking by switching the order in which we pick up the sticks. One of our philosophers will pick his left stick first. This solution is also called “partial hierarchy” – we make sure the blocking graph will be a tree and not a cycle. Run this example and see that you encounter no deadlocks and no starving philosophers.
Readers who made it this far – this example will be a part of my HotSos presentation (demonstrating two concurrency sins – deadlocks and starvation). Any comments are appreciated. If you ran my code and had problems, or worse, failed to run into dead philosophers, let me know. If you think my code plain sucks, let me know. If you didn’t understand what I’m trying to say or why I’m trying to say it, also let me know.