基本情報技術者 2019年 秋期 午前（科目A） 問29
問題文
相ロッキングプロトコルに従ってロックを獲得するトランザクションA,Bを図のように同時実行した場合に、デッドロックが発生しないデータ処理順序はどれか。ここで、readとupdateの位置は、アプリケーションプログラムでの命令発行時点を表す。また、データWへのreadは共有ロックを要求し、データX, Y, Zへのupdateは各データへの専有ロックを要求する。
選択肢
ア：
イ：
ウ：（正解）
エ：
相ロッキングプロトコルによるデッドロック判定【午前2 解説】
要点まとめ
- 結論：Bの順序が「① update X → ② read W → ③ update Y → ④ update Z」の選択肢ウが正解で、相互待ち（デッドロック）が発生しません。
- 根拠：デッドロックは「相互に必要な排他ロックを逆順で保持して待つ」循環待ちが必要で、ウではその逆順保持の可能性が排除されます。
- 差がつくポイント：read W は共有ロックのため同時保持は許され、排他ロックの獲得順（特に X と Y の順序）をどう並べるかが勝敗を分けます。
正解の理由
選択肢ウでは B がまず X の排他ロックを取得し、その後 W を共有で取得、続けて Y→Z の排他ロックを要求します。A は W（共有）→X（排他）→Y（排他）→Z（排他）という順序です。
どの順序で並行実行されても、A と B が互いに X と Y をそれぞれ片方ずつ保持して相手が持つもう一方を待つ、つまり A が X を持って Y を待ち、同時に B が Y を持って X を待つような「循環待ち」は起こりません。したがってデッドロックが発生しません。
どの順序で並行実行されても、A と B が互いに X と Y をそれぞれ片方ずつ保持して相手が持つもう一方を待つ、つまり A が X を持って Y を待ち、同時に B が Y を持って X を待つような「循環待ち」は起こりません。したがってデッドロックが発生しません。
よくある誤解
- 共有ロック（read W）は排他ロックと常に競合すると思い込む誤解：共有ロック同士は互いに干渉せず同時保持できます。
- 2PL（相ロッキング）なら必ずデッドロックを防げるという誤解：2PL は整合性を保証しますが、デッドロック自体は発生し得ます。
- 「すべてのロックを先に獲得すれば安全」と考える誤解：先行取得による待ちが逆にデッドロックを誘発する場合があります。
解法ステップ
- 各操作が要求するロック種別を明確にする（read→共有、update→排他）。
- A の固定順序（W→X→Y→Z）と、選択肢で示される B の順序を並べる。
- 排他ロック同士（X,Y,Z）に注目し、A と B がそれらを逆順に保持して互いに待つ循環（A:X→待Y, B:Y→待X）が起き得るか検討する。
- 循環が発生し得ればその選択肢は誤り、発生し得なければ正解とする。
選択肢別の誤答解説
- ア：① read W、② update Y、③ update X、④ update Z
両者とも最初に W を共有で取れるため、A が X を取り B が Y を取るように進行すると、A が Y を待ち、B が X を待つ循環待ちが発生する可能性があります（デッドロックあり）。 - イ：① read W、② update Y、③ update Z、④ update X
同様に A:X → 待Y と B:Y → 待X の逆順ロック獲得が起こり得て、デッドロックが発生します。 - ウ：① update X、② read W、③ update Y、④ update Z
B が先に X を取得するため、A と B が X と Y を互いに保持して待つような循環が発生しません。よってデッドロックは回避できます（正解）。 - エ：① update Y、② update Z、③ update X、④ read W
B が先に Y を取得し、A が先に X を取得する状況が生じると A が Y を待ち B が X を待つ循環が発生し得ます（デッドロックあり）。
補足コラム
相ロッキングプロトコル（問題文の文脈では通常「二相ロッキング（2PL）」を指します）は、トランザクションがロックを獲得する段階（成長期）と解放する段階（縮小期）を分ける方式です。2PL は一貫性を保ちますが、デッドロックを自動で防ぐものではありません。現実のDBMSではデッドロック回避（タイムアウト、wait-die／wound-wait）や検出（待ち合わせグラフの周期検査）といった補助策を併用します。
FAQ
Q1: なぜ read W（共有ロック）はデッドロックを起こしにくいのですか？
A1: 共有ロック同士は互いに共存できるため、複数のトランザクションが同時に W を読むことはブロックし合いません。衝突は排他ロックとの間で起きます。
A1: 共有ロック同士は互いに共存できるため、複数のトランザクションが同時に W を読むことはブロックし合いません。衝突は排他ロックとの間で起きます。
Q2: もしトランザクションがロックを途中で解放したら結果は変わりますか？
A2: はい。途中解放が許されると循環待ちの形が変わり得ますが、2PL（特に厳密2PL）では通常コミットまで解放しないため、問題文の前提では考慮不要です。
A2: はい。途中解放が許されると循環待ちの形が変わり得ますが、2PL（特に厳密2PL）では通常コミットまで解放しないため、問題文の前提では考慮不要です。
Q3: デッドロックを確実に避ける方法はありますか？
A3: 完全に避けるにはグローバルなロック順序を決めて強制する（全トランザクションが同じ順序でロックを取る）などの方法がありますが、性能や柔軟性のトレードオフがあります。
A3: 完全に避けるにはグローバルなロック順序を決めて強制する（全トランザクションが同じ順序でロックを取る）などの方法がありますが、性能や柔軟性のトレードオフがあります。
関連キーワード: デッドロック、二相ロッキング、共有ロック、排他ロック、待ち合わせグラフ、ロック獲得順序
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！