« 私はペンが長い | トップページ

2018年9月17日 (月)

食事をする哲学者、ランポートのパン屋

「食事をする哲学者」問題というのが有ります。この問題の原案は、ダイクストラによって提示された「5台のコンピュータが5台のテープ装置に競合アクセスするという同期問題」です。それがホーアによって「食事をする哲学者」問題にアレンジされたとのことです。その問題とは次のようなものです。

[食事をする哲学者]:円卓で5人の哲学者が食事をしています。隣り合う哲学者の間にはフォークが1本ずつ置かれており、哲学者は、両側のフォーク(両方)を使って食事をします。自分が使うべきフォークを隣の哲学者が使っている間は、自分は食事が出来ません。フォークは、両方を同時に取ることは出来ず、1本ずつ取らなければなりません。この条件の基、誰も飢えることなく食事をしなさい。

\begin{xy} (0,0)*+[o][F-]{1}; (-7,-8)*{{}_\mathrm{fork}1}; (-18,-15)*+[o][F-]{2}; (-10,-24)*{{}_\mathrm{fork}2}; (-10,-35)*+[o][F-]{3}; (0,-32)*{{}_\mathrm{fork}3}; (10,-35)*+[o][F-]{4}; (10,-24)*{{}_\mathrm{fork}4}; (18,-15)*+[o][F-]{5}; (7,-8)*{{}_\mathrm{fork}5} \end{xy}

なぜ5人なのか、なぜ奇数なのか。少し考えてみたのですが、解りませんでした。たぶん、3人でも4人でも問題に変わりは無いと思います。もしかすると、食事の出来る哲学者に偏りが出た場合、それが見やすいのが5人だったのかも知れません。

この問題では、全員が同時に同じ方(例えば右側)のフォークを取ると、逆側のフォークは隣の哲学者が持っていることになり、それが空くのを待つことでデッドロックが発生します。それならば、2本のフォークの順序を「右→左」で取る人と、「左→右」で取る人に分けておけば良さそうだという考えは、誰でも思い付くでしょう。ダイクストラも最初に提案した解のうちの1つが、それだったそうです。ただし、ダイクストラは、5番目の哲学者だけにフォークを取る順序を変えさせたのですが、それでは効率が悪いような気がします(ダイクストラは、あえて効率の悪い例を考えたのかも知れません)。偶数番目の哲学者は右のフォークから、奇数番目は左のフォークから先に取るとした方が素直でしょう。返すのも取ったのと同じ順序にします。

フォークを取る時は相互排除が必要ですが、その方法として Wikipedia の 食事する哲学者の問題 に Chady/Misra の方法が載っています。それは、各フォークを取り合う2人のどちらかがフォークを持っていて、状況に応じてフォークをやり取りすることで相互排除を実現するという方法です。その状況確認にはメッセージを用いており、これは分散システムで使用できることを意味します。 Chady/Misra の方法は2人より多い人数の間でも使えるようになっています。

相互排除の方法には、他にランポートのパン屋が有ります。これも分散システムで利用可能です。ランポートのパン屋は以下のようなものです(「並行プログラミングの原理」参照。競合が2人の場合を示します)。パスカル風仮想言語で書いてみました。

progmam bakary;
var c1, c2, n1, n2: integer;

procedure p1                                procedure p2
begin                                       begin
  repeat                                      repeat
    c1 := 1;                                    c2 := 1;
    n1 := n2 + 1;    // (1)                     n2 := n1 + 1;
    c1 := 0;                                    c2 := 0;
    repeat until (c2 == 0);    // (2)           repeat until (c1 == 0);
    repeat until ((n2 == 0)or(n1 <= n2));// (3)  repeat until ((n1 == 0) or (n2 < n1));
    crit1;        // (4)                        crit2;
    n1 := 0;                                    n2 := 0;
    rem1;                                       rem2;
  forever;                                    forever;
end;                                        end;

begin
  c1 := 0;
  c2 := 0;
  n1 := 0;
  n2 := 0;
  cobegin
    p1 ; p2
  coend;
end;

p1p2 は8行目が微妙に異なっている以外は同じ型になっているので、 p1 についてい説明します。crit1 がクリティカル領域です(4)。 n1 はクリティカル領域に侵入する意思が有ることを示すフラグになっていると同時に競合の優先順位を決定する番号にもなっています。 c1n2 をチェックするタイミングを絞る(1)働きが有り、 (2) によってその同期が保証されます。 (3) で相互排除が確定します。そこでは n1n2 を比較していますが、 (1) より前に p2n1 をチェックしていれば、 n2 < n1 になります。逆に、相手が(1)より後にチェックしていれば n1 < n2 になります。同じタイミングでチェックしたならば、 n1 == n2 ですが、そのときは p1 を優先します。

以上、「食事をする哲学者」と「ランポートのパン屋」に関する話しでした。

« 私はペンが長い | トップページ

プログラミング」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/584699/67176080

この記事へのトラックバック一覧です: 食事をする哲学者、ランポートのパン屋:

« 私はペンが長い | トップページ