情報処理安全確保支援士 2014年秋期午前2 問21

問題文

トランザクションA~Dに関する待ちグラフのうち、デッドロックが発生しているものはどれか。ここで、待ちグラフの矢印は、X→Yのとき、トランザクションXはトランザクションYがロックしている資源のアンロックを待っていることを表す。

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

ア：

イ：（正解）

ウ：

エ：

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

待ちグラフでは、X→Yが「XがYの資源の解放を待っている」ことを表します。矢印の向きに沿ってたどり、出発点に戻れる経路（閉路）があると、その経路上のトランザクションは互いに相手を待ち続け、どれも先へ進めません。これがデッドロックです。

イのグラフにはA→C、C→B、B→Aの矢印があり、A→C→B→Aと一周する閉路ができています。AはCを、CはBを、BはAを待っているので、3つのトランザクションはどれも資源を解放できません。したがって、デッドロックが発生しているのはイです。

ア：矢印はB→A、C→B、D→C、D→Aです。Aから出る矢印がないため、どこから出発してもAで行き止まりになり、閉路はありません。Aが処理を終えて資源を解放すれば、B、C、Dの順に待ちが解消します。
イ：正解。A→C→B→Aの閉路があります。A→DとC→Dの矢印もありますが、Dから出る矢印はなく、閉路には関係しません。
ウ：矢印はA→B、A→C、A→Dだけです。Aが3つのトランザクションを待っているだけで、B、C、Dは何も待っていないため閉路はありません。
エ：矢印はA→C、B→C、D→Cです。3つのトランザクションがCを待っているだけで、Cから出る矢印がないため閉路はありません。

矢印が多く集まっている頂点があるとデッドロックだと考えること。多くのトランザクションが同じ相手を待っていても、その相手が何も待っていなければ、いずれ待ちは解消します。
矢印の向きを無視して、線が輪になっていれば閉路だと考えること。アのように線だけを見ると輪に見えても、向きに沿って一周できなければ閉路ではありません。

データベース管理システムは、待ちグラフを定期的に調べて閉路を見つけると、閉路上のトランザクションのどれか1つを取り消して（ロールバックして）資源を解放させ、デッドロックを解消します。取り消されたトランザクションは、後で再実行されます。

Q. 閉路が見つかったら、どのトランザクションを取り消すのですか？
A. 一般には、取り消しによる損失が小さいもの（実行を始めてからの時間が短いもの、更新量が少ないものなど）が選ばれます。

Q. デッドロックを起こさないようにする方法はありますか？
A. すべてのトランザクションが、決められた同じ順番で資源をロックする方法があります。順番がそろっていれば、互いに待ち合う閉路はできません。

関連キーワード: デッドロック、待ちグラフ、排他制御、ロック、トランザクション

\ せっかくなら /

情報処理安全確保支援士を
クイズ形式で学習しませんか？

すぐに利用可能！