Javaはデッドロックを避ける動力ノードJava学院の整理
場合によってはデッドロックは避けられます。本論文では、デッドロックを回避するための3つの技術を示す。
1.ロックをかける順番
2.ロック時間制限
3.デッドロック検査
ロック順
複数のスレッドは同じロックが必要ですが、順番にロックをかけるとデッドロックが発生しやすくなります。
すべてのスレッドが同じ順番でロックされていることを確認できれば、デッドロックは発生しません。この例を見てください。
例えば、スレッド2とスレッド3は、ロックAを取得した後にのみ、ロックCの取得を試みることができる（ロックAを取得するために必要な条件）。スレッド1は既にロックAを持っているので、スレッド2と3はロックAがリリースされるまで待つ必要があります。その後、BまたはCにロックをかけることを試みる前に、Aにロックを成功的にかけなければなりません。
順番にロックをかけるのは有効なデッドロック予防の仕組みです。しかし、このような方法は事前に知っておく必要があります。
ロックをかける
もう一つのデッドロックを回避する方法は、ロックを取得しようとするときにタイムアウト時間を加えることであり、これは、ロックを取得しようとする過程で、このタイムアウトを超えたら、このロック要求を放棄することを意味する。スレッドが所与のタイムアウト内で必要なすべてのロックを成功裏に獲得していない場合は、リターンを行い、取得したすべてのロックを解放し、ランダムな時間を待って再試行します。このランダムな待ち時間は他のスレッドに同じ鍵を取得しようと試みる機会が与えられ、このアプリケーションはロックを獲得していない時に継続して実行することができます（ロックをかけてタイムアウトしたら先にドライポイントを実行して、後でロックをかけるロジック）。
以下は一例であり、2つのスレッドが異なる順序で同じ2つのロックを取得しようと試み、タイムアウトが発生した後にキャンセルして再試行するシーンを示している。
注意したいのは、ロックのタイムアウトがあるため、このようなシーンが必ずロックされているとは思えません。ロックされたスレッドが得られたため（他のスレッドがタイムアウトした場合）、そのタスクを完了するのに時間がかかります。
また、非常に多くのスレッドが同じ時間に同じリソースを競合している場合、タイムアウトやリターバック機構があっても、これらのスレッドが繰り返し試行される可能性がありますが、いつまでもロックがかかりません。この現象は2つのスレッドだけであり、再試行のタイムアウト時間が0から500ミリ秒の間に設定されている場合には発生しないかもしれないが、10個または20個のスレッドの場合は異なる。これらのスレッドは等しい再試行時間を待つ確率が高いからです。タイムアウトと再試行のメカニズムは、同じ時間での競争を避けるためですが、スレッドが多い場合は、2つ以上のスレッドのタイムアウト時間が同じか近い可能性が高いため、競合してタイムアウトしても、タイムアウト時間が同じであるため、新しいラウンドの競争が始まり、新しい問題が発生します。）
このような機構には、Javaでは、synchronized同期ブロックにタイムアウト時間を設定できないという問題があります。カスタムロックを作成するか、またはJava 5のjava.util.co ncurrentで包んだツールを使用する必要があります。カスタムロックを書くのは複雑ではないですが、本文の内容を超えています。
デッドロック検出
デッドロック検査は、より良いデッドロック予防メカニズムであり、主に、それらの実装が不可能であり、ロックがタイムアウトしても実行できないシーンに対応しています。
スレッドがロックされるたびに、スレッドとロックに関するデータ構造（map、graphなど）にメモします。この他に、スレッド要求ロックがあるたびに、このデータ構造に記録する必要がある。
スレッドがロック要求に失敗した時、このスレッドは巡回してロックが発生しているかどうか確認することができます。例えば、スレッドAはロック7を要求していますが、ロック7はこのときスレッドBによって保持されています。このときスレッドAはスレッドBが現在持っているロックを要求しているかどうかを確認することができます。スレッドBにこのような要求があると、デッドロックが発生します。スレッドBは、ロック7を有し、ロック1を要求する。
もちろん、デッドロックは通常、2つのスレッドが互いに相手のロックを持つ場合より複雑です。スレッドAはスレッドBを待ち、スレッドBはスレッドCを待ち、スレッドCはスレッドDを待ち、スレッドDはスレッドAを待っている。スレッドAはデッドロックを検出するために、Bによって要求されたすべてのロックを再進的に検出する必要がある。スレッドBから要求されたロックが開始され、スレッドAはスレッドCを発見し、またスレッドDを発見し、スレッドD要求のロックはスレッドA自身が保有していることが判明した。これはロックが発生したことを知っています。
これらのスレッドは、デッドロックが検出されたときに何をするべきですか？
実行可能な方法は、ロックを解除し、キャンセルし、ランダムな時間を待ってからやり直します。これは簡単なロックのタイムアウトと似ています。違いますが、ロックの要求がタイムアウトしたのではなく、ロックが発生しているだけです。キャンセルと待ちがありますが、大量のスレッドが競合して同じロックを繰り返す場合があります。
より良い方法は、これらのスレッドに優先順位を設定して、スレッドを一つ（またはいくつか）戻すことで、残りのスレッドは生死ロックが発生していないかのようにそれらの必要なロックを維持し続けることである。これらのスレッドに優先度が一定であれば、同じスレッドは常により高い優先度を持つ。この問題を避けるためには、デッドロックが発生したときにランダム優先度を設定することができます。
1.ロックをかける順番
2.ロック時間制限
3.デッドロック検査
ロック順
複数のスレッドは同じロックが必要ですが、順番にロックをかけるとデッドロックが発生しやすくなります。
すべてのスレッドが同じ順番でロックされていることを確認できれば、デッドロックは発生しません。この例を見てください。
Thread 1:
lock A
lock B
Thread 2:
wait for A
lock C (when A locked)
Thread 3:
wait for A
wait for B
wait for C例えば、スレッド2とスレッド3は、ロックAを取得した後にのみ、ロックCの取得を試みることができる（ロックAを取得するために必要な条件）。スレッド1は既にロックAを持っているので、スレッド2と3はロックAがリリースされるまで待つ必要があります。その後、BまたはCにロックをかけることを試みる前に、Aにロックを成功的にかけなければなりません。
順番にロックをかけるのは有効なデッドロック予防の仕組みです。しかし、このような方法は事前に知っておく必要があります。
ロックをかける
もう一つのデッドロックを回避する方法は、ロックを取得しようとするときにタイムアウト時間を加えることであり、これは、ロックを取得しようとする過程で、このタイムアウトを超えたら、このロック要求を放棄することを意味する。スレッドが所与のタイムアウト内で必要なすべてのロックを成功裏に獲得していない場合は、リターンを行い、取得したすべてのロックを解放し、ランダムな時間を待って再試行します。このランダムな待ち時間は他のスレッドに同じ鍵を取得しようと試みる機会が与えられ、このアプリケーションはロックを獲得していない時に継続して実行することができます（ロックをかけてタイムアウトしたら先にドライポイントを実行して、後でロックをかけるロジック）。
以下は一例であり、2つのスレッドが異なる順序で同じ2つのロックを取得しようと試み、タイムアウトが発生した後にキャンセルして再試行するシーンを示している。
Thread 1 locks A
Thread 2 locks B
Thread 1 attempts to lock B but is blocked
Thread 2 attempts to lock A but is blocked
Thread 1's lock attempt on B times out
Thread 1 backs up and releases A as well
Thread 1 waits randomly (e.g. 257 millis) before retrying.
Thread 2's lock attempt on A times out
Thread 2 backs up and releases B as well
Thread 2 waits randomly (e.g. 43 millis) before retrying.注意したいのは、ロックのタイムアウトがあるため、このようなシーンが必ずロックされているとは思えません。ロックされたスレッドが得られたため（他のスレッドがタイムアウトした場合）、そのタスクを完了するのに時間がかかります。
また、非常に多くのスレッドが同じ時間に同じリソースを競合している場合、タイムアウトやリターバック機構があっても、これらのスレッドが繰り返し試行される可能性がありますが、いつまでもロックがかかりません。この現象は2つのスレッドだけであり、再試行のタイムアウト時間が0から500ミリ秒の間に設定されている場合には発生しないかもしれないが、10個または20個のスレッドの場合は異なる。これらのスレッドは等しい再試行時間を待つ確率が高いからです。タイムアウトと再試行のメカニズムは、同じ時間での競争を避けるためですが、スレッドが多い場合は、2つ以上のスレッドのタイムアウト時間が同じか近い可能性が高いため、競合してタイムアウトしても、タイムアウト時間が同じであるため、新しいラウンドの競争が始まり、新しい問題が発生します。）
このような機構には、Javaでは、synchronized同期ブロックにタイムアウト時間を設定できないという問題があります。カスタムロックを作成するか、またはJava 5のjava.util.co ncurrentで包んだツールを使用する必要があります。カスタムロックを書くのは複雑ではないですが、本文の内容を超えています。
デッドロック検出
デッドロック検査は、より良いデッドロック予防メカニズムであり、主に、それらの実装が不可能であり、ロックがタイムアウトしても実行できないシーンに対応しています。
スレッドがロックされるたびに、スレッドとロックに関するデータ構造（map、graphなど）にメモします。この他に、スレッド要求ロックがあるたびに、このデータ構造に記録する必要がある。
スレッドがロック要求に失敗した時、このスレッドは巡回してロックが発生しているかどうか確認することができます。例えば、スレッドAはロック7を要求していますが、ロック7はこのときスレッドBによって保持されています。このときスレッドAはスレッドBが現在持っているロックを要求しているかどうかを確認することができます。スレッドBにこのような要求があると、デッドロックが発生します。スレッドBは、ロック7を有し、ロック1を要求する。
もちろん、デッドロックは通常、2つのスレッドが互いに相手のロックを持つ場合より複雑です。スレッドAはスレッドBを待ち、スレッドBはスレッドCを待ち、スレッドCはスレッドDを待ち、スレッドDはスレッドAを待っている。スレッドAはデッドロックを検出するために、Bによって要求されたすべてのロックを再進的に検出する必要がある。スレッドBから要求されたロックが開始され、スレッドAはスレッドCを発見し、またスレッドDを発見し、スレッドD要求のロックはスレッドA自身が保有していることが判明した。これはロックが発生したことを知っています。
これらのスレッドは、デッドロックが検出されたときに何をするべきですか？
実行可能な方法は、ロックを解除し、キャンセルし、ランダムな時間を待ってからやり直します。これは簡単なロックのタイムアウトと似ています。違いますが、ロックの要求がタイムアウトしたのではなく、ロックが発生しているだけです。キャンセルと待ちがありますが、大量のスレッドが競合して同じロックを繰り返す場合があります。
より良い方法は、これらのスレッドに優先順位を設定して、スレッドを一つ（またはいくつか）戻すことで、残りのスレッドは生死ロックが発生していないかのようにそれらの必要なロックを維持し続けることである。これらのスレッドに優先度が一定であれば、同じスレッドは常により高い優先度を持つ。この問題を避けるためには、デッドロックが発生したときにランダム優先度を設定することができます。