Nebenläufige Programmierung mit Java (eBook)

Konzepte und Programmiermodelle für Multicore-Systeme

Jörg Hettel, Manh Tien Tran (Autoren)

eBook Download: PDF | EPUB

2016 | 1. Auflage
378 Seiten
dpunkt (Verlag)
978-3-96088-013-4 (ISBN)

Infos

Damit die Performance-Möglichkeiten moderner Multicore-Rechner effizient genutzt werden, muss die Software dafür entsprechend entworfen und entwickelt werden. Für diese Aufgabe bietet insbesondere Java vielfältige Konzepte an. Das Buch bietet eine fundierte Einführung in die nebenläufige Programmierung mit Java. Der Inhalt gliedert sich dabei in fünf Teile: Im ersten Teil wird das grundlegende Thread-Konzept besprochen und die Koordinierung nebenläufiger Programmflüsse durch rudimentäre Synchronisationsmechanismen erläutert. Im zweiten Teil werden weiterführende Konzepte wie Threadpools, Futures, Atomic-Variablen und Locks vorgestellt. Ergänzende Synchronisationsmechanismen zur Koordinierung mehrerer Threads werden im dritten Teil eingeführt. Teil vier bespricht das ForkJoin-Framework, die Parallel Streams und die Klasse CompletableFuture, mit denen auf einfache Art und Weise nebenläufige Programme erstellt werden können. Im fünften Teil findet der Leser Beispiele für die Anwendung der vorgestellten Konzepte und Klassen. Dabei werden auch das Thread-Konzept von JavaFX und Android sowie das Programmiermodell mit Aktoren vorgestellt. Der Anhang enthält einen Ausblick auf Java 9, das bezüglich des Concurrency-API kleine Neuerungen bringt. Alle Codebeispiele stehen auf der Webseite zum Buch zum Download bereit.

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 Multicore-Programmierung. 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.

Inhalt

Vorwort 5
Inhaltsverzeichnis 9
Einführung 15
Dimensionen der Parallelität 15
Parallelität und Nebenläufigkeit 16
Die Vorteile von Nebenläufigkeit 17
Die Nachteile von Nebenläufigkeit 17
Sicherer Umgang mit Nebenläufigkeit 18
Maße für die Parallelisierung 18
Die Gesetze von Amdahl und Gustafson 18
Work-Span-Analyse 20
Parallelitätsmodelle 21
I Grundlegende Konzepte 23
Das Thread-Konzept von Java 25
Der main-Thread 25
Erzeugung und Starten von Threads 26
Thread-Erzeugung durch Vererbung 27
Thread-Erzeugung mit Runnable-Objekten 30
Der Lebenszyklus von Threads 33
Beendigung eines Threads 34
Auf das Ende eines Threads warten 35
Aktives Beenden von Threads 35
Unterbrechung mit interrupt 38
Thread-Zustände 40
Weitere Eigenschaften eines Thread-Objekts 41
Thread-Priorität 41
Daemon-Eigenschaft 42
Exception-Handler 43
Zusammenfassung 45
Konkurrierende Zugriffe auf Daten 47
Ein einleitendes Beispiel 47
Java-Speichermodell 48
Stacks und Heap 49
Speicher auf der Hardwareebene 51
Probleme mit gemeinsam nutzbaren Daten 52
Sequenzielle Konsistenz 53
Thread-sichere Daten und unveränderliche Objekte 55
Unveränderbare Objekte 56
Volatile-Attribute 57
Final-Attributte 59
Thread-lokale Daten 60
Fallstricke 63
Zusammenfassung 64
Elementare Synchronisationsmechanismen 65
Schlüsselwort synchronized 65
Synchronized-Methoden 65
Synchronized-Blöcke 67
Beispiel: Thread-sicheres Singleton 68
Monitorkonzept bei Java 70
Fallstricke 71
Zusammenfassung 76
Grundlegende Thread-Steuerung 77
Bedingungsvariablen und Signalisieren 77
Regeln zum Umgang mit wait, notify und notifyAll 83
Zusammenfassung 86
II Weiterführende Konzepte 87
Threadpools 89
Das Poolkonzept und die Klasse Executors 89
Executors mit eigener ThreadFactory 92
Explizite ThreadPoolExecutor-Erzeugung 92
Benutzerdefinierter ThreadPoolExecutor 93
Future- und Callable-Schnittstelle 94
Callable, Future und FutureTask 95
Callable, Future und ExecutorService 95
Callable und ThreadPoolExecutor 98
Callable und ScheduledThreadPoolExecutor 102
Callable und ForkJoinPool 102
Exception-Handling 104
Tipps für das Arbeiten mit Threadpools 106
Zusammenfassung 107
Atomic-Variablen 109
Compare-and-Set-Operation 110
Umgang mit Atomic-Variablen 111
Atomic-Skalare 111
Atomic-Referenzen 114
Accumulator und Adder in Java 8 116
Zusammenfassung 118
Lock-Objekte und Semaphore 119
Lock-Objekte 120
Das Lock-Interface 120
ReentrantLock 123
Das Condition-Interface 125
ReadWriteLock 129
StampedLock 131
Semaphore 134
Zusammenfassung 137
Thread-sichere Container 139
Collection-Typen 139
Thread-sichere Collections 141
Synchronisierte Collections 141
Unmodifiable Collections 143
Concurrent Collections 144
Zusammenfassung 149
III Ergänzende Synchronisationsmechanismen 151
Exchanger und BlockingQueue 153
Exchanger 153
Queues 157
Das Erzeuger-Verbraucher-Muster 160
Varianten 163
Pipeline von Erzeugern und Verbrauchern 163
Erzeuger-Verbraucher-Muster mit Empfangsbestätigung 164
Erzeuger-Verbraucher-Muster mit Work-Stealing 165
Zusammenfassung 171
CountDownLatch und CyclicBarrier 173
CountDownLatch 173
CyclicBarrier 176
Zusammenfassung 181
Phaser 183
Das Konzept des Phasers 183
Phaser als CountDownLatch 184
Phaser als CyclicBarrier 187
Phaser als variable Barriere 188
Zusammenspiel mit dem ForkJoin-Threadpool 192
Zusammenfassung 193
IV Parallelisierungsframeworks 195
Das ForkJoin-Framework 197
Grundprinzip des ForkJoin-Patterns 197
Programmiermodell 198
Einsatz von RecursiveAction 200
Einsatz von RecursiveTask 203
Einsatz von CountedCompleter 205
Work-Stealing-Verfahren 208
Zusammenfassung 211
Parallele Array- und Stream-Verarbeitung 213
Parallele Array-Verarbeitung 213
Parallele Transformation 213
Paralleles Sortieren 214
Parallele Präfixbildung 215
Funktionsprinzip der Stream-Verarbeitung 217
Funktionale Interfaces 218
Erzeugung von Streams 219
Transformations- und Manipulationsoperationen 222
Auswertungen von Streams 225
Eigenschaften und Operationsoptimierung 230
Parallele Stream-Verarbeitung: Datenparallelität 231
Arbeitsweise und korrekte Benutzung 232
Parallele Reduzierer 234
Parallele Collectoren 237
Funktionsweise von Spliteratoren 242
Benutzerdefinierte Spliteratoren 244
Zusammenfassung 249
CompletableFuture 251
CompletableFuture als Erweiterung des Future-Patterns 251
Design von asynchronen APIs 255
Asynchrone APIs mit Future 256
Asynchrone APIs mit CompletableFuture 256
Asynchrone Verarbeitung: Task-Parallelität 258
Das Starten einer asynchronen Verarbeitung 258
Definition einer asynchronen Verarbeitungskette 259
Das Arbeiten mit CompletableFutures 261
Das Konzept des CompletionStage 262
Lineare Kompositionsmöglichkeiten 263
Verzweigen und Vereinen 266
Synchronisationsbarrieren 270
Fehlerbehandlung und Abbruch einer Verarbeitung 271
Zusammenfassung 273
V Fallbeispiele 275
Asynchrones Logging 277
Lösung mit Thread-lokalen Daten 278
Verbesserte Version (Exchanger) 280
Datenstrukturen in Multithreaded-Umgebungen 285
Liste als sortierte Menge 285
Blockierende Lösungen (Locks) 290
Grobgranulare Synchronisierung 290
Feingranulare Synchronisierung 290
Optimistische Synchronisierung 293
Lockfreie Lösung (AtomicMarkableReference) 294
The Dining Philosophers Problem 301
Basisalgorithmus 302
Lösungsvarianten (Semaphore und Lock) 302
Lösung mit einem Semaphor 303
Lösung mit asymmetrischer Lock-Anforderung 304
Lösung mithilfe eines Koordinators 305
Lösung mit asymmetrischer Wait-Release-Strategie 307
Minimal aufspannende Bäume 309
Graphen und Spannbäume 309
Der Prim-Algorithmus 311
Funktionsweise des Algorithmus 311
Implementierung des Algorithmus 313
Parallelisierung (Phaser) 315
Mergesort 319
Funktionsprinzip des Algorithmus 319
Parallelisierung (ForkJoin-Framework) 321
Der k-Mean-Clusteralgorithmus 323
Der k-Mean-Algorithmus 323
Parallelisierung (Parallel Streams) 325
Datenmodell 325
Hilfsmethoden 325
Implementierung 326
Variante mit benutzerdefiniertem Collector 330
RSA-Schlüsselerzeugung 335
Verfahren für die Schlüsselerzeugung 335
Parallelisierung (CompletableFuture) 337
Threads bei JavaFX 341
Ein einfaches Beispiel 341
JavaFX-Concurrent-API 343
Handler-Konzept bei Android 349
UI-Thread und nebenläufige Aktivitäten 349
Messages, Message-Queue, Looper 350
Handler 352
Aktoren 355
Aktorenmodell 355
Beispielimplementierung mit Akka 356
Nachrichten 357
Beteiligte Aktoren 359
Starten der Anwendung 361
VI Anhang 363
Ausblick auf Java 9 365
Die Flow-Interfaces 365
Literaturverzeichnis 371
Index 371
www.dpunkt.de 0

Textauszug

1 Einführung

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.

1.1 Dimensionen der Parallelität

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.

1.2 Parallelität und Nebenläufigkeit

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].

1.2.1 Die Vorteile von Nebenläufigkeit

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.

1.2.2 Die Nachteile von Nebenläufigkeit

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.

1.2.3 Sicherer Umgang mit Nebenläufigkeit

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.

1.3 Maße für die Parallelisierung

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.

1.3.1 Die Gesetze von Amdahl und Gustafson

Eine erste Näherung für den Speedup liefert das Gesetz von Amdahl [2]. Hier...

Produkt-Details

• Erscheint lt. Verlag: 30.9.2016
• Verlagsort: Heidelberg
• Sprache: deutsch
• Themenwelt: Informatik ► Programmiersprachen / -werkzeuge ► Java
• Schlagworte: CompletableFutures • Concurrent programming • Fork-Join-Framework • Java • Java 8 • Multicore • Multicore-Processing • Multithreading • Multithread-Programmierung • Nebenläufige Programmierung • Parallele Programmierung • Threads
• ISBN-10: 3-96088-013-8 / 3960880138
• ISBN-13: 978-3-96088-013-4 / 9783960880134