2相ロッキングで循環待ちを防ぐ処理順序
基本情報技術者試験 令和元年度秋期 午前 問29 ／ データベース › トランザクション処理
過去問にチャレンジ
2相ロッキングプロトコルに従ってロックを獲得するトランザクションA，Bを図のように同時実行した場合に，デッドロックが発生しないデータ処理順序はどれか。ここで，read と update の位置は，アプリケーションプログラムでの命令発行時点を表す。また，データWへの read は共有ロックを要求し，データX，Y，Zへの update は各データへの専有ロックを要求する。
- ア
①：read W，②：update Y，③：update X，④：update Z
- イ
①：read W，②：update Y，③：update Z，④：update X
- ウ
①：update X，②：read W，③：update Y，④：update Z
- エ
①：update Y，②：update Z，③：update X，④：read W
会話形式の解説
講師注目するのは、AとBが先にどのロックを取り、次に何を待つかです。互いに待ち合う循環ができるかを調べましょう。
受験者AはWを読んでからX、Y、Zを更新します。Bが同じデータを使うところで止まりそうですが、どこから追えばよいですか。
講師まずXとYの順序を比べます。AはXを取ってからYを要求します。BがYを先に取った場合、その後に何を待つでしょうか。
受験者Bが後でXを要求すると、AはBのYを、BはAのXを待つ可能性があります。これが循環待ちですか。
講師そのとおりです。BがWを読んでからY、X、Zと進む順序では、その循環が起こり得ます。
受験者BがYの次にZを更新し、Xを最後に回しても、Yを保持したままXを待つので同じですか。
講師はい。BがW、Y、Z、Xと進む順序でも、AがXを保持してYを待つ可能性があります。Zを間に入れても循環は防げません。
受験者BがY、Z、Xと更新してからWを読む順序も、Xより先にYを取る点が問題ですね。
講師そうです。AがXを保持してYを待ち、BがYを保持してXを待つ可能性があります。Bは最後のWの読取りまで進めません。
受験者では、BもXを最初に更新する順序なら、Xを取れなかった側が待つことになりますか。
講師はい。Bが先にXを取ればAはXで待ちますが、Bは次にWを読めます。Wの読取りに使う共有ロック同士は競合しないため、その後のY、Zの更新へ進めます。
受験者BがX、W、Y、Zの順序なら互いに待ち合いません。正解はウですね。
講師そのとおりです。先に取ったロックを保持したまま次のロックを待つ、と順に追うと、見かけ上の待機とデッドロックを区別できます。
まとめ
正解はウです。AはWを読んでからX、Y、Zを更新するため、BがYをXより先に取る順序では、AとBが互いのロックを待つ可能性があります。BがXを最初に取る順序なら、AはXで待っても、Bは共有ロックでWを読んで処理を進められます。待ちが発生するかだけでなく、待ちが循環するかを確認することが判断の鍵です。
解答・解説
正解はウです
この問題のテーマ
2相ロッキングで、二つのトランザクションがロックを取得する順序とデッドロックの関係を問う問題です。
解き方の考え方
AはWを読んだ後、X、Y、Zを順に更新します。Bの各処理を図の①〜④に当てはめ、片方が保持するロックをもう片方が待つ状態を調べます。互いに相手のロックを待つ循環ができるかが判断の鍵です。
選択肢ごとの解説
- ×ア ①：read W，②：update Y，③：update X，④：update ZBはWを読んでからY、X、Zを更新します。AがXを保持してYを待ち、BがYを保持してXを待つ状態が起こり得るため、デッドロックを防げません。
- ×イ ①：read W，②：update Y，③：update Z，④：update XBはWを読んでからY、Z、Xを更新します。AがXを保持してYを待つ一方、BはYを保持したままXを待つ可能性があり、循環待ちになります。
- ○ウ ①：update X，②：read W，③：update Y，④：update ZBは最初にXを更新し、その後Wを読んでY、Zを更新します。BがXを保持している間、AはXで待ちますが、BによるWの共有ロック要求はAの共有ロックと競合しません。Bは残りの更新を進められるので、互いに待ち合う状態にはなりません。
- ×エ ①：update Y，②：update Z，③：update X，④：read WBはY、Z、Xを更新してからWを読みます。AがXを保持してYを待ち、BがYを保持してXを待つ状態が起こり得るため、最後のWの読取りまで進めなくなります。
POINT
- 共有ロック同士は同じデータに対して同時に保持できます。
- 専有ロックを別々に保持した二者が、互いの保持するロックを要求すると循環待ちになります。
- 処理の順序を比べるときは、先に取得したロックを保持したまま次に何を待つかを追います。