令和6年度秋期 データベーススペシャリスト 午前Ⅱ 問13

待ちグラフの循環を読む視点

各矢印が表す待機関係を確認し、トランザクション間の依存が一方向に進むのか、途中で循環して戻るのかに注目して、永久待ちの可能性を検討しましょう。

この問題で問われていること

一覧を作る前に、待ちグラフ上で矢印をたどったときの到達関係と循環の有無に焦点を絞り、個々のトランザクションの位置関係を比較してください。

視点

待ちグラフでは、矢印の向きがロック解放を待つ関係を示します。特定の経路をたどって出発点へ戻る構造があるかを確認し、待機関係が解消されにくい構造かという観点で整理しましょう。

確認ポイント

• 矢印の向きを読み違えていないか
• 待機関係を連続してたどれる経路があるか
• 経路が循環しているかを確認できているか

正解

ウ

解説

永久待ちとは、待ち関係が循環して解消されないため、トランザクションが完了できない状態です。この図ではB、C、Dが相互に待ち続ける循環を形成し、Fもその循環内のトランザクションを待っているため、待ちが解消されるまで永久に進めない。したがって該当するのはB、C、D、Fです。

理由

図の矢印をたどると、B、D、Cの間で待ちが循環している。この循環は、いずれかが先にロックを解放しない限り解消されない。また、FはDを待っているため、Dを含む循環が続く限りFも処理を進められず、永久待ちに含まれる。

比較

AはCから待たれているだけで、自身が循環に参加していない。EとGも循環を構成せず、Fを含めた待ち関係を正しく見る必要がある。よって、循環そのものに属するB、C、Dと、そこに依存するFを列挙した選択肢が適切です。

選択肢ア

これは不正解だよ。A，B，C，Dとするが、AはCから待たれているだけで、Aから別のトランザクションを待つ矢印はない。したがって、B，C，Dの循環に参加せず、永久待ちの対象には含まれない。また、Dを待つFが抜けている点も不適切である。

選択肢イ

これは不正解だよ。B，C，Dは相互に待ち関係が循環しているため該当するが、Fが含まれていない。FはDがロックしている資源のアンロックを待っており、Dが循環から抜けられない限りFも処理を進められないため、永久待ちに含める必要がある。

選択肢ウ（正解）

これは正解だよ。B，C，Dは待ちグラフ上で循環を形成し、互いのロック解放を待ち続ける。さらにFはDを待っているため、その循環が解消されない間はFも進行できない。循環に直接参加するトランザクションと、循環に依存するFを合わせた列挙になっている。

選択肢エ

これは不正解だよ。C，D，Fは永久待ちに関係するが、EとGはこの図の待ち関係で循環に参加していない。EはGを待ち、Gは他を待っていないため、E自身が永久待ちになる循環はない。必要なBを含めず、EとGを加えている点が誤りである。

学習のポイント

デッドロックの循環と、循環へ依存する待ちの波及を区別して理解する。