デッドロックとは？

デッドロックの意味

複数のタスクが互いに相手の占有する資源の解放を待ち合い、いずれも先へ進めなくなる状態。相互排除・保持と待ち・横取り不可・循環待ちの4条件がそろうと発生する。

デッドロックの具体例

タスクAが資源1を確保して資源2を待ち、タスクBが資源2を確保して資源1を待つと循環待ちが成立する。すべてのタスクで資源の獲得順序を統一すれば、循環待ちが起きないため予防できる。

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

資源を要求する順序が「逆」になっているタスクの組合せを探すのが定石。同じ順序で要求するタスク同士ではデッドロックは起きない。

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

• タスク管理
• 排他制御

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

• トランザクションAとBが，共通の資源であるテーブルaとbを表に示すように更新するとき，デッドロックとなるのはどの時点か。ここで，表中の①〜⑧は処理の実行順序を示…

  正解：⑥

  要点：デッドロックは互いの資源を待つ循環待ちが成立した時点で発生

  Aは③でテーブルaを、Bは④でテーブルbをロックする。⑤でAがテーブルbを更新しようとするがBが保持しているため待たされ、続く⑥でBがテーブルaを更新しようとするとAが保持しているため待たされる。互いに相手のロック解放を待つ状態が成立するのは⑥の時点である。

  出典：平成29年度 春期 高度共通_午前I試験 am1 問8（IPA）

• 二つのタスクが共用する二つの資源を排他的に使用するとき、デッドロックが発生するおそれがある。このデッドロックの発生を防ぐ方法はどれか。

  正解：資源獲得の順序を両方のタスクで同じにする。

  要点：資源の獲得順序を全タスクで統一すれば循環待ちが起きない

  デッドロックは、複数のタスクが資源を互いに保持したまま相手の資源を待つ循環待ちが生じたときに起こる。全てのタスクが同じ順序で資源を獲得するように決めておけば、この循環待ちが構造的に発生しなくなる。資源に順序番号を付けて昇順にしか獲得させない方法が代表的な対策である。

  出典：令和1年度 春期 高度共通_午前I試験 am1 問6（IPA）

• 二つのタスクが共用する二つの資源を排他的に使用するとき、デッドロックが発生するおそれがある。このデッドロックの発生を防ぐ方法はどれか。

  正解：資源獲得の順序を両方のタスクで同じにする。

  要点：資源獲得の順序を統一すれば循環待ちが起きない

  デッドロックは、複数のタスクが資源を互いに待ち合う循環待ちが生じたときに発生する。資源を獲得する順序をすべてのタスクで統一しておけば、待ちの関係が一方向にそろって循環が生まれないので、デッドロックを防止できる。

  出典：令和4年度 秋期 高度共通_午前I試験 am1 問6（IPA）

• 三つの資源X〜Zを占有して処理を行う四つのプロセスA〜Dがある。各プロセスは処理の進行に伴い、表中の数値の順に資源を占有し、実行終了時に三つの資源を一括して解放…

  正解：C, D

  要点：資源の占有順序が逆のプロセス同士でデッドロックが起こる

  デッドロックは、2つのプロセスが資源を互いに逆順で確保しようとしたときに起こりうる。AはX→Y→Zの順に占有する。BもX→Y→Zと同じ順なので待ち合わせが循環せず安全である。CはZ→X→Y、DはZ→Y→XとAとは逆向きに資源を取るため、AがXを、C（またはD）がZを保持した状態で互いに相手の資源を待ち、デッドロックとなりうる。

  出典：令和6年度 春期 高度共通_午前I試験 am1 問6（IPA）