Philosophers might be very bright and like to think a lot but they get hungry, too. Here’s what happens when they sit around a table with a bowl of spaghetti in front of them with forks in between them, one to their left and one to their right. While this is a serious problem in computer science, this version is friendly for kids, teachers, and parents.

The formal name for this problem is the Dining Philosophers Problem. First written down by Edsger Dijkstra in a computer science test given to his students, as a question about computers competing for access to a tape drive, Tony Hoare polished the problem into one about hungry philosophers. There are versions where the philosophers eat rice with chop sticks and another where they eat bowls of spaghetti with forks.

The Problem: Hungry Philosophers, Not Enough Forks

The problem to solve, however, remains the same. Philosophers need to alternate between thinking and eating. From Wikipedia:

“Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when he has both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After he finishes eating, he needs to put down both forks so they become available to others. A philosopher can take the fork on his right or the one on his left as they become available, but cannot start eating before getting both of them.

Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply is assumed.

The problem is how to design a discipline of behavior (a concurrent algorithm) such that each philosopher will not starve; i.e., can forever continue to alternate between eating and thinking, assuming that any philosopher cannot know when others may want to eat or think.”

Here is the problem stated as a series of bullet points:

• The five philosophers cannot speak to each other as they sit in front of a bowl of spaghetti with a fork to either side of their bowl.
• Each philosopher must alternate between thinking and eating.
• Each philosopher must pick up a fork on their left and a fork on their right.
• Each philosopher can pick up one fork then wait to pick up another fork. However, they cannot begin eating until they a fork on their left and a fork on their right.
• Each fork can be held by only one philosopher at a time. Forks cannot be shared.
• When a philosopher finishes eating, they must put down both forks so others can eat.

How do the philosophers manage their eating and thinking so there is no interruption and everyone alternates between thinking and eating forever?

This is a fun problem to think about because it is easy to set up in a classroom or with any group of people. Plus everyone can discuss the problem and possible solutions before and after you try out the problem in the real world.

The Dining Philosophers Problem tries to solve a problem common with computers: how do you manage the use of scarce resources among competing users of those resources?

For example, the computer hard drive could be accessed at the same time by an application, the operating system, and the basic operating system that controls direct access to memory and other computer components. Or a video game could send far more data to the computer screen than can be handled by the video card used to display data on the screen: how does the computer decide what data to send to the screen, and in what order?

Managing scarce resources also has real life examples: managing the use of crayons in a classroom, water in a dam, or how many cars can drive down a road.

The Solution

This problem is an example of concurrent programming in computer science, one of several topics computer scientists work on. There is no perfect solution, only solutions that work better than others.

Organize Your Forks

Professor Djikstra, who first included the problem in a test for his computer science students, had one solution in mind. Set a rule that your forks will always be requested in order, that no two forks out of order will ever be used by a philosopher at the same time. In English, number your forks 1 through 5 and ask your philosophers to always pick up a lower-numbered fork first then the higher-numbered fork from the forks to the left and right of their bowl of spaghetti. The order philosophers drop their forks does not matter.

What could possibly go wrong with this solution? Imagine you don’t know how many forks and philosophers are in your problem. The problem suddenly becomes complicated with philosophers having to judge when to drop a higher-number fork to possibly get a lower-number fork.

Get a Waiter to Help

Another possible solution is to hire a waiter. To pick up a fork, a philosopher must ask the waiter for permission. The waiter allows only one philosopher at a time to pick up a fork until they have both forks.

The problem with this solution, aside from breaking the rule philosophers must not talk to each other, is fewer philosophers might eat than the Organize Your Forks solution above. If a philosopher is eating their spaghetti and one of their neighbors requests their forks, all the other philosophers must wait until the request is fulfilled even if they have forks available. The ability to eat at the same time is called parallelism and this solution reduces the amount of possible parallelism.

Cheat (Maybe)

Two computer scientists, K. Mani Chandy and J. Misra, did to the Dining Philosophers Problem what’s called a Kobayashi Maru in Star Trek. If you recall, Captain Kirk failed a no-win simulation game and got so mad he reprogrammed the game so he could win OR fail (of course, he won the reprogrammed game). Kirk cheated with honor. It also helped the no-win Kobayashi Maru simulation game was designed to see how starship captains dealt with total failure.

In this case, Chandy and Misra changed the terms of the Dining Philosophers Problem. They allowed for philosophers, spaghetti, and a limited number of forks. But they made the forks either dirty or clean. And like the Waiter solution, they let the philosophers speak, in their case, to request forks from their neighbors to their left and right.

The Chandy/Misra solution works like this:

• To start, all forks are dirty, not clean.
• When a pair of philosophers want the same fork, create a fork and give it to the philosopher with the lower ID number.
• When a philosopher wants to eat, they must get the forks they need from their neighbors. If a philosopher cannot get a fork, they send a request message to the philosopher who has the fork they need to eat.
• When a philosopher gets a request message for one of their forks, they clean the fork then give the fork to their neighbor philosopher.
• When a philosopher is done eating, all their forks become dirty. If a neighbor philosopher has sent a message to request one of their forks, the philosopher then cleans the fork then gives the clean fork to their neighbor.

This solution allows for a large amount of parallelism, many philosophers eating at the same time. At its heart, the Chandy/Misra solution helps prevent philosophers from eating two times in a row without letting others use their forks. Their solution creates a set of rules about how to distribute forks and how to manage clean and dirty forks. Both rule sets help prevent deadlock, two hungry philosophers unable to eat because they both need the same fork.

Learn More

The Dining Philosophers Problem

http://en.wikipedia.org/wiki/Dining_philosophers_problem

Concurrent Programming

http://en.wikipedia.org/wiki/Concurrent_computing

Kobayashi Maru

http://en.wikipedia.org/wiki/Kobayashi_Maru