モニタを使った解法

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

モニタを使った解法

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

「食事する哲学者の問題」の記事における「モニタを使った解法」の解説

下のコード例で示した解法では、フォークが明示的に出てこない。哲学者は両隣の哲学者が食事中でないときだけ食事できる。これはつまり、2本目のフォークを取れない哲学者は必ずフォークを一旦置いて待ち、改めて1本目から試行するという方式である。 フォークごとのロックがないため、哲学者は両隣の哲学者の状態に基づいて食事を開始するかを決めなければならないが、その状態情報が古くないことを保証する必要がある。哲学者2が哲学者1が食事していないことを確認し、次に哲学者3を見るとしたとき、1は2が3を見ている間に食事を始めるかもしれない。この解法ではそのような状況を防ぐため、単一の相互排他ロックを使う。これは特定のフォークに結びついたものではなく、哲学者らの状態を変更する手続きそのものに対応したものである。それがモニタという機構である。手続き test、pickup、putdown はモニタに結びついており、1つの相互排他ロックを共有する。食事できるようになるのを待っている哲学者はフォークを持ってはいない点に注意が必要である。食事したい哲学者がいると、モニタは1つ目のフォークを手放させ、2本目も入手可能になった時点で1本目から再試行させる。食事が終わったら、哲学者はモニタにシグナルを送り、両方のフォークが利用可能な状態になったことを知らせる。 なお、例に挙げたコードではリソーススタベーションを防げない。例えば、1番と3番の哲学者が食事する期間が常にオーバーラップしていると、2番の哲学者はずっと食事できないことになる。 スタベーションを防ぐには、空腹な哲学者が食事できなかった回数を保持し、それがある限度を越えた場合に哲学者の状態を Hungry から Starving に変更する。そして、フォークを与えるかどうかを判断する際に両隣がどちらも Starving でないことという条件を加える必要がある。 どちらかの隣人が Starving だったために食事できなかった哲学者は、事実上その隣人の隣人が食事を終えるのを待つことになる。このように依存関係が追加されることで並行性が減っていく。Starving とするしきい値を大きくすれば、そのような影響を抑えることができる。