並行システム システム情報系情報工学域, システム情報工学研究科コンピュータサイエンス専攻 新城 靖 <yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2017/2017-12-15
あるいは、次のページから手繰っていくこともできます。
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.
歴史:1960年代、テープの時代。 失敗したら、巻き戻す(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 の前にクラッシュしても、常にディスク1が正しい(図?(b))。 この場合は、ディスク1からディスク1へコピーする。
チェックサムエラーが起きた場合(図?(c))、他のディスクからコピーして回復する。
もっとも単純な方法:
注意:プログラマは、ロックを意識しない。
制約が強すぎる。
読み取りロック:read lock と write lock を分ける。
ロックの粒度(granularity)が大事
図? 2相ロック/Two-phase locking
定理:トランザクションの実現で2相ロックを使うならば、インターリーブさ れることで作られるスケジュールは直列化可能である。
実際のシステムでは、Commit/Abort するまで、一度確保したロックをはなさない。
第2相で、まとめて全部ロックを解放する(strict two-phase locking)。
図? 2相ロック/Strict two-phase locking
利点
注意:2相ロックと2相コミットは別。
実現(衝突時の対応):プライベート作業空間を使う実現が便利。 どんどんプライベート作業空間上のファイルを更新して、最後にコミットする か削除する。
性質
アルゴリズム:
Lamport のアルゴリズム等でクロックが同期されていれば、分散システムでも 使える。
2種類のプロセス
https://www.slideshare.net/kumagi/ss-78765920,分散システムについて語らせてくれ by 熊崎宏樹
分離レベル | ダーティーリード | ノンリピータブル・リード | ファントム・リード |
---|---|---|---|
Read Uncommitted | 有 | 有 | 有 |
Read Committed | 無 | 有 | 有 |
Repeatable Read | 無 | 無 | 有 |
Realizable | 無 | 無 | 無 |
Barbara Liskov: "Distributed programming in Argus", Communications of
the ACM, Vol.31, No.3, pp.300-312, 1988.
http://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
if( a() ) { b(); } else { c(); }
図? 投機的実行 Speculative execution
この例では、a() が完了した時には、b()、c() が終わっていた時には、見かけ 上、即座に終わる。
SF (Science Fiction) のパラレルワールド(parallel world, parallel
universe)を、オペレーティング・システムのレベルで実現する。
図 SFのパラレルワールド
SFでは、時々別の世界にジャンプしたり人が入れ替わったりする。
世界OSでは、ファイルの内容を変更すると、2つの世界ができる。
図 世界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.
なお、この問題では、概略を示せば十分であり、変数宣言の欠如や型の不一致 等のコンパイラが検出するような誤りは、減点しない。
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.