並行システム
システム情報系/情報工学域,
システム情報工学研究群/情報理工学位プログラム
システム情報工学研究科/コンピュータサイエンス専攻
新城 靖
<yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
https://www.cs.tsukuba.ac.jp/~yas/cs/csys-2025/2025-06-27
あるいは、次のページから手繰っていくこともできます。
https://www.cs.tsukuba.ac.jp/~yas/cs/
https://www.cs.tsukuba.ac.jp/~yas/
ロックよりも楽にプログラムを作りたい。 We would like to write programs more easily than that with locks.
特に分散では。集中でも、フォールト・トレランスの実現では必要。 Especially in distributed systems. Transaction is essential to realize fault tolerance.
歴史：１９６０年代、磁気テープの時代。 失敗したら、巻き戻す(rollback)。
銀行口座間の預金の移動。
注意：Java の serializable とは意味が全く違う。
複数のトランザクションは、並行に実行可能。しかし、その複数のトランザク ションの最終結果は、それらを「ある順序」で「逐次的に」実行した時と同じ結果 になる。
逆に、トランザクションは、直列化可能なスケジュールが存在するなら、並行 に実行してもよい。直列化可能でないなら、トランザクションは、開始を遅ら せるか、アボートする。
図? トランザクションの処理（並行実行）/Concurrent execution of transactions 図? トランザクションの処理（直列化の例その1）/A serialized execution of transaction No.1 図? トランザクションの処理（直列化の例その2）/A serialized execution of transaction No.2 図? トランザクションの処理（直列化の例その3）/A serialized execution of transaction No.3
Begin_Transaction();
reserve("NRT-SFO");
reserve("SFO-MCO");
Commit();
プログラムの記述としては、これだけ。どこにもロックは出てこない。内部的
には、ロックは行われる（ことがある）。
途中の reserve() が失敗したら、トランザクション全体を abort() する。
図? ファイルの変更されたブロックだけをコピー）
シャドー・コピーを作らず、ファイルのその場所を書き換える。 その前に、次の情報を安定記憶にログとして書き込む。
クラッシュからの回復もできる。
図? 安定記憶の実現
更新時：3 の前にクラッシュしても、常にディスク１が正しい(図?(b))。 この場合は、ディスク１からディスク１へコピーする。
チェックサムエラーが起きた場合（図?(c)）、他のディスクからコピーして回復する。
もっとも単純な方法：
注意：プログラマは、ロックを意識しない。
制約が強すぎる。
読み取りロック：read lock と write lock を分ける。
ロックの粒度(granularity)が大事
図? ２相ロック/Two-phase locking
定理：トランザクションの実現で２相ロックを使うならば、インターリーブさ れることで作られるスケジュールは直列化可能である。
実際のシステムでは、Commit/Abort するまで、一度確保したロックをはなさない。
第２相で、まとめて全部ロックを解放する(strict two-phase locking)。
図? ２相ロック/Strict two-phase locking
利点
注意：２相ロックと２相コミットは別。
実現（衝突時の対応）：プライベート作業空間を使う実現が便利。 どんどんプライベート作業空間上のファイルを更新して、最後にコミットする か削除する。
性質
アルゴリズム：
Lamport のアルゴリズム等でクロックが同期されていれば、分散システムでも 使える。
２種類のプロセス
https://www.slideshare.net/kumagi/ss-78765920,分散システムについて語らせてくれ by 熊崎宏樹
| 分離レベル | ダーティーリード | ノンリピータブル・リード | ファントム・リード |
|---|---|---|---|
| Read Uncommitted | 有 | 有 | 有 |
| Read Committed | 無 | 有 | 有 |
| Repeatable Read | 無 | 無 | 有 |
| Serializable | 無 | 無 | 無 |
Barbara Liskov: "Distributed programming in Argus", Communications of
the ACM, Vol.31, No.3, pp.300-312, 1988.
https://doi.org/10.1145/42392.42399
文法は、CLU 言語に似ている。
参考:
http://www2.gssm.otsuka.tsukuba.ac.jp/staff/kuno/lectures/,(リンク切れ)
1993.5 ゼミ: CLU言語入門@GSSM
(
http://160.16.241.20/lectures/,久野の講義・講演・プレゼン資料/講義資料
)
http://www.pmg.lcs.mit.edu/CLU.html
CLU Home Page.
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
contract Bank {
mapping(address => uint256) public accounts;
function deposit() {
accounts[msg.sender] += msg.value;
}
function withdraw(uint256 amount) {
if(amount > accounts[msg.sender])
throw;
accounts[msg.sender] -= amount;
if(!msg.sender.send(amount))
throw;
}
function get_balance() {
return accounts[msg.sender];
}
}
get_balance() は、残高照会。 状態を変えないので、トランザクションではなく call で実行できる。
if( a() ) {
b();
}
else {
c();
}
図? 投機的実行 Speculative execution
この例では、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の遅延を隠す。 This paper proposes hiding RPC delays by using optimistic execution.
Consider the following transactions.
The profram of a bank branch in Argus performs transactions. Extract a code fragment that executes a transaction from the program. In this code fragment, mark the point that executes the begin_transaction operation implicitly. Mark the point that executes the commit operation implicitly. Mark the point that executes the abort operation implicitly.
In the following program in a procedural programming language, answer the place we can perform speculative execution. In this program, the function input_yes_or_no() returns YES or NO.
main() {
int x = 0;
if( input_yes_or_no() == YES ) {
x = time_consuming_computation();
}
print(x);
}
この投機的実行の実装において、トランザクションの実装と類似の技術が必要になる。
この技術を簡単に説明しなさい。
In this speculative execution, we need a similar implementation technique to that of transactions. Describe the technique briefly.