分散プログラミングと同期

並列分散ソフトウェア

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

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2003-12-25
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/
http://www.is.tsukuba.ac.jp/~yas/index-j.html
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html

■復習

■今日の重要な話

分散アルゴリズム

分散システムにおける同期

資料:

A.S.タネンバウム著、水野忠則、鈴木健二、西宮洋太郎、佐藤文明訳、分 散オペレーティングシステム、プレンティスホール (1996)
第3章 分散システムにおける同期

■分散システムの性質と目標

◆分散システム

離れていても心は1つ。

◆集中システム

◆分散システムの利点

◆分散システムの弱点

◆分散システムの設計目標

◆透明性

分散透明性 (network transparency)
システムが複数のコンピュータから構成されていることを、使っている人が 気が付かない

◆フォールト・トレランス

システムが部分的に壊れる(partial failure) 1台のシステムが故障する確率:0.05

4台同時に故障する確率:0.054==0.00006

4台のどれかが1つでも故障する確率== 1-(4台すべてが動いている確率) :1-(1-0.05)4==0.18549375

◆スケーラビリティ

構成要素の数が増えた時にどうなるか。 10台で動くものが100台、1000台で動くか。

◆(集中)アルゴリズム

(集中)システムで問題を解くための指令の集まり。

◆分散アルゴリズム

要素間のメッセージの伝達の方法の集まり 時計を使うアルゴリズムもある。

◆分散アルゴリズムの例

◆キーワード

完全を目指そうとすると、急激にコストが高くなる。

実用になり、かつ、利益に見合うコストで実現できる範囲を探すことが大事に なる。

■分散システムにおける同期

◆集中システムの問題

マルチスレッド、共有メモリ
C:
struct account
{
    lock_t l ;
    int    balance ;
};

withdraw( struct account *a, int amount )
{
    lock( &a->l );
	balance = a->balance ;
	balance -= amount ;
	a->balance = balance ;
    unlock( &a->l );
}

struct account a1, a2 ;

thread1()
{
	withdraw( &a1,100 );
}

thread2()
{
	withdraw( &a1,200 );
}

transfer( struct account *a, *b, int amount )
{
    lock( &a->l );
    lock( &b->l );
	balance_a = a->balance ;
	balance_a -= amount ;
	a->balance = balance_a ;
	balance_b = b->balance ;
	balance_b += amount ;
	b->balance = balance_b ;
    unlock( &b->l );
    unlock( &a->l );
}

thread3()
{
	transfer( &a1,&a2,100 );
}

thread4()
{
	transfer( &a2,&a1,100 );
}

詳しくは、マルチスレッド・プログラミングで。
Linda:
withdaw( int a, int amount )
{
    in("account", a,  ?balance)
    balance -= amount ;
    out("account", a,  balance)
}
transfer( int a, int b, int amount )
{
    in("account", a,  ?balance_a)
    in("account", b,  ?balance_b)
    balance_a -= x ;
    balance_b += x ;
    out("account", a,  balance_a)
    out("account", b,  balance_b)
}

◆分散システムの問題

なぜ難しいか 集中システムで、1つ壊れて動かない時は、あきらめがつく。

◆なぜクロックを同期させないといけないか

■論理クロック

◆クロック

コンピュータは、時間を追跡する回路を持っている。 水晶発振とカウンタとラッチ。

タイマ割込み。1秒間に50回〜60回割込みがかかる。 水晶発振か、電源の周波数を使う。 一回の割込みを、clock tick という。

単一のコンピュータでは、水晶でも問題がない。

複数のコンピュータでは、 クロックの進み方(clock skew)が違うので、だんだんずれてくる。

◆論理クロックと物理クロック

論理クロック
内部で一貫性がとれていればいい
物理クロック
実際の時計と大きくずれていてはいけない
相互作用しないプロセスは、同期がとれてなくてもよい。

◆Lamportの論理クロック同期アルゴリズム

事前発生(happens-before)。

「a→b」は、「aはbの前に発生する」

「→」は、推移律(transitive law)が成り立つ。

「a→bかつb→cならばa→cである」

並行性がある:「x→y」も、「y→x」も両方とも偽であることある。 xとyが別々のプロセスで発生して、それらの間でメッセージを交換しない時な ど。 どちらが先に起きたかということを言えない(言う必要がない)

◆時間値C(x)

イベント aについて、次のような性質を持つ時間値C(a) を割り当てる。 C() が与えられたら、論理クロックが実現されたことを意味する。

◆Lamportのアルゴリズム

図(a) 独自のクロックを持つ3つのプロセス
図(a) 独自のクロックを持つ3つのプロセス。進み方が異なる。

図(a) 独自のクロックを持つ3つのプロセス
図(b) Lamportのアルゴリズムによるクロックの修正。

2つのイベントの間に必ず1ティック進める。小数点。 同時なら、プロセスIDで適当に。

1つの四角には、1つのメッセージだけ。 1つのホストが「同時」に複数のメッセージを送受信することはできない。

この方法でクロックを修正すると、次の性質が得られる。

casual ordering。因果律が成り立つ。

■物理クロック

基準
太陽
地球の公転、自転は一定ではない。ふらつきがある。 だんだん1日が長くなってきている。
原子時計
セシウム133が 9,192,631,770 回振動。実際の日とずれる。
UTC (Universal Coordinated Time)。
閏秒で調整。
http://www.zdnet.co.jp/mobile/0308/04/n_crl.html
ZDNet Mobile 真の1秒を求めて〜原子時計

http://jjy.crl.go.jp/index.html
通信総合研究所(CRL)/日本標準時グループ

http://jjy.crl.go.jp/QandA/time_qa.html
周波数と時刻に関するQ&A

◆物理クロックを合わせる

GPS の普及で、正確な時刻が簡単に取り出せるようになった。 NTP で合わせる。

以前の方法。

問題点

◆adjtime(2)

進みすぎたクロックを逆行させて戻す変わりに、ペースを落とす。

UNIX

int adjtime(const struct timeval *delta, struct timeval *olddelta)

◆Cristianの方法

UTCを持っている時刻サーバに問い合わせる。
  1. T0: クライアントが要求を送る。
  2. I : サーバ内の割込み処理
  3. T1: クライアントが応答を送る。

図? 時刻サーバに問い合わせる

図? 時刻サーバに問い合わせる

単純な方法:クライアントの時刻を、送られた UTC に合わせる。

Cristianの方法は、応答メッセージの遅延時間を測定するものである。 転送時間や割込み処理の時間が不明な時には、次の式で転送時間を見積もり、 補正する。

サーバが1つなら、アルゴリズムとしては問題なし。しかし、次のような問題 がある。

◆The Berkeley algorithm

マスターとスレーブがある。 単純に平均すると、嘘つきに弱い。 実際にクロックが100倍速く進むシステムがあった。

fault-tolerant average。 往復時間の誤差。

◆NTP(The Network Time Protocol)

サーバが木構造で構成される。

図? NTP(Network Time Protocol)サーバのレベル(stratum)

図? NTP(Network Time Protocol)サーバのレベル(stratum)

同期方法

■相互排除

共有データを他のプロセスが同時に利用しないようにすることを保証する。

◆集中システムでの方法

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

集中システムのエミュレーション。 1つのプロセスをコーディネータとして選ぶ。

(a) プロセス1がコーディネータに要求、コーディネータがプロセス1にOKを送る。
(a) プロセス3がコーディネータに要求、コーディネータはキューに入れる。
(a) プロセス1がコーディネータに解放、コーディネータはプロセス3にOKを送る。

図? コーディネータを使う相互排除

普通のプロセス:

  1. 臨界領域に入る前に、コーディネータに要求メッセージを送る。
  2. コーディネータから許可の応答が得られれば、臨界領域に入る。
  3. 臨界領域から出る時には、解放メッセージをコーディネータに知らせる。
コーディネータのプロセス:
  1. 要求メッセージを受け付けた時に、他に利用しているプロセスがいなけ れば、許可の応答を送る。
  2. 他にプロセスがいれば、待ち行列に入れる。
  3. 解放メッセージを受け取った時に、待ち行列からプロセスを 取り出し、それに応答メッセージを送る。
性質 故障の単一個所性を避けたい。

◆分散相互排除

仮定

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

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

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

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

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

(a) プロセス2と3が同時に要求。
(b) プロセス2が臨界領域に入る。
(c) プロセス3が臨界領域に入る。

図? コーディネータを使わない相互排除の例

アルゴリズムの性質:

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

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

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

たとえネットワークがバス型でも、ソフトウェア的にトークンリングを作る。

図 トークンリング
図 トークンリング

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

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

性質

◆まとめ

相互排除アルゴリズムの比較
アルゴリズム1回当たりのメッセージ数入る前の遅れ 問題
集中 3 2 コーディネータのクラッシュ
分散 2(n-1) 2(n-1) プロセスのクラッシュ
トークンリング 1〜無限 0〜n-1 トークンの紛失、プロセスのクラッシュ

■選出アルゴリズム

分散アルゴリズムでは、しばしばコーディネータが必要になる。 どうやって、コーディネータを選ぶか。

生きているプロセスの中で、もっとも高い番号のプロセスを探す。

◆Bully algorithm

コーディネータが応答しないと気が付いたプロセスが起動する。
  1. プロセス P は、ELECTION メッセージを高い番号を持つプロセスに送る。
  2. もし誰も応答しなければ、P が選ばれ、コーディネータとなる。
  3. 高い番号のプロセスから1つでも応答があれば、そのプロセスが 引き続き探す(1.にもどる)。
低い番号のプロセスから ELECTION メッセージを受け取ると、OK を返す。

最後に残ったプロセスが、自分がコーディネータだと他のプロセスに知らせる。

ダウンから復帰したプロセスは、この選出アルゴリズムを起動する。

◆Ring algorithm

仮定
  1. コーディネータがクラッシュしていることに気が付いたプロセス は、自分の番号を含む ELECTIOIN メッセージ作成し、次のプロセスに送る。
  2. 次のプロセスがダウンしていれば、スキップして次のプロセスに送る。 この時、自分の番号をメッセージに付加する。
  3. メッセージが最初のプロセスに戻ってくる。自分のプロセス番号を 含むメッセージを受け取ると、1週したことがわかる。 一番高い番号のものがねコーディネータとなる。
  4. コーディネータを知らせるメッセージを、次のプロセスに送る。
  5. 4. が一週すると終り。
複数のプロセスが同時にこのアルゴリズムを起動しても、問題ない。

■アトミック・トランザクション

相互排除、デッドロックより高いレベルの抽象が欲しい。

ロックよりも楽にプログラムを作りたい。

特に分散では。集中でも、フォールト・トレランスの実現では必要。

◆トランザクションの意味

商談は、成立するか、しないか。 all or nothing。

歴史:1960年代、テープの時代。 失敗したら、巻き戻す。

銀行口座間の預金の移動。

  1. 口座1から出金
  2. 口座2に入金

◆トランザクション・モデル

仮定 必要なもの リカバリ

◆トランザクション・プリミティブ

◆特性(ACID)

Atomic
外の世界からみると1つ。中間状態が見えない。不可分。
Consistency
不変量(invariant)を保つ。例:口座間の預金の移動。預金の総額は不変。
Isolated
並行するトランザクションは、孤立している。直列化可能(serializable)
Durable
Commit すると永続的。

◆直列化可能(serializable)

注意:Javaの serializable とは意味が全く違う。

複数のトランザクションは、並行に実行可能。しかし、その複数のトランザク ションの最終結果は、それらを「ある順序」で逐次的に実行した時と同じ結果 になる。

逆に、トランザクションは、直列化可能なスケジュールが存在するなら、並行 に実行してもよい。直列化可能でないなら、トランザクションは、開始を遅ら せるか、アボートする。

◆例

航空券の乗り継ぎの予約のプログラム
Begin_Transaction();
  reserve("NRT-SFO");
  reserve("SFO-JFK");
Commit();
プログラムの記述としては、これだけ。どこにもロックは出てこない。内部的 には、ロックは行われる(ことがある)。

途中の reserve() が失敗したら、トランザクション全体を abort() する。

◆入れ子トランザクション(nested transactoin)

目的 親が abort されたら、子供が commit したものも無効になる。

◆トランザクションの実装(集中)

◆プライベート作業空間

全てのデータをコピーすると重たい。

◆先行書き込みログ(write-ahead log)

実行予定リスト(intentions list)

シャドー・コピーを作らず、ファイルのその場所を書き換える。 その前に、次の情報を安定記憶に書き込む。

コミットされると、何もしない。 アボートされると、ログを後ろから前に読み込み undo する。

クラッシュからの回復もできる。

◆トランザクションの実装(分散)

二相コミット(two-phase commit)(二相ロック(two-phase lock)ではない)。

2種類のプロセス

2つの相
第1相
全プロセスを Commit も Abort もできる状態にする。
  1. コーディネータは、ログに「準備」と書く。
  2. コーディネータは、サブオーディネートに「準備」メッセージを送る。
  3. サブオーディネートは、ログに「準備完了」と書く。
  4. サブオーディネートは、コーディネータに「準備完了」メッセージを送る。
  5. コーディネータは、全てのサブオーディネートからの応答を待つ。
第2相
実際に Commit する。
  1. コーディネータは、ログに「コミット」と書く。
  2. コーディネータは、サブオーディネートに「コミット」メッセージを送る。
  3. サブオーディネートは、ログに「コミット完了」と書く。
  4. サブオーディネートは、コーディネータに「コミット完了」メッセージを送る。
  5. コーディネータは、全てのサブオーディネートからの応答を待つ。
クラッシュした時には、ログから回復させる。

◆並行性制御

できるだけ効率のよい、直列化可能なスケジューリングを求める。

◆ロッキング

もっとも単純な方法: Begin Transaction で、ファイルをロックする。 Commit/Abort でアンロックする。

注意:プログラマは、ロックを意識しない。

制約が強すぎる。

読み取りロック:read lock と write lock を分ける。

ロックの粒度(granularity)が大事

小さくする
並列性が高まる。ロック自体のオーバヘッドが増える。 デッドロックが起こりやすくなる。
大きくする
2相ロック:デッドロックが起きにくい、直列化可能な方法。
第1相(growing phase)
ロックの数が増える一方
第2相
ロックの数が減る一方
定理:トランザクションの実現で2相ロックを使うならば、インターリーブさ れることで作られるスケジュールは直列化可能である。

実際のシステムでは、Commit/Abort するまで、一度確保したロックをはなさない。 第2相で、まとめて全部ロックを解放する(strict two-phase locking)。

利点

2相ロックでも、デッドロックは起きる。

注意:2相ロックと2相コミットは別。

◆楽観的並行性制御

どんどんやって、後でまずかったことがわかつた時点で abort する。 衝突が稀である時に有効。

実現(衝突時の対応):プライベート作業空間を使う実現が便利。 どんどんプライベート作業空間上のファイルを更新して、最後にコミットする か削除する。

性質

◆タイムスタンプ

操作にタイムスタンプを付けて、まずいものをアボートする。

前提:

アルゴリズム: 楽観的:同じファイルを独立したトランザクションで同時にアクセスすること は、あまりない。

◆長期トランザクション

直列化可能性という制限はきつすぎる。

■分散システムにおけるデッドロック

デッドロックの扱い 分散では、非常に難しい。回避は、無理。

◆検出

検出して、プロセスを kill する。

kill では済まないものもある。

トランザクションが使える場合には、回復は単に abort すればよい。

◆集中型検出アルゴリズム

集中型のアルゴリズムを、コーディネータを使って模倣する。

情報の収集方法 単純にやると、偽のデッドロックを検出する。

対策:タイムスタンプを使う。

◆分散型検出アルゴリズム

プロセスがブロックする時に起動される。

プローブ・メッセージ:3つ組

  1. プロセスがブロックする時、プローブ・メッセージを送る。
  2. メッセージを受け取ると、他のプロセスを待っていたら、第2、第3フィー ルドを書き換えて転送する。
  3. メッセージが一巡してもどってきたら、デッドロック。
単純に最初のプロセスを殺す方法では、複数のプロセスが同時にこのアルゴリ ズムを起動すると問題になる。

改良:プローブメッセージに待っているプロセスのリストを付ける。 リストの中で犠牲となるプロセスを一意に決める。

理論的には、改善の余地が大きい。

◆分散デッドロック予防

もっとも代表的な方法: 集中システムでも使われている。

大域的な時間とトランザクションを利用した方法(1):待機消滅(wait-die)型 アルゴリズム

トランザクションの時刻の増加方向にしか延びない。

大域的な時間とトランザクションを利用した方法(2):負傷待機(wound-wait) 型アルゴリズム

wait-die型アルゴリズムでは、若者は繰り返し死ぬことがある。

■まとめ

分散アルゴリズム

分散システムにおける同期


↑[もどる] ←[12月18日] ・[12月25日] →[1月8日]
Last updated: 2004/01/08 01:51:33
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>