モダンオペレーティングシステム 第2版 -第3章- - 技術書で学んだことをひたすらアウトプットするページ

デッドロック

リソースの種類

横取り可能なリソース

デッドロックを引き起こさないリソース。
（例）メモリ

横取り不可能なリソース

デッドロックを引き起こす可能性があるリソース。
（例）プリンタ

デッドロック発生条件

デッドロックが発生するのは、以下の4つが同時に起こる時である。

• 各リソースが1つのプロセスに与えられている
• リソースを持つプロセスが新たなリソースを要求する
• プロセスが他のプロセスの持つリソースを横取りできない状態にある
• プロセスに循環鎖がある

デッドロックの回避法

無視

「現実逃避アルゴリズム」のことで、デッドロックへの対応は行わない。
デッドロック自体が数ヶ月〜数年に1度しか起こらない場合、デッドロック防止のための開発に時間を使うよりも、デッドロックが生じた時の対処の時間に費やした方が得であると考えられる。

検出してから回復を試みる

各リソースタイプに1つのみリソースがある場合と、各リソースタイプに複数のリソースがある場合で、検出に対して異なるアプローチを取る。
前者では、プロセスがリソースを所持している場合にリソースからプロセスへ向かう矢印、プロセスがリソースを要求している場合はプロセスからリソースへ向かう矢印としてリソースグラフを作成し、循環を含んでいた場合にデッドロックと判断する。
後者の場合は、リソースベクトル・リソース割当行列・リソース要求行列・利用可能なリソースベクトルを用いることで、デッドロックの判断を行う。

デッドロックから回復する方法には、以下の3通りが存在する。

横取り
他のプロセスからリソースを横取りする。ただし、リソースの種類によっては不可能。

ロールバック
一定時間ごとにプロセスの状態を保存し、デッドロックが生じた時に保存しておいた、リソース割り当て前の状態に戻す。

プロセス消滅
プロセスをkillし、デッドロック解消後に再起動を行う。デッドロック前の実行結果が、再起動後の実行に影響を与えないプロセス（○コンパイル、×データベース操作）でなければならない。

注意深くリソースを割り当てる

システムには、全てのプロセスの完了が保証できる「安全状態」と、保証できない「非安全状態」に分けられる。

リソースが割り当てた後に「安全状態」になることを、リソース割り当て時に確認する。
また同じリソースを要求してきた時は、後に必要としているリソースが少ないものに割り当てを行う。
これは、バンカーのアルゴリズムと呼ばれる。
ただし、バンカーのアルゴリズムでは以下の点から、実装できないとされている。

• ユーザ（プロセス）数は逐次変わる
• プロセスが要求するリソースは前もって推測できない
• リソースは変化することがある（例:ディスク故障）

デッドロック発生条件の1つが起きないようなOS設計にする

デッドロック発生条件と、条件が成立しないための設計に関して以下に示す。

各リソースが1つのプロセスに与えられている
[条件を不成立にする方法] 全てのリソースをスプール化する
[問題点] ディスク等、スプール化できないものもある

リソースを持つプロセスが新たなリソースを要求する
[条件を不成立にする方法] プロセスが必要とするリソースを全て最初に割り当てる
[問題点] バンカーのアルゴリズムと同様、プロセスが必要なリソースを前もって知ることはできない

プロセスが他のプロセスの持つリソースを横取りできない状態にある
[条件を不成立にする方法] 他のプロセスからリソースを横取りできるようにする
[問題点] 実装が困難で、リソースによっては横取りができないものもある（例:プリンタ）

プロセスの循環鎖がある
[条件を不成立にする方法] リソースに番号付けを行い、プロセスが小さい番号から大きい番号に向かってのみ、リソースを割り当てられるようにする
[問題点] 各リソースは利用目的が異なるため、番号の付け方（順序付け）が難しい

2相ロッキング

デッドロックを回避する方法の1つで、2段階の判定を経てリソースの割り当てを行う。
第1段階では、プロセスが必要とするリソースにチェックをつけるだけで、リソースの取得を行わない。
第2段階では、リソースの取得が行える状態であれば、リソースの取得を行う。そうでなければ、第1段階へ戻る。
しかしこの方法は、全リソースを前もって取得することと似ているため、実現は困難である。

mutex・セマフォ

デッドロックはリソースの競合時だけでなく、セマフォやmutexの誤操作でも起こることがあるので注意が必要である。

飢餓状態

優先度が低いプロセスに対して優先度が高いプロセスがいると、優先度が低いプロセスはいつまでたっても実行することができない。（これを「飢餓状態」という。）
これは、FCFS (First Come, First Served) を採用すれば回避できる。