平成26年度 秋期 情報セキュリティスペシャリスト試験 午前Ⅱ 問21

✓ これが正解イ〔図〕待ちグラフ（A，B，C，D の4節点）: B → A ／ A → C ／ A → D ／ C → B ／ C → D

解説

A→C→B→A と一周する閉路がある待ちグラフがデッドロックです。

待ちグラフでは、矢印の向きに沿ってたどり、出発した節点に戻ってくる閉路があるかどうかでデッドロックを判定します。閉路の上にあるトランザクションは、互いに相手のアンロックを待ち続けるので、どれも先へ進めなくなるからです。正解のグラフでは、A が C を待ち、C が B を待ち、B が A を待っています。矢印をたどると A から C、C から B、B から A へと戻り、一周する閉路ができています。D は A と C から待たれているだけで、D から出る矢印がないので閉路には入りません。見るべきは矢印の多さではなく、ぐるりと一周するかどうかです。

ほかの選択肢はなぜ違うのか

• ア〔図〕待ちグラフ（A，B，C，D の4節…：このグラフでは、D が C と A を、C が B を、B が A を待っています。ところが A はどれも待っていないので、A が終われば順に待ちが解けていきます。行き詰まる経路はありません。
• ウ〔図〕待ちグラフ（A，B，C，D の4節…：A が B、C、D の三つを待っているだけで、B、C、D から出る矢印はありません。三つがアンロックすれば A は進めるので、待ちが一周することはなく、デッドロックではありません。
• エ〔図〕待ちグラフ（A，B，C，D の4節…：三つの矢印はすべて C に向かっており、C 自身は何も待っていません。C が資源を手放せば、待っていた三つのトランザクションも順に処理を再開できるため、行き詰まりは生じません。