デッドロックとは？

デッドロックの意味

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

デッドロックの具体例

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

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

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

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

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

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

• 並列に生起する事象間の同期を表現することが可能な、ソフトウェアの要求モデルはどれか。

  正解：ペトリネットモデル

  要点：ペトリネットは並行事象の同期を表現できるモデル

  ペトリネットは、プレース（状態）とトランジション（事象）、その間を移動するトークンでモデルを表す。一つのトランジションが複数の入力プレースにトークンが揃うまで発火しないという性質により、並行して進む複数の事象の合流や同期を自然に表現できる。デッドロックの検出など解析にも用いられる。

  出典：令和1年度 秋期 システムアーキテクト試験 am2 問2（IPA）

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

  正解：待ちグラフ

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

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

  出典：令和6年度 春期 システムアーキテクト試験 am2 問24（IPA）