排他ロックと共有ロック

2つのトランザクションが同時にロック(片方が排他)を獲得していないスケジュールはlegal
- writeにがあったentityには排他ロックを獲得している
- readがあったentityには排他・共有どちらかのロックを獲得している

ロックの粒度

議論:楽観ロックと悲観ロック
- 悲観ロック
  - スタベーション(abortし続ける)
個別にロックを取るか、まとめてロックを取るか
- まとめてロックを取る:まとめて=粒度
  - 個別に複数ロックを取るのと同じ
class $\Gamma \subset E$
$e \in E$
${e} \in \Gamma$
任意のG1,G2∈Γに対して共通部分が存在する場合、片方が新部分集合になっている
- $G_1 \cap G_2 =\emptyset $ or
- $G1 \subset G2$ or
- $G2 \subset G1$
chain of $\Gamma$
- chain $$
この構造は木構造そのもの
access lock,intention lockのrule
- 1:action対象のentityを含むgranulesのどれか一つにaccess lock獲得する
- 2:access lockしたものが所属するgranule chainのすべてのgranuleに対してintention lockを獲得する
- 3:各トランザクションはロックの解除ステップにlock stepを持たない()
議論:javaのsynchornizedの仕様が微妙
- safe,unsafe的な用語では無いのか

entityに順番にアクセスすることを前提とできるとき、two-phase lockよりも柔軟なlockプロトコルを考えることができる
- entityに対してlinear orderを定義するx1,x2,...,xn
- 例えば以下のtransactionsがそれに該当する
  - T1=A(x2)A(x3)
  - T2=A(x3)A(x4)A(x5)A(x6)
ルール
- 最初に操作対象のentityをlockする
- 操作対象のentityにaccessする
- 次の操作対象のentity xiをlockする際、前回操作対象だったxi-1のentityをunlockする
L(x3)A(x3)L(x4)U(x3)L(x4)A(x4)L(x5)U(x4)...
- 上記のtransactionはpath protocolに従っている
  - two phase lockingではない
    - unlockの後にlockしている箇所があるため
path protocol は safe
証明略
用語の定義
- triangulated/chordal:任意の3より長いcycleが含むより短いcycleのこと(長さ3のcycle)
- path:in-degree

2020/11/04~の範囲
p111~
output,arrirvedなどの概念がややこしいと思った。
以下をテストするとConflict Serializableなスケジュールが得られる
- (自分より古いトランザクションの)競合するstepが既に出力されている場合、stepを継続できる*1

timestampを使う
- のでtimestamp schedulerと呼ばれる
各activeなトランザクションには数字(timestampを割り当てる)
- 最初のステップが到着したtimestampを各トランザクションに割り当てる
  - papa本では最初のstepはbegin transaction stepとしている
    - 実際のシステムでbegin transactionの時間をccに使っているものはないのではないか？という議論があった。
entityのタイムスタンプという概念を考える
- entityに対する最後のwrite,read操作をreadのタイムスタンプ、writeのタイムスタンプと定義する
  - xのwriteのentityタイムスタンプよりr(x)のtransactionタイムスタンプが大きい時、r(x)は続行できる
  - xのread,writeのentityタイムスタンプよりw(x)のtransaction timestampが大きい時、w(x)は続行できる
dynamic modeで動作可能だが、デッドロックにあるパターンがある。p112のExample 4.3~
p113 5行目:”Notice that A2: W(x) ended up joining the queue~"とあるが、A2ではなくA1の間違い(typo?)

p113~
conflict graphを使ったcc
conflict graphに新しいstepが追加した際、acycleな場合にstepをすすめることができる。
csrなスケジュールが得られる
- theorem 4.11: the set of schedules output by the conflict graph scheduler is precisely the set of conflict serializable schedules.

次回はp116 Theorem 4.12から

*1:A step can proceed if all conflicting steps of older active transactions have already been output