Dining Philosophers Problem

Courtesy: Douglas Crockford

The Dining Philosophers Problem is one of the standard exercises in the teaching of concurrent programming. It is instructive in the design of things like operating systems and distributed systems. It is an interesting problem because it introduces management of scarce, shared resources. It is tricky because most naive implementations will result in deadlock. The statement of the problem usually goes like this:

There is a group of philosophers (usually 5) who eat together at a round table. There are forks placed between the philosophers. Philosophers spend their time either thinking or eating. In order to eat, a philosopher must pick up exactly two forks, one on his immediate left, and the other on his immediate right. When he is done eating, he will put his forks down so that his neighbors may use them, and he thinks again.

The Dining Philosophers Problem (aka The Dining Quintuple Problem) was designed in 1965 by Edsger W. Dijkstra to demonstrate the horror that is deadlock. In some versions of the problem, the forks are replaced with chopsticks. This change does not substantively alter the problem, although it can simplify the graphics. Some versions have the philosophers eating spaghetti or rice. In this version, they are dining on shrimp.

Advertisements

One Comment Add yours

  1. e stave says:

    stave Good entry, thanks. Do you have a Xing account?

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