Dining Philosophers

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:

dp

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.

So, here are three different “solutions” to the dining philosopher’s problem for Oracle.

The code you’ll find in the link contains several sections:

  1. Setup code to create the tables with the philosophers and their chopsticks.
  2. 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.
  3. Three different eating functions, representing the three typical solutions to shared resource problems.
  4. add_philosopher code that will allow us to add philosophers to the table and watch them compete for chopsticks.

I also have a nice shell script that runs the five philosophers we need to make the problem interesting.

Now, some explanation about the three eating procedures.

  1. 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.
  2. 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.
  3. 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.

About these ads

14 Comments on “Dining Philosophers”

  1. A few annoying comments first (sorry)

    1) use primary keys (to prevent INSERT from inserting rows that exist)
    2) use slash (/) after create procedure
    3) Do not create objects under SYSTEM, prefer SCOTT, or just create an user…
    4) add your name in the top of the script, maybe also a link to this page

    Ok… I have tried your script, but I failed to understand the problem/solution.

    I would start with philosopher 1 an 3, wait until they finish their plate, then go to 2 and 4, let them finish, then go to 5. How would non-speaker decide about a max time?

    I wish I could come to HotSOS to see your live demo :)

    ABout : “Each philosopher can only pick up one chopstick at a time” I find this ambigous. Once we see philosoph one take one stick, we have to wait for philosoph 3 to pick one too?

    Anyone, thanks for the disctraction ;)

  2. Forgive me for being dense on a Sunday evening.
    In the first “solution”, are you saying that Oracle will kill one of the sessions (shoots the philosopher in the head) the other 4 will never deadlock each other again ?

  3. OCP Advisor says:

    A very fascinating post illustrating concurrency for the layman!
    Definitely one of the my nominations for Oracle blogger of the Year award.

  4. ittichai says:

    Thanks for thought-provoking post. Base on reading from wiki (http://en.wikipedia.org/wiki/Dining_philosophers), it looks like the “partial hierarchy” is not the only good solution. The “Chandy / Misra solution” seems to be an alternative for a higher-numbered record system.

  5. […] about concurrency, thinking particularly about latching. I see that Chen Shapira has published an interesting note on the “Dining Philosophers” problem that she’s planning to use in her presentation on concurrency at the Hotsos conference this […]

  6. prodlife says:

    @Hemant,

    After Oracle shoots philosopher #5, philosopher #4 will always have access to his left chopstick, so once he grabbed his right chopstick, he can eat right away, he doesn’t have to wait for anyone else. So we eliminated the possibility of all processes holding one resource while waiting for another, as philosopher #4 will not have to do this any more.

    Hope this helps :)

  7. prodlife says:

    @Laurent

    * Thanks for the corrections. I’ll fix the script to reflect your feedback.
    * I’m not sure I understand the following question:
    “How would non-speaker decide about a max time?”

    The solution you described is perfect, but it requires the philosophers to coordinate with each other, or to have a “waiter” that will sit philosophers by turn. It is possible, but its nice to see that you can also coordinate the non-speaking philosophers without a third party.

    * “Each philosopher can only pick up one chopstick at a time” – the idea is that no one can pick two chopsticks at once. However all five philosophers can pick up one chopstick each at the same time (leading to a deadlock or starvation).

  8. prodlife says:

    @Ittichai

    Chandy/Misra solution is great, but requires interprocess communication (philosophers requests forks from one another), which means adding pipes to the script, which seemed too complicated to me. I just wanted to show one good solution (there are few more).

    It is exciting to see how idea similar to Chandy/Misra solution is used in Oracle RAC for managing blocks in the global cache!

  9. Ok, understood, one could pick up a stick, wait one nanosecond and pick the otherone, so it would not be “at once”. As soon as one pick a stick, he is number 1 and he picks the both sticks, then number three picks his sticks …

    The issue is, if all take the same decision at the same time, it will not work. This is surely what you call concurency :)

  10. Log Buffer says:

    Back to Chen for a moment. She gives a sneak preview of her Hotsos presentation, in her article on the dining philosophers problem, which she uses as a way to think about concurrency issues.

    Log Buffer #134

  11. Chen,

    Very interesting and creative ways to examine and understand concurrency with Oracle! I need to test out your scripts with 11gR2 beta as part of my beta test results.

    Regards,
    Ben

  12. prodlife says:

    Thanks Ben, and good luck with the 11gR2 tests :)

  13. Connor says:

    Hi Chen,

    Just a tidy up of the routines by incorporating them into a package, and some IOT’s…Feel free to use or discard.

    http://www.oracledba.co.uk/misc/dining_phil.sql

    Cheers
    Connor


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 3,114 other followers