コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

ツーフェーズロック

出典: フリー百科事典『ウィキペディア(Wikipedia)』

ツーフェーズロック (Two-Phase Locking) あるいは2相ロッキングとは、並列処理システム(特にデータベース管理システム (DBMS) や関係データベース)で使用されるロック手法である。ツーフェーズロックは以下のように分類される。

  • Strict 2PL: 厳密な (Strict) ツーフェーズロック
  • 2PL: 厳密でない (Non-Strict) ツーフェーズロック
  • C2PL: 保守的な (Conservative) ツーフェーズロック

単にツーフェーズロック (2PL) といった場合、厳密でない (Non-strict) ツーフェーズロックを指す。以下ではこれらについて解説する。

厳密な (Strict) ツーフェーズロック

[編集]

Strict 2PL には以下の2つの原則がある。

  1. トランザクションTがあるオブジェクトをリード/ライトしようとしたとき、そのオブジェクトに共有/排他ロックを使用しなければならない。
  2. トランザクションTがかけた全ての排他ロックはTがコミットする際に解放される(コミット前ではない)。

以下に2つの相互に影響する処理での Strict 2PL の例を示す。

テキストで表すと、次のようになる。

T1: S(A), R(A); T2: S(A), R(A), X(B), R(B), W(B), Commit; T1: X(C), R(C), W(C), Commit

ここで

  • S(O) は、オブジェクトO への共有(Shared)ロック操作
  • X(O) は、オブジェクトO への排他(eXclusive)ロック操作
  • R(O) は、オブジェクトO へのリード(Read)操作
  • W(O) は、オブジェクトO へのライト(Write)操作

Strict 2PL は、コミットされていないデータをリードすること、コミットされていないデータを更新すること、リードとライトの衝突などを防ぐ。従ってカスケーディングロールバック(トランザクションの中断によって発生するロールバックが複数のトランザクションを巻き込んでしまう現象)も防ぐことができる。というのもライト操作を防ぐ排他ロックをトランザクションをコミットするまでかけているからである。

Strict 2PL はデッドロックを防げない

[編集]

リアルタイムシステムではデッドロックを防ぐことは重要である。また、分散データベースや多重化されたフォールトトレラントシステムでは困難だろう。

Strict 2PL ではデッドロックが以下のような流れで発生する。

テキストでは以下のようになる T1: X(A) T2:X(B) T1:X(B) T2: X(A)

T1 は T2 が B にかけたロックが外されるのを待ち、T2 は T1 が A にかけたロックが外されるのを待つ。2つのトランザクションはその先に進むことができず、両者共にデッドロック状態になる。

デッドロック問題には汎用の解決策は存在しない。従って、状況に応じて予防/対処するしかない。状況によっては、「銀行家のアルゴリズム」や「ロック獲得順の設定」のような対策によってデッドロックを防ぐこともできる。

厳密なツーフェーズロックよりもさらに厳密な 厳格な(Rigorous)ツーフェーズロックもある。これはトランザクションのコミットの際に共有ロックを含めた全ロックを解放するものである。多くのデータベースは Strict 2PL を使用している。

厳密でないツーフェーズロック (2PL)

[編集]

2PLの原則は Strict 2PL のものに似ていて、以下のようになる。

  1. トランザクションTがあるオブジェクトをリード/ライトしようとしたとき、そのオブジェクトに共有/排他ロックを使用しなければならない。
  2. トランザクションはいずれかのロックを解放したら追加のロックをかけることができない。また、いつでもロックを解放することができる(Strict 2PL ではコミット時のみ)。

従って、トランザクションには成長期(ロック獲得期)と減退期(ロック解放期)がある。2PLは衝突直列化可能なスケジュールのみを許す。

保守的なツーフェーズロック (C2PL)

[編集]

保守的な2PL (C2PL) はデッドロックを防ぐ。

2PLとC2PLの違いは、C2PLがトランザクション開始前に必要な全ロックを獲得するという点にある。これによりトランザクションの途中でロックを獲得しようとしてデッドロックとなることがなくなる。

ロックの衝突が激しい状況では、C2PLでのトランザクションは途中でブロックされないので、2PL や Strict 2PL に比較して平均ロック獲得期間を減らすことができる。

ロックの衝突が少ない状況では、C2PLは必要以上にロックを獲得するため、オーバヘッドが高くなる。

また、トランザクションは必要とされるロックが全て獲得できるまでいかなるロックも獲得しないし、処理も開始できない。さらに、トランザクション毎にリード/ライトするデータを全て宣言する必要があり、これは必ずしも常に可能とは言えない。このような制限があるため、C2PL はあまり使われていない。