Dining philosophers problem

It's an example of a concurrency control problem. It was originally posed by Dijkstra. Here's how it works:

Five (or n) philosophers are seated around a round table. In front of each philosopher is a bowl of spaghetti (or rice). Between each pair of bowls is a single fork (or chopstick). (5 single fork/chopsticks in all)¹. Now, philosophers do one of two things; think, and eat. While thinking, philosopher does not interact with the system. From time to time a philosopher becomes hungry. To eat, she tries to pick up the two closest chopsticks (one from either side of the bowl). Chopsticks may be picked up one at a time, and a chopstick cannot be taken if a neighboring philosopher is using it. If a philosopher successfully gains both chopsticks, she eats until not hungry, without relinquishing the chopstick. Satiated, she then puts down each chopstick and resumes thinking.

The problem is that this situation can lead to deadlock. Imagine that all the philosophers become hungry simultaneously. Each reaches out and takes the chopstick on the left. Now, each reaches for the chopstick on the right. But it's in use! If the philosophers have no way of determining who should yield, they will starve.

Solutions to the problem must ensure not only that this can never occur, but that a situation does not arise in which any specific philosopher can never get the chopsticks (and hence starves, this is a true starvation problem instead of deadlock.)

This represents a set of computer science problems in which a finite set of resources is being shared by users (people, programs, etc) who need to amass a subset of those resources to perform work.

The dining-philosophers problem is a classical problem illustrating the difficulties of doing too much at once and the need for (and advantages of) an ordered, logical approach to solving a problem. The problem is an interesting and relevant one, simply because it compacts down to a simple problem many difficulties in many aspects of life.

The Problem

Consider five philosophers who spend their lives thinking and eating. The philosophers share a common circular table where they may sit together, eating and thinking. The table is surrounded by five chairs, each chair belonging to a certain philosopher. In the center of the table is a bowl of rice, the food of choice for a philosopher hungry from thinking too much. In between each chair, on the table, lies a single chopstick; thus, there are five chopsticks total on the table, one between each consecutive pair of chairs.

When a philosopher is thinking, he or she becomes totally engrossed in the train of thought, and thus entirely ignores the activities of his or her neighbors. Whenever the philosopher becomes hungry, he or she suddenly snaps to attention and tries to pick up the two chopsticks closest to him or her. A philosopher can only pick up one chopstick at once, so the philosopher looks to the left for a chopstick, then to the right for one. Obviously, a philosopher can't pick up a chopstick in the hands of a neighbor. When a philosopher has two chopsticks, the philosopher eats continuously for a while until he or she is full, then the philosopher puts the chopsticks back down, one on the right and one on the left.

Discussion

The dining-philosophers problem is a classic synchronization problem. It's a simple example of the need to allocate several resources (the chopsticks) among several processes (the philosophers) in an efficient manner; in this case, it is to avoid having an upset philosopher on our hands.

This problem has resulted in a huge number of solutions, many of which are often applied to human efficiency, computer science, and other fields where maximum efficiency is absolutely vital. Testing possible solutions against the terms of this problem is often a good way of making a quick analysis of an efficiency scheme.

The Simplest Solution & Why It Fails

The simplest solution of all is simply to have the philosophers grab for chopsticks whenever they might be hungry. The philosopher first grabs the left chopstick (or waits on it to be finished), then grabs the right chopstick (or waits on it to be finished), then eats, then puts down the right chopstick, then the left, for example. Whenever a philosopher becomes hungry, the philosopher simply goes through this procedure to eat.

The gaping flaw is the possibility of an infinite deadlock if all of the philosophers become hungry at once. They all immediately grab the chopstick to their left, then turn to their right and wait on that chopstick. With all five philosophers waiting, the system becomes deadlocked and the philosophers starve to death.

As a result, a better solution to the problem must be engineered; one that doesn't create a deadlock or, if one does happen, the philosophers have a way of breaking out of it.

Some Real Solutions

One solution would be to banish a philosopher from the table, thus emptying a seat. This leaves five chopsticks for four people, so at least one of the philosophers will be able to eat; thus, no deadlock. This means that each system must have more resources available than tables, in essence.

Another solution is to say that a philosopher can only pick up chopsticks if both are available, and then only if the neighbors are not going to pick them up. This is a permissive style that causes some extra slowdown by adding the step of permissions, but it keeps all of the philosophers alive, which is the most important thing.

A third solution is an asymmetric one: number the philosophers starting at an arbitrary chair and continuing around the table. Then, a philosopher with an odd number picks up the left chopstick and then the right, and the even numbered philosophers pike up the right chopstick and then the left. Thus, philosophers 2, 3, and 4 only can be missing a pair if one of the two people at their sides are actually eating (not just waiting), thus making sure a deadlock is impossible.

There are countless more possible solutions to the dining-philosophers problem. The primary factor in deciding if a solution is good or not is to make sure that there are no deadlocks or long pauses in the procedure; in other words, a good solution makes sure a philosopher doesn't starve to death.

Solutions to this problem show up regularly in all sorts of areas, from biology to psychology to computer science. The problem of synchronization is a fundamental one in our world, and the dining-philosophers problem addresses it simply, clearly, and directly.