What Is the Dining Philosophers Problem?

The dining philosophers problem is a thought experiment or example used in the field of computer science. The problem uses an analogy to illustrate the synchronization issues that can arise when computers share resources. Computer scientists use the dining philosophers problems to teach students about the algorithms used to resolve these issues.

The scenario of the dining philosophers problem is a circular table at which five philosophers are seated. In the center of the table is a bowl of noodles or other food. Each philosopher has one fork or chopstick on either side, meaning that there are five forks or chopsticks in total. In order to eat, a philosopher needs two utensils. Each philosopher also has to spend some time thinking, and cannot think and eat at the same time. The heart of the dining philosophers problem is the difficulty of preventing deadlock.

Deadlock in this problem occurs when philosophers put themselves into a position where they can neither think nor eat. For example, if each philosopher were to pick up the utensil to his left, no one would be able to eat, because all the utensils would be in use but no philosopher would have two. In order to allow all philosophers to eat, the student must create an algorithm that ensures that some philosophers are eating while others are thinking. This allows both eating and thinking to continue without stalling.

There are a number of possible solutions to the dining philosophers problem. One solution involves creating a sixth character, the waiter, who gives or denies permission for philosophers to pick up their forks. Others involve regulating the order in which philosophers pick up and put down their forks to maximize availability. Others involve telling the philosophers to check whether their neighbors are eating before trying to eat. In essence, each solution involves developing a set of rules, called an algorithm, which governs when the philosophers think, eat, or pick up and put down their utensils.

The dining philosophers problem was first expressed by Dutch computer scientist Edsger Dijkstra in 1965 as an exam question for students. Since then, the problem has undergone a number of changes. It appears in a number of slightly different formats, some of which only change the details of the story but others which propose additional limitations on the problem to demonstrate difficult concepts. The most common modern version was created by Tony Hoare.