Wesloo
すべてのトピックトピック

オペレーティングシステム

OS デッドロック 原因 対策と回避策

要点

デッドロックは、複数のプロセスが互いに資源を待ち続ける状態である。発生には4つの必要条件が同時に成立する必要があり、対策は防止、回避、検出と回復、無視に分かれる。

ポイント

  • 発生条件は相互排除、保持と待機、非横取り、循環待機の4つである。
  • 防止策は少なくとも1条件を成立させない設計である。
  • 回避策はBanker's Algorithmなどで安全状態を確認する。
  • 検出後はプロセス終了や資源横取りで回復する。

OS デッドロック 原因 対策を整理するには、デッドロックを資源待ちの循環として捉える必要がある。デッドロックとは、複数のプロセスが資源を握ったまま互いの資源を待ち、全体が停止する状態である。資源は有限であり、カテゴリごとに管理される。

デッドロックの4つの必要条件

デッドロックは、4つの必要条件がそろったときにだけ発生する。条件のいずれかが成立しなければ、デッドロックは起きない。

条件意味
相互排除資源を同時に1つのプロセスだけが使用できる。
保持と待機資源を保持したまま、別の資源を待つ。
非横取り保持中の資源をOSが強制的に奪えない。
循環待機待ち関係が輪になって閉じる。

食事する哲学者問題では、各哲学者がフォークを1本取ってもう1本を待つと、待ちが輪になる。

OS デッドロック 原因 対策の全体像

対策は大きく4つに分かれる。防止は条件を事前に破る。回避は安全状態を維持する。検出と回復は発生後に処理する。無視は稀な場合に再起動で済ませる。

手法目的特徴
防止条件を成立させない事前設計が必要
回避安全状態を維持要求ごとに判定
検出と回復発生後に解消自由な要求を許す
無視稀な障害を許容実装が単純

OSの基本的な役割は OS とは 仕組み:役割と起動の流れ で扱う。資源待ちの順序は CPU スケジューリング アルゴリズムの仕組み とも関係する。

防止策:条件を成立させない

防止策では、4条件のうち少なくとも1つを成立させないように設計する。相互排除を破るのは難しい場合がある。プリンタのように本質的に排他利用の資源では共有できない。

  • 保持と待機を破るには、必要な資源をまとめて要求する。ただし、後で使う資源まで早く確保することになり、占有期間が延びる。
  • 非横取りを破るには、要求が拒否されたときに保持中の資源を解放し、後で再取得できるようにする。資源の横取りを許す設計も含まれる。
  • 循環待機を破るには、資源に順序を付け、番号の小さい資源から大きい資源へ昇順で要求する。

資源管理の考え方は 仮想メモリ 仕組み:ページング方式の図解 にも関係する。

回避策:安全状態を保つ

回避策では、要求を許可する前にシステムが安全状態を保てるかを動的に判定する。安全状態とは、すべてのプロセスが終了できる順序がある状態である。安全でない状態が必ずしもデッドロックというわけではないが、危険は高まる。

Banker's Algorithmは、資源に複数インスタンスがある場合に使う。要求を仮に割り当て、すべてのプロセスが完了できるかを確かめ、安全なら許可する。Resource Allocation Graph Algorithmは、各資源が1インスタンスの場合に使う。グラフに循環がないかを確かめる。

要求をすぐ満たせないときは、資源が空くまで待つ。open()、malloc()、new()、request() といった呼び出しが例になる。

資源割当グラフに循環がなければ、その時点でデッドロックは起きていない。

検出と回復

検出策では、循環待機を定期的に調べる。資源割当グラフの循環検査が用いられる。発生後は、プロセス終了または資源横取りで回復する。

  • プロセス終了:デッドロックしたプロセスを1つまたは複数中止し、循環を断つ。
  • 資源横取り:一部のプロセスから資源を一時的に奪い、別のプロセスへ再配分する。

検出策は資源要求を制限しないため、要求を即座に満たしやすい。一方で、中止や横取りによる損失が課題になる。

防止も検出もしないと、デッドロック発生後に待機プロセスが増えるにつれて全体が徐々に遅くなる。重いリアルタイム処理による一般的な遅延と見分けにくい。

無視策と実務上の判断

無視策では、デッドロックが非常に稀にしか起きない場合に、発生しても再起動し、なかったことにする。Ostrich Algorithmと呼ばれる。WindowsとUNIXでは、この方式が採られる。

防止や検出には継続的なオーバーヘッドと性能低下が伴う。デッドロックが年に1回ほどしか起きないなら、発生時に再起動で済ませる方がよい場合がある。

関連概念:飢餓とライブロック

飢餓は資源を無期限に待つ状態である。ライブロックはプロセスが動き続けるが進展せず、デッドロックのように停止しているわけではない。

食事する哲学者問題は、共有フォークを使う古典的な同期の問題であり、各哲学者がフォークを1本取ってもう1本を待つとデッドロックになる。

よくある質問

デッドロックが発生する条件は何か。

相互排除、保持と待機、非横取り、循環待機の4条件が同時に成立することである。

防止策と回避策の違いは何か。

防止策は条件を事前に破り、回避策は要求ごとに安全状態を確認する。

Banker's Algorithmは何に使うか。

複数インスタンスの資源がある場合に、安全状態を維持するか判定するために使う。

検出後の回復方法は何か。

デッドロックしたプロセスを終了するか、資源を横取りして再配分する。

無視策とは何か。

デッドロックが稀な場合に、発生しても再起動してなかったことにする方法である。

関連ページ

  • デバイスドライバ 仕組み:OSとハードウェアの橋渡し

    デバイスドライバは、OSとハードウェアの間で命令と結果をやり取りするソフトウェアです。OSは機器の詳細を知らなくても、ドライバが翻訳役となって印刷や音声出力などを実行します。

  • RTOS 汎用OS 違い:リアルタイム性と特徴の比較

    RTOSは期限内の決定論的応答を優先し、汎用OSは柔軟性とスループットを優先する。両者はOSの基本原則を共有するが、設計優先順位と能力が大きく異なる。選択は、アプリケーションが厳密なタイミング制約を必要とするか、一般的な計算能力を必要とするかに依存する。

  • OS 起動プロセス 仕組み:電源からOS起動まで

    電源投入後、OSがメモリに読み込まれて使える状態になるまでの連鎖的な処理がOSの起動プロセスです。冷起動と暖起動ではハードウェア初期化の範囲が異なり、BIOS/UEFI、ブートローダー、カーネル、initが順に動作します。

  • 32 ビットと 64 ビットの違い os:メモリと互換性

    32ビットOSと64ビットOSの違いは、扱えるメモリ量とデータ幅にあります。32ビットは最大4GB前後、64ビットはそれを大きく超えるメモリを扱えます。選択時はCPU、OS、ソフト、ドライバの互換性を確認します。

  • cpu スケジューリング アルゴリズムの仕組み

    OSはCPUを1タスクずつしか実行できないため、ready queueにあるプロセスから次に実行するものを選ぶ。cpu スケジューリング アルゴリズムは、CPU利用率や待ち時間、応答時間などの指標をもとにこの選択を決める。プリエンプティブ方式とノンプリエンプティブ方式があり、FCFS、SJF、SRTF、Priority、Round Robinなどが用途に応じて使われる。

  • 仮想メモリ 仕組み:ページング方式の図解

    仮想メモリは、各プロセスに独立したアドレス空間を与え、物理メモリの容量を超える領域を安全に扱うためのOSの機能です。ページング方式では、アドレス空間を固定長のページに分け、必要なページだけを物理メモリへ載せます。

このページの作成方法

執筆の前に、下記の情報源でテーマを調査しました。その後、自動の品質チェックを通過しています。

このページの誤りを報告する