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

Sperren

Bedingungen

Atomare Variablen

Concurrent Collections

Copy-On-Write-Collections

Queues

Synchronisatoren

Ausführbare Tätigkeiten

Thread-Pools

Behandlung von ungefangenen Exceptions

Timing/Scheduling

Ü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

Atomare Variablen und Concurrent Collections

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.

Copy-On-Write Collections

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

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.

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.

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):

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

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

Exchanger

V exchange (V data);

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

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

• 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

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

Leserzuschrift

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)