デッドロック

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

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

イマシルちゃんの解説

工作で、きみはハサミ、友達はのりを持っているとするね。
きみはのりが来るまでハサミを返さず、友達もハサミが来るまでのりを返さない。
このままでは、どちらの工作も終わらないよね。
道具を借りる決まりを、みんなでそろえておくと防げるんだ。

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

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

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

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

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

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

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