Das Fork/Join-Framework in Java 7

Inhaltsverzeichnis

Wann sollte man den neuen ForkJoinPool dem klassischen ThreadPoolExecutor vorziehen, und wann lässt man es besser bleiben? Dieser Artikel stellt die wichtigsten Neuerungen des Fork/Join-Framework aus Java 7 vor und vergleicht die Performance in zwei Anwendungsgebieten aus der Praxis.

Eine wesentliche Neuerung von Java 5 war der ExecutorService, eine Abstraktion zur asynchronen Ausführung von Tasks. Der ThreadPoolExecutor implementiert das Konzept mit einem intern verwalteten Thread Pool, dessen Worker Threads die anfallenden Tasks abarbeiten. Der ThreadPoolExecutor besitzt eine zentrale Eingangs-Queue für neue Tasks (Runnables oder Callables), die alle Worker Threads gemeinsam nutzen.

Ein Nachteil des ThreadPoolExecutor ist, dass es beim Zugriff der Threads auf die gemeinsame Eingangs-Queue zu Konkurrenzsituationen kommen kann und durch den Synchronisations-Overhead wertvolle Zeit für die Bearbeitung der Tasks verloren geht. Auch gibt es keine Unterstützung für die Zusammenarbeit mehrerer Threads bei der Berechnung von Tasks.

Seit Java 7 gibt es mit dem ForkJoinPool eine weitere Implementierung des ExecutorService: Er verwendet zusätzliche Strukturen, um die Nachteile des ThreadPoolExecutor zu kompensieren und gegebenenfalls eine effizientere Bearbeitung von Tasks zu ermöglichen. Das zugrunde liegende Konzept, das Fork/Join-Framework, wurde von Doug Lea bereits 2000 vorgestellt (PDF) und seitdem weiter verfeinert und verbessert.

Wenn der ForkJoinPool in der Praxis zum Einsatz kommen soll, stellt sich leider oft Verunsicherung ein. Das liegt zum einen daran, dass viele Tutorials nur "Sandkastenbeispiele" verwenden. So entsteht schnell der Eindruck, der ForkJoinPool wäre nur für gekünstelte Fragestellungen oder ganz spezielle Anwendungen geeignet. Für Irritation sorgt außerdem, wenn der ForkJoinPool in scheinbar vielversprechenden Szenarien keinerlei Performancegewinn oder sogar eine Verschlechterung gegenüber dem ThreadPoolExecutor aufweist.

Dieser Artikel soll etwas Licht ins Dunkel bringen und anhand von Anwendungen aus der "echten" Praxis ein besseres Verständnis dafür schaffen, welche Szenarien sich für den ForkJoinPool eignen (und warum das so ist).

Arbeitsweise und Struktur

Genau wie der ThreadPoolExecutor verwendet der ForkJoinPool eine zentrale Eingangs-Queue und einen internen Thread Pool. Allerdings besitzt jeder Worker Thread zusätzlich eine eigene Task Queue, in die er selbst neue Tasks einplanen kann (siehe Abb. 1). So lange seine Task Queue noch Tasks enthält, arbeitet der Thread ausschließlich diese Tasks ab. Ist die eigene Queue leer, folgt der Thread einem Work-Stealing-Algorithmus: Er sucht in den Task Queues anderer Worker Threads nach einem verfügbaren Task und bearbeitet ihn. Sollte keiner zu finden sein, greift er auf die zentrale Eingangs-Queue zu.

Das Verfahren hat zwei potenzielle Vorteile: Erstens arbeitet jeder Thread soweit möglich über einen längeren Zeitraum nur auf seiner eigenen Queue, ohne mit den anderen Threads in Kontakt zu kommen. Zweitens besteht für die Threads die Möglichkeit, sich gegenseitig Arbeit abzunehmen.

Um den Overhead durch die zusätzlichen Queues und das Work Stealing zu minimieren, wurde die Implementierung des ForkJoinPool stark in Bezug auf Performance verbessert. Zwei Aspekte sind hervorzuheben:

• Die Task Queues der Worker Threads verwenden als Datenstruktur eine Deque (double-ended queue), die effizientes Einfügen und Entfernen von Elementen an beiden Enden unterstützt. Der Worker Thread selbst arbeitet nur an einem Ende seiner Deque, analog zu einem Stack: Er legt neue Tasks auf die Spitze des Stacks (push) und holt sich von dort Tasks zur Bearbeitung (pop). Die anderen Threads hingegen greifen beim Work Stealing stets auf das andere Ende der Deque zu. Es kommt also beim Work Stealing in der Regel nur zu Konkurrenzsituationen zwischen Threads, die sich gleichzeitig aus derselben Task Queue bedienen möchten -- der "Eigentümer" der Queue ist nur selten involviert.
• Findet ein Thread beim Work Stealing keine verfügbaren Tasks, besteht die Gefahr, dass er fortwährend dieselben leeren Queues abklappert und so CPU-Zeit verbrennt. Um das zu vermeiden, gehen "arbeitslose" Worker Threads nach bestimmten Regeln in einen Ruhezustand über. Das Framework spricht sie gezielt an, sobald wieder Tasks verfügbar sind.

Fork und Join

Eine wichtige Beobachtung ist, dass die lokalen Task Queues und das Work Stealing nur zum Einsatz kommen (und daher auch nur dann einen Vorteil bringen), wenn die Worker Threads tatsächlich neue Tasks in die eigene Queue einplanen. Geschieht das nicht, reduziert sich das Verhalten des ForkJoinPool auf das eines ThreadPoolExecutor mit sinnlosem Overhead.

Der ForkJoinPool bietet daher eine explizite Schnittstelle an, mit der Tasks im Rahmen ihrer Ausführung neue Tasks einplanen können. Statt auf Runnables oder Callables arbeitet der ForkJoinPool auf sogenannten ForkJoinTasks. Ein ForkJoinTask besitzt während seiner Ausführung einen Kontext, innerhalb dessen neu erzeugte ForkJoinTasks automatisch in die lokale Task Queue eingeplant werden (fork). Benötigt der ursprüngliche Task die Ergebnisse der abgezweigten Tasks, kann er auf diese warten und sie zu einem Gesamtergebnis zusammenführen (join). Um die Anwendung von Fork und Join zu vereinfachen, gibt es zwei konkrete Implementierungen der ForkJoinTask: Der RecursiveTask liefert ein Ergebnis zurück, die RecursiveAction nicht.

Geeignete Szenarien für den ForkJoinPool

Ein Szenario, bei dem Tasks weitere Tasks einplanen, beruht auf dem Prinzip der Zerlegung: Ist der Berechnungsaufwand für einen Task sehr groß, lässt er sich rekursiv in viele kleine Subtasks zerlegen. Durch das Work Stealing beteiligen sich andere Threads ebenfalls an der Berechnung (und zerlegen ihre Subtasks wenn möglich erneut). Nur wenn ein Subtask nach bestimmten Kriterien klein genug ist und sich eine weitere Zerlegung nicht lohnt, wird er direkt berechnet. Besonders verlockend an dem Ansatz ist, dass zu Beginn einer rekursiven Zerlegung recht große Subtasks entstehen, die andere Threads dann unmittelbar stehlen können. Das begünstigt eine gleichmäßige Lastverteilung zwischen den Threads.

In einem anderen, gerne unterschätzten Szenario planen Tasks auch ohne Zerlegung weitere Tasks ein. Ein Task stellt dann zwar eine in sich abgeschlossene Aktion dar, löst aber trotzdem Folge-Aktionen aus, die durch zusätzliche Tasks dargestellt werden. Im Prinzip kann man so jede Form ereignisgesteuerter Abläufe modellieren. Im Extremfall könnte sich in einem solchen Szenario jeder Worker Thread fortlaufend selbst mit weiteren Tasks versorgen. Alle Threads wären beschäftigt, und trotzdem käme keine Konkurrenzsituation auf.

Im Folgenden wird an jeweils einem Praxisbeispiel untersucht, wie sich der ForkJoinPool in den beiden genannten Szenarien gegenüber dem ThreadPoolExecutor schlägt. Der komplette Quellcode der Beispiele ist auf GitHub verfügbar.