Jörg Hettel studierte Theoretische Physik und promovierte am Institut für Informationsverarbeitung und Kybernetik an der Universität Tübingen. Nach seiner Promotion war er als Berater bei nationalen und internationalen Unternehmen tätig. Er begleitete zahlreiche Firmen bei der Einführung von objektorientierten Technologien und übernahm als Softwarearchitekt Projektverantwortung. Seit 2003 ist er Professor an der Hochschule Kaiserslautern am Standort Zweibrücken. Seine aktuellen Arbeitsgebiete sind u.a. verteilte internetbasierte Transaktionssysteme und die MulticoreProgrammierung.
Manh Tien Tran studierte Informatik an der TU Braunschweig. Von 1987 bis 1995 war er wissenschaftlicher Mitarbeiter am Institut für Mathematik der Universität Hildesheim, wo er 1995 promovierte. Von 1995 bis 1998 war er als Softwareentwickler bei BOSCH Blaupunkt beschäftigt. 1999 wechselte er zu Harman Becker und war dort bis 2000 für Softwarearchitekturen zuständig. Seit 2000 ist er Professor an der Hochschule Kaiserslautern am Standort Zweibrücken. Seine aktuellen Arbeitsgebiete sind Frameworks, Embedded-Systeme und die Multicore-Programmierung.
Zu diesem Buch – sowie zu vielen weiteren dpunkt.büchern – können Sie auch das entsprechende E-Book im PDF-Format herunterladen. Werden Sie dazu einfach Mitglied bei dpunkt.plus+: www.dpunkt.de/plus |
Konzepte und Programmiermodelle für Multicore-Systeme
Prof. Dr. Jörg Hettel
joerg.hettel@hs-kl.de
Prof. Dr. Manh Tien Tran
manhtien.tran@hs-kl.de
Lektorat: Christa Preisendanz
Copy-Editing: Ursula Zimpfer, Herrenberg
Satz: Jörg Hettel, Manh Tien Tran
Herstellung: Frank Heidt
Umschlaggestaltung: Helmut Kraus, www.exclam.de
Druck und Bindung: M.P. Media-Print Informationstechnologie GmbH, 33100 Paderborn
Bibliografische Information der Deutschen Nationalbibliothek
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie;
detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar.
ISBN:
Print 978-3-86490-369-4
PDF 978-3-96088-012-7
ePub 978-3-96088-013-4
mobi 978-3-96088-014-1
1. Auflage 2016
Copyright © 2016 dpunkt.verlag GmbH
Wieblinger Weg 17
69123 Heidelberg
Die vorliegende Publikation ist urheberrechtlich geschützt. Alle Rechte vorbehalten. Die Verwendung der Texte und Abbildungen, auch auszugsweise, ist ohne die schriftliche Zustimmung des Verlags urheberrechtswidrig und daher strafbar. Dies gilt insbesondere für die Vervielfältigung, Übersetzung oder die Verwendung in elektronischen Systemen.
Es wird darauf hingewiesen, dass die im Buch verwendeten Soft- und Hardware-Bezeichnungen sowie Markennamen und Produktbezeichnungen der jeweiligen Firmen im Allgemeinen warenzeichen-, marken- oder patentrechtlichem Schutz unterliegen.
Alle Angaben und Programme in diesem Buch wurden mit größter Sorgfalt kontrolliert. Weder Autor noch Verlag können jedoch für Schäden haftbar gemacht werden, die in Zusammenhang mit der Verwendung dieses Buches stehen.
5 4 3 2 1 0
Warum ist das Schreiben von nebenläufiger Software so schwer? Zeitgleiche Abläufe beherrschen doch unseren Alltag. Wir arbeiten in Teams, koordinieren unsere Termine und übernehmen oder verteilen Aufgaben. In der Regel kommen wir mit dieser Art der Parallelität ganz gut zurecht.
Die uns vertraute Parallelität erweist sich bei der Entwicklung von Softwaresystemen als schwer zugänglich. Das liegt sicherlich mit daran, dass wir dabei immer das Ganze im Blick haben und Abläufe immer wieder über neue Koordinationsregeln steuern müssen. Darüber hinaus haben wir es technikbedingt mit einer anderen Art der Beschreibung von Parallelität zu tun.
Die Abstraktion der nebenläufigen Programmierung ist bei vielen Konzepten der Thread, ein Kontrollfluss bzw. -faden, der unabhängig von anderen agiert und durch einen Programmcode gesteuert wird. Diese Beschreibungsweise hat ihren Ursprung in der sequenziellen Programmierung, bei der es genau einen Ablaufstrang gibt. Leider ist es für uns auch im normalen Leben unmöglich, viele gleichzeitige, obwohl sequenzielle Vorgänge zu bewältigen. Diese Parallelitätsabstraktion ist intuitiv nicht leicht zugänglich; wir denken im Alltag nicht in Threads.
Der Umgang mit Threads birgt deshalb zahlreiche Fehlerquellen. Viele Multithreaded-Anwendungen enthalten Anomalien, die erst nach Monaten oder Jahren auftreten (siehe z. B. [36]). Nicht reproduzierbare Programmabstürze oder Verklemmungen, die häufig erst spät im Produktivbetrieb auftreten, sind typische Symptome dafür.
Um einfache, sichere Programmiermodelle zu ermöglichen, versucht man auf den in der Sprache vorhandenen primitiven Mechanismen Abstraktionskonzepte und Frameworks aufzubauen. Auf diesem Gebiet hat sich in den letzten Jahren sehr viel getan. Insbesondere wurde die Programmiersprache Java um viele solcher Konzepte erweitert.
Die nebenläufige Programmierung ist keine neue Domäne und es existiert auch schon viel Literatur hierzu. Einen guten Überblick über diesen komplexen Themenbereich findet man z. B. in dem Buch Multicore-Software von Urs Gleim und Tobias Schüle [15]. Im Bereich der Java-Programmierung gilt nach wie vor das Buch von Doug Lea Concurrent Programming in Java: Design Principles and Patterns [34] als Standardwerk. Viele Ideen aus diesem Buch wurden sukzessive in die einzelnen Java-Versionen übernommen. Als Fortsetzung dieses Werks gilt das 2005 erschienene Buch Java Concurrency in Practice von Brian Goetz et al. [16], das ausführlich das Java 5 Concurrency-API diskutiert. Gute Beiträge zu vielen einzelnen Themen gibt es z. B. von Klaus Kreft und Angelika Langer [30] oder Heinz Kabutz [27].
Mit dem vorliegenden Buch möchten wir an diese Literatur anknüpfen und eine fundierte Einführung in die nebenläufige Programmierung mit Java geben und insbesondere auch die in den letzten Jahren eingeführten Konzepte und Frameworks detailliert beschreiben. Das Buch richtet sich vor allem an erfahrene Softwareentwickler sowie fortgeschrittene Studenten, die nebenläufige Konzepte in Projekten einsetzen möchten.
Wir hoffen, dass Ihnen das Buch Nebenläufige Programmierung mit Java gefällt und vor allem, dass es Ihnen ein guter Ratgeber ist.
Das Buch besteht aus fünf Teilen. Im ersten Teil werden die für die nebenläufige Programmierung grundlegenden Konzepte besprochen. Es wird der Thread-Mechanismus eingeführt und die Koordinierung nebenläufiger Programmflüsse durch rudimentäre Low-Level-Synchronisationsmechanismen erläutert. Im Wesentlichen sind dies die Verfahrensweisen, die seit Einführung von Java im Sprachumfang zur Verfügung stehen. Die Basiskonzepte bilden die Grundlage für die weiteren Teile des Buches.
Mit dem Aufkommen von Multicore-Prozessoren und den damit verbundenen Möglichkeiten ist die nebenläufige Programmierung immer mehr in den Fokus der Anwendungsentwicklung gerückt. Da die rudimentären Konzepte sehr leicht zu fehleranfälligen Implementierungen führen, wurde mit Java 5 ein umfangreiches Concurrency-API eingeführt, das mit den folgenden Versionen immer wieder ausgebaut wurde und wird.
Im Teil zwei werden verschiedene weiterführende Konzepte, wie Threadpools, Futures, Atomic-Variablen und Locks, vorgestellt.
Im dritten Teil werden ergänzende Synchronisationsmechanismen zur Koordinierung mehrerer Threads eingeführt. Neben dem Exchanger sind dies die Klassen CountDownLatch, CyclicBarrier und Phaser.
Teil vier bespricht die Parallelisierungsframeworks, mit denen auf einfache Art und Weise nebenläufige Programme erstellt werden können. Die Frameworks übernehmen hier im Wesentlichen die Thread-Koordination und -Synchronisation. Im Einzelnen werden das ForkJoin-Framework, die Parallel Streams und die Klasse CompletableFuture besprochen. Das ForkJoin-Framework erlaubt die Parallelisierung von Divide-and-Conquer-Algorithmen und parallele Streams die zeitgleiche Verarbeitung von Datensammlungen, wie z. B. Collections. Die Klasse CompletableFuture entspricht einem Framework zur Erstellung von asynchronen Abläufen und ist eine Erweiterung des Future-Mechanismus um sogenannte push-Methoden.
Der fünfte Teil widmet sich der Anwendung der vorgestellten Konzepte und Klassen. Hierbei wurden die Beispiele aus verschiedenen Anwendungsgebieten ausgewählt. Des Weiteren gehen wir kurz auf das Thread-Konzept von JavaFX und Android ein. Abschließend stellen wir das Programmiermodell mit Aktoren vor, wobei hier das Akka-Framework benutzt wird, da im Java-Standard selbst (noch) kein solches Framework vorhanden ist.
Im Anhang geben wir der Vollständigkeit halber einen kurzen Ausblick auf Java 9, das bezüglich des Concurrency-API kleine Neuerungen bringt.
Vorausgesetzt werden gute Java-Kenntnisse, und erste Erfahrungen im Umgang mit Lambda-Ausdrücken wären wünschenswert. Als ergänzende Literatur empfehlen wir das Buch von Michael Inden [25], von dem wir auch einige Praxistipps übernommen haben. Die Streams von Java 8 und die in dem Zusammenhang benötigten funktionalen Interfaces werden in Kapitel 14 eingeführt.
Wir haben versucht, die Beispiele »so einfach wie möglich und so komplex wie notwendig« zu halten. Insbesondere sind die Fallbeispiele im fünften Teil noch nicht »voll praxistauglich«. Der benutzte Coding Style ist zum großen Teil der Buchform angepasst, was z. T. herausfordernd ist, da hier die Zeilenbreite sehr beschränkt ist. Das macht insbesondere die Darstellung von Stream- und CompletableFuture-Operationen oft schwierig. Wenn möglich, haben wir für das Verständnis nicht relevanten Code weggelassen. Insbesondere wird stets auf die import-Anweisungen verzichtet. Alle Codebeispiele findet man auch auf unserer Webseite zum Download. Bei den besprochenen APIs haben wir keinen Wert auf Vollständigkeit gelegt, sondern versucht, das Wesentliche zu extrahieren. Mit dem hier erworbenen Verständnis sollte man keine Probleme haben, die API-Dokumentation zu verstehen. Ein Blick in die Dokumentation ist immer zu empfehlen, da mittlerweile auch Verwendungsbeispiele aufgenommen wurden.
Ein herzliches Dankeschön geht an die Mitarbeiter des dpunkt.verlags und insbesondere an Frau Christa Preisendanz, die die Fertigstellung des Buches professionell begleitet haben. Wir möchten uns auch bei unseren Studenten und den Reviewern, insbesondere Prof. Dr. Schiedermeier und Michael Inden, für die kritische Prüfung und kompetenten Hinweise bedanken. Zu guter Letzt geht auch ein Dank an unsere Familien für die Unterstützung und die Geduld.
Trotz sorgfältiger Prüfung wird das Buch wahrscheinlich leider noch Fehler enthalten, für die ausschließlich die Autoren verantwortlich sind. Falls Sie Fehler finden, lassen Sie es uns bitte wissen.
Jörg Hettel und Manh Tien Tran
Zweibrücken, Juni 2016
http://www.hs-kl.de/java-concurrency
1 Einführung
1.1 Dimensionen der Parallelität
1.2 Parallelität und Nebenläufigkeit
1.2.1 Die Vorteile von Nebenläufigkeit
1.2.2 Die Nachteile von Nebenläufigkeit
1.2.3 Sicherer Umgang mit Nebenläufigkeit
1.3 Maße für die Parallelisierung
1.3.1 Die Gesetze von Amdahl und Gustafson
1.3.2 Work-Span-Analyse
1.4 Parallelitätsmodelle
I Grundlegende Konzepte
2 Das Thread-Konzept von Java
2.1 Der main-Thread
2.2 Erzeugung und Starten von Threads
2.2.1 Thread-Erzeugung durch Vererbung
2.2.2 Thread-Erzeugung mit Runnable-Objekten
2.3 Der Lebenszyklus von Threads
2.3.1 Beendigung eines Threads
2.3.2 Auf das Ende eines Threads warten
2.3.3 Aktives Beenden von Threads
2.3.4 Unterbrechung mit interrupt
2.3.5 Thread-Zustände
2.4 Weitere Eigenschaften eines Thread-Objekts
2.4.1 Thread-Priorität
2.4.2 Daemon-Eigenschaft
2.5 Exception-Handler
2.6 Zusammenfassung
3 Konkurrierende Zugriffe auf Daten
3.1 Ein einleitendes Beispiel
3.2 Java-Speichermodell
3.2.1 Stacks und Heap
3.2.2 Speicher auf der Hardwareebene
3.2.3 Probleme mit gemeinsam nutzbaren Daten
3.2.4 Sequenzielle Konsistenz
3.2.5 Thread-sichere Daten und unveränderliche Objekte
3.3 Unveränderbare Objekte
3.4 Volatile-Attribute
3.5 Final-Attributte
3.6 Thread-lokale Daten
3.7 Fallstricke
3.8 Zusammenfassung
4 Elementare Synchronisationsmechanismen
4.1 Schlüsselwort synchronized
4.1.1 Synchronized-Methoden
4.1.2 Synchronized-Blöcke
4.1.3 Beispiel: Thread-sicheres Singleton
4.1.4 Monitorkonzept bei Java
4.2 Fallstricke
4.3 Zusammenfassung
5 Grundlegende Thread-Steuerung
5.1 Bedingungsvariablen und Signalisieren
5.2 Regeln zum Umgang mit wait, notify und notifyAll
5.3 Zusammenfassung
II Weiterführende Konzepte
6 Threadpools
6.1 Das Poolkonzept und die Klasse Executors
6.1.1 Executors mit eigener ThreadFactory
6.1.2 Explizite ThreadPoolExecutor-Erzeugung
6.1.3 Benutzerdefinierter ThreadPoolExecutor
6.2 Future- und Callable-Schnittstelle
6.2.1 Callable, Future und FutureTask
6.2.2 Callable, Future und ExecutorService
6.3 Callable und ThreadPoolExecutor
6.4 Callable und ScheduledThreadPoolExecutor
6.5 Callable und ForkJoinPool
6.6 Exception-Handling
6.7 Tipps für das Arbeiten mit Threadpools
6.8 Zusammenfassung
7 Atomic-Variablen
7.1 Compare-and-Set-Operation
7.2 Umgang mit Atomic-Variablen
7.2.1 Atomic-Skalare
7.2.2 Atomic-Referenzen
7.3 Accumulator und Adder in Java 8
7.4 Zusammenfassung
8 Lock-Objekte und Semaphore
8.1 Lock-Objekte
8.1.1 Das Lock-Interface
8.1.2 ReentrantLock
8.1.3 Das Condition-Interface
8.1.4 ReadWriteLock
8.1.5 StampedLock
8.2 Semaphore
8.3 Zusammenfassung
9 Thread-sichere Container
9.1 Collection-Typen
9.2 Thread-sichere Collections
9.2.1 Synchronisierte Collections
9.2.2 Unmodifiable Collections
9.2.3 Concurrent Collections
9.3 Zusammenfassung
III Ergänzende Synchronisationsmechanismen
10 Exchanger und BlockingQueue
10.1 Exchanger
10.2 Queues
10.3 Das Erzeuger-Verbraucher-Muster
10.4 Varianten
10.4.1 Pipeline von Erzeugern und Verbrauchern
10.4.2 Erzeuger-Verbraucher-Muster mit Empfangsbestätigung
10.4.3 Erzeuger-Verbraucher-Muster mit Work-Stealing
10.5 Zusammenfassung
11 CountDownLatch und CyclicBarrier
11.1 CountDownLatch
11.2 CyclicBarrier
11.3 Zusammenfassung
12 Phaser
12.1 Das Konzept des Phasers
12.1.1 Phaser als CountDownLatch
12.1.2 Phaser als CyclicBarrier
12.2 Phaser als variable Barriere
12.3 Zusammenspiel mit dem ForkJoin-Threadpool
12.4 Zusammenfassung
IV Parallelisierungsframeworks
13 Das ForkJoin-Framework
13.1 Grundprinzip des ForkJoin-Patterns
13.2 Programmiermodell
13.2.1 Einsatz von RecursiveAction
13.2.2 Einsatz von RecursiveTask
13.2.3 Einsatz von CountedCompleter
13.3 Work-Stealing-Verfahren
13.4 Zusammenfassung
14 Parallele Array- und Stream-Verarbeitung
14.1 Parallele Array-Verarbeitung
14.1.1 Parallele Transformation
14.1.2 Paralleles Sortieren
14.1.3 Parallele Präfixbildung
14.2 Funktionsprinzip der Stream-Verarbeitung
14.2.1 Funktionale Interfaces
14.2.2 Erzeugung von Streams
14.2.3 Transformations- und Manipulationsoperationen
14.2.4 Auswertungen von Streams
14.2.5 Eigenschaften und Operationsoptimierung
14.3 Parallele Stream-Verarbeitung: Datenparallelität
14.3.1 Arbeitsweise und korrekte Benutzung
14.3.2 Parallele Reduzierer
14.3.3 Parallele Collectoren
14.3.4 Funktionsweise von Spliteratoren
14.3.5 Benutzerdefinierte Spliteratoren
14.4 Zusammenfassung
15 CompletableFuture
15.1 CompletableFuture als Erweiterung des Future-Patterns
15.2 Design von asynchronen APIs
15.2.1 Asynchrone APIs mit Future
15.2.2 Asynchrone APIs mit CompletableFuture
15.3 Asynchrone Verarbeitung: Task-Parallelität
15.3.1 Das Starten einer asynchronen Verarbeitung
15.3.2 Definition einer asynchronen Verarbeitungskette
15.4 Das Arbeiten mit CompletableFutures
15.4.1 Das Konzept des CompletionStage
15.4.2 Lineare Kompositionsmöglichkeiten
15.4.3 Verzweigen und Vereinen
15.4.4 Synchronisationsbarrieren
15.5 Fehlerbehandlung und Abbruch einer Verarbeitung
15.6 Zusammenfassung
V Fallbeispiele
16 Asynchrones Logging
16.1 Lösung mit Thread-lokalen Daten
16.2 Verbesserte Version (Exchanger)
17 Datenstrukturen in Multithreaded-Umgebungen
17.1 Liste als sortierte Menge
17.2 Blockierende Lösungen (Locks)
17.2.1 Grobgranulare Synchronisierung
17.2.2 Feingranulare Synchronisierung
17.2.3 Optimistische Synchronisierung
17.3 Lockfreie Lösung (AtomicMarkableReference)
18 The Dining Philosophers Problem
18.1 Basisalgorithmus
18.2 Lösungsvarianten (Semaphore und Lock)
18.2.1 Lösung mit einem Semaphor
18.2.2 Lösung mit asymmetrischer Lock-Anforderung
18.2.3 Lösung mithilfe eines Koordinators
18.2.4 Lösung mit asymmetrischer Wait-Release-Strategie
19 Minimal aufspannende Bäume
19.1 Graphen und Spannbäume
19.2 Der Prim-Algorithmus
19.2.1 Funktionsweise des Algorithmus
19.2.2 Implementierung des Algorithmus
19.3 Parallelisierung (Phaser)
20 Mergesort
20.1 Funktionsprinzip des Algorithmus
20.2 Parallelisierung (ForkJoin-Framework)
21 Der k-Mean-Clusteralgorithmus
21.1 Der k-Mean-Algorithmus
21.2 Parallelisierung (Parallel Streams)
21.2.1 Datenmodell
21.2.2 Hilfsmethoden
21.2.3 Implementierung
21.2.4 Variante mit benutzerdefiniertem Collector
22 RSA-Schlüsselerzeugung
22.1 Verfahren für die Schlüsselerzeugung
22.2 Parallelisierung (CompletableFuture)
23 Threads bei JavaFX
23.1 Ein einfaches Beispiel
23.2 JavaFX-Concurrent-API
24 Handler-Konzept bei Android
24.1 UI-Thread und nebenläufige Aktivitäten
24.2 Messages, Message-Queue, Looper
24.3 Handler
25 Aktoren
25.1 Aktorenmodell
25.2 Beispielimplementierung mit Akka
25.2.1 Nachrichten
25.2.2 Beteiligte Aktoren
25.2.3 Starten der Anwendung
VI Anhang
A Ausblick auf Java 9
A.1 Die Flow-Interfaces
Literaturverzeichnis
Index
Die meisten Computer können heute verschiedene Anweisungen parallel abarbeiten. Um diese zur Verfügung stehende Ressource auszunutzen, müssen wir sie bei der Softwareentwicklung entsprechend berücksichtigen. Die nebenläufige Programmierung wird deshalb häufiger eingesetzt. Der Umgang und die Koordinierung von Threads gehören heute zum Grundhandwerk eines guten Entwicklers.
Bei Softwaresystemen gibt es verschiedene Ebenen, auf denen Parallelisierung eingesetzt werden kann bzw. bereits eingesetzt wird. Grundlegend kann zwischen Parallelität auf der Prozessorebene und der Systemebene unterschieden werden [26, 15]. Auf der Prozessorebene lassen sich die drei Bereiche Pipelining (Fließbandverarbeitung), superskalare Ausführung und Vektorisierung für die Parallelisierung identifizieren.
Auf der Systemebene können je nach Prozessoranordnung und Zugriffsart auf gemeinsam benutzte Daten folgende Varianten unterschieden werden:
Bei Multinode-Systemen wird die Aufgabe über verschiedene Rechner hinweg verteilt. Jeder einzelne Knoten (in der Regel ein eigenständiger Rechner) hat seinen eigenen Speicher und Prozessor. Man spricht in diesem Zusammenhang von verteilten Anwendungen.
Bei Multiprocessor-Systemen ist die Anwendung auf verschiedene Prozessoren verteilt, die sich in der Regel alle auf demselben Rechner (Mainboard) befinden und die alle auf denselben Hauptspeicher zugreifen, wobei die Zugriffszeiten nicht einheitlich sind. Jeder Prozessor hat darüber hinaus auch noch verschiedene Cache-Levels. Solche Systeme besitzen häufig eine sogenannte NUMA-Architektur (Non-Uniform Memory Access).
Bei Multicore-Systemen befinden sich verschiedene Rechenkerne in einem Prozessor, die sich den Hauptspeicher und zum Teil auch Caches teilen. Der Zugriff auf den Hauptspeicher ist von allen Kernen gleich schnell. Man spricht in diesem Zusammenhang von einer UMA-Architektur (Uniform Memory Access).
Neben den hier aufgeführten allgemeinen Unterscheidungsmerkmalen gibt es noch weitere, herstellerspezifische Erweiterungsebenen. Genannt sei hier z. B. das von Intel eingeführte Hyper-Threading. Dabei werden Lücken in der Fließbandverarbeitung mit Befehlen von anderen Prozessen möglichst aufgefüllt.
Hinweis
In dem vorliegenden Buch werden wir uns ausschließlich mit den Konzepten und Programmiermodellen für Multicore- bzw. Multiprocessor-Systeme mit Zugriff auf einen gemeinsam benutzten Hauptspeicher befassen, wobei wir auf die Besonderheiten der NUMA-Architektur nicht eingehen. Bei Java hat man außer der Verwendung der beiden VM-Flags -XX:+UseNUMA und -XX:+UseParallelGC kaum Einfluss auf das Speichermanagement.
Zwei oder mehrere Aktivitäten (Tasks) heißen nebenläufig, wenn sie zeitgleich bearbeitet werden können. Dabei ist es unwichtig, ob zuerst der eine und dann der andere ausgeführt wird, ob sie in umgekehrter Reihenfolge oder gleichzeitig erledigt werden. Sie haben keine kausale Abhängigkeit, d.h., das Ergebnis einer Aktivität hat keine Wirkung auf das Ergebnis einer anderen und umgekehrt. Das Abstraktionskonzept für Nebenläufigkeit ist bei Java der Thread, der einem eigenständigen Kontrollfluss entspricht.
Besitzt ein Rechner mehr als eine CPU bzw. mehrere Rechenkerne, kann die Nebenläufigkeit parallel auf Hardwareebene realisiert werden. Dadurch besteht die Möglichkeit, die Abarbeitung eines Programms zu beschleunigen, wenn der zugehörige Kontrollfluss nebenläufige Tasks (Aktivitäten) beinhaltet. Dabei können moderne Hardware und Übersetzer nur bis zu einem gewissen Grad automatisch ermitteln, ob Anweisungen sequenziell oder parallel (gleichzeitig) ausgeführt werden können. Damit Programme die Möglichkeiten der Multicore-Prozessoren voll ausnutzen können, müssen wir die Parallelität explizit im Code berücksichtigen.
Die nebenläufige bzw. parallele Programmierung beschäftigt sich zum einen mit Techniken, wie ein Programm in einzelne, nebenläufige Abschnitte/Teilaktivitäten zerlegt werden kann, zum anderen mit den verschiedenen Mechanismen, mit denen nebenläufige Abläufe synchronisiert und gesteuert werden können. So schlagen z. B. Mattson et al. in [37] ein »patternbasiertes« Vorgehen für das Design paralleler Anwendungen vor. Ähnliche Wege werden auch in [7] oder [38] aufgezeigt. Spezielle Design-Patterns für die nebenläufige Programmierung findet man in [15, 38, 42, 45].
Der Einsatz von Nebenläufigkeit ermöglicht die Anwendung verschiedener neuer Programmierkonzepte. Der offensichtlichste Vorteil ist die Steigerung der Performance. Auf Maschinen mit mehreren CPUs kann zum Beispiel das Sortieren eines großen Arrays auf mehrere Threads verteilt werden. Dadurch kann die zur Verfügung stehende Rechenleistung voll ausgenutzt und somit die Leistungsfähigkeit der Anwendung verbessert werden. Ein weiterer Aspekt ist, dass Threads ihre Aktivitäten unterbrechen und wiederaufnehmen können. Durch Auslagerung der blockierenden Tätigkeiten in separate Threads kann die CPU in der Zwischenzeit andere Aufgaben erledigen. Hierdurch ist es möglich, asynchrone Schnittstellen zu implementieren und somit die Anwendung reaktiv zu halten. Dieser Gesichtspunkt gewinnt immer mehr an Bedeutung.
Der Einsatz von Nebenläufigkeit hat aber nicht nur Vorteile. Er kann unter Umständen sogar mehr Probleme verursachen, als damit gelöst werden. Programmcode mit Multithreading-Konzepten ist nämlich oft schwer zu verstehen und mit hohem Aufwand zu warten. Insbesondere wird das Debugging erschwert, da die CPU-Zuteilung an die Threads nicht deterministisch ist und ein Programm somit jedes Mal verschieden verzahnt abläuft.
Parallel ablaufende Threads müssen koordiniert werden, sodass man immer mehrere Programmflüsse im Auge haben muss, insbesondere wenn sie auf gemeinsame Daten zugreifen. Wenn eine Variable von einem Thread geschrieben wird, während der andere sie liest, kann das dazu führen, dass das System in einen falschen Zustand gerät. Für gemeinsam verwendete Objekte müssen gesondert Synchronisationsmechanismen eingesetzt werden, um konsistente Zustände sicherzustellen. Des Weiteren kommen auch Cache-Effekte hinzu. Laufen zwei Threads auf verschiedenen Kernen, so besitzt jeder seine eigene Sicht auf die Variablenwerte. Man muss nun dafür Sorge tragen, dass gemeinsam benutzte Daten, die aus Performance-Gründen in den Caches gehalten werden, immer synchron bleiben. Weiter ist es möglich, dass sich Threads gegenseitig in ihrem Fortkommen behindern oder sogar verklemmen.
Den verschiedenen Nachteilen versucht man durch die Einführung von Parallelisierungs- und Synchronisationskonzepten auf höherer Ebene entgegenzuwirken. Ziel ist es, dass Entwickler möglichst wenig mit Low-Level-Synchronisation und Thread-Koordination in Berührung kommen. Hierzu gibt es verschiedene Vorgehensweisen. So wird z. B. bei C/C++ mit OpenMP1 die Steuerung der Parallelität deklarativ über #pragma im Code verankert. Der Compiler erzeugt aufgrund dieser Angaben parallel ablaufenden Code. Die Sprache Cilk erweitert C/C++ um neue Schlüsselworte, wie z. B. cilk_for2.
Java geht hier den Weg über die Bereitstellung einer »Concurrency-Bibliothek«, die mit Java 5 eingeführt wurde und sukzessive erweitert wird. Nachdem zuerst Abstraktions- und Synchronisationskonzepte wie Thread-pools, Locks, Semaphore und Barrieren angeboten wurden, sind mit Java 7 und Java 8 auch Parallelisierungsframeworks hinzugekommen. Nicht vergessen werden darf hier auch die Einführung Thread-sicherer Datenstrukturen, die unverzichtbar bei der Implementierung von Multithreaded-Anwendungen sind. Der Umgang mit diesen High-Level-Abstraktionen ist bequem und einfach. Nichtsdestotrotz gibt es auch hier Fallen, die man nur dann erkennt, wenn man die zugrunde liegenden Low-Level-Konzepte beherrscht. Deshalb werden im ersten Teil des Buches die Basiskonzepte ausführlich erklärt, auch wenn diese im direkten Praxiseinsatz immer mehr an Bedeutung verlieren.
Neben der Schwierigkeit, korrekte nebenläufige Programme zu entwickeln, gibt es auch inhärente Grenzen für die Beschleunigung durch Parallelisierung. Eine wichtige Maßzahl für den Performance-Gewinn ist der Speedup (Beschleunigung bzw. Leistungssteigerung), der wie folgt definiert ist:
Hierbei ist Tseq die Laufzeit mit einem Kern und Tpar die Laufzeit mit mehreren.
Eine erste Näherung für den Speedup liefert das Gesetz von Amdahl [2]. Hier fasst man die Programmteile zusammen, die parallel ablaufen können. Wenn P der prozentuale, parallelisierbare Anteil ist, dann entspricht (1−P) dem sequenziellen, nicht parallelisierbaren. Hat man nun N Prozessoren bzw. Rechenkerne zur Verfügung, so ergibt sich der maximale Speedup
wobei hier implizit davon ausgegangen wird, dass die Parallelisierung einen konstanten, vernachlässigbaren, internen Verwaltungsaufwand verursacht. Durch Grenzwertbildung N → ∞ ergibt sich dann der theoretisch maximal erreichbare Speedup beim Einsatz von unendlich vielen Kernen bzw. Prozessoren zu
An der Formel sieht man, dass der nicht parallelisierbare Anteil den Speedup begrenzt. Beträgt der parallelisierbare Anteil z.B. nur 50%, so kann nach dem Amdahl’schen Gesetz maximal nur eine Verdopplung der Ausführungsgeschwindigkeit erreicht werden (vgl. Abb. 1-1).
Abbildung 1-1: Speedup in Abhängigkeit von P und N
Man kann die Parallelisierung aber auch unter einem anderen Gesichtspunkt betrachten. Amdahl geht von einem fest vorgegebenen Programm bzw. einer fixen Problemgröße aus. Gustafson betrachtet dagegen eine variable Problemgröße in einem festen Zeitfenster [18]. Er macht die Annahme, dass sich die Vergrößerung des zu berechnenden Problems im Wesentlichen üblicherweise nur auf den parallelisierbaren Programmteil P auswirkt (man sagt, die Anwendung ist skalierbar). Unter diesem Aspekt ergibt sich ein Speedup von
d.h., der Zuwachs ist hier proportional zu N.
Die unterschiedlichen Sichtweisen zwischen Amdahl und Gustafson sind in der Abbildung 1-2 verdeutlicht.
Abbildung 1-2: Amdahl (oben) versus Gustafson (unten)
Eine weitere Methode, den Grad einer Parallelisierung zu beschreiben, ist die Work-Span-Analyse [10]. In dem zugrunde liegenden Modell werden die Abhängigkeiten der auszuführenden Aktivitäten in einem azyklischen Graphen dargestellt (vgl. Abb. 1-3). Eine Aktivität kann hier erst dann ausgeführt werden, wenn alle »Vorgänger« abgeschlossen sind.
Die von dem Algorithmus zu leistende Gesamtarbeit ist die Summe der auszuführenden Aktivitäten. Man bezeichnet die benötigte Zeit (work) hierfür mit T1. Der sogenannte span, der mit T1 bezeichnet wird, entspricht dem kritischen Pfad, also dem längsten Weg von Aktivitäten, die nacheinander ausgeführt werden müssen3.
Abbildung 1-3: Azyklischer Aktivitätsgraph
Wenn wir uns den Aktivitätsgraphen in Abbildung 1-3 anschauen und annehmen, dass jede Aktivität eine Zeiteinheit dauert, so erhalten wir für den work T1 = 12 und den span T∞ = 6. Sei N wieder die Anzahl der Rechenkerne bzw. Prozessoren, dann erhält man als Speedup:
Der Speedup wächst linear mit der Anzahl der Prozessoren, vorausgesetzt dass die CPU immer voll ausgelastet ist (greedy scheduling). Der Speedup ist allerdings durch den span begrenzt, da der kritische Pfad sequenziell abgearbeitet werden muss:
In unserem Beispiel beträgt der maximal erreichbare Speedup T1/T1 = 2.
In der Literatur wird zwischen verschiedenen Modellen für die Parallelisierung unterschieden. Java unterstützt jedes dieser Modelle durch das Bereitstellen verschiedener Konzepte und APIs.
Zur Parallelisierung von Anwendungen gibt es grundsätzlich zwei Ansätze: Daten- und Task-Parallelität4. Bei der Datenparallelität wird ein Datenbestand geteilt und die Bearbeitung der Teilbereiche verschiedenen Threads zugeordnet. Hierbei führt jeder Thread dieselben Operationen aus.
Diese Art der Parallelisierung wird durch das Gesetz von Gustafson beschrieben und ist in der Regel gut skalierbar [53]. Mit dem ForkJoin-Framework und dem Stream-API stehen bei Java hierfür zwei leistungsfähige Möglichkeiten zur Verfügung (siehe Kapitel 13 und 14). Falls man diese Frameworks nicht einsetzen möchte, kann für eine explizite Umsetzung auf zahlreiche Synchronisationskonzepte zurückgegriffen werden (siehe Kapitel 11 und 12).
Bei der Task-Parallelität5 wird die Anwendung in Funktionseinheiten zerlegt, die dann bezüglich ihrer Abhängigkeiten ausgeführt werden. Diese Art der Parallelisierung wird durch die Work-Span-Analyse beschrieben und kann bei Java mithilfe der CompletableFuture-Klasse oder je nachdem auch mit dem ForkJoin-Framework realisiert werden (siehe Kapitel 13 und 15).
Neben diesen beiden grundsätzlichen Ansätzen wird auch oft noch zwischen dem Master-Slave-, dem Work-Pool- und dem Erzeuger-Verbraucher-bzw. Pipeline-Programmiermuster unterschieden [32]. Das Unterscheidungsmerkmal ist hierbei die Art und Weise, wie die beteiligten Komponenten miteinander kommunizieren. Beim Master-Slave-Modell gibt es einen dedizierten Thread, der Aufgaben an andere verteilt und dann die Ergebnisse einsammelt. Bei Java kann dieses Modell mit dem Future-Konzept umgesetzt werden (siehe Abschnitt 6.2). Das Work-Pool-Modell entspricht dem ExecutorService, dem man Aufgaben zur Ausführung delegieren kann (siehe Abschnitt 6.1). Das bewährte Erzeuger-Verbraucher-Modell wird typischerweise durch BlockingQueue-Datenstrukturen realisiert und existiert in verschiedenen Varianten (siehe Abschnitt 10.3). In der Praxis findet man häufig Kombinationen der verschiedenen Modelle bzw. Muster.
Grundlegende Konzepte
Die Unterstützung der Thread-Programmierung ist ein zentraler Bestandteil der Java-Sprachdefinition. Man erkennt dies sowohl an der Klasse Thread, die im Paket java.lang zu finden ist, als auch an Schlüsselwörtern, wie z.B. synchronized und volatile. Durch diese wichtige Sprachverankerung können portable Multithreaded-Anwendungen implementiert werden1.
Da es mit Java sehr einfach ist, Threads zu erzeugen und zu starten, werden sie auch gerne eingesetzt und mitunter ohne wirklichen Nutzen. Insbesondere möchte man ja die Ressourcen eines Multicore-Rechners ausschöpfen. Dabei machen sich viele Entwickler wenig Gedanken darüber, dass man mit dem Einsatz von Threads den Programmfluss aufspaltet, asynchrone Programmfäden (Nebenflüsse) startet und damit unter Umständen parallel auf gemeinsam genutzte Daten zugreift.
In diesem Kapitel stellen wir das grundlegende Thread-API von Java vor. Es sind nur wenige Konstrukte und Klassen, die speziell für die Unterstützung der nebenläufigen Programmierung entworfen wurden. Dabei spielt die Klasse java.lang.Thread eine zentrale Rolle.
Eine Java-Anwendung wird in einer Java Virtual Machine (JVM) ausgeführt. Die JVM selbst entspricht hierbei einem Prozess des Betriebssystems. Zur Ausführung des Programms startet die JVM unter anderem den sogenannten main-Thread 2, der die Befehlszeilen Schritt für Schritt abarbeitet.
Codebeispiel 2.1 zeigt ein einfaches Programm, das neben der Anzahl der zur Verfügung stehenden Rechenkerne (Hardware-Threads) einige Eigenschaften des main-Threads ausgibt. Dabei werden Kerne mit Hyperthread-Unterstützung doppelt gezählt, da diese zwei Hardware-Threads bereitstellen.
public class MainThreadEigenschaft
{
public static void main(String[] args)
{
// Anzahl der Prozessoren abfragen
int nr = Runtime.getRuntime().availableProcessors();
System.out.println("Anzahl der Prozessoren " + nr);
// Eigenschaften des main-Threads
Thread self = Thread.currentThread();
System.out.println("Name : " + self.getName());
System.out.println("Priorität : " + self.getPriority());
System.out.println("ID : " + self.getId());
}
}
Codebeispiel 2.1: Ausgabe verschiedener Attribute des main-Threads
Zugriff auf den ausführenden Thread erhält man über die Klassenmethode Thread.currentThread. Im Codebeispiel 2.1 werden der Name, die Priorität und die Kennung des Threads, die ihm von der JVM zugewiesen wurde, auf die Konsole ausgegeben.
Der von der JVM erzeugte Thread, ein sogenannter Java-Thread, ist lediglich ein Abstraktionskonzept. Falls das zugrunde liegende Betriebssystem selbst Threads unterstützt (Betriebssystem- bzw. OS-Threads), kann die JVM die Java-Threads auf sie abbilden. Die Zuordnung der OS- auf die Hardware-Threads übernimmt der Scheduler des Betriebssystems (vgl. Abb. 2-1).
Da moderne Betriebssysteme Threads unterstützen und zeitgemäße Hardware auch mehrere Rechenkerne besitzen, werden wir im Folgenden oft implizit davon ausgehen, dass ein Java-Thread einem Hardware-Thread zugeordnet ist. In vielen Fällen sprechen wir, falls die Unterscheidung unwesentlich ist, deshalb nur noch von Threads, meinen aber streng genommen immer Java-Threads.
Innerhalb eines Java-Programms können mithilfe der Klasse Thread zusätzliche Java-Threads gestartet werden. Der von dem erzeugten Thread auszuführende Code kann hierbei auf zwei Arten zur Verfügung gestellt werden:
Abbildung 2-1: Zuordnung der Java-Threads zu einzelnen Kernen
Man leitet direkt von der Klasse Thread ab und überschreibt die run-Methode.
Man stellt eine Klasse bereit, die das Runnable-Interface implementiert. Ein Objekt dieser Klasse wird auch oft als Task bezeichnet. Es wird dann einem Thread zur Ausführung übergeben.
In der Praxis sollte man die zweite Möglichkeit bevorzugen, da hier konzeptuell klar zwischen dem Programmfluss (Thread) und der nebenläufig durchzuführenden Aufgabe (Task) unterschieden wird.
Eine einfache Art, einen nebenläufigen Programmfluss zu definieren, ist die Implementierung einer Unterklasse von Thread, bei der die run-Methode mit dem auszuführenden Code überschrieben wird. Das eigentliche Starten des Threads erfolgt durch den Aufruf der start-Methode.
Abbildung 2-2 zeigt den schematischen Ablauf im Sequenzdiagramm. Nachdem ein MyThread-Objekt erzeugt wurde, wird start aufgerufen. Dadurch wird der JVM mitgeteilt, dass vom Betriebssystem ein OS-Thread angefordert wird, der den in der run-Methode hinterlegten Code abarbeitet. Auf den exakten Startpunkt der Ausführung von run hat man keinen Einfluss. Sobald die run-Methode ausgeführt wird und der main-Thread noch aktiv ist, laufen in der Anwendung zwei nebenläufige Programmfäden (Programmflüsse) ab. Wenn der Thread mit der run-Methode fertig ist, terminiert er. Ein häufig gemachter Anfängerfehler ist der direkte Aufruf von run. In dem Fall wird sie nicht parallel in einem neuen Thread, sondern in dem des Aufrufers ausgeführt.
Abbildung 2-2: Sequenzdiagramm für das Starten eines neuen Threads
Codebeispiel 2.2 zeigt ein Programm, in dem drei Threads erzeugt und gestartet werden. Danach gibt jeder zwei Meldungen auf die Konsole aus.
class MyWorker extends Thread ➊
{
public MyWorker(String name) ➋
{
super(name);
}
@Override
public void run() ➌
{
Thread self = Thread.currentThread(); ➍
System.out.println("Hallo Welt von "+ self.getName());
System.out.println("Die ID von " + self.getName()
+ " ist " + self.getId());
}
}
public class ThreadDurchVererbung
{
public static void main(String[] args)
{
for (int i = 0; i < 3; i++)
{
MyWorker t = new MyWorker("Worker " + i); ➎
t.start();
}
}
}
Codebeispiel 2.2: Erzeugung von Threads durch Vererbung
Die Klasse MyWorker ist hier von Thread abgeleitet (➊). Die auszuführenden Aktionen werden in der überschriebenen run-Methode implementiert (➌). Über den Konstruktor wird dem Thread ein Name zugewiesen (➋). Erst durch den Aufruf von start wird run von einem neu gestarteten Thread ausgeführt (➎). Statt Thread.currentThread kann auch direkt this verwendet werden, da ein MyWorker-Objekt einem Java-Thread entspricht (➍).
In dem Beispiel greifen bereits alle drei Threads konkurrierend auf eine Ressource zu, nämlich auf den OutputStream von System.out. Die println-Methode von System.out besitzt einen Serialisierungsmechanismus (Lock), sodass immer nur ein Thread sie ausführen kann. Damit ist gewährleistet, dass sich die Ausgaben nicht gegenseitig überschreiben. Sie können aber durchaus vermischt werden, z. B.:
Hallo Welt von Worker 0
Hallo Welt von Worker 1
Die ID von Worker 0 ist 1
Hallo Welt von Worker 2
Die ID von Worker 2 ist 3
Die ID von Worker 1 ist 2