「食事する哲学者の問題」の版間の差分
削除された内容 追加された内容
m 外部リンクの修正 http:// -> https:// (books.google.com) (Botによる編集) |
Lingualatin (会話 | 投稿記録) |
||
60行目:
=== Chandy / Misra の解法 ===
1984年、{{仮リンク|K. M. Chandy|en|K. Mani Chandy}}と J. Misra は食事する哲学者の問題に別の解法を提案した。それは、任意のエージェント
# あるリソースを獲得しようとする2人の哲学者の組合せそれぞれについて、フォークを1個生成して識別番号の小さい哲学者に与える。このフォークは ''dirty'' と ''clean'' の2つの状態があって、初期状態は ''dirty'' である。
71行目:
スタベーション問題も解決できる。''clean'' と ''dirty'' のラベルは、最も長く食事にありつけていないプロセスを優先し、最近食事したプロセスの優先順位を下げる効果がある。哲学者がフォークを手放さずに2回続けて食事できないという規定を設けた解法と比べてみると、上に述べた解法の方が柔軟だが、傾向は後者と同じだということがわかる。
この分析から、彼らはフォークの配布とその ''clean'' / ''dirty'' 状態による優先レベルのシステムを導き出した。彼らはこのシステムを非環状グラフで表せるかもしれないとし、もしそうなら、その動作は環状グラフに変換できないことになる。それは、デッドロックが起きないことを保証しているのと等しい。しかし、システムが最初に完全に対称な状態（例えば、哲学者が全員左のフォークを持っている状態）に初期化される場合、グラフは最初から環状になり、デッドロックを防ぐことができない。小さい識別番号の哲学者が ''dirty'' 状態のフォークを持つよう初期化することで、初期状態を非環状グラフにできる。
== 解法の例 ==
| |||