並行システム システム情報系情報工学域, システム情報工学研究科コンピュータサイエンス専攻 新城 靖 <yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2011/2012-02-23
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/
ロックよりも楽にプログラムを作りたい。
特に分散では。集中でも、フォールト・トレランスの実現では必要。
歴史:1960年代、テープの時代。 失敗したら、巻き戻す(rollback)。
銀行口座間の預金の移動。
注意:Javaの serializable とは意味が全く違う。
複数のトランザクションは、並行に実行可能。しかし、その複数のトランザク ションの最終結果は、それらを「ある順序」で「逐次的に」実行した時と同じ結果 になる。
逆に、トランザクションは、直列化可能なスケジュールが存在するなら、並行 に実行してもよい。直列化可能でないなら、トランザクションは、開始を遅ら せるか、アボートする。
図? トランザクションの処理(並行実行) 図? トランザクションの処理(直列化の例その1) 図? トランザクションの処理(直列化の例その2) 図? トランザクションの処理(直列化の例その3)
Begin_Transaction(); reserve("NRT-SFO"); reserve("SFO-MCO"); Commit();プログラムの記述としては、これだけ。どこにもロックは出てこない。内部的 には、ロックは行われる(ことがある)。
途中の reserve() が失敗したら、トランザクション全体を abort() する。
図? ファイルの変更されたブロックだけをコピー)
シャドー・コピーを作らず、ファイルのその場所を書き換える。 その前に、次の情報を安定記憶にログとして書き込む。
クラッシュからの回復もできる。
図? 安定記憶の実現
更新時:3 の前にクラッシュしても、常にディスク1が正しい(図?(b))。 この場合は、ディスク1からディスク1へコピーする。
チェックサムエラーが起きた場合(図?(c))、他のディスクからコピーして回復する。
もっとも単純な方法: Begin Transaction で、ファイルをロックする。 Commit/Abort でアンロックする。
注意:プログラマは、ロックを意識しない。
制約が強すぎる。
読み取りロック:read lock と write lock を分ける。
ロックの粒度(granularity)が大事
図? 2相ロック)
定理:トランザクションの実現で2相ロックを使うならば、インターリーブさ れることで作られるスケジュールは直列化可能である。
実際のシステムでは、Commit/Abort するまで、一度確保したロックをはなさない。
第2相で、まとめて全部ロックを解放する(strict two-phase locking)。
図? 2相ロック)
利点
注意:2相ロックと2相コミットは別。
実現(衝突時の対応):プライベート作業空間を使う実現が便利。 どんどんプライベート作業空間上のファイルを更新して、最後にコミットする か削除する。
性質
アルゴリズム:
Lamport のアルゴリズム等でクロックが同期されていれば、分散システムでも 使える。
2種類のプロセス
Barbara Liskov: "Distributed programming in Argus", Communications of the ACM, Vol.31, No.3, pp.300-312, 1988.
1: branch = guardian is create handles total, open, close, deposit, withdraw 2: % type definitions 3: htable = atomic_array[bucket] 4: bucket = atomic_array[pair] 5: pair = atomic_record[num: account_number, acct: acct_info] 6: acct_info = atomic_record[bal: int] 7: account_number = atomic_record[code: string, num: int] 8: intcell = atomic_record[val: int] 9: 10: stable ht: htable % the table of accounts 11: stable code: string % the code for the branch 12: stable seed: intcell % the seed for generating new account numbers 13: 14: create = creator (c: string, size: int) returns (branch) 15: code := c 16: seed.val := 0 17: ht := htable$new() 18: for i: int in int$from_to(1, size) do 19: htable$addh(ht, bucket$new()) 20: end 21: return (self) 22: end create 23: 24: total = handler () returns (int) 25: sum: int := 0 26: for b: bucket in htable$elements(ht) do 27: for p: pair in bucket$elements(b) do 28: sum := sum + p.acct.bal 29: end 30: end 31: return (sum) 32: end total 33: 34: open = handler () returns (account_number) 35: intcell$write_lock(seed) % get a write lock on the seed 36: a: account_number := account_number${code: code, num: seed.val} 37: seed.val := seed.val + 1 38: bucket$addh(ht[hash(a.num)], pair${num: a, acct: acct_info${bal: 0}}) 39: return (a) 40: end open 41: 42: close = handler (a: account_number) signals (no_such_acct, positive_balance) 43: b: bucket := ht[hash(a.num)] 44: for i: int in bucket$indexes(b) do 45: if b[i].num != a then continue end 46: if b[i].acct.bal > 0 then signal positive-balance end 47: b[i] := bucket$top(b) % store topmost element in place of closed account 48: bucket$remh(b) % discard topmost element 49: return 50: end 51: signal no_such_acct 52: end close 53: 54: lookup = proc (a: account_number) returns (acct_info) signals (no_such__acct) 55: for p: pair in bucket$elements(ht[hash(a.num)]) do 56: if p.num = a then return (p.acct) end 57: end 58: signal no_such_acct 59: end lookup 60: 61: deposit = handler (a: account_number, amt: int) signals (no_such_acct, 62: negativ_amount) 63: if amt < 0 then signal negative_amount end 64: ainfo: acct_info := lookup(a) resignal no_such_acct 65: ainfo.bal := ainfo.bal + amt 66: end deposit 67: 68: withdraw = handler (a: account_number, amt: int) signals (no_such_acct, 69: negative_amount, insufficient_funds) 70: if amt < 0 then signal negative amount end 71: ainfo: acct_info := lookup(a) resignal no_such_acct 72: if ainfo.bal < amt then signal insufficient_funds end 73: ainfo.bal := ainfo.bal - amt 74: end withdraw 75: end branch
if( a() ) { b(); } else { c(); }
図? 投機的実行
この例では、a() が完了した時には、b()、c() が終わっていた時には、見かけ 上、即座に終わる。
SF (Science Fiction) のパラレルワールド(parallel world, parallel
universe)を、オペレーティング・システムのレベルで実現する。
図 SFのパラレルワールド
SFでは、時々別の世界にジャンプしたり人が入れ替わったりする。
世界OSでは、ファイルの内容を変更すると、2つの世界ができる。
図 世界OSで使える世界の操作
普通の仮想計算機では、融合はできない。継承のコストが大きい。
C. Cowan and H. L. Lutfiyya: "A wait-free algorithm for optimistic programming: Hope realized", In Proceedings of the 16th International Conference on Distributed Computing Systems(ICDCS), pages 484-493, 1996.
RPCの遅延を隠す。