平成26年度 秋期 午前Ⅱ 問21

✓ これが正解イ（原典は図。待ちグラフの矢印は B→A，A→C，A→D，C→B，C→D）

解説

待ちの矢印がひと回りして元に戻る閉路があるグラフが、デッドロックです。

デッドロックは、複数のトランザクションが互いに相手のロックの解除を待ち合い、どれも先へ進めなくなる状態です。待ちグラフでは、矢印をたどっていくと出発したトランザクションに戻ってくる輪、つまり閉路があるときにデッドロックが発生しています。B→A、A→C、A→D、C→B、C→Dの矢印をもつグラフでは、AはCを待ち、CはBを待ち、BはAを待っているので、A→C→B→Aという閉路ができています。三つのトランザクションのどれもが他の解放を待ち続けるので、外から手を打たない限り処理は進みません。待ちグラフの問題では、矢印を順にたどって元の場所へ戻れるかどうかだけを確かめればよい、と覚えておくと素早く判断できます。

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

• ア（原典は図。待ちグラフの矢印は B→A，…：矢印がB→A、D→A、D→C、C→Bのグラフでは、Aから出る矢印が無く、Aはだれも待っていません。Aが処理を終えてロックを解放すればBが進み、次いでC、最後にDも進めるので、閉路は無くデッドロックではありません。
• ウ（原典は図。待ちグラフの矢印は A→B，…：矢印がA→B、A→C、A→Dのグラフでは、AがB、C、Dの三つを待っているだけで、B、C、Dはだれも待っていません。それぞれが処理を終えてロックを解放すればAも進めるので、デッドロックではありません。
• エ（原典は図。待ちグラフの矢印は A→C，…：矢印がA→C、B→C、D→Cのグラフでは、A、B、DがそろってCを待っていますが、Cはだれも待っていません。Cが処理を終えてロックを解放すれば他も進めるので、閉路は無く、デッドロックではありません。