Chandy / Misra の解法

ウィキペディア小見出し辞書

Chandy / Misra の解法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/04 23:33 UTC 版)

「食事する哲学者の問題」の記事における「Chandy / Misra の解法」の解説

1984年、K. M. Chandy（英語版）と J. Misra は食事する哲学者の問題に別の解法を提案した。それは、任意のエージェント（P1, ..., Pn）が任意のリソース（R1, ..., Rm）を獲得しようとする状況に拡張されたものである。ダイクストラの解法とは異なり、順番付けも任意である。彼らはこの一般化された問題を以下のような解法で解決した。 あるリソースを獲得しようとする2人の哲学者の組合せそれぞれについて、フォークを1個生成して識別番号の小さい哲学者に与える。このフォークは dirty と clean の2つの状態があって、初期状態は dirty である。 哲学者がリソースをいくつか組み合わせて使用したい場合（つまり、食事したい場合）、競合している隣人からフォークをもらわなければならない。そのような自分が持っていない全フォークについて要求メッセージを送る。 要求メッセージを受け取ったフォークを持つ哲学者は、持っているフォークが clean なら持ち続けるが、dirty ならそれを手放す。フォークを要求した側に送る際、それを clean 状態にする。 食事が終わると、フォークは dirty 状態になる。他の哲学者がそのフォークを要求したことがあったら、そのフォークを clean 状態にして送る。 この解法は大規模な並列実行でも適用可能である。 スタベーション問題も解決できる。clean と dirty のラベルは、最も長く食事にありつけていないプロセスを優先し、最近食事したプロセスの優先順位を下げる効果がある。哲学者がフォークを手放さずに2回続けて食事できないという規定を設けた解法と比べてみると、上に述べた解法の方が柔軟だが、傾向は後者と同じだということがわかる。 この分析から、彼らはフォークの配布とその clean / dirty 状態による優先レベルのシステムを導き出した。彼らはこのシステムを非環状グラフで表せるかもしれないとし、もしそうなら、その動作は環状グラフに変換できないことになる。それは、デッドロックが起きないことを保証しているのと等しい。しかし、システムが最初に完全に対称な状態（例えば、哲学者が全員左のフォークを持っている状態）に初期化される場合、グラフは最初から環状になり、デッドロックを防ぐことができない。小さい識別番号の哲学者が dirty 状態のフォークを持つよう初期化することで、初期状態を非環状グラフにできる。