土居範久「相互排除問題」を読みました

共有記憶を用いた相互排除

飢餓状態に陥るプロセスがないとき、そのアルゴリズムは公平(fair)であるという。

整構造化表現とは何ですか。

また、並行プロセスを実現する際に注意すべきことは、デッドロック(dead-lock)、すなわち決して起こり得ない事象を待つ状態、に陥らないようにすることと、飢餓状態(starvation)、すなわち特定のプロセスだけが永遠に待たされる状態、が生じないようにすることである。

際どい部分を実行するに当たっては、その際どい部分を相互排除するために、際どい部分に入ることができるかどうか確かめる必要がある。この部分をプレリュード(prelude)と呼ぶ。

際どい部分から出るときには、それらのひとつが入れるようにするか、待っているプロセスがなければ際どい部分が空いた状態にするかする必要がある。この部分をポストルード(postlude)と呼ぶ。

ソフトウェアによる解法

Dekkerのアルゴリズム

まず、二つのプロセスの間で相互排除を行うことを考える。

そこで、共有変数turnを使って入る順番を覚えておく。

しかし、これではうまくいかない。二つのプロセスが”ほぼ同時に”プレリュードを実行し、usingがfalse(偽)であることを検出して、usingにtrueを設定し、共に際どい部分に入ってしまうことが起き得るからである。

そこで、プロセスが際どい部分の中にいるか外にいるかを示す共有変数controlを導入してみることにしよう。

しかし、この解では条件(5)を満たしていない。というのは、たとえ一方が入っていないときですら、自分の番が来なければ入れないからである。

そこで、入る順番を覚えておき、同時に入りたいような状態が生じたときに限って、その順番に従うようにしてみると、この問題はすべて解決する。この解は、オランダの数学者Th.J.Dekkerによって初めて与えられたので、Dekkerのアルゴリズムと呼ばれる。

たとえば、プロセスが３個ある場合について考えると、２個のプロセスが共に内側のループで待っているにもかかわらず、順番を示すturnが際どい部分に入ろうとしていないプロセスを指していることも起こり得るからである。

turnの値を自分にしようとして互いに張り合うのだが、turnは際どい部分に入るための”鍵”だと考え、これを奪い合うような状況を考えるとわかりやすい。

(a)証明

その結果、b[turn]はfalseなので、ひとつ以上のプロセスがL3でb[turn]=falseになり、”turn:=i”を実行することになる。

cで相互実行が起こり得ないことを、また、bとturnで相互封鎖が起こり得ないことを保証している。

したがって、Dijkstraの相互排除問題の解が満たさなければならない条件に、さらに、次のような条件が加わることになる。

(7)際どい部分に入ろうとするプロセスは有限時間内に入ることができる。

同期基本命令とは何ですか。

同期問題

セマフォアとは何ですか。

モニタによる五人の哲学者の食事問題の解とはどういうことですか。共有記憶を用いた相互排除と並べて見てみます。

共有記憶を用いた相互排除について、ソフトウェアによる解法とハードウェアによる解法を並べて見てみます。

同期基本命令

”高々”操作および”少なくとも”操作は、P-V命令、逆P-V命令(inverse P-V operation)およびawait-cause命令[Brinch Hansen 1972a][Brinch Hansen 1973]を用いて実装することができる。[土居 1981]。

ハードウェアによる解法

順路式、強制論理、待合せとは何ですか。

CSPの待合せの概念を拡大したものを採用したものにAdaがある。

この表記法を用いて表した表現を強制論理(forcing logic)と呼ぶ。

したがって、プロセス間のメッセージ通信にもとづいた相互排除アルゴリズムが考えられる。

トークンがプロセス間を動く順序を先天的に与えない最初の完全な解をLamportが考案した。

まず、１章でのturnのような帯域的な変数を用いず、プロセスに局所的かあるいは他のプロセスからは読み出せても書き込むことができない変数だけを用いるアルゴリズムについて考察する。