図? トランザクションの処理（並行実行）
図? トランザクションの処理（直列化の例その1）
図? トランザクションの処理（直列化の例その2）
図? トランザクションの処理（直列化の例その3）
並行システム
システム情報工学研究科コンピュータサイエンス専攻、電子・情報工学系
新城 靖
<yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/sie/csys-2009/2010-02-19
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/sie/
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.
branch = guardian is create handles total, open, close, deposit, withdraw
% type definitions
htable = atomic_array[bucket]
bucket = atomic_array[pair]
pair = atomic_record[num: account_number, acct: acct_info]
acct_info = atomic_record[bal: int]
account_number = atomic_record[code: string, num: int]
intcell = atomic_record[val: int]
stable ht: htable % the table of accounts
stable code: string % the code for the branch
stable seed: intcell % the seed for generating new account numbers
create = creator (c: string, size: int) returns (branch)
code := c
seed.val := 0
ht := htable$new()
for i: int in int$from_to(1, size) do
htable$addh(ht, bucket$new())
end
return (self)
end create
total = handler () returns (int)
sum: int := 0
for b: bucket in htable$elements(ht) do
for p: pair in bucket$elements(b) do
sum := sum + p.acct.bal
end
end
return (sum)
end total
open = handler () returns (account_number)
intcell$write_lock(seed) % get a write lock on the seed
a: account_number := account_number${code: code, num: seed.val}
seed.val := seed.val + 1
bucket$addh(ht[hash(a.num)], pair${num: a, acct: acct_info${bal: 0}})
return (a)
end open
close = handler (a: account_number) signals (no_such_acct, positive_balance)
b: bucket := ht[hash(a.num)]
for i: int in bucket$indexes(b) do
if b[i].num != a then continue end
if b[i].acct.bal > 0 then signal positive-balance end
b[i] := bucket$top(b) % store topmost element in place of closed account
bucket$remh(b) % discard topmost element
return
end
signal no_such_acct
end close
lookup = proc (a: account_number) returns (acct_info) signals (no_such__acct)
for p: pair in bucket$elements(ht[hash(a.num)]) do
if p.num = a then return (p.acct) end
end
signal no_such_acct
end lookup
deposit = handler (a: account_number, amt: int) signals (no_such_acct,
negativ_amount)
if amt < 0 then signal negative_amount end
ainfo: acct_info := lookup(a) resignal no_such_acct
ainfo.bal := ainfo.bal + amt
end deposit
withdraw = handler (a: account_number, amt: int) signals (no_such_acct,
negative_amount, insufficient_funds)
if amt < 0 then signal negative amount end
ainfo: acct_info := lookup(a) resignal no_such_acct
if ainfo.bal < amt then signal insufficient_funds end
ainfo.bal := ainfo.bal - amt
end withdraw
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の遅延を隠す。