Erzeuger-Verbraucher-Probleme

Bob und Lisa betreiben zusammen eine Pizzaria. Während Bob in der Küche die Pizzen bäckt, bedient Lisa die Kunden im Restaurantbereich. Zwischen den Bereichen befindet sich in der Wand eine Öffnung mit einem kleinen Tresen. Immer wenn Bob eine Pizza fertiggebacken hat, legt er sie auf den Tresen. Lisa schaut immer wieder beim Tresen vorbei und sieht nach, ob Pizzen draufliegen, die sie abholen und an die Tische bringen kann.

Lisa findet es anstrengend, immer wieder beim Tresen vorbeizuschauen um nachzusehen, ob neue Pizzen fertig sind.
Oft ist der Tresen aber auch voll und Bob muss warten, bis er neue Pizzen drauflegen kann.

Lisa schlägt vor, eine Tischglocke auf den Tresen zu stellen. Erklären Sie ihre Idee.

Das Erzeuger-Verbraucher-Problem tritt in der Informatik immer dann auf, wenn es Threads gibt, die Ressourcen erzeugen und in einem Ablagebereich mit beschränkter Kapazität ablegen während andere Threads, die Ressourcen aus dem Bereich entnehmen und verbrauchen.

Ein ungünstiger Lösungsansatz besteht im aktiven Warten, d.h. Erzeuger sehen immer wieder nach, ob der Ablagebereich wieder Platz hat um Ressourcen abzulegen und Verbraucher sehen immer wieder nach, ob im Ablagebereich schon wieder Ressourcen da sind um abgeholt zu werden.
Besser ist passives Warten:
- Der Erzeuger sieht nach, ob Platz im Ablagebereich ist.
  - Falls "ja", legt er Ressourcen ab und benachrichtigt den Verbraucher. Falls dieser im Wartezustand ist, "wacht er auf".
  - Falls "nein", geht er in einen Wartezustand, der keine Systemressourcen verbraucht.
- Der Verbraucher sieht nach, ob Ressourcen im Ablagebereich sind.
  - Falls "ja", nimmt er welche heraus und benachrichtigt den Erzeuger. Falls dieser im Wartezustand ist, "wacht er auf".
  - Falls "nein", geht er in einen Wartezustand, der keine Systemressourcen verbraucht.

Um passives Warten zu ermöglichen besitzt der Monitor die Methoden wait() (versetzt den aktuellen Thread in den Wartezustand) und notify() (holt einen der wartenden Threads aus dem Wartezustand).

Aktives Warten

Passives Warten

Das zentrale Element des nachfolgenden Programms sind die Methoden legPizzaDrauf und holPizzaAb:

class Tresen {
 
   int anzahlPizzen = 0;
 
   synchronized void legPizzaDrauf() {
      while (anzahlPizzen == 1) {
         wait();                        // aktueller Thread geht in den Wartezustand und blockiert
      }
      anzahlPizzen = 1;
      notify();                         // beliebigen Thread aus dem Wartezustand "aufwecken"
   }
 
   synchronized void holPizzaAb() {
      while(anzahlPizzen == 0) {
         wait();                       // aktueller Thread geht in den Wartezustand und blockiert
      }
      anzahlPizzen = 0;
      notify();                        // beliebigen Thread aus dem Wartezustand "aufwecken"
   }
 
}

In der folgenden Darstellung ist Bobs Thread blau gekennzeichnet, Lisas Thread grün. Die Stelle, an der sich der Thread jeweils befindet, ist mit einem Punkt gekennzeichnet. Der hellrot hinterlegte Bereich kennzeichnet das Tresen-Objekt mit seinen synchronized-Methoden und seinem Zustand (anzahlPizzen).

Stellen Sie sich mit Hilfe der Darstellung Bob und Alice vor, wie

sie sich unterschiedlich schnell im Kreis bewegen,
warten (wait()),
einander mit der Glocke bescheidgeben (notify())
und wie sich dabei jeweils der Zustand des Tresen-Objekts (d.h. anzahlPizzen) verändert.

Tidying up loose ends

In den obigen Erklärungen wurden ein paar Sachverhalte vereinfacht, damit Sie das Prinzip des passiven Wartens gut verstehen können. Vielleicht sind Ihnen daher ein paar kleinere Ungereimtheiten aufgefallen. Es wird Zeit, sie jetzt im Detail zu klären!

Solange es nur genau einen Erzeuger und genau einen Verbraucher gibt, könnte man statt der while-Loops in den Methoden legPizzaDrauf und holPizzaAb auch einfach nur if-statements verwenden. Sobald es mehrere Erzeuger/Verbraucher gibt, könnte es aber sein, dass ein Erzeuger durch das notify() eines anderen Erzeugers "aufgeweckt" wurde. In diesem Fall ist dann die while-loop unverzichtbar, da der Erzeuger "aufgeweckt" wurde ohne dass ein freier Platz im Austauschbereich geschaffen worden war.
In der Praxis könnte man in so einem Fall aber - noch besser - zwei unterschiedliche Monitore für Verbraucher und Erzeuger verwenden.
In den obigen Erklärungen wurde vereinfachend so getan, also ob der Aufruf von notify() durch den Erzeuger direkt den Verbraucher "aufweckt" (und umgekehrt), so dass letzterer sofort mit der Abarbeitung der Anweisung fortfährt, die auf die wait()-Anweisung folgt. Aber dann wären ja sowohl Erzeuger als auch Verbraucher gleichzeitig in der synchronized-Methode! Das darf nicht sein, denn nach dem notify() könnten ja ohne Weiteres noch weitere Anweisungen in der synchronized-Methode stehen.

In der Tat sind die Abläufe in der Realität etwas komplexer. Jeder Thread in Java hat einen Zustand (thread state), der die Werte new, runnable, running, waiting und terminated annehmen kann. Nur im Zustand running werden die Anweisungen des Threads ausgeführt.

Durch den Aufruf von wait() des Monitor-Objekts geht der Thread in den Zustand waiting über. Wird später irgendwann die Methode notify() des Monitor-Objekts aufgerufen, so geht einer der aktuell für diesen Monitor wartenden Threads in den Zustand runnable über, nicht jedoch in den Zustand running! Erst, wenn alle kritischen Bereiche des Monitors vom letzten Thread verlassen wurden, wird einer der Threads vom Zustand runnable in den Zustand running versetzt und setzt seine Ausführung fort.
Jedes Objekt in Java kann Monitor sein. Es
- "kennt" den Thread, falls sicher einer gerade in einem seiner kritischen Bereiche befindet,
- führt eine Liste aller ihm zugeordneten Threads im Zustand waiting und
- eine Liste aller ihm zugeordneten Threads im Zustand runnable.

Aufgaben

Aufgabe 1

Erweitern Sie den obigen Algorithmus zum passiven Warten so, dass es 10 Producer und 10 Verbraucher gibt und die Kapazität des Tresens erhöht werden kann (z.B. auf 3 Pizzen).
Sie werden dazu die Aufrufe von notify() durch notifyAll() ersetzen müssen. Erklären Sie, weshalb dies nötig ist und welchen Nachteil es mit sich bringt.

Lösung