ITサービスマネージャ 2014年午前2 問21

問題文

トランザクションA〜Dに関する待ちグラフのうち、デッドロックが発生しているものはどれか。ここで、待ちグラフの矢印は、

X \to Y

のとき、トランザクションXはトランザクションYがロックしている資源のアンロックを待っていることを表す。

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

ア：

イ：（正解）

ウ：

エ：

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

待ちグラフでは、矢印

X \to Y

は「トランザクションXが、Yのロック解除を待っている」ことを表します。

イには、

B \to A \to C \to B

という閉じた経路、すなわち有向サイクルがあります。これは、BがAを待ち、AがCを待ち、CがBを待っている状態です。互いに相手の処理完了を待っているため、どのトランザクションも先に進めず、デッドロックが発生しています。

ア： $B \to A$ 、 $C \to B$ 、 $D \to C$ 、 $D \to A$ です。矢印をたどって出発点に戻る経路はなく、サイクルはありません。
イ： $B \to A \to C \to B$ のサイクルがあります。したがって、デッドロックが発生しています。 $A \to D$ や $C \to D$ の矢印が加わっていても、サイクルの存在は変わりません。
ウ：矢印はAからB、C、Dへ向かっていますが、各頂点からAへ戻る矢印はありません。サイクルはありません。
エ：A、B、DからCへ矢印が向かっていますが、Cから他の頂点へ戻る矢印はありません。サイクルはありません。

待ちグラフは、トランザクション間の待ち関係を有向グラフで表したものです。基本的な問題では、グラフに有向サイクルがあればデッドロックと判断します。サイクルを見つけたら、矢印の向きに沿って一周できることを確かめると、見落としを防げます。

Q. サイクルに含まれないDがある場合でも、デッドロックですか？
A. はい。デッドロックを判定するのは、待ちグラフ内にサイクルが存在するかどうかです。サイクルに含まれないトランザクションがあっても、サイクルがあればデッドロックが発生しています。

Q. 矢印が一方向に並んでいるだけでは、デッドロックになりませんか？
A. 一方向に並ぶだけでは、出発点へ戻るサイクルがありません。そのため、デッドロックとは判断できません。

関連キーワード: 待ちグラフ、デッドロック、有向グラフ、有向サイクル、トランザクション、ロック

\ せっかくなら /

ITサービスマネージャを
クイズ形式で学習しませんか？

すぐに利用可能！