並列分散ソフトウェア
電子・情報工学系
新城 靖
<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
分散システムにおける同期
トレードオフ。
資料：
Ａ．Ｓ．タネンバウム著、水野忠則、鈴木健二、西宮洋太郎、佐藤文明訳、分
散オペレーティングシステム、プレンティスホール (1996)
第６章 分散共有メモリ
Andrew Tanenbaum, Maarten Van Steen: "Distributed Systems: Principles
and Paradigms", Prentice Hall (2001). ISBN: 0130888931
Chapter 6 Consistency and Replication
目的
プロセスが、あるアクセスの仕方を守れば、メモリは「正しく」動作する ことを保証する。
制限が少ないと、遅くなる。使える範囲でいかに手を抜く（コストを下げる） かが大事になる。
以下で「メモリ」は、data store の意味で使う。変数かもしれないし、ファ イルかもしれないし、ページかもしれない。
メモリがページで、プロセスがプロセッサなら、分散共有メモリ(distributed shared memory,DSM)という。
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(集中システム)ですら、キャッシュがあれば、実現不可能。
救い：実際の応用では、そこまで要求されていない。
例：厳密一貫性がある(横方向が時間軸、右に向って増加)
P1: W(x)1 P2: R(x)1例：厳密一貫性がない
P1: W(x)1 P2: R(x)0 R(x)1
いかる実行の結果は、全てのプロセスによるメモリ(data store)に対する読み 書き操作が、ある逐次的な順序で行われた時と常に同じになる。ただし、個々 のプロセスによる操作は、メモリに対してそのプログラムに書かれた順序で行 われる。
インターリーブは、許されるが、インターリーブのされ方は、全てのプロセス から見て同じでなければならな。
例：厳密一貫性がないが、順序一貫性がある(横方向が時間軸、右に向って増加)
P1: W(x)1 P2: R(x)0 R(x)1例：厳密一貫性も、順序一貫性もある。
P1: W(x)1 P2: R(x)1 R(x)1
P1()
{
x=1 ;
print(y,z);
}
P2()
{
y=1 ;
print(x,z);
}
P3()
{
z=1 ;
print(x,y);
}
４つの正しい実行系列（縦方向が、時間軸で、下に向って増加）。 正しい系列は、全部で９０個ある。
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履歴から、２つの制約を満たすような、文字列 S を合成する。
制約１：プログラム順序が保たれる。
Hi = ... A .... B .... なら S = ..... A ..... B ....
制約２：メモリの整合性(memory coherence)が保たれる。 ある位置 x に対する読み取りは、常に最近の書込みの値を返す。
これらの制約を満たす S は、今の例では１つだけ。
S = R(x)0 W(x)1 R(x)1いくつかある正しい S のうち、１つを満たせば 順序一貫性を満たしている。
読み取りを速くすると、書込みが遅くなる。
順序一貫性を弱めたもの。
ネットワーク・ニュースで、フォローアップ記事が元記事より先に届く。これ は、因果一貫性が満たされていない。こういうことが無いようにしたい。
潜在的な因果関係がある: プロセス 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)3P2 が、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)2P2 が、x を Read して Write している。
因果一貫性を満す。
P1: W(x)1 P2: W(x)2 P3: R(x)2 R(x)1 P4: R(x)1 R(x)2P1 の W と P2 の W は、並行なので、見え方が違ってもよい。
命令と命令の依存関係を追跡しなければならない。
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一貫性では、２つのプロセスが止まってしまうことがあり得る例。
int a=0;
int b=0;
P1()
{
a = 1 ;
if( b == 0 ) kill( P2 );
}
P2()
{
b = 1 ;
if( a == 0 ) kill( P1 );
}
弱一貫性の特性
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 SSは、同期変数のアクセス。
弱一貫性を満たさない
P1: W(x)1 W(x)2 S P2: S R(x)1
プロセスが 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
実装は、２つの方法
部分空間は、ハッシュ表として構成する。
in では、全マシンから取り除く必要がある。二相コミットを使う。
タプル空間が、大きくない時には有効。
in では、formal をブロードキャストを繰り返して、タプルを探す。