デッドロック

読み：でっどろっく　／　英語表記：deadlock

サーバ・ストレージ

複数の処理が、互いの持つ資源の解放を待ち、どの処理も先へ進めなくなる状態。資源を取得する順序を統一することは、その発生を防ぐ方法である。

イマシルちゃんの解説

コンピュータの処理が使うファイルや装置などを、資源と呼ぶよ。
ほかの処理が使っている資源は、空くまで待つ場合があるんだ。
ある処理が資源Xを確保したままYを待っているとするね。
別の処理がYを確保したままXを待っていたら、どちらも相手が手放すのを待ち続けてしまうよ。
こうして処理同士が互いに必要な資源を待ち合って動けなくなる状態を、デッドロックというんだ。
防ぐには、どの処理もXからYの順に資源を取るようにする方法があるよ。
Xを取れなかった処理はYも取らずに待つので、お互いを待ち続ける状況を避けられるんだ。

より深い解説

成立する条件

資源にはロック、ファイル、装置などがある。単に実行が遅い状態と違い、待っている相手自身も待ちから抜け出せない。

条件	意味
相互排他	同時に資源を使える処理が一つに限られる
ホールドアンドウェイト	資源を保持したまま、別の資源を待つ
非横取り	他の処理から資源を強制的に取り上げられない
循環待ち	相手の解放を待つ関係が輪になる

これらの条件のうち、どれかが成立しないようにすれば発生を予防できる。処理の優先順位を変えても、必要な資源が解放されるとは限らない。

資源を取得する順序

すべての処理に対して「資源Xを先に取り、その後でYを取る」と定める。Xを取れない処理は、Yを保持しないまま待つため、互いに一つずつ持って待つ状況を避けられる。資源が増えても、全体で矛盾しない大小関係に従って取得する。

順序を処理ごとに逆にすると、かえって問題を起こすことがある。資源の解放忘れは別の不具合なので、例外が発生した場合も後始末が必要である。

対処方法の違い

方法	考え方
予防	成立条件を崩す設計にする
回避	資源を渡した後も安全に完了できるかを事前に判定する
検出と回復	待ち関係を調べ、発生後に処理の中止などで解消する
タイムアウト	長すぎる待ちを打ち切る。ただし発生そのものの証明ではない

回復のために処理を打ち切る場合は、途中の変更を取り消して整合性を保つ必要がある。再試行を同時に繰り返すと衝突が続くため、再試行間隔にも配慮する。

待ち続ける現象との区別

他の処理だけが優先され、ある処理が実行機会を得られないのは飢餓状態である。各処理が動いてはいるが、互いに譲り続けて有用な仕事が進まないのはライブロックである。何を待ち、誰がそれを解消できるかを追って区別する。

実際の試験ではここに出る！全1問

テクニカルエンジニア（ネットワーク）

午前

H20秋問3