AngelikaLanger.com - Java Multithread Support - Threadsichere Collections und Synchronizers (original) (raw)

Java Multithread Support - Threadsichere Collections und Synchronizers

Im September 2004 ist die Version 5.0 der Java Standard Edition freigegeben worden. Der Multithread-Support ist in dieser Java-Version substantiell erweitert worden. In den nächsten 3 Beiträgen dieser Kolumne wollen wir uns diese Neuerungen genauer ansehen. Dieses Mal geht es um neue threadsichere Collections und um High-Level-Abstraktion zur Synchronisierung von Threads (die sogenannten Synchronisatoren, engl. Synchronizers).

Überblick über Multithread-Neuheiten in Java 5.0

Verschaffen wir uns erst einmal Überblick über die Neuheiten im Java 5.0 Multithreading. Die Erweiterungen in Java 5.0 lassen sich in die folgenden Themengebiete einordnen:

• Sperren
• Bedingungen
• Atomare Variablen
• Concurrent Collections
• Copy-On-Write-Collections
• Queues
• Synchronisatoren
• Ausführbare Tätigkeiten
• Thread-Pools
• Behandlung von ungefangenen Exceptions
• Timing/Scheduling

Die Erweiterungen finden sich im wesentlichen in dem neuen Package java.util.concurrent(bzw. Unter-Packages davon). Minimal betroffen sind auch noch java.langund java.util.

Über die neuen Abstraktionen für explizite Sperren und Bedingungen haben wir ja bereits gesprochen (siehe /KRE3/ und /KRE5/). In diesem und den nächsten beiden Artikeln wollen wir uns die verbleibenden Java 5.0 Multithread-Erweiterungen ansehen.

Motivationen und Absichten

Bevor wir uns die Erweiterungen im Detail ansehen, wollen wir erst einmal klären, was die Motivationen und Absichten hinter der Erweiterung waren. Vor dem JDK 5.0 war der Multithread-Support in Java, was Umfang und Komplexität angeht, auf das Notwendige beschränkt, also auf einen Funktionsumfang, der alles bietet, was für die Multithread-Programmierung unerläßlich ist. Dieser Ansatz führte zum einen dazu, dass in Java gewisse anspruchsvollere Low-Level-Techniken überhaupt nicht möglich waren (z.B. Hand-Over-Hand-Locking) oder dass mächtige und damit komplexere Abstraktionen für die Multithread-Programmierung (z.B. ein Thread-Pool) nicht enthalten waren. Letzteres hatte dann zur Konsequenz, dass solche Abstraktionen in unterschiedlichen Formen lösungsspezifisch in der Java Community entstanden.
Mit den JDK 5.0 Erweiterungen werden daher zwei Ziele verfolgt: einerseits werden mächtige High-Level-Abstraktionen als Standard bereitgestellt; andererseits werden die Möglichkeiten der Low-Level-Programmierung umfangreicher gestaltet und dabei ihre APIs näher an den Posix-Thread Standard herangebracht, um Programmierern mit Multithread-Erfahrung aus C bzw. C++ den Umstieg zu Java zu erleichtern.

Atomare Variablen und Concurrent Collections

Neben den Erweiterungen für explizite Sperren und Bedingungen gehören die atomaren Variablen zu den wichtigsten Low-Level-Erweitungen des Java 5.0 Multithread-APIs. Traditionell gibt es im Befehlsatz einer CPU eine Assembleranweisung, mit der man eine Speicherstelle auf einen Wert prüfen kann und bei Übereinstimmung einen neuen Wert setzen kann: den sogenannten Test-And-Set- oder Compare-And-Set-Befehl. Da dies ein Assemblerbefehl ist, ist damit die gesamte Operation atomar. Deshalb haben sich auf die Fähigkeit eines solchen Befehls aufbauend Programmiertechniken entwickelt, die es erlauben, threadsichere Abstraktionen zu implementieren, die ohne Sperren auskommen. Diese Techniken werden als Lock-Free- oder Wait-Free-Programming bezeichnet. In massiv parallelen Systemen läßt sich mit solchen Abstraktionen ein deutlich höherer Durchsatz erreichen, als es mit einer als auf Sperren basierenden Lösung möglich wäre. Allerdings muß man einräumen, dass es nicht möglich ist, ausnahmslos jedes Multithread-Problem ohne die Benutzung von Sperren zu lösen. Es gibt vielmehr eine Anzahl wohlbekannter Standardalgorithmen, um typische Datenstrukturen wie Listen, usw. ohne Sperren allein auf Basis des Compare-And-Set-Befehls threadsicher zu implementieren. Variationen dieser Algorithmen können auch gelegentlich bei der Implementierung einer spezifischen eigenen Abstraktion helfen.

Was hat nun der Compare-And-Set-Assemblerbefehl mit Java zu tun? Im Package java.util.concurrent.atomic gibt es im JDK 5.0 Abstraktionen, die Compare-And-Set-Funktionalität für Javatypen wie boolean, int, long und die generische Referenz (siehe AtomicBoolean, AtomicInteger, AtomicLong und AtomicReference) zur Verfügung stellen. Um möglichst effizient zu sein, setzen ihre Implementierungen auf den unterliegenden Compare-And-Set-Assemblerbefehl auf. Daneben gibt es in dem erwähnten Package noch zwei Abstraktionen, die atomare Compare-And-Set-Funktionalität für die Kombination einer Referenz mit einem boolean bzw. einem int (siehe AtomicMarkableReference und AtomicStampedReference) zur Verfügung stellen. Zusätzlich gibt es noch sogenannte Atomic Updater, die es erlauben, eine beliebige Speicherstelle über Reflection mit Compare-And-Set-Semantik anzusprechen.

Als Anwendung dieser neuen Abstraktionen enthält das Package java.util.concurrent zwei neue Collections, ConcurrentHashMap und ConcurrentLinkedQueue (siehe Abbildung 1), deren Threadsicherheit im wesentlichen auf atomaren Variablen basiert. Sie sind gerade bei Zugriffen von vielen Threads die performantere Alternative, verglichen mit den bereits aus dem JDK 1.2 bekannten threadsicheren Collections, die man sich z.B. mit Collections.synchronizedMap(new HashMap()) erzeugen kann. Wie alle Collections ab JDK 5.0 sind auch die Concurrent Collections generische Typen mit dem Elementtyp als Typparameter.

Wer sich für weitere Details threadsicherer Programmierung ohne Sperren interessiert, kann in die JavaDoc der ConcurrentLinkedQueue schauen. Dort gibt es einen Link auf die ausführliche Beschreibung des zugrundeliegenden Algorithmus.

Abbildung 1: Klassen und Interfaces im Zusammenhang mit Concurrent Collections im JDK 5.0

Copy-On-Write Collections

Neben den Concurrent Collections ohne Sperren gibt es weitere threadsichere Collections, die neu im JDK 5.0 sind. Dazu gehören die Copy-On-Write Collections: CopyOnWriteArrayList und CopyOnWriteArraySet (siehe Abbildung 2). Das sind threadsichere Collections, die ebenfalls ohne Sperren auskommen, aber nicht auf den atomaren Variablen beruhen, sondern Veränderungen auf Snapshots durchführen.

Abbildung 2: Klassen und Interfaces im Zusammenhang mit Copy-On-Write-Collections im JDK 5.0

Vereinfacht kann man sich das so vorstellen: die Copy-On-Write Collection hält intern ein Array mit allen Elementen der Collection. Wenn nun eine Veränderung gemacht werden soll (über Methoden wie add, set, usw.), dann wird zunächst einmal eine Kopie des aktuellen Arrays gemacht. Dabei wird das Array nur gelesen, nicht verändert. Es gibt also keine Kollisionen mit anderen lesenden Threads. Auf dieser Kopie wird dann die Veränderung vorgenommen. Die Kopie kennt nur der verändernde Thread. Es kann also auch hier keine Kollisionen mit anderen Threads geben. Danach wird die intern gehaltene Referenz auf das Array so umgebogen, dass sie auf das veränderte Array zeigt. Das Umbiegen der Referenz ist eine Adreßzuweisung und ist atomar, kann also nicht unterbrochen werden. Nach der Referenzzuweisung steht die Veränderung den konkurrierenden Threads zur Verfügung.

Damit das funktioniert, werden Garantien für die Sichtbarkeit von volatile Referenzen gebraucht, die es erst seit Java 5.0 gibt und die in der Neufassung der Memory Model Spezifikation (siehe /JSR133/) ausgearbeitet wurden. Auf die Details wollen wir an dieser Stelle nicht eingehen. Aber man erkennt, dass man mit dieser Technik ganz ohne Sperren auskommt, weil Veränderungen an der Collection stets auf einer Kopie der Collection gemacht werden.

Iteratoren auf den Copy-On-Write Collections arbeiten auf einem sogenannten_Snapshot_der Liste. Das ist die Liste, so wie sie zum Zeitpunkt der Konstruktion des Iterators war. Das heißt, über einen solchen Iterator sieht man nicht, wenn Elemente aus der Collection entfernt oder zur Collection hinzugefügt wurden. Die modifzierenden Methoden erzeugen, wie oben beschrieben, eine Kopie des internen Arrays, modifzieren die Kopie und hängen das modifizierte Array als neuen Inhalt der Liste ein. Davon bekommt der Iterator nichts mit. In diesem Sinne arbeitet er auf einem Snapshot der Liste.

Diese Copy-On-Write Iteratoren haben den Vorteil, dass sie keine Fast-Fail Iteratoren sind. Die Iteratoren, die man für eine synchronisierte Collection (z.B. über Collections.synchronizedList()) bekommt, werfen nämlich eine ConcurrentModificationException, wenn sie bemerken, dass während der Iteration die Collection geändert wurde. Das ist bei den Copy-On-Write Iteratoren natürlich anders; sie bekommen von der Modifikation nichts mit und es stört sie auch nicht. Die Semantik der Iterierung ist als bei den Copy-On-Write Collections anders als bei den synchronisierten Collections.

Das Anlegen von Kopien bei jeder Modifikation an der Collection ist natürlich reichlich teuer und die Verwendung von Copy-On-Write Collections macht nur dann Sinn, wenn die Anzahl der lesenden Zugriffe die der schreibenden bei Weitem übersteigt. Andernfalls wird der Performance-Gewinn durch das Vermeiden der Sperren durch den Overhead des Kopieren zunichte gemacht.

Queues

Neben den threadsicheren Collections ohne Sperren gibt es weitere Collections, die neu im JDK 5.0 sind. Und zwar gibt es nun verschiedene Queue Abstraktionen in den Packages java.util und java.util.concurrent. In einer Multithread-Umgebung ist die Queue das typische Austauschmedium zwischen Produzenten und Konsumenten: Produzenten-Threads schreiben in die Queue; Konsumenten-Threads lesen daraus. So ist es nur natürlich, dass im Rahmen der Erweiterung des JDK um High-Level-Abstraktionen für die Multithread-Programmierung, Queues ins Package java.util.concurrent aufgenommen wurden.

Bisher gab es keine explizite Queue Abstraktion im JDK, obwohl die LinkedList mit Methoden wie addFirst(), getLast() und removeLast() Queue-spezifische Funktionalität zur Verfügung stellt. Mit dem JDK 5.0 gibt es nun ein explizites Interface Queue, das von Collection abgeleitet ist. Dieses stellt fünf Queue-spezifische Methoden zur Verfügung:

• eine, um ein Element einzufügen,
• zwei, um ein Element zu lesen ohne es zu entfernen und
• zwei, um ein Element zu lesen und es zu entfernen. Es gibt jeweils zwei Methoden beim Lesen, weil die eine Methode bei leerer Queue null zurückliefert, während die andere in einem solchen Fall eine Laufzeit-Exception vom Typ NoSuchElement wirft.

Die LinkedList implementiert jetzt auch das Queue Interface und stellt damit so etwas wie die Standard-Queue im JDK dar. Daneben gibt es noch die PriorityQueue (siehe Abbildung 3). Sie ordnet ihre Element nicht nach der Reihenfolge des Eingangs, sondern entsprechen der Ordnung ihres Elementtyps; dieser muss dazu das Comparable Interface implementiert haben. Wie bei Baum-basierten Collections kann alternativ ein Comperator bei der Konstruktion der PriorityQueue übergeben werden, der dann als Basis der Ordnung benutzt wird. Weitere Änderungen gibt es im Package java.util zum Thema Queue nicht. Man beachte, dass Queue und PriorityQueue ganz „normale“ Collection sind, so wie LinkedList, d.h. sie sind nicht threadsicher.

Abbildung 3: Klassen und Interfaces im Zusammenhang mit „normalen“ Queues im Package java.util des JDK 5.0

Threadsichere, blockierende Queues, also solche, an denen Threads ggf. warten, gibt es im Package java.util.concurrent. Dort gibt das Interface BlockingQueue, das von Queue ableitet. Dies erlaubt einer Leseoperation (mit Entfernen des Elements) bei leerer Queue zu warten bis ein anderer Thread ein Element in die Queue geschrieben hat. Falls die Queue in ihrer Größe beschränkt ist, kann auch beim Schreiben gewartet werden. Zum Warten werden jeweils zwei Methoden angeboten: eine mit Timeout und eine, die unbeschränkt wartet.

Es gibt fünf neue Java-Klassen in java.util.concurrent, die das Interface BlockingQueue implementieren (siehe Abbildung 4):

Abbildung 4: Klassen und Interfaces im Zusammenhang mit synchronisierten Queues im JDK 5.0

ArrayBlockingQueue und LinkedBlockingQueue sind die Standardimplementierung für wartende Queues im JDK. Wie die Namen schon ahnen lassen, basiert die Implementierung von ArrayBlockingQueue auf einem Array und die von LinkedBlockingQueue auf einer verketteten Liste. Die ArrayBlockingQueue hat nach der Konstruktion eine fixe Größe. Die LinkedBlockingQueue kann optional mit beschränkter oder unbeschränkter Größe konstruiert werden.

PriorityBlockingQueue entspricht im wesentlichen der PriorityQueue, wobei sie natürlich zusätzlich die wartenden Methoden aus dem BlockingQueue Interface anbietet. Sie ist immer unbeschränkt in ihrer Größe.

DelayQueue ist eine besondere Art von PriorityBlockingQueue, in der die Element zeitlich geordnet sind. Diese zeitliche Ordnung baut auf die vordefinierte Verweildauer der Elemente in der Queue auf. Das heißt ein Element muss eine vorher definierten Zeitdauer in der Queue verbleiben, bevor es wieder gelesen werden kann. Diese Verweildauer eines Elements wird dadurch definiert, dass es von Delayed abgeleitet sein muss und damit die Methode: getDelay() implementiert. Die getDelay() Methode muss den Returnwert (d.h. die Verweildauer) immer dynamisch zum Zeitpunkt des jeweiligen Aufrufs neu berechnen.

SynchronousQueue hat einen recht komplexen Synchronisationsmechanismus, den man sich von den Rendezvous Channeln in Ada abgeschaut hat. Ein Lese-Thread muss jeweils auf einen Schreib-Thread warten und umgekehrt. Das heißt ein Lese-Thread, der an eine solche Queue kommt, muss auf einen Schreib-Thread warten, wenn es nicht bereits einen Schreib-Thread gibt, der auf einen Lese-Thread wartet. Somit bilden sich Paare von jeweils einem Lese- und einem Schreib-Thread, die vom Warten an der Queue befreit werden. Derjenige von beiden (egal ob Lese- oder Schreib-Thread), der als erster kommt, muss dabei auf den anderen warten.

Auch auf die Gefahr uns zu wiederholen: die Queueabstraktionen (Interfaces wie auch Klassen) sind, wie alle Collections im JDK 5.0, generische Typen. Der Elementtyp ist der Typparameter.

Abstraktionen zur Synchronisation von Threads

Alle Klassen, die das Interface BlockingQueue implementieren, kann man als High-Level-Synchronisationsmechanismus zwischen zwei oder mehr Threads benutzten. Das einfachste Beispiel ist dabei sicherlich die schon erwähnte Nutzung einer in der Größe festen ArrayBlockingQueue zum Datenaustausch und zur Synchronisation zwischen einem Produzenten-Thread, der in die Queue schreibt, und einem Konsumenten-Thread, der aus der Queue liest.

Zwar bieten alle BlockingQueue Typen zusammengenommen eine große Auswahl an verschiedenen High-Level-Synchronisationsmöglichkeiten, aber abgerundet wird das Angebot im JDK mit zusätzlichen Abstraktionen, die spezielle Synchronisationsfähigkeiten bieten. Diese werden im Englischen häufig Synchronizers genannt. Wir werden sie hier im Deutschen als Synchronisatoren bezeichen.

Semaphore

Den einfachsten Synchronisator, das Semaphore, haben wir wegen seiner semantischen Nähe zur Sperre, bereits in einem vorhergehenden Artikel (siehe /KRE3/) besprochen, in dem es um die neuen Sperren im JDK 5.0 ging.

Exchanger

Der Exchanger ist einer SynchronousQueue relativ ähnlich. Bei dem Exchanger können zwei Threads an einem Synchronisationspunkt aufeinander warten und Informationen in beide Richtungen austauschen. Der Austausch in beide Richtungen unter der Voraussetzung, dass es immer genau zwei Threads (und nicht mehr) sein müssen, ist der wesentliche Unterschied zur SynchronousQueue. Der Exchanger hat im wesentlichen nur eine Methode, die folgendermaßen aussieht:

V exchange (V data);

Dabei ist V der Typparameter; d.h. der Exchanger ist ebenfalls ein generischer Typ.

Jeder der beiden Theads ruft diese Methode auf und übergibt ihr die Daten, die er für den anderen Thread hat. Die Methode kommt dann mit den empfangenen Daten zurück. Der Vollständigkeit halber sollte noch erwähnt werden, dass es noch eine weitere exchange() Methode mit Timeout gibt.

CyclicBarrier

Bei der CyclicBarrier geht es allein um Synchronisation, nicht um Datenaustausch. Eine beliebige, aber feste Anzahl von Threads synchronisiert sich zyklisch, indem sie jeweils await() auf der CyclicBarrier Instanz aufrufen. Das heißt, ein Thread, der await() aufgerufen hat, kommt erst wieder von dem Aufruf zurück, wenn alle anderen Threads auch await() aufgerufen haben. Zusätzlich ist es möglich, eine sogenannte Barrier-Aktion (englisch: barrier action) einzuhängen, die abläuft, nachdem alle Threads await() aufgerufen haben. Die Threads warten auch noch, während die Aktion abläuft, und dürfen erst danach weiterlaufen.

Eine CyclicBarrier wird man typischerweise dann nutzen, wenn sich Threads regelmäßig, z.B. für jeden neuen gemeinsamen Arbeitsschritt, synchronisieren müssen.

CountDownLatch

Ein Latch (deutsch: Verschluss, Riegel) bezeichnet in der Multithread-Programmierung einen Mechanismus, bei dem ein oder mehrere Threads warten müssen, bis ein oder mehrere andere Threads die wartenden Threads zum Weiterlaufen freigeben. Beim CountDownLatch im JDK 5.0 rufen die Threads, die warten möchten, await() auf der Instanz des Latches auf. Die Threads, die freigeben wollen, rufen countDown() auf. Bei der Konstruktion des CountDownLatch kann parametrisiert werden, wie häufig countDown()aufgerufen werden muss, bis die wartenden Threads freigegeben werden. Dabei ist es unerheblich, ob countDown() von einem Thread mehrmals oder von mehreren Threads einmal aufgerufen wird. Ist das Latch einmal ausgelöst worden, kann es nicht wieder verwendet werden, anders als bei der zyklischen Barriere.

Ein Beispiel für die Nutzung eines Latches ist die Initialisierungsphase eines Systems, bei dem einige Threads erst einmal nicht loslaufen dürfen, sondern warten müssen, bis bestimmte Initialisierungen abgeschlossen sind.

Wichtig ist, dass man bei den verschiedenen High-Level-Synchronisationsmechanismen den Überblick behält und versteht, wo sie mit ihrer Funktionalität aneinanderstoßen und sich ergänzen. So wird zum Beispiel aus einem Latch eine einfache (d.h. nicht zyklische) Barriere, wenn alle beteiligten Threads bei der gemeinsamen Synchronisation erst countDown() und dann await() aufrufen. Die Nähe von Exchanger und SynchronousQueue haben wir ja bereits auch schon kurz erwähnt.

Sinn der High-Level-Synchronisationsmechanismen

Was bedeutet es nun für die Realisierung von Multithread-Systemen, dass mit den verschiedenen BlockingQueues und den Synchronisatoren neue High-Level-Synchronisationsmechanismus zur Verfügung stehen?
Schauen wir uns dazu noch einmal das Beispiel eines Produzenten-Konsumenten-Modells mit einer ArrayBlockingQueue, über die die Threads kommunizieren, an. Wenn man so etwas nun mit Hilfe des JDK 5.0 implementiert, wird man im Programm folgende Anweisungen sehen:

• eine new-Anweisung zum Anlegen einer ArrayBlockingQueue Instanz mit gewünschter Kapazität
• im Code des Produzenten-Threads den Aufruf der wartenden Schreibmethode (put()) auf der ArrayBlockingQueue Instanz
• im Code des Konsumenten-Threads den Aufruf der wartenden Lesemethode(take()) auf der ArrayBlockingQueue Instanz Dabei muss man explizit keinerlei Low-Level-Multithread-Synchronisationsmechanismen wie etwa eine Bedingung (z.B. java.util.concurrent.Condition) benutzten. Trotzdem basiert diese Lösung technisch gesehen natürlich auf der Nutzung von einer oder mehreren Bedingungen. Diese sind aber implizit in der ArrayBlockingQueue enthalten. Deren Implementierung kann man sich übrigens ähnlich wie die des BlockingIntStack aus einem unser vorhergehenden Artikel vorstellen.

Verallgemeinert bedeutet dies, dass es erst mit den Synchronisatoren bzw. den BlockingQueues aus dem JDK 5.0 möglich ist, Multithread-Lösungen mit komplexen Synchronisationssituationen zu implementieren, ohne explizite Low-Level-Synchronisationmechanismen zu nutzen. Das hat zum einen den Vorteil, dass der Programmierer die elementaren Synchronisierungsmechanismen nicht mehr im Detail kennen muß; damit werden potentielle Fehler vermieden. Zum anderen reduziert sich natürlich der Implementierungsaufwand, wenn nicht schon wieder das Rad neu erfunden werden muß und statt dessen auf bereits fertige und getestete Standard-Abstraktionen zurückgegriffen werden kann. Wir können nur grundsätzlich dazu raten, bei Synchronizationsproblemen bevorzugt zu den High-Level-Mechanismen zu greifen. Erst wenn diese nicht passen oder einen unnötigen Overhead erzeugen, sind die Low-Level-Mechanismen (z.B. Sperren und Bedingungen) das richtige Mittel.

Zusammenfassung und Ausblick

In Java 5.0 gibt es zahlreiche Neuerungen für die Multithread-Programmierung. In diesem Artikel haben wir schwerpunktmäßig die threadsicheren Collections, die synchronisierten Queues und die Synchronisatoren wie Semaphore, Barrieren, Latches, usw. kennengelernt. In den nächsten beiden Artikeln gehen wir genauer auf den Threadpool und die dafür relevanten Abstraktionen ein.

Leserzuschrift

In die Originalfassung dieses Artikels hatte sich ein Fehler eingeschlichen, der in der obigen Fassung bereits korrigiert ist. Wir danken dem sorgfältigen Leser, der uns auf den Fehler aufmerksam gemacht hat.

Literaturverweise

If you are interested to hear more about this and related topics you might want to check out the following seminar:
Seminar Concurrent Java - Java Multithread Programming 4 day seminar (open enrollment and on-site)