Informatik 12/13 (G9)

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Erzeuger-Verbraucher-Probleme ======
<WRAP center round tip 80%>
{{ :parallelism:producerconsumer:producerconsumerintroduction.svg?400|}}
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.
{{:parallelism:producerconsumer:bell.svg?50 |}}
Lisa schlägt vor, eine Tischglocke auf den Tresen zu stellen. Erklären Sie ihre Idee.
</WRAP>

<WRAP center round info 80%>
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).
</WRAP>

===== Aktives Warten =====
<HTML>

<div class="java-online" style="height: 60vh; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'ActiveWaiting1'}">

<script type="text/plain" title="ActiveWaiting1.java">
Tresen t = new Tresen();
new Bob(t, 1e2).start();
new Lisa(t).start();



class Bob extends Thread {
   Tresen tresen;
   int anzahlPizzenTodo;
   
   Bob(Tresen tresen, int anzahlPizzenTodo) {
      this.tresen = tresen;
      this.anzahlPizzenTodo = anzahlPizzenTodo;
   }

   public void run() {
      while (anzahlPizzenTodo > 0) {
         Thread.sleep(Random.randint(10, 100));
         anzahlPizzenTodo -= tresen.legPizzaDrauf();
      }
      println("Bob ist fertig!", Color.aquamarine);
      System.exit(0);
   }

}

class Lisa extends Thread {
   Tresen tresen;
   int anzahlPizzenServiert = 0;

   Lisa(Tresen tresen) {
      this.tresen = tresen;
   }

   public void run() {
      while (true) {
         Thread.sleep(Random.randint(10, 100));
         anzahlPizzenServiert += tresen.holPizzaAb();
         if(anzahlPizzenServiert % 10 == 0) {
            println(anzahlPizzenServiert + " Pizzen serviert.");
         }
      }
   }

}

class Tresen {
   
   int anzahlPizzen = 0;

   /*
    * Gibt die Anzahl draufgelegter Pizzen zurück
    */
   synchronized int legPizzaDrauf() {
      if(anzahlPizzen == 0) {
         anzahlPizzen = 1;
         return 1;
      } else {
         println("Bob kann nichts drauflegen.", Color.chocolate);
         return 0;
      }

   }

   /**
    * Gibt die Anzahl abgeholter Pizzen zurück
    */
   synchronized int holPizzaAb() {
      if(anzahlPizzen == 1) {
         anzahlPizzen = 0;
         return 1;
      } else {
         println("Lisa hat umsonst nachgesehen.", Color.red);
         return 0;
      }

   }

}
</script>

</div>

</HTML>


===== Passives Warten =====
<WRAP center round info 80%>
Das zentrale Element des nachfolgenden Programms sind die Methoden ''legPizzaDrauf'' und ''holPizzaAb'':
<code java>
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"
   }

}
</code>
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.
{{ :parallelism:producerconsumer:passiveswarten1.svg?800 |Passives Warten}}
</WRAP>


<HTML>

<div class="java-online" style="height: 60vh; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'PassiveWaiting1'}">

<script type="text/plain" title="PassiveWaiting1.java">
Tresen t = new Tresen();
new Bob(t, 100).start();
new Lisa(t).start();



class Bob extends Thread {
   Tresen tresen;
   int anzahlPizzenTodo;
   int lastTimePizzaBaked = System.currentTimeMillis();

   
   Bob(Tresen tresen, int anzahlPizzenTodo) {
      this.tresen = tresen;
      this.anzahlPizzenTodo = anzahlPizzenTodo;
   }

   public void run() {
      while (anzahlPizzenTodo > 0) {
         tresen.legPizzaDrauf();
         anzahlPizzenTodo--;

         // Wir warten, bis Bob die nächste Pizza gebacken hat.
         // Das ist nicht informatikrelevant, macht den Vergleich mit 
         // aktivem Warten aber realistischer.
         int timeToBakeNextPizza = Random.randint(10, 100);
         int timeSinceLastPizzaBaked = System.currentTimeMillis() - lastTimePizzaBaked;
         if(timeSinceLastPizzaBaked < timeToBakeNextPizza) {
            Thread.sleep(timeToBakeNextPizza - timeSinceLastPizzaBaked);
            lastTimePizzaBaked = System.currentTimeMillis();
         }

      }
      println("Bob ist fertig!", Color.aquamarine);
      System.exit(0);
   }

}

class Lisa extends Thread {
   Tresen tresen;
   int anzahlPizzenServiert = 0;

   Lisa(Tresen tresen) {
      this.tresen = tresen;
   }

   public void run() {
      while (true) {
         tresen.holPizzaAb();
         anzahlPizzenServiert++;
         if(anzahlPizzenServiert % 10 == 0) {
            println(anzahlPizzenServiert + " Pizzen serviert.");
         }
         // Lisa bringt jetzt die Pizza zu den Kunden:
         Thread.sleep(Random.randint(10, 100)); 
      }
   }

}

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

}</script>

</div>

</HTML>

==== Tidying up loose ends ====

<WRAP center round tip 80%>
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. 
{{ :parallelism:producerconsumer:java-threadstates.svg?600 |}}
  * 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''.
</WRAP>

===== Aufgaben =====
==== Aufgabe 1 ====
<WRAP center round todo 80%>
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. \\ \\ 
[[.aufgabe1loesung:start|Lösung]]
</WRAP>