Wie ist das Fork / Join-Framework besser als ein Thread-Pool?

134

Was sind die Vorteile der Verwendung des neuen Fork / Join-Frameworks, wenn Sie die große Aufgabe zu Beginn einfach in N Unteraufgaben aufteilen, sie an einen zwischengespeicherten Thread-Pool (von Executors ) senden und auf den Abschluss jeder Aufgabe warten? Ich verstehe nicht, wie die Verwendung der Fork / Join-Abstraktion das Problem vereinfacht oder die Lösung effizienter macht als seit Jahren.

Der parallelisierte Unschärfealgorithmus im Tutorial-Beispiel könnte beispielsweise folgendermaßen implementiert werden:

public class Blur implements Runnable {
    private int[] mSource;
    private int mStart;
    private int mLength;
    private int[] mDestination;

    private int mBlurWidth = 15; // Processing window size, should be odd.

    public ForkBlur(int[] src, int start, int length, int[] dst) {
        mSource = src;
        mStart = start;
        mLength = length;
        mDestination = dst;
    }

    public void run() {
        computeDirectly();
    }

    protected void computeDirectly() {
        // As in the example, omitted for brevity
    }
}

Am Anfang teilen und Aufgaben an einen Thread-Pool senden:

// source image pixels are in src
// destination image pixels are in dst
// threadPool is a (cached) thread pool

int maxSize = 100000; // analogous to F-J's "sThreshold"
List<Future> futures = new ArrayList<Future>();

// Send stuff to thread pool:
for (int i = 0; i < src.length; i+= maxSize) {
    int size = Math.min(maxSize, src.length - i);
    ForkBlur task = new ForkBlur(src, i, size, dst);
    Future f = threadPool.submit(task);
    futures.add(f);
}

// Wait for all sent tasks to complete:
for (Future future : futures) {
    future.get();
}

// Done!

Die Aufgaben werden in die Warteschlange des Thread-Pools gestellt, aus der sie ausgeführt werden, sobald Arbeitsthreads verfügbar werden. Solange die Aufteilung detailliert genug ist (um nicht besonders auf die letzte Aufgabe warten zu müssen) und der Thread-Pool über genügend (mindestens N Prozessoren) Threads verfügt, arbeiten alle Prozessoren mit voller Geschwindigkeit, bis die gesamte Berechnung abgeschlossen ist.

Vermisse ich etwas Was ist der Mehrwert der Verwendung des Fork / Join-Frameworks?

Joonas Pulakka
quelle

Antworten:

136

Ich denke, das grundlegende Missverständnis ist, dass die Fork / Join-Beispiele NICHT das Stehlen von Arbeit zeigen , sondern nur eine Art Standard-Teilen und Erobern.

Das Stehlen von Arbeit wäre wie folgt: Arbeiter B hat seine Arbeit beendet. Er ist nett, also schaut er sich um und sieht, dass Arbeiter A immer noch sehr hart arbeitet. Er geht hinüber und fragt: "Hey Junge, ich könnte dir helfen." A antwortet. "Cool, ich habe diese Aufgabe von 1000 Einheiten. Bis jetzt habe ich 345 beendet und 655 verlassen. Könnten Sie bitte an den Nummern 673 bis 1000 arbeiten, ich mache die 346 bis 672." B sagt "OK, lass uns anfangen, damit wir früher in die Kneipe gehen können."

Sie sehen, die Arbeiter müssen miteinander kommunizieren, selbst wenn sie mit der eigentlichen Arbeit begonnen haben. Dies ist der fehlende Teil in den Beispielen.

Die Beispiele zeigen dagegen nur so etwas wie "Subunternehmer einsetzen":

Arbeiter A: "Verdammt, ich habe 1000 Arbeitseinheiten. Zu viel für mich. Ich werde 500 selbst machen und 500 an jemand anderen vergeben." Dies geht so lange weiter, bis die große Aufgabe in kleine Pakete von jeweils 10 Einheiten zerlegt ist. Diese werden von den verfügbaren Arbeitern ausgeführt. Aber wenn ein Paket eine Art Giftpille ist und erheblich länger dauert als andere Pakete - Pech - ist die Teilungsphase vorbei.

Der einzige verbleibende Unterschied zwischen Fork / Join und dem Aufteilen der Aufgabe im Voraus besteht darin, dass beim Aufteilen im Voraus die Arbeitswarteschlange von Anfang an voll ist. Beispiel: 1000 Einheiten, der Schwellenwert ist 10, die Warteschlange enthält also 100 Einträge. Diese Pakete werden an die Threadpool-Mitglieder verteilt.

Fork / Join ist komplexer und versucht, die Anzahl der Pakete in der Warteschlange kleiner zu halten:

  • Schritt 1: Stellen Sie ein Paket mit (1 ... 1000) in die Warteschlange
  • Schritt 2: Ein Mitarbeiter öffnet das Paket (1 ... 1000) und ersetzt es durch zwei Pakete: (1 ... 500) und (501 ... 1000).
  • Schritt 3: Ein Arbeiter knallt das Paket (500 ... 1000) und drückt (500 ... 750) und (751 ... 1000).
  • Schritt n: Der Stapel enthält die folgenden Pakete: (1..500), (500 ... 750), (750 ... 875) ... (991..1000)
  • Schritt n + 1: Paket (991..1000) wird gepoppt und ausgeführt
  • Schritt n + 2: Paket (981..990) wird gepoppt und ausgeführt
  • Schritt n + 3: Das Paket (961..980) wird gepoppt und in (961 ... 970) und (971..980) aufgeteilt. ....

Sie sehen: In Fork / Join ist die Warteschlange kleiner (im Beispiel 6) und die Phasen "Teilen" und "Arbeiten" sind verschachtelt.

Wenn mehrere Arbeiter gleichzeitig knallen und pushen, sind die Interaktionen natürlich nicht so klar.

AH
quelle
Ich denke, das ist in der Tat die Antwort. Ich frage mich, ob es irgendwo tatsächliche Fork / Join-Beispiele gibt, die auch die Fähigkeit zeigen, Arbeit zu stehlen. Mit einfachen Beispielen ist der Arbeitsaufwand anhand der Größe des Geräts (z. B. der Array-Länge) ziemlich perfekt vorhersehbar, sodass die Aufteilung im Voraus einfach ist. Das Stehlen würde sicherlich einen Unterschied bei Problemen bewirken, bei denen die Arbeitsbelastung pro Einheit anhand der Größe der Einheit nicht gut vorhersehbar ist.
Joonas Pulakka
AH Wenn Ihre Antwort richtig ist, erklärt sie nicht, wie. Das von Oracle gegebene Beispiel führt nicht zum Diebstahl von Arbeit. Wie würde Fork and Join funktionieren, wie in dem Beispiel, das Sie hier beschreiben? Könnten Sie Java-Code anzeigen, mit dem Fork und Join Steal so funktionieren, wie Sie es beschreiben? danke
Marc
@Marc: Es tut mir leid, aber ich habe kein Beispiel zur Verfügung.
AH
6
Das Problem mit dem Beispiel von Oracle, IMO, ist nicht, dass es keinen Arbeitsdiebstahl demonstriert (wie von AH beschrieben), sondern dass es einfach ist, einen Algorithmus für einen einfachen ThreadPool zu codieren, der dies auch tut (wie Joonas). FJ ist am nützlichsten, wenn die Arbeit nicht in genügend unabhängige Aufgaben vorab aufgeteilt werden kann, sondern rekursiv in Aufgaben aufgeteilt werden kann, die untereinander unabhängig sind. Siehe meine Antwort für ein Beispiel
Ashirley
2
Einige Beispiele, wo sich das Stehlen von Arbeit als nützlich erweisen
Volley
27

Wenn Sie n ausgelastete Threads haben, die alle zu 100% unabhängig voneinander arbeiten, ist dies besser als n Threads in einem Fork-Join (FJ) -Pool. Aber so funktioniert es nie.

Möglicherweise kann das Problem nicht genau in n gleiche Teile aufgeteilt werden. Selbst wenn Sie dies tun, ist die Thread-Planung weit davon entfernt, fair zu sein. Sie werden am Ende auf den langsamsten Thread warten. Wenn Sie mehrere Aufgaben haben, können diese jeweils mit weniger als n-Wege-Parallelität (im Allgemeinen effizienter) ausgeführt werden. Wenn andere Aufgaben abgeschlossen sind, können Sie jedoch auf n-Wege gehen.

Warum schneiden wir das Problem nicht einfach in Stücke in FJ-Größe und lassen einen Thread-Pool daran arbeiten. Die typische Verwendung von FJ schneidet das Problem in winzige Stücke. Um dies in zufälliger Reihenfolge zu tun, ist auf Hardwareebene viel Koordination erforderlich. Die Gemeinkosten wären ein Killer. In FJ werden Aufgaben in eine Warteschlange gestellt, die der Thread in der Reihenfolge Last In First Out (LIFO / Stack) abliest, und das Stehlen von Arbeiten (in der Kernarbeit im Allgemeinen) erfolgt First In First Out (FIFO / "Warteschlange"). Das Ergebnis ist, dass die Verarbeitung langer Arrays weitgehend sequentiell erfolgen kann, obwohl sie in winzige Teile aufgeteilt ist. (Es ist auch der Fall, dass es möglicherweise nicht trivial ist, das Problem in kleinen, gleich großen Stücken in einem großen Knall aufzuteilen. Sagen wir, Sie müssen sich mit einer Form von Hierarchie befassen, ohne zu balancieren.)

Schlussfolgerung: FJ ermöglicht eine effizientere Verwendung von Hardware-Threads in ungleichmäßigen Situationen. Dies ist immer dann der Fall, wenn Sie mehr als einen Thread haben.

Tom Hawtin - Tackline
quelle
Aber warum sollte FJ nicht auch auf den langsamsten Thread warten? Es gibt eine vorbestimmte Anzahl von Unteraufgaben, und natürlich werden einige von ihnen immer die letzten sein, die erledigt werden. Das Anpassen des maxSizeParameters in meinem Beispiel würde eine fast ähnliche Teilaufgabenteilung erzeugen wie die "binäre Aufteilung" im FJ-Beispiel (erfolgt innerhalb der compute()Methode, die entweder etwas berechnet oder Unteraufgaben an sendet invokeAll()).
Joonas Pulakka
Weil sie viel kleiner sind, werde ich meine Antwort ergänzen.
Tom Hawtin - Tackline
Ok, wenn die Anzahl der Unteraufgaben um eine Größenordnung größer ist als das, was tatsächlich parallel verarbeitet werden kann (was sinnvoll ist, um nicht auf die letzte warten zu müssen), kann ich die Koordinationsprobleme erkennen. Das FJ-Beispiel kann irreführend sein, wenn die Unterteilung so detailliert sein soll: Es wird ein Schwellenwert von 100000 verwendet, der für ein 1000x1000-Bild 16 tatsächliche Unteraufgaben erzeugen würde, wobei jede 62500 Elemente verarbeitet. Für ein 10000x10000-Bild gäbe es 1024 Unteraufgaben, was bereits etwas ist.
Joonas Pulakka
19

Das ultimative Ziel von Thread-Pools und Fork / Join ist gleich: Beide möchten die verfügbare CPU-Leistung so gut wie möglich für einen maximalen Durchsatz nutzen. Maximaler Durchsatz bedeutet, dass so viele Aufgaben wie möglich in einem langen Zeitraum erledigt werden sollten. Was wird dazu benötigt? (Für das Folgende gehen wir davon aus, dass es nicht an Berechnungsaufgaben mangelt: Es gibt immer genug zu tun für eine 100% ige CPU-Auslastung. Zusätzlich verwende ich "CPU" äquivalent für Kerne oder virtuelle Kerne im Falle von Hyper-Threading).

  1. Zumindest müssen so viele Threads ausgeführt werden, wie CPUs verfügbar sind, da durch das Ausführen weniger Threads ein Kern nicht verwendet wird.
  2. Maximal müssen so viele Threads ausgeführt werden, wie CPUs verfügbar sind, da durch das Ausführen von mehr Threads eine zusätzliche Last für den Scheduler entsteht, der den verschiedenen Threads CPUs zuweist, wodurch einige CPU-Zeit für den Scheduler und nicht für unsere Rechenaufgabe benötigt wird.

Daher haben wir herausgefunden, dass wir für einen maximalen Durchsatz genau die gleiche Anzahl von Threads benötigen wie CPUs. Im verwischenden Beispiel von Oracle können Sie beide einen Thread-Pool mit fester Größe verwenden, wobei die Anzahl der Threads der Anzahl der verfügbaren CPUs entspricht, oder einen Thread-Pool verwenden. Es wird keinen Unterschied machen, Sie haben Recht!

Wann werden Sie Probleme mit einem Thread-Pool bekommen? Dies ist der Fall , wenn ein Thread blockiert , da Ihr Thread darauf wartet, dass eine andere Aufgabe abgeschlossen wird. Nehmen Sie das folgende Beispiel an:

class AbcAlgorithm implements Runnable {
    public void run() {
        Future<StepAResult> aFuture = threadPool.submit(new ATask());
        StepBResult bResult = stepB();
        StepAResult aResult = aFuture.get();
        stepC(aResult, bResult);
    }
}

Was wir hier sehen, ist ein Algorithmus, der aus drei Schritten A, B und C besteht. A und B können unabhängig voneinander ausgeführt werden, aber Schritt C benötigt das Ergebnis von Schritt A UND B. Dieser Algorithmus übergibt Aufgabe A an den Threadpool und führen Sie Aufgabe b direkt aus. Danach wartet der Thread, bis auch Aufgabe A erledigt ist, und fährt mit Schritt C fort. Wenn A und B gleichzeitig abgeschlossen sind, ist alles in Ordnung. Aber was ist, wenn A länger dauert als B? Dies kann daran liegen, dass die Art von Aufgabe A dies vorschreibt, aber es kann auch daran liegen, dass zu Beginn kein Thread für Aufgabe A verfügbar ist und Aufgabe A warten muss. (Wenn nur eine einzige CPU verfügbar ist und Ihr Threadpool daher nur einen einzigen Thread hat, führt dies sogar zu einem Deadlock, aber im Moment ist das nicht der Punkt). Der Punkt ist, dass der Thread, der gerade Aufgabe B ausgeführt hatblockiert den gesamten Thread . Da wir die gleiche Anzahl von Threads wie CPUs haben und ein Thread blockiert ist, bedeutet dies, dass eine CPU inaktiv ist .

Fork / Join löst dieses Problem: Im Fork / Join-Framework würden Sie denselben Algorithmus wie folgt schreiben:

class AbcAlgorithm implements Runnable {
    public void run() {
        ATask aTask = new ATask());
        aTask.fork();
        StepBResult bResult = stepB();
        StepAResult aResult = aTask.join();
        stepC(aResult, bResult);
    }
}

Sieht genauso aus, nicht wahr? Der Hinweis ist jedoch, dass aTask.join nicht blockieren wird . Stattdessen kommt hier das Stehlen von Arbeit ins Spiel: Der Thread wird sich nach anderen Aufgaben umsehen, die in der Vergangenheit gegabelt wurden, und mit diesen fortfahren. Zunächst wird geprüft, ob die von ihm gegabelten Aufgaben verarbeitet wurden. Wenn A noch nicht von einem anderen Thread gestartet wurde, führt es als nächstes A aus. Andernfalls wird die Warteschlange anderer Threads überprüft und deren Arbeit gestohlen. Sobald diese andere Aufgabe eines anderen Threads abgeschlossen ist, wird geprüft, ob A jetzt abgeschlossen ist. Wenn es der obige Algorithmus ist, kann er aufrufen stepC. Andernfalls wird nach einer weiteren Aufgabe gesucht, die gestohlen werden muss. Somit können Fork / Join-Pools eine 100% ige CPU-Auslastung erreichen, selbst angesichts blockierender Aktionen .

Es gibt jedoch eine Falle: Arbeitsdiebstahl ist nur für den joinAnruf von ForkJoinTasks möglich. Dies kann nicht für externe Blockierungsaktionen wie das Warten auf einen anderen Thread oder das Warten auf eine E / A-Aktion durchgeführt werden. Was ist damit? Das Warten auf den Abschluss der E / A ist eine häufige Aufgabe. In diesem Fall ist es am zweitbesten, wenn wir dem Fork / Join-Pool einen zusätzlichen Thread hinzufügen könnten, der nach Abschluss der Blockierungsaktion erneut gestoppt wird. Und das ForkJoinPoolkann genau das, wenn wir ManagedBlockers verwenden.

Fibonacci

In JavaDoc for RecursiveTask finden Sie ein Beispiel für die Berechnung von Fibonacci-Zahlen mit Fork / Join. Eine klassische rekursive Lösung finden Sie unter:

public static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

Wie in den JavaDocs erläutert, ist dies eine hübsche Dump-Methode zur Berechnung von Fibonacci-Zahlen, da dieser Algorithmus eine O (2 ^ n) -Komplexität aufweist und einfachere Methoden möglich sind. Dieser Algorithmus ist jedoch sehr einfach und leicht zu verstehen, daher bleiben wir dabei. Nehmen wir an, wir möchten dies mit Fork / Join beschleunigen. Eine naive Implementierung würde folgendermaßen aussehen:

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();
   }
}

Die Schritte, in die diese Aufgabe unterteilt ist, sind viel zu kurz und daher wird dies eine schreckliche Leistung bringen. Sie können jedoch sehen, wie das Framework im Allgemeinen sehr gut funktioniert: Die beiden Summanden können unabhängig voneinander berechnet werden, aber dann benötigen wir beide, um das Finale zu erstellen Ergebnis. Eine Hälfte wird also in einem anderen Thread gemacht. Viel Spaß mit Thread-Pools, ohne einen Deadlock zu bekommen (möglich, aber bei weitem nicht so einfach).

Der Vollständigkeit halber: Wenn Sie Fibonacci-Zahlen tatsächlich mit diesem rekursiven Ansatz berechnen möchten, finden Sie hier eine optimierte Version:

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);
        }
    }
}

Dadurch bleiben die Unteraufgaben viel kleiner, da sie nur dann aufgeteilt werden, wenn n > 10 && getSurplusQueuedTaskCount() < 2dies der Fall ist. Dies bedeutet, dass deutlich mehr als 100 Methodenaufrufe zu erledigen sind ( n > 10) und nicht sehr viele Aufgaben bereits warten ( getSurplusQueuedTaskCount() < 2).

Auf meinem Computer (4 Core (8 beim Zählen von Hyper-Threading), Intel (R) Core (TM) i7-2720QM-CPU bei 2,20 GHz) fib(50)dauert dies beim klassischen Ansatz 64 Sekunden und beim Fork / Join-Ansatz nur 18 Sekunden ist ein beachtlicher Gewinn, wenn auch nicht so viel wie theoretisch möglich.

Zusammenfassung

  • Ja, in Ihrem Beispiel hat Fork / Join keinen Vorteil gegenüber klassischen Thread-Pools.
  • Fork / Join kann die Leistung beim Blockieren drastisch verbessern
  • Fork / Join umgeht einige Deadlock-Probleme
Yankee
quelle
17

Fork / Join unterscheidet sich von einem Thread-Pool, da es das Stehlen von Arbeit implementiert. Von Fork / Join

Wie bei jedem ExecutorService verteilt das Fork / Join-Framework Aufgaben an Arbeitsthreads in einem Thread-Pool. Das Fork / Join-Framework unterscheidet sich dadurch, dass es einen Work-Stealing-Algorithmus verwendet. Arbeitsthreads, denen die Aufgaben ausgehen, können Aufgaben von anderen Threads stehlen, die noch beschäftigt sind.

Angenommen, Sie haben zwei Threads und 4 Aufgaben a, b, c, d, die jeweils 1, 1, 5 und 6 Sekunden dauern. Zu Beginn werden a und b Thread 1 und c und d Thread 2 zugewiesen. In einem Thread-Pool würde dies 11 Sekunden dauern. Mit Fork / Join wird Thread 1 beendet und kann Arbeit von Thread 2 stehlen, sodass Aufgabe d von Thread 1 ausgeführt wird. Thread 1 führt a, b und d, Thread 2 nur c aus. Gesamtzeit: 8 Sekunden, nicht 11.

BEARBEITEN: Wie Joonas betont, sind Aufgaben nicht unbedingt einem Thread vorab zugewiesen. Die Idee von Fork / Join ist, dass ein Thread eine Aufgabe in mehrere Unterteile aufteilen kann. Um das oben Gesagte noch einmal zu wiederholen:

Wir haben zwei Aufgaben (ab) und (cd), die 2 bzw. 11 Sekunden dauern. Thread 1 beginnt mit der Ausführung von ab und teilt es in zwei Unteraufgaben a & b auf. Ähnlich teilt sich Thread 2 in zwei Unteraufgaben c & d auf. Wenn Thread 1 a & b beendet hat, kann er d von Thread 2 stehlen.

Matthew Farwell
quelle
5
Thread-Pools sind normalerweise ThreadPoolExecutor- Instanzen. In solchen Fällen werden Aufgaben in eine Warteschlange gestellt ( BlockingQueue in der Praxis), aus der die Arbeitsthreads Aufgaben übernehmen, sobald sie ihre vorherige Aufgabe abgeschlossen haben. Soweit ich weiß, sind Aufgaben bestimmten Threads nicht vorab zugewiesen. Jeder Thread hat (höchstens) 1 Aufgabe gleichzeitig.
Joonas Pulakka
4
AFAIK gibt es eine Warteschlange für einen ThreadPoolExecutor, der wiederum mehrere Threads steuert . Dies bedeutet, dass beim Zuweisen von Aufgaben oder ausführbaren Dateien (nicht Threads!) Zu einem Executor die Aufgaben auch keinem bestimmten Thread vorab zugewiesen werden. Genau so macht es FJ auch. Bisher kein Vorteil für die Verwendung von FJ.
AH
1
@AH Ja, aber mit Fork / Join können Sie die aktuelle Aufgabe aufteilen. Der Thread, der die Aufgabe ausführt, kann sie in zwei verschiedene Aufgaben aufteilen. Mit dem ThreadPoolExecutor haben Sie also eine feste Liste von Aufgaben. Mit fork / join kann die ausführende Aufgabe ihre eigene Aufgabe in zwei Teile aufteilen, die dann von anderen Threads übernommen werden können, wenn sie ihre Arbeit beendet haben. Oder Sie, wenn Sie zuerst fertig sind.
Matthew Farwell
1
@Matthew Farwell: Im FJ-Beispiel wird compute()die Aufgabe innerhalb jeder Aufgabe entweder berechnet oder in zwei Unteraufgaben aufgeteilt. Welche Option ausgewählt wird, hängt nur von der Größe der Aufgabe ab ( if (mLength < sThreshold)...). Es ist also nur eine ausgefallene Möglichkeit, eine feste Anzahl von Aufgaben zu erstellen. Für ein 1000x1000-Bild gibt es genau 16 Unteraufgaben, die tatsächlich etwas berechnen. Zusätzlich gibt es 15 (= 16 - 1) "Zwischen" -Aufgaben, die nur Unteraufgaben generieren und aufrufen und selbst nichts berechnen.
Joonas Pulakka
2
@ Matthew Farwell: Es ist möglich, dass ich nicht alle FJ verstehe, aber wenn eine Unteraufgabe beschlossen hat, ihre computeDirectly()Methode auszuführen , gibt es keine Möglichkeit mehr, etwas zu stehlen. Die gesamte Aufteilung erfolgt a priori , zumindest im Beispiel.
Joonas Pulakka
14

Alle oben genannten haben Recht, die Vorteile werden durch das Stehlen von Arbeit erzielt, aber um zu erläutern, warum dies so ist.

Der Hauptvorteil ist die effiziente Koordination zwischen den Arbeitsthreads. Die Arbeit muss aufgeteilt und wieder zusammengesetzt werden, was eine Koordinierung erfordert. Wie Sie in der obigen Antwort von AH sehen können, hat jeder Thread seine eigene Arbeitsliste. Eine wichtige Eigenschaft dieser Liste ist, dass sie sortiert ist (große Aufgaben oben und kleine Aufgaben unten). Jeder Thread führt die Aufgaben am Ende seiner Liste aus und stiehlt Aufgaben am Anfang anderer Thread-Listen.

Das Ergebnis ist:

  • Kopf und Ende der Aufgabenlisten können unabhängig voneinander synchronisiert werden, wodurch Konflikte auf der Liste reduziert werden.
  • Wichtige Teilbäume der Arbeit werden von demselben Thread aufgeteilt und wieder zusammengesetzt, sodass für diese Teilbäume keine Koordination zwischen den Threads erforderlich ist.
  • Wenn ein Faden Arbeit stiehlt, nimmt er ein großes Stück, das er dann in seine eigene Liste unterteilt
  • Durch die Arbeitsstahlung sind die Gewinde bis zum Ende des Prozesses nahezu voll ausgelastet.

Die meisten anderen Divide- und Conquer-Schemata, die Thread-Pools verwenden, erfordern mehr Kommunikation und Koordination zwischen den Threads.

iain
quelle
13

In diesem Beispiel fügt Fork / Join keinen Wert hinzu, da kein Forking erforderlich ist und die Arbeitslast gleichmäßig auf die Arbeitsthreads verteilt ist. Fork / Join erhöht nur den Overhead.

Hier ist ein schöner Artikel zu diesem Thema. Zitat:

Insgesamt können wir sagen, dass der ThreadPoolExecutor vorzuziehen ist, wenn die Arbeitslast gleichmäßig auf die Arbeitsthreads verteilt ist. Um dies garantieren zu können, müssen Sie genau wissen, wie die Eingabedaten aussehen. Im Gegensatz dazu bietet der ForkJoinPool unabhängig von den Eingabedaten eine gute Leistung und ist somit eine wesentlich robustere Lösung.

Volley
quelle
8

Ein weiterer wichtiger Unterschied scheint zu sein, dass Sie mit FJ mehrere komplexe "Join" -Phasen durchführen können. Betrachten Sie die Zusammenführungssortierung von http://faculty.ycp.edu/~dhovemey/spring2011/cs365/lecture/lecture18.html . Es wäre zu viel Orchestrierung erforderlich, um diese Arbeit vorab aufzuteilen. zB müssen Sie folgende Dinge tun:

  • sortiere das erste Quartal
  • sortiere das zweite Quartal
  • die ersten 2 Quartale zusammenführen
  • sortiere das dritte Quartal
  • sortiere das vierte Viertel
  • die letzten 2 Quartale zusammenführen
  • füge die 2 Hälften zusammen

Wie legen Sie fest, dass Sie die Sortierungen vor den Zusammenführungen vornehmen müssen, die sie betreffen usw.

Ich habe mir überlegt, wie man für jede Liste von Elementen am besten eine bestimmte Sache macht. Ich denke, ich werde die Liste einfach vorab teilen und einen Standard-ThreadPool verwenden. FJ scheint am nützlichsten zu sein, wenn die Arbeit nicht in genügend unabhängige Aufgaben vorab aufgeteilt werden kann, sondern rekursiv in Aufgaben aufgeteilt werden kann, die untereinander unabhängig sind (z. B. das Sortieren der Hälften ist unabhängig, das Zusammenführen der beiden sortierten Hälften zu einem sortierten Ganzen jedoch nicht).

Ashirley
quelle
6

F / J hat auch einen deutlichen Vorteil, wenn Sie teure Zusammenführungsvorgänge haben. Da es sich in eine Baumstruktur aufteilt, führen Sie nur log2 (n) -Zusammenführungen durch, im Gegensatz zu n-Zusammenführungen mit linearer Thread-Aufteilung. (Dies setzt die theoretische Annahme voraus, dass Sie so viele Prozessoren wie Threads haben, aber dennoch einen Vorteil.) Für eine Hausaufgabe mussten wir mehrere tausend 2D-Arrays (alle die gleichen Dimensionen) zusammenführen, indem wir die Werte an jedem Index summierten. Bei Fork Join- und P-Prozessoren nähert sich die Zeit log2 (n), wenn sich P der Unendlichkeit nähert.

1 2 3 .. 7 3 1 .... 8 5 4
4 5 6 + 2 4 3 => 6 9 9
7 8 9 .. 1 1 0 .... 8 9 9

Daemon Fisher
quelle
3

Sie werden von der Leistung von ForkJoin in Anwendungen wie Crawlern begeistert sein. Hier ist das beste Tutorial, aus dem Sie lernen würden.

Die Logik von Fork / Join ist sehr einfach: (1) Trennen Sie jede große Aufgabe in kleinere Aufgaben; (2) jede Aufgabe in einem separaten Thread verarbeiten (diese bei Bedarf in noch kleinere Aufgaben aufteilen); (3) die Ergebnisse verbinden.

Daniel Adenew
quelle
3

Wenn das Problem so ist, dass wir warten müssen, bis andere Threads abgeschlossen sind (wie beim Sortieren des Arrays oder der Summe des Arrays), sollte der Fork-Join verwendet werden, da Executor (Executors.newFixedThreadPool (2)) aufgrund von Einschränkungen erstickt Anzahl der Themen. Der Forkjoin-Pool erstellt in diesem Fall mehr Threads, um den blockierten Thread zu vertuschen und die gleiche Parallelität beizubehalten

Quelle: http://www.oracle.com/technetwork/articles/java/fork-join-422606.html

Das Problem mit den Ausführenden beim Implementieren von Divide- und Conquer-Algorithmen hängt nicht mit dem Erstellen von Unteraufgaben zusammen, da ein Callable eine neue Unteraufgabe an seinen Ausführenden senden und synchron oder asynchron auf das Ergebnis warten kann. Das Problem ist das der Parallelität: Wenn ein Callable auf das Ergebnis eines anderen Callable wartet, wird es in einen Wartezustand versetzt, wodurch die Gelegenheit verpasst wird, einen anderen Callable zu verarbeiten, der zur Ausführung in die Warteschlange gestellt wird.

Das Fork / Join-Framework, das durch die Bemühungen von Doug Lea zum Paket java.util.concurrent in Java SE 7 hinzugefügt wurde, schließt diese Lücke

Quelle: https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ForkJoinPool.html

Der Pool versucht, genügend aktive (oder verfügbare) Threads aufrechtzuerhalten, indem interne Worker-Threads dynamisch hinzugefügt, angehalten oder fortgesetzt werden, selbst wenn einige Aufgaben blockiert sind und darauf warten, anderen beizutreten. Bei blockierten E / A-Vorgängen oder anderen nicht verwalteten Synchronisierungen sind solche Anpassungen jedoch nicht garantiert

public int getPoolSize () Gibt die Anzahl der Arbeitsthreads zurück, die gestartet, aber noch nicht beendet wurden. Das von dieser Methode zurückgegebene Ergebnis kann von getParallelism () abweichen, wenn Threads erstellt werden, um die Parallelität aufrechtzuerhalten, wenn andere kooperativ blockiert werden.

VS
quelle
2

Ich möchte eine kurze Antwort für diejenigen hinzufügen, die nicht viel Zeit haben, lange Antworten zu lesen. Der Vergleich stammt aus dem Buch Applied Akka Patterns:

Ihre Entscheidung, ob Sie einen Fork-Join-Executor oder einen Thread-Pool-Executor verwenden, hängt weitgehend davon ab, ob die Vorgänge in diesem Dispatcher blockiert werden. Ein Fork-Join-Executor gibt Ihnen eine maximale Anzahl aktiver Threads, während ein Thread-Pool-Executor Ihnen eine feste Anzahl von Threads gibt. Wenn Threads blockiert sind, erstellt ein Fork-Join-Executor mehr, ein Thread-Pool-Executor hingegen nicht. Für Blockierungsvorgänge sind Sie im Allgemeinen mit einem Thread-Pool-Executor besser dran, da er verhindert, dass Ihre Thread-Zählungen explodieren. Mehr "reaktive" Operationen sind in einem Fork-Join-Executor besser.

Vadim S.
quelle