図? トランザクションの処理（並行実行）
図? トランザクションの処理（直列化の例その1）
図? トランザクションの処理（直列化の例その2）
図? トランザクションの処理（直列化の例その3）
並行システム
システム情報系情報工学域,
システム情報工学研究科コンピュータサイエンス専攻
新城 靖
<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/
ロックよりも楽にプログラムを作りたい。
特に分散では。集中でも、フォールト・トレランスの実現では必要。
歴史：１９６０年代、テープの時代。 失敗したら、巻き戻す(rollback)。
銀行口座間の預金の移動。
注意：Javaの serializable とは意味が全く違う。
複数のトランザクションは、並行に実行可能。しかし、その複数のトランザク ションの最終結果は、それらを「ある順序」で「逐次的に」実行した時と同じ結果 になる。
逆に、トランザクションは、直列化可能なスケジュールが存在するなら、並行 に実行してもよい。直列化可能でないなら、トランザクションは、開始を遅ら せるか、アボートする。
図? トランザクションの処理（並行実行） 図? トランザクションの処理（直列化の例その1） 図? トランザクションの処理（直列化の例その2） 図? トランザクションの処理（直列化の例その3）
Begin_Transaction();
reserve("NRT-SFO");
reserve("SFO-MCO");
Commit();
プログラムの記述としては、これだけ。どこにもロックは出てこない。内部的
には、ロックは行われる（ことがある）。
途中の reserve() が失敗したら、トランザクション全体を abort() する。
図? ファイルの変更されたブロックだけをコピー）
シャドー・コピーを作らず、ファイルのその場所を書き換える。 その前に、次の情報を安定記憶にログとして書き込む。
クラッシュからの回復もできる。
図? 安定記憶の実現
更新時：3 の前にクラッシュしても、常にディスク１が正しい(図?(b))。 この場合は、ディスク１からディスク１へコピーする。
チェックサムエラーが起きた場合（図?(c)）、他のディスクからコピーして回復する。
もっとも単純な方法： Begin Transaction で、ファイルをロックする。 Commit/Abort でアンロックする。
注意：プログラマは、ロックを意識しない。
制約が強すぎる。
読み取りロック：read lock と write lock を分ける。
ロックの粒度(granularity)が大事
図? ２相ロック）
定理：トランザクションの実現で２相ロックを使うならば、インターリーブさ れることで作られるスケジュールは直列化可能である。
実際のシステムでは、Commit/Abort するまで、一度確保したロックをはなさない。
第２相で、まとめて全部ロックを解放する(strict two-phase locking)。
図? ２相ロック）
利点
注意：２相ロックと２相コミットは別。
実現（衝突時の対応）：プライベート作業空間を使う実現が便利。 どんどんプライベート作業空間上のファイルを更新して、最後にコミットする か削除する。
性質
アルゴリズム：
Lamport のアルゴリズム等でクロックが同期されていれば、分散システムでも 使える。
２種類のプロセス
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のパラレルワールド
ＳＦでは、時々別の世界にジャンプしたり人が入れ替わったりする。
世界ＯＳでは、ファイルの内容を変更すると、２つの世界ができる。
図 世界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の遅延を隠す。