In den vorangegangenen Artikel dieser Reihe haben wir uns die Threadsynchronisation in Java angesehen.  Dazu kann man die implizite Locks (angesprochen durch das synchronized Schüsselwort) oder seit Java 1.5 explizite Locks (siehe Lock, ReentrantLock und ReentrantReadWriteLock im Package java.util.concurrent.locks) verwenden.  In diesem und dem nächsten Artikel wollen wir uns mit der Threadsynchronisation mit Hilfe von Signalen beschäftigen.  Dieses Mal sehen wir uns die traditionellen Mittel, nämlich die Methoden Methoden wait() und notify() (bzw. notifyAll()), ansehen. Im nächsten Artikel gehen wir u.a. auf die in Java 1.5 neue Condition ein.
 

Einleitung

Die Verwendung von Sperren ist eine Form der Threadsynchronisation in Java; es gibt eine weitere Form der Threadsynchronisierung in Java, die bewußter und aktiver von den an der Synchronisation teilnehmenden Threads gesteuert wird. Ein Beispiel für ihre Nutzung sind verschiedene Threads, die sowohl parallel als auch in mehreren Stufen hintereinander ein mathematisches Ergebnis berechnet sollen. Dabei können die Threads der nachfolgenden Stufe erst loslaufen, wenn sie die Ergebnisse der Threads der vorhergehenden Stufe erhalten haben. Diese Form der Synchronisation löst man nicht (oder besser gesagt: nicht allein) mit Sperren. Dazu bieten sich vielmehr die Methoden wait() und notify() (bzw. notifyAll()) an. Diese Methoden werden bereits von der obersten Superklasse Object zur Verfügung gestellt. Wie die Synchronisation mit wait() und notify() geht, wollen wir uns in diesem Artikel genauer ansehen.
 

Datenaustauch über den IntStack

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); }
}

Grundsätzlich kann man ein IntStack-Objekt für den Datenaustausch zwischen zwei Threads nutzten. Wie wir in den letzen Artikeln im Detail beschrieben haben, ist die obige Implementierung der Klasse IntStack threadsicher, so dass von zwei Threads parallel auf eine Instanz des IntStacks zugegriffen werden kann, ohne dass es dabei zu Problemen kommt. Was aber ist, wenn bei vollem Stack die Methode push() vom Produzenten aufgerufen wird? (Anmerkung: ein IntStack Objekt hat eine feste Größe und wächst nicht dynamisch.) Dann wird eine Runtime-Exception, nämlich IndexOutOfBoundsException, geworfen. Wenn der Produzent diese Exception richtig behandelt, funktioniert der Datenaustausch zwischen beiden Threads ohne Probleme. ‚Richtig behandeln’ heißt in diesem Fall: zu einem späteren Zeitpunkt noch einmal push() aufrufen und dabei hoffen, dass der Konsumenten-Thread zwischenzeitlich einen oder mehrere int-Werte abgeholt hat und damit Platz im Stack geschaffen hat. Um zu warten, könnte der Produzenten-Thread zum Beispiel Thread.sleep() mit einem geeigneten Timeout-Wert aufrufen, oder vorübergehend eine andere Tätigkeit ausführen, falls es eine solche für ihn gibt. Ein analoges Problem mit entsprechend ähnlicher Diskussion ergibt sich für den Konsumenten-Thread, wenn der Stack leer ist.

Wir haben es in der Einleitung schon angedeutet: in Java gibt es die Möglichkeit, dass sich Threads aktiv mit wait() und notify() (bzw. notifyAll()) synchronisieren. Dies ist in unserem Benutzungsszenario sicherlich eine attraktive Alternative zum Werfen und Behandeln der IndexOutOfBoundsException. Wir können den Stack mit wait() und notify() so implementieren, dass der Produzent bei vollem Stack warten muß, bis der Konsument ihn in Kenntnis setzt, dass wieder Platz im Stack ist. Und genauso kann der Produzent einem an einem leeren Stack wartenden Konsumenten mitteilen, dass im Stack ein neuer int-Wert eingetragen wurde.

Eine solche Lösung mit wait() und notify() hat den Vorteil, dass das Verhalten der Software bedeutend stabiler und damit deterministischer ist als bei einer Lösung, die auf Exceptions und Timeouts aufbaut. Das gilt insbesondere im Falle von Portierungen oder wenn weitere Threads hinzukommen, die auf das gleiche Ereignis warten. In der Lösung mit Exceptions und Timeouts muss sich der "wartende" Thread in der Zeit zwischen den Zugriffsversuchen irgendwie beschäftigen; er kann sich in einfachsten Fall einfach schlafen legen.  Die Zeit, die er im sleep() verbringt wird empirisch durch Ausprobieren ermittelt: wenn er zu lange schläft, verschläft er den Moment, in dem der Zugriff möglich gewesen wäre; wenn er zu schnell aufwacht, macht er zu viele zwecklose Zugriffsversuche.  Also probiert man einfach aus, welche "Zwischenzeit" am besten funktioniert. Wenn sich das Zeitverhalten der Applikation später ändert (durch Portierung auf eine andere Umgebung oder durch das Hinzufügen oder Ändern von Threads), dann muss die "Zwischenzeit" entsprechend angepasst werden. Wenn man die Anpassung vergißt, dann funktioniert die ganze Applikation u.U. nicht mehr.  Aus diesem Grunde ist die Lösung mit Exceptions und Timeouts relativ instabil und wenig empfehlenswert.  Die Lösung mit wait() und notify() (bzw. notifyAll()) ist wesentlich robuster.  Der wartende Thread muss nicht "erraten", wie lange er nun am sinnvollsten warten soll, sondern er bekommt im richtigen Moment ein Signal, auf das er dann reagieren kann.
 

wait(), notify() und notifyAll()

Die Semantik der Methoden lässt sich relativ einfach von ihren Namen ableiten. wait() wird von einem oder mehreren Threads aufgerufen, die auf das Eintreten einer benutzerspezifischen Bedingung warten. Korrespondierend dazu wird notify() bzw. notifyAll() von einem oder mehren Threads aufgerufen, die den wartendenden Threads signalisieren, dass die Bedingung, auf die sie warten, eingetroffen ist. notify() führt dazu, dass genau einer der wartenden Threads loslaufen darf, auch wenn mehr als ein Thread auf die Bedingung warten. Bei notifyAll() dürfen alle wartenden Threads loslaufen. Dabei ist zu beachten, dass die wartenden und die signalisierenden Threads wait() und notify() bzw. notifyAll() auf demselben Objekt aufrufen müssen. In Anlehnung an Multithread-APIs, die bereits vor Java existierten, nennt man dieses Objekt Bedingung (englisch: Condition).

Damit das Ganze so wie oben beschrieben funktioniert, muss jeder Thread, der wait(), notify() oder notifyAll() aufrufen will, vor dem Aufruf das Mutex des Objekts, das als Bedingung genutzt wird, sperren. Falls er das nicht tut, wird der Aufruf der jeweiligen Methode mit einer IllegalMonitorException abgebrochen. Das Sperren des Mutex sieht im Augenblick vielleicht eher wie eine künstliche Einschränkung aus. Wir werden aber am konkreten Beispiel sehen, dass dies ein subtiler Bestandteil der Threadsynchronisation mit wait() und notify() (bzw. notifyAll() ) ist.
 

Beispiel: BlockingIntStack

public class BlockingIntStack {

 // Konstruktor und Attribute wie bisher

 synchronized public void push (int elm) throws InterruptedException {
   while (cnt == array.length)
     wait();
   array[cnt++] = elm;
   notifyAll();
 }

 synchronized public int pop () throws InterruptedException {
   while (cnt == 0)
     wait();
   notifyAll();
   return(array[--cnt]);
 }

 // alle weiteren Methoden wie bisher

}

Fangen wir die Diskussion mit der Situation eines Produzenten an, der push() aufruft.  Wenn der Stack noch nicht voll ist (cnt < array.length),  wird die while-Schleife übersprungen, der int-Wert in das Array eingetragen und danach notifyAll() aufgerufen, um einem potentiell wartenden Konsumenten zu signalisieren, dass wieder ein neuer Wert im Stack verfügbar ist. Vor dem notifyAll() steht kein explizites Objekt, auf dem wir es aufrufen, d.h. wir rufen hier this.notifyAll() auf.  Da in der ursprünglichen Implementierung des IntStacks sowohl push() als auch pop() über den gesamten Ablauf der Methode das mit this assoziierte Mutex sperren, war es naheliegend, this auch als die Bedingung zu verwenden, auf der wait() und notifyAll() aufgerufen werden. So ist immer sichergestellt, dass das Mutex der Bedingung gesperrt ist, bevor wait() oder notifyAll() aufgerufen wird.

Was geschieht nun, wenn der Produzent push() bei vollem Stack (cnt == array.length) aufruft? Es wird in die while-Schleife verzweigt und wait() aufgerufen. Der Kontrollfluß kehrt erst aus dem wait() zurück, wenn eine InterruptedException geworfen wird oder notifyAll() auf unserer Bedingung this aufgerufen wird. Natürlich hätte auch der Aufruf von notify()eine Auswirkung auf unseren wartenden Thread. Aber notify() wird in unserer Implementierung nicht verwendet. Warum das so ist, diskutieren wir später.

Kommen wir zurück zu unserem Produzenten-Thread, der im wait()-Aufruf der push()-Methode darauf wartet, dass der Konsumenten-Thread die pop()-Methode aufruft (und dort insbesondere das notifyAll()), damit er wieder weiterlaufen kann.  Erinnern wir uns noch einmal daran, warum wir die push() und pop() Methode synchronized deklariert haben: damit die beiden Methoden push() und pop() nicht parallel ablaufen können, weil in beiden Methoden der Stackpointer cnt und der Inhalt des Arrays array konsistent verwaltet werden müssen. Das klingt jetzt wie ein Widerspruch: wie kann der Produzenten-Thread im wait() mitten in der push() Methode erwarten, dass ihn der Konsument-Thread durch Aufruf von notifyAll() in der pop() Methode anstößt? Der Produzenten-Thread hält das Mutex, das der Konsumenten-Thread benötigt, um pop() auszuführen. An dieser Stelle kommt ein allgemeines Muster aus der Multithread-Programmierung zum tragen: mit dem Aufruf von wait() wird automatisch die Sperre des Mutex, auf dem wait() aufgerufen wurde, freigegeben. Das ist der Knackpunkt. Damit ist es für den Konsumenten-Thread möglich, seinerseits die Sperre des Mutex zu bekommen und pop() bzw. notifyAll() aufzurufen.

Man kann noch auf die Idee kommen, dass die Reihenfolge der Statements am Ende von pop() anders sein sollte, denn immerhin wird erst notifyAll() aufgerufen und dann erst Platz für einen neuen Werte im Stack geschaffen (return(array[--cnt])).  Sollte man nicht besser den Wert aus dem array in eine temporäre Variable schreiben, dann notifyAll() aufrufen und danach die temporäre Variable zurückgeben? Schließlich weckt der Aufruf von notifyAll() den wartenden Produzenten-Thread. Das ist aber in Ordnung so. Es besteht nicht die Gefahr, dass der Produzenten-Thread sofort losläuft, denn er benötigt noch die Sperre des mit this assoziierten Mutex und diese wird vom Konsumenten-Thread bis zum Ende von pop() gehalten.

Die Abbildung 1 zeigt noch einmal als Sequenzdiagramm den oben beschriebenen Ablaufs.

Für einen Konsumenten-Thread, der an einem leeren Stack wartet funktioniert unsere Implementierung ganz analog.

Abbildung 1: Synchronisation von push() und pop() über wait() und notifyAll()

notify() oder notifyAll()

Fangen wir mit etwas Naheliegendem an. Warum benutzen wir nicht notify() statt notifyAll()? Zugegeben, in unserem einfachen System mit einem Produzenten und einem Konsumenten, würde dies sogar funktionieren.

In Java ist man häufig dazu gezwungen, an einer Bedingung verschiedene logische Bedingungen zu signalisieren. Mit anderen Worten: man ruft wait() und notify() bzw. notifyAll() für logisch ganz verschiedene Bedingungen auf. Schon in unserem Fall ist das so: an der Bedingung this wartet man bei vollem und bei leerem Stack und es wird signalisiert, dass der Stack nicht mehr leer oder nicht mehr voll ist. Prinzipiell kann die Verwendung von notify() statt notifyAll()in einer solchen Situation (eine Bedingung für mehrer logische Bedingungen) zu Problemen führen. In unserem Beispiel treten keine Probleme auf, weil sich die beiden Bedingungen "Stack leerW" und "Stack voll" logisch ausschließen.

Also nehmen wir noch eine dritte Bedingung hinzu, die sich mit einer der beiden vorhergehenden überlappt. Nehmen wir an, wir haben zwei Sorten von Produzenten: hochpriore, die bei vollem Stack warten müssen (wie bisher) und niedrigpriore, die schon bei halbvollem Stack aufhören müssen. Die Threadnamen der hochprioren Produzenten-Threads beginnen mit HighPriorityProducer. Die Implementierung der push() Methode sieht dann folgendermaßen aus:

synchronized public void push (int elm) throws InterruptedException {
  if (Thread.currentThread().getName().startsWith("HighPriorityProducer")) {
    while (cnt >= array.length)
      wait();
  }
  else {
    while (cnt >= (array.length / 2))
      wait();
  array[cnt++] = elm;
  notifyAll();
}

Wie sieht das Ganze nun aus, wenn wir bei vollem Stack einen wartenden HighPriorityProducer und einen wartenden LowPriorityProducer haben und vom Konsumenten im pop() nur notify() statt notifyAll() aufgerufen wird? Die Java Language Specification macht keine Aussage, welcher wartende Thread bei einem notify() loslaufen darf. Das heißt, in unserem Fall könnte dies sowohl der HighPriorityProducer als auch der LowPriorityProducer sein. Falls es der LowPriorityProducer ist, stellt er in seiner while-Bedingung fest, dass er noch nicht weiterlaufen darf, und geht wieder in den wait(). Damit geht das Notifikationssignal ungenutzt verloren, weil es nicht den richtigen Empfänger erreicht. Abhängig vom konkreten Programm kann so ein Signalverlust unter Umständen zum vollständigen Stillstand des Programms führen.

Wie sieht das Ganze aus, wenn in dieser Situation vom Konsumenten im pop() die Methode notifyAll() anstelle von notify() aufgerufen wird? Dann wäre nach dem LowPriorityProducer, der mit dem Signal nichts anfangen kann, auch der HighPriorityProducer an die Reihe gekommen und hätte sein push() zu Ende ausführen können.

Bleibt noch die Frage, wie der Ablauf aussieht, wenn zwei HighPriorityProducer am vollen Stack warten und in pop() vom Konsumenten notifyAll() aufgerufen wird. Laufen dann beide HighPriorityProducer Threads? Ja und nein. Einer der beiden HighPriorityProducer wird als erster das Mutex bekommen und ein neues Element in den Stack schreiben. Wenn der zweite HighPriorityProducer danach das Mutex bekommt, durchläuft er zunächst die while-Bedingung (cnt >= array.length). Da diese nun wieder wahr ist (der erste HighPriorityProducer hat den Stack ja wieder aufgefüllt), bleibt dem zweiten HighPriorityProducer nicht anderes, als wieder wait() aufzurufen.

Diese vorhergehende Diskussion beantwortet eine weitere Frage, die wir bisher noch gar nicht explizit gestellt haben: warum wird in der Abfrage der logischen Bedingung while und nicht if verwendet? Das Beispiel mit den zwei wartenden HighPriorityProducern hat deutlich gemacht, dass in einer solchen Situation while benötigt wird. Es gibt noch einen weiteren Grund, der erst mit der Arbeit am JSR-133 (Java Memory Model) explizit in die Java Spezifikation (siehe / JMM /) aufgenommen wurde:  es ist erlaubt, dass eine JVM (Java Virtual Machine) so implementiert ist, dass sie sogenannte "spurious wake-ups" macht. Das bedeutet, dass der Aufruf von wait() "versehentlich" zurückkommt, d.h. ohne dass ein notify() oder notifyAll() auf der Condition aufgerufen wurde.  Es ist also auf jeden Fall sinnvoll, wenn der Thread sich nach dem Aufwachen erst einmal vergewissert, ob die logische Bedingung, auf die er gewartet hat, überhaupt eingetreten ist und sich ggf. wieder in den Wartezustand begibt.

Zusammenfassend läßt sich zur Verwendung von notify() vs. notifyAll() sagen, dass in Situationen, in denen nur ein logischer Zustand ein einer Condition signalisiert wird, notify() ausreichend ist. Die Nutzung von notifyAll() führt aber zu Code, der gerade im Fall von Änderungen stabiler ist.
 

Weitere Variationen

 synchronized public void push (int elm) throws InterruptedException {
   while (cnt == array.length)
     wait();
   if (cnt == 0)
     notifyAll();
   array[cnt++] = elm;
 }

 synchronized public int pop () throws InterruptedException {
   while (cnt == 0)
     wait();
   if (cnt == array.length)
     notifyAll();
   return(array[--cnt]);
 }

private void handlePopCondition() throws InterruptedException {
   while (cnt == 0)
     wait();
}

private void signalNotFullAnymore() {
   if (cnt == array.length)
     notifyAll();
}

synchronized public int pop () throws InterruptedException {
   handlePopCondition();
   signalNotFullAnymore();
   return(array[--cnt]);
 }

Da der Java-Compiler private Methoden inlinen kann, ergibt sich aus der Restrukturierung auch kein Performanceverlust.

Eine weitere Variante besteht darin, den Zustand explizit sichtbar zu machen, beispielsweise indem eine Zustandsvariable eingeführt und verwaltet wird.  In unserem Beispiel könnte diese Zustandsvariable die Zustände "voll", "mittel", "leer" haben.  Im Fall unseres Stacks ist eine explizite Zustandsvariable nicht unbedingt nötig, da die Werte des Stackpointers cnt schon recht signifikant und aussagekräftig sind. In komplexeren Situationen kann eine Zustandsvariable aber durchaus hilfreich sein, um den Code verständlicher und damit wartbarer zu machen.

Zustandsabhängige Operationen

In einer Singlethread-Umgebung macht eine wartende Lösung keinen Sinn. Worauf soll der einzige Thread beim push() auf einen vollen Stack warten? Es gibt niemandem außer ihm selbst, der die Rolle des Konsumenten übernehmen kann. Es macht also durchaus Sinn, wenn einer Singlethread-Umgebung der push() auf einen vollen Stack mit einer Exception scheitert. Dabei ist auch angemessen, eine RuntimeException zu verwenden (beim  IntStack: IndexOutOfBoundsException) .  Da der Thread die Größe des Stacks kennt (er hat das Stackobjekt selbst erzeugt), sollte er ähnlich wie bei einem built-in-Array wissen, wann er an die Kapazitätsgrenzen stößt.

In einer Multithread-Umgebung ist wiederum eine Abstraktion, die den Methodenaufruf mit einer Exception zurückweist, nicht so gut zu gebrauchen. Wir haben das Problem bereits diskutiert. Es besteht darin, dass der zurückgewiesene Thread auf sinnvolle Art darauf warten muss, dass sich der Zustand der Abstraktion ändert und die Operation zugelassen wird. Schwieriger wird es noch, wenn mehr als ein Thread auf diese Zustandsänderung warten. Grundsätzlich aber ist es möglich, dass eine zurückweisende Abstraktion auch in einer Multithread-Umgebung genutzt wird. Vielleicht sollte man dann aber bei der Zurückweisung keine RuntimeException, sondern eine zu überprüfte (checked) Exception verwenden.
 
 

Zusammenfassung

Dabei sind diverse Details zu beachten. Wir haben den Unterschied zwischen notify() und  notifyAll() diskutiert. Dabei hat sich herausgestellt, dass die robusteste Art der Verwendung von wait() und notify() darin besteht, in einer while-Schleife den Zustand abzufragen und danach per wait() zu warten, während der signalisierende Thread die Benachrichtigung per notifyAll() an alle wartenden Threads (und nicht per notify() an nur genau einen Thread) versendet.
 
 

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)