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

待ちグラフとは

トランザクション処理において、複数のトランザクションが互いに相手の保持する資源の解放を待ち合い、処理が進まなくなる状態を永久待ち（デッドロック）と呼びます。待ちグラフはトランザクションの待ち状態を有向グラフで表したもので、グラフ内に閉路（ループ）が存在する場合、その閉路に含まれるトランザクションは永久待ちに陥っています。

正解の根拠

待ちグラフの接続関係から、各トランザクションの待ち状態を整理します。矢印 $X \to Y$ は、XがYのアンロックを待っていることを表します。

• CからB、BからD、DからCへ矢印が向かっています。これにより、$B \to D \to C \to B$ という閉路が形成されています。したがって、トランザクションB、C、Dは互いにアンロックを待ち合うことになり、永久待ちの状態となります。
• FからDへ矢印が向かっています。Fは永久待ち状態であるDを待つため、F自身も永久待ちの状態となります。
• AとGからは出ている矢印がない（誰も待っていない）ため、これらは他のトランザクションを待たずに終了できます。
• CからAへの矢印がありますが、Aは終了できるため、これが原因でCが永久待ちになることはありません（CはBを待つことで永久待ちになっています）。
• EからGへ矢印がありますが、Gは終了できるため、Gを待つEもやがて終了できます。

以上より、永久待ちの状態になっているトランザクションはB、C、D、Fです。したがって正解は「ウ」です。

各選択肢の解説

• ア: 誰も待っていないAは終了できるため、永久待ちにはなりません。
• イ: 永久待ち状態であるB、C、Dのほかに、Dを待っているFも永久待ちとなるため、列挙として不足しています。
• ウ: 正解です。閉路を形成するB、C、Dと、閉路内のDを待つFが永久待ちになります。
• エ: C、D、Fは永久待ちですが、Gと、Gを待つだけのEは終了できるため永久待ちにはなりません。