分散プログラミング -- 状態

並列分散ソフトウェア

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

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/2001-12-20
あるいは、次のページから手繰っていくこともできます。
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)
第6章 分散共有メモリ

Andrew Tanenbaum, Maarten Van Steen: "Distributed Systems: Principles and Paradigms", Prentice Hall (2001). ISBN: 0130888931
Chapter 6 Consistency and Replication

■一貫性モデル

◆複製(replication)

コピーを作る。

目的

元とコピーが非対称なら、キャッシング、対称的なら、複製と言うことが多い。

◆一貫性モデル(consistency model)

プロセスとメモリ(データの入れ物)の関わり方。

プロセスが、あるアクセスの仕方を守れば、メモリは「正しく」動作する ことを保証する。

制限が少ないと、遅くなる。使える範囲でいかに手を抜く(コストを下げる) かが大事になる。

以下で「メモリ」は、data store の意味で使う。変数かもしれないし、ファ イルかもしれないし、ページかもしれない。

メモリがページで、プロセスがプロセッサなら、分散共有メモリ(distributed shared memory,DSM)という。

◆厳密一貫性(strict consistency)

あるメモリ x を読み出すと、そのメモリ x に対する最新の書込みの結果が返 される。

a=1;
a=2;
print(a);

厳密一貫性では、常に 2 がプリントされる。

厳密一貫性では、「最新」の定義で、ニュートン物理学での絶対的な時間が必 要になる。

3 m 離れたコンピュータでは、光の速さででも 10ns かかる。 a=2; と print(a); 差が 1ns 以内という要求なら、光の 10 倍の速度が必要になる。

       3 m
P1 <---------> P2
a=1;
a=2;
              print(a);

SMP(集中システム)ですら、キャッシュがあれば、実現不可能。

救い:実際の応用では、そこまで要求されていない。

◆表記方法

W(x)a
x に a を書込む。
R(y)b
y から読込んだ結果、b が得られた。
初期値は、0。

例:厳密一貫性がある(横方向が時間軸、右に向って増加)

P1:     W(x)1
P2:                R(x)1
例:厳密一貫性がない
P1:     W(x)1
P2:                R(x)0  R(x)1

◆順序一貫性(sequential consistency)

Lamport による。

いかる実行の結果は、全てのプロセスによるメモリ(data store)に対する読み 書き操作が、ある逐次的な順序で行われた時と常に同じになる。ただし、個々 のプロセスによる操作は、メモリに対してそのプログラムに書かれた順序で行 われる。

インターリーブは、許されるが、インターリーブのされ方は、全てのプロセス から見て同じでなければならな。

例:厳密一貫性がないが、順序一貫性がある(横方向が時間軸、右に向って増加)

P1:     W(x)1
P2:                R(x)0    R(x)1
例:厳密一貫性も、順序一貫性もある。
P1:     W(x)1
P2:                R(x)1    R(x)1

◆3つのプロセス

P1()
{
    x=1 ;
    print(y,z);
}
P2()
{
    y=1 ;
    print(x,z);
}
P3()
{
    z=1 ;
    print(x,y);
}

4つの正しい実行系列(縦方向が、時間軸で、下に向って増加)。 正しい系列は、全部で90個ある。

Prints: は、画面に時系列で現れた表示、 Signature: は、プロセス P1, P2, P3 の出力をその順で繋げたもの。

(a)
    x=1 ;
    print(y,z);
    y=1 ;
    print(x,z);
    z=1 ;
    print(x,y);

Prints: 000111
Signature: 001011

(b)
    x=1 ;
    y=1 ;
    print(x,z);
    print(y,z);
    z=1 ;
    print(x,y);

Prints: 101011
Signature: 101011

(c)
    y=1 ;
    z=1 ;
    print(x,y);
    print(x,z);
    x=1 ;
    print(y,z);

Prints: 010111
Signature: 110101

(d)
    y=1 ;
    x=1 ;
    z=1 ;
    print(x,z);
    print(y,z);
    print(x,y);

Prints: 010111
Signature: 110101

考えられる Signature は、26==64 個あるが、全部は許されてい ない。

◆順序一貫性の形式的な記述

P1:     W(x)1
P2:                R(x)0  R(x)1
プロセスの履歴
H1 = W(x)1
H2 = R(x)0 R(x)1
履歴から、2つの制約を満たすような、文字列 S を合成する。

制約1:プログラム順序が保たれる。
Hi = ... A .... B .... なら S = ..... A ..... B ....

制約2:メモリの整合性(memory coherence)が保たれる。 ある位置 x に対する読み取りは、常に最近の書込みの値を返す。

これらの制約を満たす S は、今の例では1つだけ。

S = R(x)0 W(x)1 R(x)1
いくつかある正しい S のうち、1つを満たせば 順序一貫性を満たしている。

◆順序一貫性の性能上の問題

r
読み取り時間
w
書込み時間
t
転送時間
r+w>=t になる。

読み取りを速くすると、書込みが遅くなる。

◆因果一貫性(causal consistency)

順序一貫性を弱めたもの。

ネットワーク・ニュースで、フォローアップ記事が元記事より先に届く。これ は、因果一貫性が満たされていない。こういうことが無いようにしたい。

潜在的な因果関係がある: プロセス P1 が x に書く。 プロセス P2 が x を読んで y に書く。

並行性がある: 因果関係がないもの。

因果一貫性があるメモリ(data store):

潜在的に因果関係のある書込みは、全プロセスに同じ順序で見えなければならない。 並行性がある書込みは、異なる順序で見えてもよい。

因果一貫性は満たすが、順序一貫性(厳密一貫性も)を満たさない例

P1: W(x)1                W(x)3
P2:        R(x)1  W(x)2  
P3:        R(x)1               R(x)3  R(x)2
P4:        R(x)1               R(x)2  R(x)3
P2 が、x を Read して Write している。 P1 の W(x)3 と P2の W(x)2 は、並行なので、見え方が違ってもよい。

因果一貫性を満たさない例。

P1: W(x)1              
P2:        R(x)1  W(x)2  
P3:                      R(x)2 R(x)1
P4:                      R(x)1 R(x)2
P2 が、x を Read して Write している。

因果一貫性を満す。

P1: W(x)1              
P2:               W(x)2  
P3:                      R(x)2 R(x)1
P4:                      R(x)1 R(x)2
P1 の W と P2 の W は、並行なので、見え方が違ってもよい。

命令と命令の依存関係を追跡しなければならない。

◆FIFO一貫性(PRAM一貫性(Pipelined RAM))

1つのプロセスによる書込みは、それが発行された順で全プロセスに受け取ら れるが、異なるプロセスによる書込みは、異なるマシンで異なる順序で見えて もよい。

FIFO一貫性を満たす(因果一貫性を満たさない)例。

P1: W(x)1              
P2:        R(x)1  W(x)2  
P3:                      R(x)2 R(x)1
P4:                      R(x)1 R(x)2

FIFO一貫性では、2つのプロセスが止まってしまうことがあり得る例。

int a=0;
int b=0;
P1()
{
    a = 1 ;
    if( b == 0 ) kill( P2 );
}
P2()
{
    b = 1 ;
    if( a == 0 ) kill( P1 );
}

◆弱一貫性(weak consistency)

同期変数に着目する。 臨界領域から抜けた時に、そのプロセス上の全書込みが他のプロセスに知らされ、 他のプロセスの全書込みが、そのプロセスから見えるようになる。

弱一貫性の特性

  1. 同期変数へのアクセスは、順序一貫性を満たす。
  2. 普通の変数への書込みが全て終了するまで、同期変数へのアクセスは許されない。 (同期変数がアクセスされた時には、全ての書込みが完了するのを待つ。)
  3. 同期変数へのアクセスが全て終了するまで、データアクセス(読み取り・書込み)は、許されない。 (通常の変数がアクセスされた時には、全ての同期が完了している。)
1. は、同期変数については、コストがかかるが順序一貫性を実現することを 意味する。通常変数については、手を抜く。

2. は、パイプラインのフラッシュの意味。

3. があるので、同期をとってから普通の変数にアクセスすれば最新の状態に なっていることが言える。

弱一貫性を満たす

P1: W(x)1  W(x)2  S
P2:                      R(x)1 R(x)2  S
P3:                      R(x)2 R(x)1  S
Sは、同期変数のアクセス。

弱一貫性を満たさない

P1: W(x)1  W(x)2  S
P2:                  S   R(x)1 

◆リリース一貫性

同期を2種類に分類する。 Acquire と Release の間にだけ、共有変数(保護されたた共有変数)の一貫 性が保たれる。

プロセスが Acquire した時、メモリは、必要ならそれらの共有変数の全コピー をリモートのコピーと一致させる。

リリース一貫性を満たす

P1: Acq(L) W(x)1  W(x)2  S Rel(L)
P2:                               Acq(L) R(x) 2 Rel(L)
P3:                                                    R(x)1

実装は、2つの方法

Eager
Release した時に、修正されたデータのコピーを他のプロセスに送る。 コーディネータを使う相互排除アルゴリズムと似た方法で実現可能。
Lazy
Release では何もしない。Acquire の時に、最新のものを得る。 たとえば、タイムスタンプが必要になる。

◆エントリ一貫性

同期変数と普通の変数を関連づける。 ある同期変数が Acquire されたら、関連している共有変数だけ 最新のものにする。

◆まとめ

同期操作を使わない
厳密一貫性
全ての共有アクセスを、絶対時間順序で見る。絶対時間は、 分散システムでは実現不可能である。
順序一貫性
全てのプロセスは、全ての書込みを同じ順序で見る。
因果一貫性
全てのプロセスは、因果関係(依存関係)のあるものについて、 全ての書込みを同じ順序で見る。
FIFO一貫性
単一プロセスについてのみ、指示された順序で実行される。
同期操作を使う。
弱一貫性
共有データは同期がとられた後にのみ一貫性が確保される。
リリース一貫性
臨界領域から出る時に、共有データの一貫性をとる。
エントリ一貫性
臨界領域に入る時に、臨界領域に関連した共有データの一貫性をとる。
同期操作を使う方は、プログラマの負担が大きいが、実現は容易。

■実装

◆分散共有メモリ

ページ単位、MMU を使う。

◆Lindaの実装

課題 高速化の方法 これらの情報を使って、全タプル空間を部分空間に分割する。 この分割は、コンパイル時に概ね確定できる。

部分空間は、ハッシュ表として構成する。

◆複製を使った実装

全部のマシンに、全部分空間のコピーを持たせる。 out で、全マシンにコピーする。

in では、全マシンから取り除く必要がある。二相コミットを使う。

タプル空間が、大きくない時には有効。

◆複製を使わない方法

out は、ローカルで行う。

in では、formal をブロードキャストを繰り返して、タプルを探す。

◆両方

マシンを格子状に配置する。 out で、横方向に複製する。 in で、縦方向に formal を放送する。

■まとめ


↑[もどる] ←[12月13日] ・[12月20日] →[1月10日]
Last updated: 2001/12/20 20:31:02
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>