Dining philosophers problem

When philosophers problem (English Dining Philosophers Problem ) is a case study in the field of theoretical computer science. Thus the problem of concurrency to be explained, and the risk of jamming of processes. The problem was formulated by Edsger W. Dijkstra.

Construction

Five philosophers sit at a round table, and everyone has a plate of spaghetti in front of him. To eat spaghetti every philosopher needs two forks. However, in the household only five forks were present that now lie between the plates. Thus, the philosopher can not eat at the same time.

Expiration

The philosophers sit at the table and thinking about philosophical problems after. If one is hungry, it attacks the first fork to the left of his plate, then on the right side and begins to eat. If he is tired, he puts the forks back and begins to think again. Should not be in place a fork, if the philosopher wants to take it, so he waits until the fork is available again.

As long as only a few philosophers are hungry, this method works beautifully. However, it may happen that all five philosophers decide to eat at the same time. So grab them all at once her left fork and take the left so that the each of them his colleagues seated right fork away. Now wait every five that the right fork reappears. But that does not happen, because none of the five his left fork travels. The philosophers starve.

Description: Every hungry philosopher takes the two next available forks, regardless of whether they were last used by a neighbor. Hence the case is possible, for example, that any two philosophers always the same two other philosophers over their forks and the fifth philosopher would have to starve.

Application

The scenario of five (sometimes even three) dining philosophers is often used to illustrate the problem of inter-process communication, and resource management in the development of operating systems. The example is intended to illustrate what can happen when parallel processes are dependent on the same resources and are accessing it. Then it may happen that all are blocked, waiting for an event that will never arrive through this blockade. Such a state is referred to as a deadlock or jamming.

To solve the problem typically mutexes or semaphores are used for sequencing, for example, after Peterson 's algorithm or the Dekker algorithm.