「食事する哲学者の問題」の版間の差分

もう1つの単純な解法は、リソース（この場合はフォーク）に[[順序集合|半順序]]を割り当てる方法で、リソースの要求順序は常にリソースの順序の通りに行い、リソース解放はその逆の順序に行う。そして、順序的に無関係なリソースをあるユニットが同時に使うことはないとする。リソース（フォーク）に1から5までの番号を付与し、動作ユニット（哲学者）は常に番号の若小さい方のフォークを先にとり、それから番号の大きい方のフォークをとる。個々の哲学者がとるフォークの番号は決まっている。そして、フォークを置く場合は番号の大きい方を先に置き、それから番号の若小さい方のフォークを置く。この場合、5人の哲学者のうち4人が同時に番号の若小さい方のフォークをとると、番号の一番大きいフォークだけが残ることになり、5番目の哲学者はフォークをとることができない。さらに、その番号が一番大きいフォークをとれる哲学者は1人しかいないため、その哲学者だけが両方のフォークを持って食事できる。彼が食事を終えてフォークを置くとき、まず番号の大きい方から置き、続いて番号の若小さい方のフォークを置くので、後者のフォークを待っていた哲学者がそのフォークをとって食事を始められるようになる。

この分析から、彼らはフォークの配布とそのclean/dirty状態による優先レベルのシステムを導き出した。彼らはこのシステムを非環状グラフで表せるかもしれないとし、もしそうなら、その動作は環状グラフに変換できないことになる。それは、デッドロックが起きないことを保証しているのと等しい。しかし、システムが最初に完全に対称な状態（例えば、哲学者が全員左のフォークを持っている状態）に初期化される場合、グラフは最初から環状になり、デッドロックを防ぐことができない。若小さい識別番号の哲学者がdirty状態のフォークを持つよう初期化することで、初期状態を非環状グラフにできる。