Philosopher problem

from Wikipedia, the free encyclopedia
Structure of the Philosophers Problem

When philosophers problem ( English dining philosophers problem- ) is, to a case study in the field of theoretical computer science . This is intended to illustrate the problem of concurrency and the risk of processes getting stuck . The problem was formulated by Edsger W. Dijkstra .

construction

Five philosophers are seated at a round table, each with a plate of spaghetti. Every philosopher needs two forks to eat spaghetti. However, there were only five forks in the household, which are now between the plates. So the philosophers cannot dine at the same time. Everyone can only take the two forks that are to the right and left of them.

procedure

The philosophers sit at the table and think about philosophical problems. When one gets hungry, he grabs the fork on the left of his plate first, then the one on the right and begins to eat. When he is full he puts the forks back and starts thinking again. If a fork is not in its place when the philosopher wants to pick it up, he waits until the fork is available again.

As long as only individual philosophers are hungry, this procedure works. But it can happen that all five philosophers decide to eat at the same time. So they all grab their left fork at the same time and take away the right fork of the colleague sitting on their left. Now all five are waiting for the right fork to reappear. But that doesn't happen because none of the five put their left fork back. The philosophers are starving.

Variation: Each hungry philosopher takes the next two available forks, regardless of whether they were last used by a neighbor. This z. B. the case is possible that every two philosophers always hand over their forks to the same other two philosophers and the fifth philosopher would starve to death.

application

The scenario of the five (occasionally only three or four) dining philosophers is often used to illustrate the problem of interprocess communication and resource management in the development of operating systems . The example is intended to show what can happen when parallel processes rely on the same resources and access them at the same time . Then it can happen that everyone is blocked and waiting for an event that will never occur due to this blockage. Such a condition is known as deadlock or deadlock .

To solve the problem, mutexes or semaphores are typically used for sequencing , for example according to the Peterson or Dekker algorithm .

See also

literature

  • Abraham Silberschatz & James L. Peterson: Operating Systems Concepts. Addison-Wesley 1988, ISBN 0-201-18760-4
  • K. Mani Chandy & Jayadev Misra: The Drinking Philosophers Problem. In: ACM Transactions on Programming Languages ​​and Systems. Vol. 6, No. 4, October 1984, pp. 632–646 ( PDF; 960 kB )
  • Edsger W. Dijkstra : Hierarchical ordering of sequential processes. In: Acta Informatica. 1 (2), 1971, pp. 115-138 ( PDF; 1.0 MB )
  • Daniel J. Lehmann & Michael O. Rabin : On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. In: Principles Of Programming Languages ​​1981 (POPL '81). 1981, pp. 133-138

Web links