相互排除

分散システム

                                       電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/dsys-1997/1998-02-10 /mutual-exclusion.html
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html

■相互排除

◆集中システム

• ロック
• セマフォ
• モニタ
• ランデブ
• Java synchronized

◆コーディネータを使うアルゴリズム

普通のプロセス：

1. 臨界領域に入る前に、コーディネータに要求メッセージを送る。
2. コーディネータから許可の応答が得られれば、臨界領域に入る。
3. 臨界領域から出る時には、解放メッセージをコーディネータに知らせる。

1. 要求メッセージを受け付けた時に、他に利用しているプロセスがいなけ れば、許可の応答を送る。
2. 他にプロセスがいれば、待ち行列に入れる。
3. 解放メッセージを受け取った時に、待ち行列からプロセスを 取り出し、それに応答メッセージを送る。

• 公正(fair)
• 飢餓が起きない
• メッセージが３種類(要求、応答、解放)
• コーディネータの単一箇所性単一箇所性(single point of failure)
• コーディネータへの負荷の集中

◆分散相互排除

• Lamportのアルゴリズムなどで、論理クロックが同期しており、 事象の全順序が保証されている。
• メッセージ伝送は、信頼性(reliable)がある。

プロセスが臨界領域に入ろうとすると、 領域の名前、自分のプロセス番号、現在時刻のメッセージを用意する。

このメッセージを他のプロセス（自分も含む）に送信する。

あるプロセスがメッセージを受け取った時、次の３つの場合がある。

• 自分が臨界領域にいないし、入ろうともしていないなら、 送信者にＯＫのメッセージを送信する。
• 自分が既に臨界領域にいる時には、応答せず、待ち行列に入れる。
• 自分が臨界領域に入ろうとしていたまだ入っていない時には、 到着したメッセージのタイムスタンプと 他のプロセスに送ったタイムスタンプを比較する。 一番タイムスタンプの低いもの（古いもの）が勝つ。 もし到着した方のメッセージが低いなら、ＯＫを返す。 自分のタイムスタンプが低いなら、待ち行列に入れてなにもしない。

すべてのプロセスからＯＫをもらったら、臨界領域に入る。

臨界領域から出る時には、待ち行列のすべてのプロセスにＯＫを送る。

アルゴリズムの性質：

• デッドロックも飢餓もない
• プロセス数がnの時、メッセージ数は、2(n-1)
• 故障の単一箇所性は、ない（コーディネータのような死ぬとやばいプロ セスがない。）
• しかし、単一箇所ではなくて、n箇所に増えている。涙。
• 遅いプロセスがいたら、そこがボトルネックになる。
• グループ通信プリミティブが必要。

結論：元の集中アルゴリズムよりも、遅く、複雑で、高価で、ロバスト性も小 さい。

分散アルゴリズムの可能性が示されたこと、将来への課題、 ほうれん草やラテン語。

◆トークンリング・アルゴリズム

トークンは、point-to-point のメッセージで送られる。 （グループ通信は使われない。）

隣のプロセスからトークンを受け取ると、自分が臨界領域に入りたければ入る。

性質

• 簡単に正しいことがわかる
• トークンが失われると、再生しなければならない。実際には 失われたことと遅いだけを区別することが難しい。
• プロセスがクラッシュすると、トークンの送信に失敗するという形で 検出できることがある。その時には、クラッシュしたプロセスを リングから外す。

◆まとめ