In vorhergehenden Artikeln haben wir uns einige Methoden angesehen, die von der gemeinsamen Basisklasse Object zur Verfügung gestellt werden. Wir haben diskutiert, wie diese Methoden in abgeleiteten Klassen zu nutzen bzw. zu überschreiben sind. Die betreffenden Methoden waren: clone() , equals() und hashcode() .  Neben den genannten Methoden beschreibt die JavaDoc von Object noch acht weitere Methoden, von denen allein fünf dem Themenkomplex „Multithread-Support in Java“ zugerechnet werden können: wait() (in drei überladenen Versionen ) sowie notify() und notifyAll() .

Ähnlich wie bei clone() , equals() und hashcode() ist es schwierig, wenn nicht unmöglich, die korrekte Nutzung dieser Methoden allein durch das Lesen der JavaDoc-Beschreibungen zu verstehen, insbesondere weil in den Beschreibungen Begriffe aus der Multithread-Programmierung bereits vorausgesetzt werden. Der erste Satz zu notifyAll() lautet zum Beispiel: “Wakes up all threads that are waiting on this object's monitor (/ JDOC /).” Hier muss der Leser der JavaDoc schon etwas mehr Kenntnisse mitbringen, als nur die Erkenntnis, dass mit „Monitor“ offensichtlich nicht der Bildschirm des Rechners gemeint ist.

Wir werden in diesem und den folgenden Artikeln die Details der Multithread-Programmierung in Java diskutieren. Obwohl der Multithread-Support in Java schon seit den Anfangstagen der Sprache in relativ unveränderter Form existiert, gibt es einen aktuellen Anlass für das Thema. Mit dem JDK 1.5 (der Mitte des Jahres freigegeben werden soll) wird es hier die ersten großen Ergänzungen geben, die wohl auch zu Änderungen bei Multithread-Programmieridiomen führen werden. Zu den Neuerungen gehören einerseits die neuen Concurrency Utilities, die eine ganze Reihe von nützlichen High-Level-Abstraktionen für die Multithread-Programmierung liefern werden, aber auch die Änderungen am Java Memory Model, die u.a. Klärungen und Änderungen im Bereich der unsynchronisierten Zugriffe auf volatile und final Variablen bringen werden.  (Dem interessierten Leser seien in diesem Zusammenhang die Spezifikationen der entsprechenden Java Community Groups JSR 133 für das Java Memory Model (siehe / JSR133 /) und JSR 166 für die Concurrency Utilities (siehe / JSR166 /) empfohlen.) Selbstverständlich werden wir diese Ergänzungen und ihre Auswirkungen in diesem Artikel bereits berücksichtigen und in späteren Artikeln dieser Kolumne genauer beschreiben.
 

Eine kurze Geschichte der Systemarchitektur

In den Anfängen der IT-Welt gab es keine Threads, ja nicht einmal Prozesse. Auf einem Rechner gab es nur eine einzige Ausführungseinheit.  Das war entweder das Betriebssystem, das direkt die Ein-/Ausgabe bediente, oder das Betriebssystem führte ein Anwendungsprogramm aus, welches dann die Kontrolle über die Ein-/Ausgabe übernahm. Diese eine Ausführungseinheit hatte dabei sowohl als Betriebssystem als auch als Anwendungsprogramm die volle Kontrolle über CPU und Speicher. (Ein gutes Beispiel für eine solche Konstellation ist ein PC mit dem Betriebssystem MS-DOS.  Zwar stammt MS-DOS nicht einmal aus den Anfängen der Informationstechnologie, aber es hat in gewissem Sinne die Entwicklung der Großrechnerwelt auf dem PC wiederholt.)

Über verschiedene Entwicklungsstufen entstand die Systemarchitektur, wie wir sie vom UNIX der späten 80er / frühen 90er Jahre her kennen. Ein Rechner hat mehrere Ausführungseinheiten, die Prozesse genannt werden. Diese teilen sich die Rechnerleistung der CPU (oder der CPUen) des Rechners.  Dabei wird die CPU-Leistung nach Algorithmen verteilt, die im Betriebssystem implementiert sind. Jeder Prozess hat seinen eigenen Stack und auch die Heapdaten sind im eigenen Adressraum vor dem Zugriff anderer Prozesse geschützt. Die Ausführung eines Anwendungsprogramms läuft in einem Prozess oder über mehrere Prozessen verteilt ab. So ist sichergestellt, dass sich verschiedene Anwendungen nicht gegenseitig blockieren oder behindern. Die Adressraumgrenzen sorgen dafür, dass Daten nicht gegenseitig überschrieben werden.  Das Prozess-Scheduling des Betriebssystem sorgt dafür, dass die Rechnerleistung fair auf alle Prozesse verteilt wird. Kleinere Nachteile hat diese Architektur dann, wenn eine Anwendung aus mehreren Prozesse besteht: um Daten zwischen den einzelnen Prozessen auszutauschen, muss auf sogenannte IPC-Mechnismen (IPC = Inter Process Communication) zurückgegriffen werden. Komunikation über IPC-Mechanismen ist langsamer und ressourcenintensiver als direkte Speicherzugriffe. Außerdem ist sie aufwändiger zu programmieren als direkte Speicherzugriffe.

An dieser Stelle kommen nun Threads ins Spiel. Threads sind  parallele Ausführungseinheiten innerhalb einer Anwendung, die direkt über Speicherzugriffe miteinander kommunizieren können, ohne aufwändige IPC-Mechanismen nutzen zu müssen. Innerhalb eines Prozesses hat man nun mehrere Threads, die alle im selben Adressraum ablaufen, aber ihren eigenen Stack haben. Jeder Thread bildet dabei eine eigene Ausführungseinheit, so dass es relativ natürlich ist, die parallelen Funktionen eines Anwendungsprogramms den Threads eines Prozesses zu zuordnen. Da alle Threads eines Prozesses auf dieselben Heapdaten zugreifen können, können sie Daten untereinander schnell und effizient austauschen.. Das Scheduling des Betriebssystem sorgt dafür, dass die Rechnerleistung fair auf Prozesse und ihre Threads verteilt wird. (Beispiele für diese Architektur sind alle Microsoft Betriebssysteme seit Windows NT und neuere UNIX Derivate inklusive Linux.)

In den Programmiersprachen, die zur Zeit der Einführung von  Threads populär waren (dies waren im wesentlichen C und C++), wurde die Multithread-Funktionalität über neue Bibliotheks-APIs zugänglich gemacht. Ein Beispiel für ein solches API ist IEEE POSIX 1003.1c (/ PTH /), auch bekannt als POSIX Threads oder Pthreads. Ein Nachteil dieses Bibliotheksansatzes ist ganz offensichtlich: eine Anwendung, die in C bzw. C++ implementiert ist und Multithreading nutzt, ist niemals portabel, sondern immer an ein bestimmtes Multithread-API gebunden.

Da Java erst nach der Einführung von Threads entstanden ist, wurde getreu nach dem Java-Motto „Write once, run everywhere.“  der Multithread-Support plattformübergreifend direkt in die Sprache integriert. Die Java Language Specification (/ JLS /) beschreibt alle Details des Verhalten von Threads, die für eine Java-Implementierung, die Multithreading nutzt, relevant sind.
 

Ein erstes Multithread-Beispiel

Dazu schauen wir uns ein Beispiel an:

public class IntStack {
 private final int[] array;
 private int cnt = 0;

 public IntStack (int sz) { array = new int[sz]; }

 public void push (int elm) {
   if (cnt < array.length) {
      array[cnt] = elm;
      cnt++;
   }
   else throw new IndexOutOfBoundsException();
 }

 // und weitere Methoden wie pop(), ...
}

Nehmen wir nun an, wir haben eine Java-Anwendung, in der zwei verschiedene Threads Zugriff auf eine Instanz des IntStack s haben, und beide Threads rufen die push() -Methode auf (siehe Abbildung 1).  Beiden Threads wird ihre Laufzeit vom Threadscheduler zugewiesen. Dabei ist es grundsätzlich möglich, dass die Ablaufreihenfolge so ist, dass der erste Thread vom Scheduler unterbrochen wird, nachdem er das Statement array[cnt] = elm; der  push() -Methode aufgerufen hat, und nun der zweite Thread laufen darf. Nachdem der zweite Thread die push() Methode vollständig ausgeführt hat, gibt es wieder einen Wechsel zum ersten Thread, der nun den Rest der push() -Methode ausführt. Ein solches Szenario ist in Abbildung 2 dargestellt. Natürlich ist eine solche Abfolge nicht zwingend, aber sie ist möglich.

Abbildung 1: Zwei Threads mit Zugriff auf ein gemeinsam verwendetes IntStack-Objekt

Abbildung 2: Verschränkter Ablauf der push()-Methode

Was ist bei einem solchen Ablauf mit dem Stack geschehen?

Der erste an der Stelle array[0] durch den ersten Thread eingetragene Wert ist sofort durch den zweiten Thread überschrieben worden, weil das cnt++ des ersten Threads wegen des Threadwechsels nicht ausgeführt werden konnte.

Das spätere Ausführen des cnt++ durch den ersten Thread führt dazu, dass der Stackpointer noch einmal verändert wird, obwohl sich an der Stelle array[1] gar kein zulässig eingetragener Wert befindet.

Grundlagen der Multithread-Programmierung

public class IntStack {
 private final int[] array;
 private int cnt = 0;

 public IntStack (int sz) { array = new int[sz]; }

 public void push (int elm) {
   if (cnt < array.length) array[cnt++] = elm;
   else throw new IndexOutOfBoundsException();
 }

 public int pop () {
   if (cnt > 0) return(array[--cnt]);
   else throw new IndexOutOfBoundsException();
 }

 public int peek() {
   if (cnt > 0) return(array[cnt-1]);
   else throw new IndexOutOfBoundsException();
 }

 public int size() { return cnt; }

 public int capacity() { return (array.length); }
}

Atomare Operationen

• Eintragen des int -Wertes in das Array und
• Verändern des Stackpointers cnt

Damit ergibt sich die Frage: Hätte uns diese kleine Veränderung vor einem Ablauf, wie weiter oben diskutiert, bewahrt? Mit anderen Worten: würde auf diese Weise kein Threadwechsel zwischen Eintragen des Wertes ins Array und Verändern des Stackpointers auftreten, da beide Aktionen jetzt in einem Statement sind?

Die kurze Antwort ist: Nein. Die ausführlichere Antwort lautet: Statementgrenzen haben keinerlei Einfluss auf das Threadscheduling.

Es gibt aber Operationen, die Einfluss auf das Threadscheduling haben, d.h. Operationen, die nicht vom Scheduler unterbrochen werden und damit garantiert vollständig ausgeführt werden. Solche Operationen werden als atomar bezeichnet. Laut Java Language Specification  sind die atomaren Operationen (a) die Lese- und Schreiboperationen für alle primitiven Datentypen außer double und long , sowie (b) das Lesen und Schreiben von Objektreferenzen. Die atomaren Operationen in Java sind damit deutlich feingranularer als ein Statement. Dass sie uns trotzdem weiterhelfen, werden wir zu einem späteren Zeitpunkt noch sehen.

Was die 64-bit Datentypen double und long angeht, so ermutigt die Java Language Specification die Anbieter von Virtuellen Maschinen sie so zu implementieren, dass auch für diese Datentypen Lese- und Schreiboperationen atomar sind. Trotzdem wird man als Java Nutzer aus Gründen der Portabilität den eigenen Code immer so implementieren, als wären sie nicht atomar.

Das abstrakte Problem

Das sind dann auch schon die beiden Aspekte, auf die man eine Methode im Multithread-Umfeld untersucht:

• Verändert sie Attribute, so dass diese während des Ablaufs der Methode irgendwann zueinander inkonsistent werden?
• Welche Attribute müssen konsistent sein, damit die Methode korrekt ausgeführt werden kann?

Konfliktmenge

Wenn man mit solchen Überlegungen noch nicht so vertraut ist, kann man das ganze relativ formal angehen, indem man sich die Kombination aller Methoden einer Klasse ansieht. Zur Verdeutlichung wollen wir hier das Beispiel mit den Methoden des IntStacks betrachten.  Die Tabelle aller relevanten Kombinationen von Methoden miteinander bildet eine Dreiecksmatix, weil das Problem symmetrisch ist:  wenn push() mit  pop() verträglich oder unverträglich ist, dann gilt das gleiche auch für die umgekehrte Kombination pop() und push() .
 

	push	pop	peek	size	capacity
push	push / push	push / pop	push / peek	push / size	push / capacity
pop		pop / pop	pop / peek	pop / size	pop / capacity
peek			peek / peek	peek / size	peek / capacity
size				size / size	size / capacity
capacity					capacity / capacity

Wir werden jetzt die einzelnen Kombinationen untersuchen und solche Kombinationen aus der Tabelle löschen, die ohne Probleme parallel ablaufen können. Was uns dann bleibt, ist die Menge an Kombinationen, bei denen es potenziell zu Konflikten kommen kann.

push/push

push/pop

pop/pop

push/peek, pop/peek

peek/peek

push/size, pop/size

peek/size, size/size

*/capacity

Unter Umständen stellt man sich die Frage, ob auch der Konstruktor bei der Ermittlung der Konfliktmenge zu berücksichtigen ist. Dem ist aber im allgemeinen nicht so. Die Begründung dafür ist: Zu dem Zeitpunkt, wenn der Konstruktor ausgeführt wird, gibt es noch keine Referenz auf das Objekt. Die Referenz auf das neu konstruierte Objekt wird ja erst als Ergebnis des new -Statements zurückgeliefert, also wenn die Ausführung des Konstruktors bereits beendet ist. Erst dann können die anderen Methoden auf dem Objekt aufgerufen werden.
Es gibt allerdings dennoch eine Situation, in der diese Argumentation nicht richtig ist, nämlich im Falle von Selbstregistrierung. Bei einer solchen Registrierung übergibt ein Objekt die eigene Selbstreferenz this im Konstruktor an ein anderes Objekt. Vom Registrierungszeitpunkt an kann diese Referenz dann auch von einem anderen Thread genutzt werden. In einem solchen Fall ist eine gewisse Vorsicht angebracht. Diese problematische Situation kann man vermeiden, wenn das Registrierungsstatement ans Ende des Konstruktors verschoben wird, aber das hilft nur, wenn die Klasse keine Subklassen hat. Einige zusätzliche Details zu dieser Situation finden sich in einem unserer vorhergehenden Artikel / KRE /, in dem wir diskutiert haben, dass Selbstregistrierung auch ohne Berücksichtigung von mehreren Threads bereits problematisch sein kann.
Zusammenfassend lässt sich sagen, dass wir im Fall des IntStack den Konstruktor nicht berücksichtigen müssen, da keine Selbstregistrierung im Konstruktor vorgenommen wird.
 

	push	pop	peek	size	capacity
push	push / push	push / pop	push / peek	-	-
pop		pop / pop	pop / peek	-	-
peek			-	-	-
size				-	-
capacity					-

 

Die Java Lösung: synchronized

public class IntStack {
 private final int[] array;
 private volatile int cnt = 0;

 public IntStack (int sz) { array = new int[sz]; }

 synchronized public void push (int elm) {
   if (cnt < array.length) array[cnt++] = elm;
   else throw new IndexOutOfBoundsException();
 }

 synchronized public int pop () {
   if (cnt > 0) return(array[--cnt]);
   else throw new IndexOutOfBoundsException();
 }

 synchronized public int peek() {
   if (cnt > 0) return(array[cnt-1]);
   else throw new IndexOutOfBoundsException();
 }

 public int size() { return cnt; }

 public int capacity() { return (array.length); }
}

Verwendung von volatile

Zusammenfassung

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)