Dining Philosophers Problem
| Depends on | Semaphores • Deadlock |
|---|
It seems to be compulsory for all operating systems courses to use this illustrative example; therefore there are plenty of resources available without adding too much here.
The problem illustrates the sort of way that deadlocks can arise by unpredicted interactions with unsynchronised processes.
In brief:
- five philosophers sit around a round table; each has a plate of spaghetti.
- (the number five is arbitrary; if you want a simplification, try two.)
- five forks are distributed evenly – one between each pair of neighbours.
- (oriental versions use chopsticks; it doesn’t matter)
- it takes two forks to eat.
- each philosopher independently thinks for a while, then gets hungry…
- a hungry philosopher picks up one adjacent fork, then picks up the other, then eats then puts the forks down again.
Left to run randomly – and assuming infinite spaghetti – they will eventually deadlock, with each philosopher holding one fork and unable to get the other.
This will (probably) happen more rapidly with just two philosophers; the probability will decrease with more. With the algorithm as stated the risk never disappears.
This example illustrates the sort of complex interaction which can come from a non-deterministic system. There are various ways to avoid such problems, provided you spot them coming. Here’s one way:
Number the forks (not necessarily in any particular order) and introduce the rule that everyone has to pick up the lower numbered utensil first. (Each philosopher has two forks in view.) Now, in the worst case,no one picks up fork #5 unless (s)he is already holding another fork. This breaks the symmetry of the problem and guarantees someone can eat – eventually relinquishing cutlery for someone else.
Here’s another:
Instead of picking up forks, each philosopher must summon the waiter to pass them. The waiter acts as a centralised arbiter who has an overview of the whole table and makes the
get_forksprocess atomic. Clearly this is less efficient than parallel-fork-picking-up but it is safe. Are there problems if we employ more waiters?
There are other ways of solving this too.
Here’s a 2 min. animation – as mentioned, it works with chopsticks too!
… and for light relief.
| Also refer to: | Operating System Concepts, 10th Edition: Chapter 7.1.3, pages 293-295 |
|---|
