並行システム
システム情報系/情報工学域,
システム情報工学研究群/情報理工学位プログラム
システム情報工学研究科/コンピュータサイエンス専攻
新城 靖
<yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2021/2021-06-18
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://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.
アンケートはTWINSから回答してください。
なお、皆さんの評価が成績に影響することは一切ありません。 また、評価結果を教育の改善以外の目的に利用することはありませんし、 評価結果を公開する場合には個人を特定できるような情報は含めません。
アンケートは、次の2つに別れています。
The FD Committee of the Department of Computer Science/Master's and Doctoral Programs in Computer Science conducts a survey of all students for the purpose of evaluating and improving instruction. Please complete this questionnaire in TWINS.
These answers will not affect your academic grades. The result will not be used for any purpose other than instruction evaluation and its further improvement. When the summarized information of this questionnaire is released to the public (for FD activities), no private information about you will be included.
This class has the following two groups of questionnaires.
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.
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.