6

Brian Goetzは、fork-joinに関する素晴らしい記事をhttp://www.ibm.com/developerworks/java/library/j-jtp03048.htmlに書いています。その中で、彼はフォークジョインメカニズムを使用したマージソートアルゴリズムをリストしています。このアルゴリズムでは、配列の両側で並列にソートを実行し、結果をマージします。

アルゴリズムは、同じ配列の2つの異なるセクションで同時にソートします。可視性を維持するためにAtomicIntegerArrayまたはその他のメカニズムが必要ないのはなぜですか？一方のスレッドがもう一方のスレッドによって行われた書き込みを確認するという保証はありますか、それともこれは微妙なバグですか？フォローアップとして、ScalaのForkJoinSchedulerもこの保証をしますか？

ありがとう！

4

2 に答える 2

8

（ForkJoinの）結合自体には、最も重要な情報である同期ポイントが必要です。同期ポイントは、発生するすべての書き込みがそのポイントの後に表示されることを保証します。

コードを見ると、同期ポイントが発生する場所がわかります。これは、invokeAllを呼び出す1つのメソッドです。

public static void invokeAll(ForkJoinTask<?> t1, ForkJoinTask<?> t2) {
    t2.fork();
    t1.invoke();
    t2.join();
}

ここで、t2は別のプロセスに分岐し、t1はそのタスクを実行し、その呼び出しスレッドはt2.join（）を待機します。t2を通過するとき。これで、t1とt2へのすべての書き込みが表示されます。

編集：この編集は、同期ポイントの意味をもう少し説明するためのものです。

2つの変数があるとしましょう

int x;
volatile int y;

yに書き込むときはいつでも、yを読み取る前に発生したすべての書き込みが使用可能になります。例えば

public void doWork(){
   x = 10;
   y = 5;
}

別のスレッドがy=5を読み取る場合、そのスレッドはx = 10を読み取ることが保証されます。これは、yへの書き込みによって同期ポイントが作成され、そのポイントの前のすべての書き込みが書き込み後に表示されるためです。

Fork Joinプールを使用すると、ForkJoinTaskの結合によって同期ポイントが作成されます。ここで、t2.fork（）とt1.invoke（）の場合、t2を結合すると、以前に発生したすべての書き込みが確実に表示されます。以前のすべての書き込みは同じ構造内にあるため、可視性に対して安全です。

それが明確でない場合は、さらに説明させていただきます。

于 2011-01-26T01:34:27.820 に答える
1

推測：マージにはスレッドでの結合が含まれ、結合は可視性を保証します。

2番目の部分は確かです。マージがどのように実装されているのかわかりません。

于 2011-01-26T01:12:16.147 に答える