次のコードは、テスト用に作成されています。このテストでは、読者は、コードを開始してから 1 秒以内にコードがデッドロックに入る理由を説明するよう求められます。
このコードのデッドロックの原因を正確に説明できる人はいますか?
public class Test {
static class FailerThread implements Runnable {
final Object[] objects;
final Random random;
final int number;
public FailerThread(final Object[] objects, final int number) {
this.objects = objects;
this.random = new Random();
this.number = number;
}
@Override
public void run() {
final boolean isWriter = number % 2 == 0;
int index = random.nextInt(objects.length);
try {
while (Thread.interrupted() == false) {
synchronized (objects) {
if (isWriter) {
while (objects[index] == null) {
System.out.println(number + ": Index " + index + " is null, waiting...");
objects.wait();
}
for (int copyIndex = 0; copyIndex < objects.length; ++copyIndex) {
if (objects[copyIndex] == null) {
objects[copyIndex] = this.objects[index];
}
}
objects.notifyAll();
} else {
objects[index] = null;
}
}
++index;
if (index >= objects.length) {
index = 0;
}
}
} catch (InterruptedException e) {
}
}
}
public static void main(String[] args) throws InterruptedException {
final Object[] objects = new Object[10];
for (int i = 0; i < objects.length; ++i) {
objects[i] = new Object();
}
final int NUM_THREADS = 32;
final ExecutorService executor = Executors.newFixedThreadPool(NUM_THREADS);
for (int i = 0; i < NUM_THREADS; ++i) {
executor.execute(new FailerThread(objects, i));
}
}
}
編集：このテストに対する公式の回答（チューダーが書いたものに似ていますが、より詳細です）
上記の構成では、ある時点ですべての「ライター」が null を待機するため、デッドロックが発生しますが、これらのライターはそれらを解放できる唯一のライターであるため、無期限にハングします。ただし、より重要な質問は次のとおりです。なぜですか？
一見すると、コードはこれらのライターが優勢であるように見えます。各ループでは、単一のスレッド (ライターまたは nuller) が選択されて配列で処理されますが、nuller は 1 つの null のみを書き込みますが、ライターは配列内のすべての null を削除します。したがって、デッドロックが発生する可能性は非常に低いと考えられます (ただし、驚くべきことに、コードは 1 秒以内にデッドロックします)。しかし、よく見ると、スレッドを扱っているため、この仮定は誤りであることがわかります。
十分な実行時間が与えられた場合、マルチスレッド アプリケーションで問題になるのは、コードのどの部分を実際にブロックできるかということです。ライター/ヌラーで起こりうる最悪のシナリオを見てみましょう。
nuller は、最悪の場合、何の影響もなく実行できます。つまり、すでに null である配列内の位置に null を書き込みます。
ライターは、最悪の場合、無期限にブロックする可能性があります。
さらに、同期ブロックの開始時に、(多かれ少なかれ) ランダムな候補が選択されて入力されます。最初は、これはライターと nuller の両方で 50% ですが、ブロックされた各ライターについては、nuller の方向に有利になります。書き込みが成功するとすべての null が除去されますが、nuller の可能性は常に 50% 以上になります。したがって、スレッド化された観点からは、システム全体が同期ブロックの候補としてヌラーを優先するように設計されているため、実際にはヌラーが支配的な部分です。
さらに、これが重要な部分ですが、スレッドの実行順序は定義されていません。どのスレッドが代替の実行を許可されているかというのは素朴な印象ですが、そうではありません。同期されたブロックには設定がなく、どのスレッドがアクセスを取得するかは定義されていません (完全にランダムであると言えますが、ランダムは関係ありません)。したがって、16 個のスレッドすべてが同期を待機している場合、20 回の実行内でスレッドが完全に交互に実行される可能性は、20 個のライターまたは 20 個のヌラーが連続して呼び出される可能性とまったく同じです。しかし、nuller が支配的であるため (20 個のライターが何もしない)、20 個の nuller を続けて呼び出すと、配列全体が null に設定されることがほぼ保証され、その後のライターは無期限にブロックされます。
コードにログ出力を追加して、実際に選択されているスレッドを確認すると、通常は最初の 200 ループ内で、10 個以上のヌラーが連続して呼び出されていることがすぐにわかります。その直後、システムがハングします。
この質問をした理由
私は現在、熟練した Java プログラマー向けの評価用のテスト セットを開発しており、すべてのコードを記述して、最終的にテストする必要があります。良いニュース: 成功しました。;)
StackOverflow の不適切な使用について文句を言う前に、こちらを Q&A としてご覧ください。そして、マルチスレッド アーキテクチャを実際に実装するために、この例から学ぶべきことがたくさんあります。これは専門家レベルの質問であるため、予想どおり、多くの人が回答できず、理解することさえできませんでした。ただし、専門家レベルの質問の良い点は、専門家レベルの回答から多くを学ぶことができることです。そのため、完全に詳細な回答を含めました。
候補者の評価方法
この質問は評価テストには難しすぎると考える人がいると予想し、テスターの視点を与えるために、候補者は次のように評価されます。
はい、問題は難しすぎます。テスト中に誰も正しい答えを見つけることは期待されていません。問題は、問題にどのように取り組むかです。プログラマーは毎日、これまでに解決したことのないタスクに遭遇し、すぐに解決する方法がわからないため、このビジネスでは問題解決の優れたスキルを持っていることが重要です。誰もすべてを知ることはできませんが、誰もが学ぶことができます。
一般に、4 つの可能な結果があります。
候補者は答えを知らず、そう言う。これは、受験者がストレスの多いテスト状況でそれを認める強さを持っているため、初心者に適したレベルです。良い生徒は耳を傾ける生徒であり、したがって教えられる生徒です。
候補者は答えを知っていますが、「悪い」質問を非難するか（別名反対票）、間違った答えを思いつき、それを猛烈に擁護します。これは基本的に最悪の候補者です。彼は初級/中級レベルですが、自分は専門家であると考えているため、学習を拒否し、このレベルで行き詰まるでしょう。チーム内では、この候補者はチームの昇進を妨害するか (彼が「専門家」であると彼らが信じている場合)、すぐに厄介者になります。
候補者は (多かれ少なかれ正しい) 答えを思いつき、それを見つけるために系統的なアプローチを使用します。これは、中級/エキスパート レベルの優れた候補です。彼/彼女は困難な課題に対して整然としたアプローチを開発しており、答えによってはさらに前進することが期待できます。
候補者は系統的なアプローチを使用して、正しい答えを導き出します。これは可能な限り最良の結果ですが、おそらく 100 万分の 1 にすぎません。
最初の nuller は、ライターによって中断されることなく (ポスターの言うこととは逆に) 行内のいくつかの値をリセットし、次に writer は配列を上書きし、次に nuller はすべての配列をリセットします (一度にいくつかの要素)。問題。