並行システム
システム情報工学研究科コンピュータサイエンス専攻、電子・情報工学系
新城 靖
<yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/sie/csys-2007/2008-02-29
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/sie/
http://www.cs.tsukuba.ac.jp/~yas/
分散アルゴリズム
分散システムにおける同期
- 論理クロック、Lamportの論理クロック同期アルゴリズム,
- 物理クロック、UTC、NTP
- 分散相互排除、集中、分散、トークンリング
- 選出アルゴリズム
- デッドロック検出
資料：
Ａ．Ｓ．タネンバウム著、水野忠則、鈴木健二、西宮洋太郎、佐藤文明訳、分
散オペレーティングシステム、プレンティスホール (1996)
第３章 分散システムにおける同期
（集中）システムで問題を解くための指令の集まり。
要素間のメッセージの伝達の方法の集まり
- どのコンピュータもシステム全体の状態に関して完全な情報を持たない
- コンピュータは、ローカルな情報だけで決定する。
- １台のコンピュータが故障しても、全体が破滅しない。
singlepoint of failure を回避したい。
- (グローバルな時計が存在しない)
時計を使うアルゴリズムもある。
- 電話で放送
- 電話で多数決
- 時計を合わせる
- 戸籍、住民登録
- 筑波大学安否確認アルゴリズム
マルチスレッド、共有メモリ
- 臨界領域(critical region)
- セマフォ(semaphore)、モニタ(monitor)
- デッドロック
- アトミック・トランザクション
- クロックの同期
- 相互排除
- 選出アルゴリズム
- アトミック・トランザクション
- デッドロック
なぜ難しいか
- メッセージが紛失する
- 通信遅延がある
- 時計がたくさん
- システムが部分的に壊れる(partial failure)
集中システムで、１つ壊れて動かない時は、あきらめがつく。
- クロックを使うアルゴリズムのため
- ファイルの最終更新時刻
- キャッシュの一貫性, HTTP if-modified-since
- メッセージ配信、ネットワーク・ニュース
- 認証チケットの時間切れ
- トランザクション
- 時間は、人間の思考の基本
コンピュータは、時間を追跡する回路を持っている。
水晶発振とカウンタとラッチ。
タイマ割込み。１秒間に５０回〜６０回割込みがかかる。
水晶発振か、電源の周波数を使う。
一回の割込みを、clock tick という。
単一のコンピュータでは、水晶でも問題がない。
複数のコンピュータでは、
クロックの進み方(clock skew)が違うので、だんだんずれてくる。
- 論理クロック
- 内部で一貫性がとれていればいい
- 物理クロック
- 実際の時計と大きくずれていてはいけない
相互作用しないプロセスは、同期がとれてなくてもよい。
事前発生(happens-before)。
「a→b」は、「aはbの前に発生する」
- もしaとbが同じプロセスの事象で、bより前にaが生じるなら、a→bは真であ
る。
- もしaがあるプロセスがあるメッセージを送信したという事象で、
bが別のプロセスでそのメッセージを受信したという事象なら、a→bは真である。
(送信まえには受信できない。
メッセージの到着には、有限の時間がかかるので、送信と同時にも受信できな
い。)
「→」は、推移律(transitive law)が成り立つ。
「a→bかつb→cならばa→cである」
並行性がある：「x→y」も、「y→x」も両方とも偽であることある。
xとyが別々のプロセスで発生して、それらの間でメッセージを交換しない時な
ど。
どちらが先に起きたかということを言えない（言う必要がない）
イベント aについて、次のような性質を持つ時間値C(a) を割り当てる。
- a→b ならば、C(a)＜C(b)
- 常に前進する。逆戻りしない。
C() が与えられたら、論理クロックが実現されたことを意味する。
図(a) 独自のクロックを持つ３つのプロセス。進み方が異なる。
図(b) Lamportのアルゴリズムによるクロックの修正。
２つのイベントの間に必ず１ティック進める。小数点。
同時なら、プロセスＩＤで適当に。
１つの四角には、１つのメッセージだけ。
１つのホストが「同時」に複数のメッセージを送受信することはできない。
この方法でクロックを修正すると、次の性質が得られる。
- 同じプロセスにおいてaがbの前に発生すれば、C(a)＜C(b)となる。
- もしaおよびbが同じメッセージの送信と受信の事象ならば、C(a)＜C(b)
となる。
- すべての事象a,bについて、a≠bならば、C(a)≠C(b)。
(total ordering)
casual ordering。因果律が成り立つ。
基準
- 太陽
- 地球の公転、自転は一定ではない。ふらつきがある。
だんだん１日が長くなってきている。
- 原子時計
- セシウム１３３が 9,192,631,770 回振動。実際の日とずれる。
- UTC (Universal Coordinated Time)。
- 閏秒で調整。
GPS の普及で、正確な時刻が簡単に取り出せるようになった。
NTP で合わせる。
以前の方法。
問題点
進みすぎたクロックを逆行させて戻す変わりに、ペースを落とす。
UNIX
int adjtime(const struct timeval *delta, struct timeval *olddelta)
UTCを持っている時刻サーバに問い合わせる。
- T0: クライアントが要求を送る。
- I : サーバ内の割込み処理
- T1: クライアントが応答を送る。
図？ 時刻サーバに問い合わせる
単純な方法：クライアントの時刻を、送られた UTC に合わせる。
- 問題1: 時刻が逆行することがある。adjtime() を使う。
- 問題2: サーバの割込み処理の時間(I)だけずれてしまう。
- 問題3: 応答メッセージの転送時間は、0ではない。しかも、変動する。
Cristianの方法は、応答メッセージの遅延時間を測定するものである。
転送時間や割込み処理の時間が不明な時には、次の式で転送時間を見積もり、
補正する。
- 遅延を(T1-T0)/2 とする。
- 何回かやって、最小値を調べる。
サーバが１つなら、アルゴリズムとしては問題なし。しかし、次のような問題
がある。
- サーバが落ちている／ネットワークが落ちている
- サーバが狂う
マスターとスレーブがある。
- マスターを１台選ぶ。
- スレーブから情報を定期的に集める。
- 時計の進み具合いの傾向を調べる。
- あまりに大きくずれているものを除外する
単純に平均すると、嘘つきに弱い。
実際にクロックが１００倍速く進むシステムがあった。
fault-tolerant average。
往復時間の誤差。
- インターネット上のクライアントに UTC を提供
- 通信が切れても耐える。冗長性を持たせる。
- 高いスケーラビリティ。合わせる頻度を調整。
- 競合に強い。一種の認証技術を含む。
サーバが木構造で構成される。
- レベルを stratum (ストレータム) と呼ぶ。
- レベルの値が小さいほど正確。
- Stratum 1 は、UTC の供給源に直接接続されている。原子時計やGPSなど。
図？ NTP(Network Time Protocol)サーバのレベル(stratum)
同期方法
- 手続き呼出しモード
- 対称モード
- マルチキャストモード
共有データを他のプロセスが同時に利用しないようにすることを保証する。
- ロック
- セマフォ
- モニタ
- ランデブ
- Mutex
- Java synchronized
集中システムのエミュレーション。
１つのプロセスをコーディネータとして選ぶ。
図？ コーディネータを使う相互排除
普通のプロセス：
- 臨界領域に入る前に、コーディネータに要求メッセージを送る。
- コーディネータから許可の応答が得られれば、臨界領域に入る。
- 臨界領域から出る時には、解放メッセージをコーディネータに知らせる。
コーディネータのプロセス：
- 要求メッセージを受け付けた時に、他に利用しているプロセスがいなけ
れば、許可の応答を送る。
- 他にプロセスがいれば、待ち行列に入れる。
- 解放メッセージを受け取った時に、待ち行列からプロセスを
取り出し、それに応答メッセージを送る。
性質
- 公正(fair)
- 飢餓が起きない
- メッセージが３種類(要求、応答、解放)
- コーディネータの単一箇所性(single point of failure)
- コーディネータへの負荷の集中
故障の単一個所性を避けたい。
仮定
- Lamportのアルゴリズムなどで、論理クロックが同期しており、事象の全
順序が保証されている。
- メッセージ伝送は、信頼性(reliable)がある。
プロセスが臨界領域に入ろうとする時、領域の名前、自分のプロセス番号、現
在時刻のメッセージを用意する。
このメッセージを他のプロセス（自分も含む）に送信する。
あるプロセスがメッセージを受け取った時、次の３つの場合がある。
- 自分が臨界領域にいないし、入ろうともしていないなら、
送信者にＯＫのメッセージを送信する。
- 自分が既に臨界領域にいる時には、応答せず、待ち行列に入れる。
- 自分が臨界領域に入ろうとしていたまだ入っていない時には、
到着したメッセージのタイムスタンプと
他のプロセスに送ったタイムスタンプを比較する。
一番タイムスタンプの低いもの（古いもの）が勝つ。
もし到着した方のメッセージが低いなら、ＯＫを返す。
自分のタイムスタンプが低いなら、待ち行列に入れてなにもしない。
すべてのプロセスからＯＫをもらったら、臨界領域に入る。
臨界領域から出る時には、待ち行列のすべてのプロセスにＯＫを送る。
図？ コーディネータを使わない相互排除の例
アルゴリズムの性質：
- デッドロックも飢餓もない
- プロセス数がnの時、メッセージ数は、2(n-1)
- 故障の単一箇所性は、ない（コーディネータのような死ぬとやばいプロ
セスがない。）
- しかし、単一箇所ではなくて、n箇所に増えている。涙。
- 遅いプロセスがいたら、そこがボトルネックになる。
- グループ通信プリミティブが必要。
結論：元の集中アルゴリズムよりも、遅く、複雑で、高価で、ロバスト性も小
さい。
分散アルゴリズムの可能性が示されたこと、将来への課題、
ほうれん草やラテン語。
たとえネットワークがバス型でも、ソフトウェア的にトークンリングを作る。
図 トークンリング
トークンは、point-to-point のメッセージで送られる。
（グループ通信は使われない。）
隣のプロセスからトークンを受け取ると、自分が臨界領域に入りたければ入る。
性質
- 簡単に正しいことがわかる
- トークンが失われると、再生しなければならない。実際には
失われたことと遅いだけを区別することが難しい。
- プロセスがクラッシュすると、トークンの送信に失敗するという形で
検出できることがある。その時には、クラッシュしたプロセスを
リングから外す。
相互排除アルゴリズムの比較
| アルゴリズム | １回当たりのメッセージ数 | 入る前の遅れ | 問題 |
|---|
| 集中 | 3 | 2 | コーディネータのクラッシュ |
| 分散 | 2(n-1) | 2(n-1) | プロセスのクラッシュ |
| トークンリング | 1〜無限 | 0〜n-1 | トークンの紛失、プロセスのクラッシュ |
分散アルゴリズムでは、しばしばコーディネータが必要になる。
どうやって、コーディネータを選ぶか。
- プロセスには、番号が振られている。
- すべてのプロセスは、他のプロセスの番号を知っている。
生きているプロセスの中で、もっとも高い番号のプロセスを探す。
コーディネータが応答しないと気が付いたプロセスが起動する。
- プロセス P は、ELECTION メッセージを高い番号を持つプロセスに送る。
- もし誰も応答しなければ、P が選ばれ、コーディネータとなる。
- 高い番号のプロセスから１つでも応答があれば、そのプロセスが
引き続き探す(1.にもどる)。
低い番号のプロセスから ELECTION メッセージを受け取ると、OK を返す。
最後に残ったプロセスが、自分がコーディネータだと他のプロセスに知らせる。
ダウンから復帰したプロセスは、この選出アルゴリズムを起動する。
図？ Bullyアルゴリズムによるコーディネータの選出
仮定
- 各プロセスは、次のプロセス(successor)を知っている。
- トークンはつかわない。
- コーディネータがクラッシュしていることに気が付いたプロセス
は、自分の番号を含む ELECTIOIN メッセージ作成し、次のプロセスに送る。
- 次のプロセスがダウンしていれば、スキップして次のプロセスに送る。
この時、自分の番号をメッセージに付加する。
- メッセージが最初のプロセスに戻ってくる。自分のプロセス番号を
含むメッセージを受け取ると、１週したことがわかる。
一番高い番号のものがねコーディネータとなる。
- コーディネータを知らせるメッセージを、次のプロセスに送る。
- 4. が一週すると終り。
複数のプロセスが同時にこのアルゴリズムを起動しても、問題ない。
デッドロックの扱い
- ダチョウ・アルゴリズム。(問題を無視する。)
- 検出。デッドロックを起させて、検出し、回復する。
- 予防。静的に構造的にデッドロックが起きないようにする。
- 回避。資源を注意深く配置することで回避する。銀行家アルゴリズム。
分散では、非常に難しい。回避は、無理。
検出して、プロセスを kill する。
kill では済まないものもある。
トランザクションが使える場合には、回復は単に abort すればよい。
集中型のアルゴリズムを、コーディネータを使って模倣する。
- 各マシンは、ローカルのプロセスの資源要求グラフを管理する。
- コーディネータは、大域的なグラフを管理する。サイクルを検出すると、
ドットロックと判定する。
-
情報の収集方法
- 各マシンが、変更（資源要求、資源確保）があると、コーディネータに通知する。
- 各マシンが、定期的に前回との差分をコーディネータに通知する。
- コーディネータが各マシンに問い合わせる。
単純にやると、偽のデッドロックを検出する。
-
プロセスＢが資源Ｒを解放し、資源Ｔを要求する。
- 先に解放のメッセージが届く。
- 先に要求のメッセージが届く。
図？ コーディネータにおける偽のデッドロックの検出
対策：タイムスタンプを使う。
- コーディネータがデッドロックを検出したように見えた時に、
各マシンにその時刻より前のメッセージをフラッシュさせる。
重たい。
プロセスがブロックする時に起動される。
プローブ・メッセージ：３つ組
- ブロックしたプロセス
- メッセージを送信しているプロセス
- 送信相手のプロセス
- プロセスがブロックする時、プローブ・メッセージを送る。
- メッセージを受け取ると、他のプロセスを待っていたら、第２、第３フィー
ルドを書き換えて転送する。
- メッセージが一巡してもどってきたら、デッドロック。
図？ Chandy-Misra-Haas分散デッドロック検出アルゴリズム
単純に最初のプロセスを殺す方法では、複数のプロセスが同時にこのアルゴリ
ズムを起動すると問題になる。
改良：プローブメッセージに待っているプロセスのリストを付ける。
リストの中で犠牲となるプロセスを一意に決める。
理論的には、改善の余地が大きい。
もっとも代表的な方法：
集中システムでも使われている。
大域的な時間とトランザクションを利用した方法(1)：待機消滅(wait-die)型
アルゴリズム
- プロセスが別のプロセスが保持している資源を
要求してブロックしようとする時、
タイムスタンプを比較する。
- 要求しているプロセスが古い時には、そのプロセスを待たせる。
- 要求しているプロセスが新しい時には、そのプロセスを殺す。
（トランザクションで回復。）
トランザクションの時刻の増加方向にしか延びない。
大域的な時間とトランザクションを利用した方法(2)：負傷待機(wound-wait)
型アルゴリズム
- プロセスが別のプロセスが保持している資源を
要求してブロックしようとする時、
タイムスタンプを比較する。
- 要求しているプロセスが古い時には、
横取り(preempt)させ、
資源を保持しているプロセスを殺す。
（トランザクションで回復。）
- 要求しているプロセスが新しい時には、そのプロセスを待たせる。
wait-die型アルゴリズムでは、若者は繰り返し死ぬことがある。
分散アルゴリズム
分散システムにおける同期
- 論理クロック、Lamportの論理クロック同期アルゴリズム,
- 物理クロック、UTC、NTP
- 分散相互排除、集中、分散、トークンリング
- 選出アルゴリズム
- デッドロック検出
↑[もどる]
←[2月20日]
・[2月29日]
Last updated: 2008/02/28 13:54:45
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>