Database Concurrency Control Papadimitriou 読会33回ノート:Schedulerのmode,Two-Phase Lockingなど

• p96 4.2 Lockingからp103 Exclusive and Shared Lockの手前まで。
• 次回はp103 Exclusive~から

connpass.com

Schedulerの3つのモード(個人的な復習)

Dynamic mode

• 初期状態で何の情報も持たない。
  • Transacionのstepが順次到着するが、そのstepの情報のみ(操作内容read,writeや操作対象のentity)
  • 最終ステップに関しては最終ステップである趣旨の通知がスケジューラになされる。

Declaration Mode

• 各トランザクションの最初のステップ到着時に、残りのトランザクションに関する全ての情報が取得可能と想定する。
• クライアントはpoorな制御構造しか持てない。(少なくともトランザクション内のif文は難しい)

Static Mode

開始時にすべてのTransactionの情報がすべて把握できている。

Static Two-Phase Locking

• 以下をテストする
  • "A step can always proceed, unless it is the first step of a transaction, and this transaction conflicts with an active transaction."
    • あるTransactionの最初のstepはActiveなtransactionとconflictしていない場合のみ進行可能である
      • →conflictしている場合はactiveなもう一方のtransactionの終了を待つ(FIFO queuing)
• declaration modeでのみ可能

Dynamic Two-Phase Locking

• 以下をテストする
  • "A step can always proceed, unless it conflicts with a previous step of an active transaction(other than its own)"
  • つまり、activeなtransactionで実行済みなstepでconflictがあるものは実行されない
    • 実行中のtransactionで操作対象としているentityに対するstepはqueuingされる。
      • つまりconflictしている実行中のtransactionが終了した時にqueueからoutされる
• dynamic modeで実行可能。

Two-Phase Locking

• 1.entityに対するactionの前に必ずロックをとる

• 2.各トランザクションのlock stepの前にunlock stepが来ることはない(entity関係なく)

• 関係ないけどTwo-Phase Lockの証明はかなり綺麗らしい(serializable?weikum本にある？)

Theory of Database Concurrency Control