デッドロックとは？

デッドロックの意味

複数のトランザクションが互いに相手の保持するロックの解放を待ち、どれも先に進めなくなる状態。

デッドロックの具体例

T1が表Aをロックして表Bを待ち、T2が表Bをロックして表Aを待つ。

デッドロックは試験でどう引っ掛けられる？

検出は待ちグラフに閉路があるかで判定する。閉路に含まれるトランザクションだけでなく、そこへ向かって待っているトランザクションも永久に待たされる点に注意。予防策としてはロック獲得順序を全トランザクションでそろえるのが有効。

デッドロックと関連する用語

• 待ちグラフ
• 2相ロッキングプロトコル

デッドロックが出た過去問

• DBMSにおいて、トランザクション間でデッドロックが発生していることを検出するために使用するものはどれか。

  正解：待ちグラフ

  要点：待ちグラフの閉路でデッドロックを検出する

  待ちグラフは、トランザクションをノード、ロック解放を待っている関係を有向辺として表したグラフである。このグラフに閉路が生じていれば互いに待ち合う状態、すなわちデッドロックが発生していると判定できる。

  出典：平成28年度 春期 データベーススペシャリスト試験 am2 問13（IPA）

• DBMSにおいて、デッドロックを検出するために使われるデータ構造はどれか。

  正解：待ちグラフ

  要点：待ちグラフの閉路がデッドロックの判定材料になる

  待ちグラフは、トランザクションをノード、あるトランザクションが別のトランザクションのロック解放を待っている関係を有向辺として表す。このグラフに閉路があれば互いに待ち合っている状態であり、デッドロックの発生と判定できる。

  出典：平成30年度 春期 データベーススペシャリスト試験 am2 問16（IPA）

• 複数のバッチ処理を並行して動かすとき、デッドロックの発生をできるだけ回避したい。バッチ処理の設計ガイドラインのうち、適切なものはどれか。

  正解：複数レコードを更新するときにロックを掛ける順番を決めておき、全てのバッチ処理がこれに従って処理するように設計する。

  要点：ロックの獲得順序をそろえれば循環待ちは生じない

  デッドロックは、複数の処理が資源を互いに逆の順序で確保しようとして待ち合うことで起こる。そこで更新対象にあらかじめ一定の順序を決め、すべての処理が同じ順序でロックを取るようにすれば、循環した待ちが生じなくなる。よってエが適切である。

  出典：令和4年度 秋期 データベーススペシャリスト試験 am2 問13（IPA）

• a〜cそれぞれの障害に対して、DBMSはロールフォワード又はロールバックを行い回復を図る。適切な回復手法の組合せはどれか。 a デッドロックによるトランザクショ…

  正解：a=ロールバック, b=ロールフォワード又はロールバック, c=ロールフォワード

  要点：トランザクション障害は戻し、媒体障害は進めて回復する

  デッドロックで打ち切られたトランザクションは、開始前の状態へ戻すロールバックで回復する。システム障害では、コミット済みのものはログから再現するロールフォワード、未完了のものはロールバックと使い分ける。媒体障害はバックアップを復元したうえで更新後ログを適用するロールフォワードで回復する。この組合せはイである。

  出典：令和5年度 秋期 データベーススペシャリスト試験 am2 問15（IPA）

• トランザクションA〜Gの待ちグラフにおいて、永久待ちの状態になっているトランザクション全てを列挙したものはどれか。ここで、待ちグラフのX→Yは、トランザクション…

  正解：B, C, D, F

  要点：永久待ちは待ちグラフの閉路とそこへ到達する待ち全部

  待ちグラフに閉路があると、その閉路上のトランザクションは互いのアンロックを待ち続けるためデッドロックとなる。さらに、閉路上のトランザクションを待っているトランザクションも、閉路が解消されない限り永久に待たされる。したがって永久待ちは閉路の構成メンバーと、そこへ到達する矢印を持つものの合計になる。閉路に含まれず一方向に待つだけのものは、いずれ解放されるので永久待ちではない。

  出典：令和6年度 秋期 データベーススペシャリスト試験 am2 問13（IPA）