並行システム
システム情報系情報工学域,
システム情報工学研究科コンピュータサイエンス専攻
新城 靖
<yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-08-09
あるいは、次のページから手繰っていくこともできます。
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://dl.acm.org/citation.cfm?id=42399
文法は、CLU 言語に似ている。
参考:
http://www2.gssm.otsuka.tsukuba.ac.jp/staff/kuno/lectures/
1993.5 ゼミ: CLU言語入門@GSSM
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() が終わっていた時には、見かけ 上、即座に終わる。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.
SF (Science Fiction) のパラレルワールド(parallel world, parallel
universe)を、オペレーティング・システムのレベルで実現する。
図 SFのパラレルワールド
ＳＦでは、時々別の世界にジャンプしたり人が入れ替わったりする。
世界ＯＳでは、ファイルの内容を変更すると、２つの世界ができる。
図 世界OSで使える世界の操作
普通の仮想計算機では、融合はできない。継承のコストが大きい。
次の内容を含む「テキスト」ファイルを作成し、 レポート提出ページ から提出しなさい。 締切りは、2019年8月13日、 23:59:59 とする。
なお、この問題では、概略を示せば十分であり、変数宣言の欠如や型の不一致 等のコンパイラが検出するような誤りは、減点しない。
Write a sketch of a program that transfers money between two bank accounts. You may use the syntax of the C, Java, or Ruby language. You can use the library functions that implement transactions. These library functions must have good names that are similar to the operations to realize transaction.
You do not have to write a runnable program in this question. You do not have to fix compilation errors, such as no variable declaration and type incompatibility.
In 問題(1001) , write advantages of using transaction over using locking.