システムアーキテクト 2022年午前2 問24

問題文

t_{1}

~~$t_{10}$ の時刻でスケジュールされたトランザクション $T_{1}$~~

T_{4}

がある。時刻

t_{10}

で

T_{1}

がcommitを発行する直前の、トランザクションの待ちグラフを作成した。aに当てはまるトランザクションはどれか。ここで、select(

X

)は共有ロックを掛けて資源

X

を参照することを表し、update(

X

)は専有ロックを掛けて資源

X

を更新することを表す。これらのロックは、commitされた時にアンロックされるものとする。また、トランザクションの待ちグラフの矢印は、

T_{i}

→

T_{j}

としたとき、

T_{j}

がロックしている資源のアンロックを、

T_{i}

が待つことを表す。

🖊️ 解答を隠して解いてみる

選択肢

ア：

T_{1}

イ：

T_{2}

（正解）

ウ：

T_{3}

エ：

T_{4}

🔒 解説は解答すると表示されます

待ちグラフのノード対応【午前2解説】

正解の理由

設問の正答はイ（T₂）です。理由はスケジュールから導ける「各トランザクションがどのトランザクションのアンロックを待っているか」を資源（A, B, C）のロック状況に基づいて明示的に列挙すると、T₂ の位置（入次数1・出次数1）が図中のノードaの入出辺の構成と一致するためです。以下でスケジュールに基づく待ち関係を逐一示し、図の矢印と照合してaがT₂ に対応することを示します。

解法ステップ

スケジュールから各時刻でのロック獲得要求とブロックの発生を順に追う。共有ロック（select）は共有許可、専有ロック（update）は他の共有・専有ロックが存在する場合に待ちになる。
t₁～t₁₀ を順に見て、各トランザクションが「誰のロック解除を待っているか（Tᵢ → Tⱼ）」を明確にする。
得られた待ち関係（有向辺）を図の矢印と照合して、各図のノードがどのトランザクションに対応するかを決定する。特にノードaの入出辺の相手ノードが誰かを資源に紐づけて確定する。

以下にステップ2の詳細（ロックと待ち関係の具体的導出）を示します。

T1の操作
- t1: select(A) → T1はAにSロックを保持（t10のcommitで解放される直前まで保持）
- t6: select(C) → T1はCにSロックを保持
- t10: commit（ただし問題はcommit発行直前の状態を問うているため、まだロックは解放されていない）
T2の操作
- t2: select(B) → BにSロックを保持
- t7: select(C) → CにSロックを取得（T1もCのS所有者であり、共有は許容）
- t8: update(C) → CのX（専有）ロックを要求。Xを得るには他のCのS所有者（ここではT1）が解放する必要があるため、T2はT1のアンロックを待つ（T2 → T1）。
T3の操作
- t3: select(B) → BにSロックを保持
- t9: update(A) → AのXロックを要求。Aは現在T1（t1によるS）とT4（t4によるS）がSロックを持っているため、T3はT1とT4のアンロックを待つ（T3 → T1, T3 → T4）。
T4の操作
- t4: select(A) → AにSロックを保持
- t5: update(B) → BのXロックを要求。BはT2（t2）とT3（t3）がSを持っているため、T4はT2とT3のアンロックを待つ（T4 → T2, T4 → T3）。

これらを纏めると、t10（T1のcommit発行直前）の待ち関係は次の通りになります（矢印は「待ち」）：

T2 → T1 （T2はCのXを得るためT1の解放を待つ）
T3 → T1 （T3はAのXを得るためT1の解放を待つ）
T3 → T4 （T3はAのXを得るためT4の解放を待つ）
T4 → T2 （T4はBのXを得るためT2の解放を待つ）
T4 → T3 （T4はBのXを得るためT3の解放を待つ）

ここから得られる各トランザクションの次数（in/out）は：

T1: in = 2（T2, T3が待つ）、out = 0
T2: in = 1（T4が待つ）、out = 1（T1を待つ）
T3: in = 1（T4が待つ）、out = 2（T1, T4を待つ）
T4: in = 1（T3が待つ）、out = 2（T2, T3を待つ）

図の矢印（a↔dとb↔cの二つの双方向辺）とこの待ち関係を照合すると、少なくとも「互いに待ち合っているペア（一方がもう一方を待ち、逆も同様）」はT3とT4の組であることが確実に分かります（T3 → T4とT4 → T3が両方存在）。したがって図中の相互辺が描かれている一組（上下に向き合うペア、図中でbとcに対応すると自然に整合します）。残るノード（a, d）はT1とT2に対応します。aの入出辺の構成（入1本、出1本）がT2のin=1/out=1と一致するため、ノードaはT2に対応します。以上からイ（T₂）が正答になります。

選択肢別の誤答解説

ア: T1
誤り。T1は他者のロック解放を待っていない（out = 0）一方で、他トランザクションから待たれている（in = 2）。したがって「入出両方を持つノードa」には一致しません。
イ: T2
正答。T2はt8のupdate(C) によりT1のアンロックを待っており（T2 → T1）、さらにT4からBに関して待たれている（T4 → T2）。すなわちin = 1, out = 1の構造がノードaと一致します。
ウ: T3
誤り。T3はT4に対しても待っている（T3 → T4）一方でT4からも待たれているが、T3のoutは2本（T1とT4）あり、図中のaはout = 1のため一致しません。
エ: T4
誤り。T4はout = 2（T2とT3を待つ）であり、図中のaの出次数構成とは異なります。

よくある誤解

誤解1: 「次数（入出次数）が一致すれば一意に対応付けられる」
→ 部分的には有用ですが、次数だけで一意決定できない場合があります。必ずどの資源（A,B,C）による待ちかを突き合わせて、矢印が表す具体的な待ち（誰が誰のどの資源の解放を待つか）で対応付けを行ってください。
誤解2: 「共有ロック同士は競合しないから待ちは発生しない」
→共有ロック同士は同時保持可能ですが、その後の専有ロック（update）要求時にアップグレード待ちが発生します。共有取得順やタイミングに注意して待ちが生じる点を見落とさないでください。

補足コラム

「待ちグラフ」を正しく構築するコツ
1. 各トランザクションの時系列操作を追い、各時点で保有しているロックをリスト化する。
2. 専有ロック（X）要求が来た時点で、その資源の現在の全保有者を列挙し、それらすべてに対して待ち辺を張る。
3. commit（またはabort）で初めてロックが解放される点を忘れない。
  「次数だけで判断せず」「資源単位での待ち関係」を明示的に照合するのが正確な方法です。

FAQ

Q1: 「select（共有）→ update（専有）への昇格は自動的にできるか？」
A1: 単純に同トランザクション内で昇格を要求しても、他のトランザクションが共有ロックを保持していれば待ちになります。昇格（S→X）は既存の他の共有ロック保持者がいない場合にのみ即時成功します。

Q2: 「待ちグラフにサイクルがあればデッドロック確定か？」
A2: はい。待ちグラフにサイクル（例えばT3 ↔ T4のような双方向の待ち）が存在すると、それらのトランザクション群は互いにロックを解放できずデッドロックとなります。デッドロック解消にはタイムアウトやデッドロック検出とロールバックが必要です。

Q3: 「図とスケジュールが一致しないように見える場合は？」
A3: 図示とスケジュールは必ず突き合わせて確認してください。特に図だけで次数の一致を見て早合点するのではなく、資源ごとの実際の待ち（誰が誰のロックを待つか）を明示的に導出することが重要です。

関連キーワード: ロック（共有/専有）、待ちグラフ、デッドロック、トランザクションスケジュール、排他制御、ロック待ち検出