システムアーキテクト 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: 図示とスケジュールは必ず突き合わせて確認してください。特に図だけで次数の一致を見て早合点するのではなく、資源ごとの実際の待ち（誰が誰のロックを待つか）を明示的に導出することが重要です。

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