デッドロック（OSレベル）とは？

デッドロック（OSレベル）の意味

複数のプロセスが、互いに相手が確保している資源（メモリ、ファイル、周辺機器など）の解放を待ち続け、どちらも処理を進められなくなる状態。「相互排除」「保持と待機」「非割込み」「循環待ち」の4条件がすべて揃うと発生する。

デッドロック（OSレベル）の具体例

プロセスAがプリンタを確保しつつスキャナの解放を待ち、プロセスBがスキャナを確保しつつプリンタの解放を待つと、互いに永遠に待ち続けるデッドロックが発生する。

デッドロック（OSレベル）は試験でどう引っ掛けられる？

4条件は「すべて揃ったとき」に発生するので、対策は1つでも崩せばよい（資源の要求順序を統一すれば循環待ちが崩れる）。「4条件のどれか1つで発生する」は誤り。またデッドロックは互いに待ち合って永久に進まない状態であり、優先度の低いプロセスが順番を回されず処理されないスタベーション（飢餓状態）とは別物。スタベーションは待っている相手がいなくても起こる。

デッドロック（OSレベル）と関連する用語

• プロセス管理とスケジューリング
• デッドロックの検出と回避

デッドロック（OSレベル）が出た過去問

• トランザクションA（処理A1→処理A2の順に実行する）とトランザクションB（処理B1→処理B2の順に実行する）が，データベースの資源SとTに対し，次のように処理…

  正解：A1=S, B1=T, A2=T, B2=S

  要点：互いに相手の保持資源を要求し合うとデッドロックになる

  デッドロックは、互いが相手の保持する資源を待ち合うときに発生する。AがSを、BがTを先に確保し、次にAがT、BがSを要求する組合せでは、両者が相手の解放を待ち続けて処理が進まなくなる。

  出典：平成28年度 春期 応用情報技術者試験 午前 問28（IPA）

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

  正解：⑥

  要点：デッドロックは互いに相手のロック解放を待ち合った時点で成立する

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

  出典：平成29年度 春期 応用情報技術者試験 午前 問29（IPA）

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

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

  要点：資源の獲得順序を全タスクで統一すればデッドロックは防げる

  デッドロックは、複数のタスクが資源を互いに違う順序で確保し、相手が持つ資源を待ち合う状態になることで生じる。すべてのタスクが資源を同じ順序で獲得するよう決めておけば、循環した待ち関係が作れなくなるためデッドロックは発生しない。

  出典：令和1年度 春期 応用情報技術者試験 午前 問18（IPA）

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

  正解：C, D

  要点：資源の占有順序が逆になる組合せでデッドロックが起こる

  デッドロックは、2つのプロセスが資源を互いに逆順で要求したときに発生し得る。Aの占有順はX→Y→Zで、Bも同じ順なので待ち合わせが循環せず安全である。CはZ→X→Y、DはZ→Y→XとZを先に取るため、AがX（とY）を持ちCまたはDがZを持った状態で相互に待つ可能性がある。

  出典：令和2年度 10月 応用情報技術者試験 午前 問17（IPA）

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

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

  要点：資源の獲得順序を統一すればデッドロックを防げる

  デッドロックは、複数のタスクが資源を互いに保持したまま相手の資源を待つ循環待ちで起きます。全タスクで資源を獲得する順序をあらかじめ一本化しておけば循環が生じないため、デッドロックを予防できます。

  出典：令和4年度 秋期 応用情報技術者試験 午前 問16（IPA）