TL;DR
- デッドロックへの対処には、何もしない、検出する、回避する、防ぐの 4 つがある。
- 検出には Resource Allocation Graph の循環検出、回避には銀行家のアルゴリズム、防止にはロックの順序をそろえる方法がある。
内容
1. 何もしない
何もしない方法をオーストリッチアルゴリズムと呼ぶ。デッドロックがめったに起きず、起きても影響が小さいと確実に分かっている場合にだけ有効である。
2. デッドロックを検出する
Go にはデッドロックを検出する機能が組み込まれている。ただし、ランタイムがすべてのゴルーチンが待機していると判断した場合にしか検出せず、そのときは panic を起こす。
デッドロックを完全に検出するには、Resource Allocation Graph をプログラムで作り、グラフの循環を見つける。循環の検出には、深さ優先探索を応用した方法がある。走査中に訪れたノードを記録し、訪問済みのノードに再び出会ったら循環していると判断する。この方法は、他のフレームワークやランタイム、MySQL などのデータベースシステムで採用されている。Go がこの方法を採らない理由はGo のランタイムはなぜ完全なデッドロック検出を提供していないかにまとめた。
デッドロックを検出した後の処理には 2 つある。1 つは、動けなくなった実行を終了することである。Go はこちらを採る。もう 1 つは、リソースを要求している実行にエラーを返すことである。実行はエラーを受けて、リソースを解放したり、一定時間後に再試行したりといった後処理ができる。多くの RDBMS はこちらを採り、デッドロックのエラーが起きたらトランザクションをロールバックして再試行する。
3. デッドロックを回避する
実行をうまくスケジューリングすれば、デッドロックは回避できる。その方法の 1 つが銀行家のアルゴリズム（Banker’s algorithm）である。
このアルゴリズムは、リソースの要求を許可するかどうかを決めるときに実行される。システムが「安全」な状態を保てる場合にだけ要求を許可する。「安全でない」状態に移る場合は、要求を許可できるようになるまで実行を一時停止する。ここでの「安全」とは、各実行がリソースを最大数まで要求しても、すべての実行が完了するようにスケジューリングできることを指す。判断には、各実行が要求できるリソースの最大数、各実行が保持しているリソース、各リソースの利用可能数を使う。
固定数のセッションを持つデータベースのコネクションプールで考える。ある状態では、空いている 3 つのリソースをすべて実行 b に割り当て、b が完了して解放したリソースを実行 c に回す、というように、すべての実行を完了させるスケジューリングが存在する。この状態は安全である。一方、空きが 2 つしかなく、実行 a、b、c がそれぞれさらに 5、3、5 のリソースを要求しうる状態は安全でない。
ただし、OS やランタイムは各プロセスやスレッドが要求するリソースの最大数を事前に知ることができないので、OS や言語のランタイムでは銀行家のアルゴリズムは使えない。たとえば、プログラムが実行中にスレッドを作ったとき、そのスレッドがどんなリソースを使うかは実行するまで分からない。また、このアルゴリズムは実行の数が固定されている前提で設計されているが、実際の OS ではプロセスやスレッドが頻繁に生成・終了する。
各ゴルーチンがどのリソースを必要とするか分かっている場合は、処理を簡単にできる。たとえば送金システムでは、あるゴルーチンが送金元と送金先の口座をロックしようとしたとき、どちらかの口座を他のゴルーチンが使っていれば一時停止させる。これは条件変数で実現できる。
4. デッドロックを防ぐ
ロックの順序をすべての実行でそろえれば、デッドロックは起きない（Effective Rust 項目17 も参照）。
排他的なリソースが事前に分かっている場合は、UUID の順にロックをかけるなどの方法がある。分かっていない場合は、いま保持しているリソースより前の順序のリソースを獲得しないようにする。前の順序のリソースが必要になったら、保持しているリソースをいったん解放してから要求し直す。
キーワード
- デッドロック
- オーストリッチアルゴリズム
- Resource Allocation Graph
- 銀行家のアルゴリズム
- 条件変数
- ゴルーチン