Dining Philosophers Problem: Difference between revisions
 Yuron [   PHRhYmxlIGNsYXNzPSJ0d3BvcHVwIj48dHI+PHRkIGNsYXNzPSJ0d3BvcHVwLWVudHJ5dGl0bGUiPkdyb3Vwczo8L3RkPjx0ZD51c2VyPGJyIC8+YnVyZWF1Y3JhdDxiciAvPmludGVyZmFjZS1hZG1pbjxiciAvPnN5c29wPGJyIC8+PC90ZD48L3RyPjwvdGFibGU+] (talk | contribs)m (1 revision imported) |
pc>Yuron No edit summary |
||
| Line 1: | Line 1: | ||
{{#set: Priority=2 | Summary=A 'classic' illustration of deadlocks.}}<!-- | {{#set: Priority=2 | Summary=A 'classic' illustration of deadlocks.}}<!-- | ||
-->{{#invoke:Dependencies|add|Semaphores,4|Deadlock,3}} | -->{{#invoke:Dependencies|add|Semaphores,4|Deadlock,3}} | ||
It seems to be compulsory for all operating systems courses to use | It seems to be compulsory for all operating systems courses to use this illustrative example; therefore there are plenty of [https://en.wikipedia.org/wiki/Dining_philosophers_problem resources] available without adding too much here. | ||
this illustrative example; therefore there are plenty of [https://en.wikipedia.org/wiki/Dining_philosophers_problem resources] available without adding too much here. | |||
The problem illustrates the sort of way that [[deadlock]]s | The problem illustrates the sort of way that [[deadlock]]s can arise by unpredicted interactions with unsynchronised processes. | ||
can arise by unpredicted interactions with unsynchronised processes. | |||
In brief: | In brief: | ||
| Line 17: | Line 15: | ||
*a hungry philosopher picks up one adjacent fork, then picks up the other, then eats then puts the forks down again. | *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 | Left to run randomly – and assuming infinite spaghetti – they will eventually <strong>deadlock</strong>, with each philosopher holding one fork and unable to get the other. | ||
eventually <strong>deadlock</strong>, with each philosopher holding one fork and | |||
unable to get the other. | |||
<blockquote> | <blockquote> | ||
This will (probably) happen more rapidly with just two philosophers; | 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. | ||
the probability will decrease with more. With the algorithm as | |||
stated the risk never disappears. | |||
</blockquote> | </blockquote> | ||
This example illustrates the sort of complex interaction which can | 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 <em>one</em> way: | ||
come from a non-deterministic system. There are various ways to avoid | |||
such problems, provided you spot them coming. Here’s <em>one</em> way: | |||
<blockquote> | <blockquote> | ||
Number the forks (not necessarily in any particular order) and | Number the forks (not necessarily in any particular order) and introduce the rule that everyone has to pick up the lower numbered | ||
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 | ||
utensil first. (Each philosopher has two forks in view.) Now, in | holding another fork. This breaks the symmetry of the problem and guarantees <em>someone</em> can eat – eventually relinquishing cutlery for someone else. | ||
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 <em>someone</em> can eat – eventually relinquishing cutlery for | |||
someone else. | |||
</blockquote> | </blockquote> | ||
Here’s another: | Here’s another: | ||
<blockquote> | <blockquote> | ||
Instead of picking up forks, each philospoher must summon the waiter | Instead of picking up forks, each philospoher 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 <code>get_forks</code> process [[Atomicity|atomic]]. | ||
to pass them. The waiter acts as a centralised arbiter who has an | Clearly this is less efficient than parallel-fork-picking-up but it is safe. | ||
overview of the whole table and makes the <code>get_forks</code> process | |||
[[Atomicity|atomic]]. | |||
Clearly this is less efficient than parallel-fork-picking-up but it | |||
is safe. | |||
Are there problems if we employ <em>more</em> waiters? | Are there problems if we employ <em>more</em> waiters? | ||
</blockquote> | </blockquote> | ||
| Line 54: | Line 38: | ||
… and for [https://www.youtube.com/watch?v=6QgCfnBtF7M light relief]. | … and for [https://www.youtube.com/watch?v=6QgCfnBtF7M light relief]. | ||
---- | ---- | ||
{{BookChapter|7.1.3|293-295}} | |||
{{PageGraph}} | {{PageGraph}} | ||
Revision as of 16:25, 31 July 2019
| 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 philospoher 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 |
|---|
