スレッド プールと Fork/Join の最終的な目標は似ています。つまり、どちらも利用可能な CPU パワーを最大限に活用して、最大のスループットを実現したいと考えています。最大スループットとは、できるだけ多くのタスクを長期間で完了する必要があることを意味します。そのためには何が必要ですか？(以下では、計算タスクが不足していないと仮定します: 100% の CPU 使用率を達成するには、常に十分な計算タスクがあります。さらに、ハイパースレッディングの場合は、コアまたは仮想コアに「CPU」を同等に使用します)。
- 少なくとも、使用可能な CPU と同じ数のスレッドを実行する必要があります。これは、実行するスレッドが少なくなるとコアが未使用のままになるためです。
- 最大で、使用可能な CPU と同じ数のスレッドを実行する必要があります。より多くのスレッドを実行すると、別のスレッドに CPU を割り当てるスケジューラに追加の負荷が発生し、一部の CPU 時間が計算タスクではなくスケジューラに費やされるためです。
したがって、スループットを最大にするには、CPU とまったく同じ数のスレッドが必要であることがわかりました。Oracle のぼかしの例では、使用可能な CPU の数と同じ数のスレッドを持つ固定サイズのスレッド プールを使用するか、スレッド プールを使用することができます。違いはありません、あなたは正しいです！
では、いつスレッド プールで問題が発生するのでしょうか? これは、スレッドが別のタスクの完了を待っているため、スレッドがブロックされた場合です。次の例を想定します。
class AbcAlgorithm implements Runnable {
public void run() {
Future<StepAResult> aFuture = threadPool.submit(new ATask());
StepBResult bResult = stepB();
StepAResult aResult = aFuture.get();
stepC(aResult, bResult);
}
}
ここに表示されているのは、3 つのステップ A、B、C で構成されるアルゴリズムです。A と B は互いに独立して実行できますが、ステップ C にはステップ A と B の結果が必要です。このアルゴリズムが行うことは、タスク A をサブミットすることです。スレッドプールを開き、タスク b を直接実行します。その後、スレッドはタスク A も完了するのを待ち、ステップ C に進みます。A と B が同時に完了した場合、すべて問題ありません。しかし、A が B よりも時間がかかる場合はどうなるでしょうか。これは、タスク A の性質が原因である可能性がありますが、最初に使用可能なタスク A のスレッドがなく、タスク A が待機する必要があるためです。(使用可能な CPU が 1 つしかなく、スレッドプールにスレッドが 1 つしかない場合、デッドロックが発生することさえありますが、今のところそれは重要ではありません)。ポイントは、タスク B を実行したばかりのスレッドがスレッド全体をブロックします。CPU と同じ数のスレッドがあり、1 つのスレッドがブロックされているため、1 つの CPU がアイドル状態であることを意味します。
Fork/Join はこの問題を解決します: fork/join フレームワークでは、同じアルゴリズムを次のように記述します。
class AbcAlgorithm implements Runnable {
public void run() {
ATask aTask = new ATask());
aTask.fork();
StepBResult bResult = stepB();
StepAResult aResult = aTask.join();
stepC(aResult, bResult);
}
}
同じに見えますよね？ただし、手がかりは、それaTask.join がブロックされないことです。代わりに、ここでワークスティーリングの出番です。スレッドは、過去にフォークされた他のタスクを探して、それらを続行します。最初に、それ自体が fork したタスクが処理を開始したかどうかを確認します。したがって、A が別のスレッドによってまだ開始されていない場合は、次に A を実行します。それ以外の場合は、他のスレッドのキューをチェックして、それらの作業を盗みます。別のスレッドのこの他のタスクが完了すると、A が現在完了しているかどうかがチェックされます。上記のアルゴリズムである場合は、 を呼び出すことができますstepC。それ以外の場合は、スチールする別のタスクを探します。したがって、ブロック アクションに直面しても、プールの fork/join は 100% の CPU 使用率を達成できます。
ただし、落とし穴があります。ワークスティーリングは s のjoin呼び出しでのみ可能ですForkJoinTask。別のスレッドの待機や I/O アクションの待機などの外部ブロッキング アクションに対しては実行できません。では、I/O の完了を待つのは一般的なタスクでしょうか? この場合、Fork/Join プールに追加のスレッドを追加できれば、ブロック アクションが完了するとすぐに再び停止することが 2 番目に良い方法です。s を使用している場合、ForkJoinPoolは実際にそれを行うことができますManagedBlocker。
フィボナッチ
RecursiveTaskのJavaDoc には、Fork/Join を使用してフィボナッチ数を計算する例があります。従来の再帰的なソリューションについては、次を参照してください。
public static int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
JavaDocs で説明されているように、これはフィボナッチ数を計算するためのかなりダンプ的な方法です。このアルゴリズムは O(2^n) の複雑さを持ちますが、より単純な方法が可能です。しかし、このアルゴリズムは非常にシンプルで理解しやすいので、私たちはそれを使い続けています。Fork/Join でこれをスピードアップしたいとしましょう。単純な実装は次のようになります。
class Fibonacci extends RecursiveTask<Long> {
private final long n;
Fibonacci(long n) {
this.n = n;
}
public Long compute() {
if (n <= 1) {
return n;
}
Fibonacci f1 = new Fibonacci(n - 1);
f1.fork();
Fibonacci f2 = new Fibonacci(n - 2);
return f2.compute() + f1.join();
}
}
このタスクが分割されたステップは短すぎるため、これは恐ろしく実行されますが、フレームワークが一般的にどのようにうまく機能するかを見ることができます:結果。したがって、半分は別のスレッドで行われます。デッドロックを起こさずにスレッドプールで同じことを楽しんでください (可能ですが、それほど単純ではありません)。
完全を期すために：この再帰的アプローチを使用してフィボナッチ数を実際に計算したい場合は、最適化されたバージョンを次に示します。
class FibonacciBigSubtasks extends RecursiveTask<Long> {
private final long n;
FibonacciBigSubtasks(long n) {
this.n = n;
}
public Long compute() {
return fib(n);
}
private long fib(long n) {
if (n <= 1) {
return 1;
}
if (n > 10 && getSurplusQueuedTaskCount() < 2) {
final FibonacciBigSubtasks f1 = new FibonacciBigSubtasks(n - 1);
final FibonacciBigSubtasks f2 = new FibonacciBigSubtasks(n - 2);
f1.fork();
return f2.compute() + f1.join();
} else {
return fib(n - 1) + fib(n - 2);
}
}
}
が true の場合にのみサブタスクが分割されるため、これによりサブタスクが大幅に小さく保たれn > 10 && getSurplusQueuedTaskCount() < 2ます。つまり、100 をはるかに超える do へのメソッド呼び出しがあり ( n > 10)、すでに待機しているマン タスクはそれほど多くありません ( getSurplusQueuedTaskCount() < 2)。
私のコンピューター (4 コア (ハイパースレッディングを数える場合は 8)、Intel(R) Core(TM) i7-2720QM CPU @ 2.20GHz) ではfib(50)、従来のアプローチで 64 秒、Fork/Join アプローチでわずか 18 秒かかります。理論的に可能な限りではありませんが、かなり顕著なゲインです。
概要
- はい、あなたの例では、フォーク/ジョインには従来のスレッドプールよりも利点がありません。
- Fork/Join は、ブロッキングが関係している場合にパフォーマンスを大幅に向上させることができます
- フォーク/ジョインはデッドロックの問題を回避します