Leitfaden zum Stehlen von Arbeit in Java

1. Übersicht

In diesem Tutorial werden wir uns mit dem Konzept des Arbeitsdiebstahls in Java befassen .

2. Was ist Arbeitsdiebstahl?

In Java wurde Work Stealing eingeführt , um Konflikte in Multithread-Anwendungen zu reduzieren . Dies erfolgt mithilfe des Fork / Join-Frameworks.

2.1. Ansatz teilen und erobern

Im Fork / Join-Framework werden Probleme oder Aufgaben rekursiv in Unteraufgaben unterteilt . Die Unteraufgaben werden dann einzeln gelöst, wobei die Unterergebnisse kombiniert werden, um das Ergebnis zu bilden:

Result solve(Problem problem) { if (problem is small) directly solve problem else { split problem into independent parts fork new subtasks to solve each part join all subtasks compose result from subresults } }

2.2. Arbeiter-Threads

Die aufgeschlüsselte Aufgabe wird mithilfe von Arbeitsthreads gelöst, die von einem Thread-Pool bereitgestellt werden . Jeder Arbeitsthread hat Unteraufgaben, für die er verantwortlich ist. Diese werden in doppelseitigen Warteschlangen (Deques) gespeichert.

Jeder Worker-Thread erhält Unteraufgaben aus seiner Deque, indem er kontinuierlich eine Unteraufgabe von der Oberseite der Deque entfernt. Wenn die Deque eines Worker-Threads leer ist, bedeutet dies, dass alle Unteraufgaben entfernt wurden.

Zu diesem Zeitpunkt wählt der Worker-Thread zufällig einen Peer-Thread-Pool-Thread aus, von dem er Arbeit „stehlen“ kann. Anschließend wird der FIFO-Ansatz (First-In, First-Out) verwendet, um Unteraufgaben vom hinteren Ende der Deque des Opfers aus zu übernehmen.

3. Fork / Join Framework-Implementierung

Wir können einen Work-Stealing-Thread-Pool entweder mit der ForkJoinPool- Klasse oder der Executors- Klasse erstellen :

ForkJoinPool commonPool = ForkJoinPool.commonPool(); ExecutorService workStealingPool = Executors.newWorkStealingPool();

Die Executors- Klasse verfügt über eine überladene newWorkStealingPool- Methode, die ein ganzzahliges Argument verwendet, das den Grad der Parallelität darstellt .

Executors.newWorkStealingPool ist eine Abstraktion von ForkJoinPool.commonPool . Der einzige Unterschied besteht darin, dass Executors.newWorkStealingPool einen Pool im asynchronen Modus erstellt und ForkJoinPool.commonPool nicht.

4. Synchrone und asynchrone Thread-Pools

ForkJoinPool.commonPool verwendet eine LIFO-Warteschlangenkonfiguration (Last-In, First-Out), während Executors.newWorkStealingPool einen FIFO-Ansatz (First-In, First-Out) verwendet.

Laut Doug Lea hat der FIFO-Ansatz gegenüber LIFO folgende Vorteile:

  • Es reduziert Konflikte, indem Stealer als Eigentümer auf der gegenüberliegenden Seite der Deque operieren
  • Es nutzt die Eigenschaft rekursiver Divide-and-Conquer-Algorithmen, um frühzeitig „große“ Aufgaben zu generieren

Der zweite Punkt oben bedeutet, dass es möglich ist, eine ältere gestohlene Aufgabe durch einen Thread, der sie gestohlen hat, weiter aufzuschlüsseln.

Gemäß der Java-Dokumentation kann das Setzen von asyncMode auf true für die Verwendung mit Aufgaben im Ereignisstil geeignet sein, die niemals verbunden werden.

5. Arbeitsbeispiel - Primzahlen finden

Wir werden das Beispiel des Findens von Primzahlen aus einer Sammlung von Zahlen verwenden, um die Rechenzeitvorteile des Work-Stealing-Frameworks zu zeigen . Wir werden auch die Unterschiede zwischen der Verwendung von synchronen und asynchronen Thread-Pools zeigen.

5.1. Das Problem der Primzahlen

Das Finden von Primzahlen aus einer Sammlung von Zahlen kann ein rechenintensiver Prozess sein. Dies ist hauptsächlich auf die Größe der Zahlensammlung zurückzuführen.

Die PrimeNumbers- Klasse hilft uns, Primzahlen zu finden:

public class PrimeNumbers extends RecursiveAction { private int lowerBound; private int upperBound; private int granularity; static final List GRANULARITIES = Arrays.asList(1, 10, 100, 1000, 10000); private AtomicInteger noOfPrimeNumbers; PrimeNumbers(int lowerBound, int upperBound, int granularity, AtomicInteger noOfPrimeNumbers) { this.lowerBound = lowerBound; this.upperBound = upperBound; this.granularity = granularity; this.noOfPrimeNumbers = noOfPrimeNumbers; } // other constructors and methods private List subTasks() { List subTasks = new ArrayList(); for (int i = 1; i <= this.upperBound / granularity; i++) { int upper = i * granularity; int lower = (upper - granularity) + 1; subTasks.add(new PrimeNumbers(lower, upper, noOfPrimeNumbers)); } return subTasks; } @Override protected void compute() { if (((upperBound + 1) - lowerBound)> granularity) { ForkJoinTask.invokeAll(subTasks()); } else { findPrimeNumbers(); } } void findPrimeNumbers() { for (int num = lowerBound; num <= upperBound; num++) { if (isPrime(num)) { noOfPrimeNumbers.getAndIncrement(); } } } public int noOfPrimeNumbers() { return noOfPrimeNumbers.intValue(); } }

Einige wichtige Dinge, die Sie zu dieser Klasse beachten sollten:

  • Es erweitert RecursiveAction , wodurch wir die Berechnungsmethode implementieren können, die beim Berechnen von Aufgaben mithilfe eines Thread-Pools verwendet wird
  • Es rekursiv bricht Aufgaben in Teilaufgaben auf der Grundlage der Granularität Wert
  • Die Konstruktoren verwenden untere und obere Grenzwerte, die den Zahlenbereich steuern, für den wir Primzahlen bestimmen möchten
  • Es ermöglicht uns, Primzahlen entweder mithilfe eines Work-Stealing-Thread-Pools oder eines einzelnen Threads zu bestimmen

5.2. Schnelleres Lösen des Problems mit Thread-Pools

Lassen Sie uns Primzahlen in einem einzigen Thread bestimmen und auch Work-Stealing-Thread-Pools verwenden.

Schauen wir uns zunächst den Single-Threaded-Ansatz an :

PrimeNumbers primes = new PrimeNumbers(10000); primes.findPrimeNumbers();

Und jetzt der ForkJoinPool.commonPool- Ansatz :

PrimeNumbers primes = new PrimeNumbers(10000); ForkJoinPool pool = ForkJoinPool.commonPool(); pool.invoke(primes); pool.shutdown();

Schließlich werfen wir einen Blick auf den Executors.newWorkStealingPool- Ansatz :

PrimeNumbers primes = new PrimeNumbers(10000); int parallelism = ForkJoinPool.getCommonPoolParallelism(); ForkJoinPool stealer = (ForkJoinPool) Executors.newWorkStealingPool(parallelism); stealer.invoke(primes); stealer.shutdown();

Wir verwenden die invoke Methode der ForkJoinPool Klasse Aufgaben an den Threadpool zu übergeben. Diese Methode berücksichtigt Instanzen von Unterklassen von RecursiveAction . Mit Java Microbench Harness vergleichen wir diese verschiedenen Ansätze in Bezug auf die durchschnittliche Zeit pro Vorgang miteinander:

# Run complete. Total time: 00:04:50 Benchmark Mode Cnt Score Error Units PrimeNumbersUnitTest.Benchmarker.commonPoolBenchmark avgt 20 119.885 ± 9.917 ms/op PrimeNumbersUnitTest.Benchmarker.newWorkStealingPoolBenchmark avgt 20 119.791 ± 7.811 ms/op PrimeNumbersUnitTest.Benchmarker.singleThread avgt 20 475.964 ± 7.929 ms/op

Es ist klar, dass sowohl ForkJoinPool.commonPool als auch Executors.newWorkStealingPool es uns ermöglichen, Primzahlen schneller zu bestimmen als mit einem Single-Threaded-Ansatz.

Mit dem Fork / Join-Pool-Framework können wir die Aufgabe in Unteraufgaben aufteilen. Wir haben die Sammlung von 10.000 Ganzzahlen in Chargen von 1-100, 101-200, 201-300 usw. aufgeteilt. Wir haben dann Primzahlen für jede Charge ermittelt und die Gesamtzahl der Primzahlen mit unserer Methode noOfPrimeNumbers verfügbar gemacht .

5.3. Die zu stehlende Arbeit stehlen

Bei einem synchronen Thread-Pool fügt ForkJoinPool.commonPool Threads in den Pool ein, solange die Aufgabe noch ausgeführt wird. Infolgedessen hängt der Grad des Arbeitsdiebstahls nicht vom Grad der Aufgabengranularität ab.

Der asynchrone Executors.newWorkStealingPoolwird besser verwaltet, sodass der Grad des Arbeitsdiebstahls vom Grad der Aufgabengranularität abhängt.

Mit dem getStealCount der ForkJoinPool- Klasse erhalten wir den Grad des Arbeitsdiebstahls :

long steals = forkJoinPool.getStealCount();

Das Bestimmen der Anzahl der Arbeitsdiebstähle für Executors.newWorkStealingPool und ForkJoinPool.commonPool führt zu einem unterschiedlichen Verhalten:

Executors.newWorkStealingPool -> Granularity: [1], Steals: [6564] Granularity: [10], Steals: [572] Granularity: [100], Steals: [56] Granularity: [1000], Steals: [60] Granularity: [10000], Steals: [1] ForkJoinPool.commonPool -> Granularity: [1], Steals: [6923] Granularity: [10], Steals: [7540] Granularity: [100], Steals: [7605] Granularity: [1000], Steals: [7681] Granularity: [10000], Steals: [7681]

Wenn sich die Granularität für Executors.newWorkStealingPool von fein zu grob (1 bis 10.000) ändert , verringert sich der Grad des Arbeitsdiebstahls . Daher ist die Anzahl der Diebstähle eins, wenn die Aufgabe nicht aufgeschlüsselt ist (Granularität von 10.000).

Der ForkJoinPool.commonPool hat ein anderes Verhalten. Der Grad des Arbeitsdiebstahls ist immer hoch und wird nicht wesentlich von der Änderung der Aufgabengranularität beeinflusst.

Technisch gesehen unterstützt unser Beispiel für Primzahlen die asynchrone Verarbeitung von Aufgaben im Ereignisstil. Dies liegt daran, dass unsere Implementierung das Zusammenführen von Ergebnissen nicht erzwingt.

Es kann der Fall angeführt werden, dass Executors.newWorkStealingPool den besten Einsatz von Ressourcen zur Lösung des Problems bietet.

6. Fazit

In diesem Artikel haben wir uns mit dem Stehlen von Arbeit und der Anwendung mit dem Fork / Join-Framework befasst. Wir haben uns auch die Beispiele für das Stehlen von Arbeit angesehen und wie dies die Verarbeitungszeit und den Ressourcenverbrauch verbessern kann.

Wie immer ist der vollständige Quellcode des Beispiels auf GitHub verfügbar.