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.
==== Aufgabe 1: Das Philosophenproblem =====
<WRAP center round info 80%>
Das Philosophenproblem wurde vom Informatiker [[https://de.wikipedia.org/wiki/Edsger_W._Dijkstra|Edsger W. Dijkstra]] formuliert um die Problematik der Nebenläufigkeit/Verklemmung zu illustrieren. \\ \\ 
"Fünf Philosophen, nummeriert von eins bis fünf, leben in einem Haus, in dem der Tisch für sie gedeckt ist, wobei jeder Philosoph seinen eigenen Platz am Tisch hat. Ihr einziges Problem – neben dem der Philosophie – ist, dass es sich bei dem servierten Gericht um eine sehr schwierige Sorte Spaghetti handelt, die mit zwei Gabeln gegessen werden muss. Zwischen den Tellern befindet sich jeweils eine Gabel, sodass dies für einen einzelnen Philosophen kein Problem darstellt. Allerdings können zwei Nachbarn nicht gleichzeitig essen." [[https://de.wikipedia.org/wiki/Philosophenproblem|(Quelle: Wikipedia-Artikel)]]
</WRAP>

<WRAP center round todo 80%>
  * a) Erläutern Sie, inwiefern die Coffman-Bedingungen erfüllt sind.
  * b) Starten Sie das untenstehende Programm und untersuchen Sie, ob es zu einer Verklemmung kommt. Welche Rolle spielen die ''sleep''-Anweisungen?
  * c) Ändern Sie das Programm so ab, dass die Bedingung "cyclic waiting" nicht mehr zutrifft und verifizieren Sie, dass damit die Verklemmung nicht mehr auftritt.
  * d) Ändern Sie das Programm so ab, dass eine andere der Coffman-Bedingungen nicht mehr zutrifft. Erläutern Sie Ihr Vorgehen.
</WRAP>

===== Lösung zu Teilaufgabe a) =====
  - **mutual exclusion (gegenseitiger Ausschluss)** ist in diesem Fall erfüllt, weil eine Gabel zu einem gegebenen Zeitpunkt jeweils nur von einem Philosophen gehalten werden kann.
  - **hold and wait (Halten und Warten)**: ist 
  - **non preemption (Ununterbrechbarkeit)**: Der Zugriff eines Threads auf eine Ressource kann nicht unterbrochen werden, d.h. dem Thread kann die Ressource nicht von außen entzogen werden (z.B. durch das Betriebssystem)
  - **cyclic waiting (zyklisches Warten)**: Im resource allocation graph gibt es mindestens einen Zyklus.

===== Lösung zu Teilaufgabe c) =====
<HTML>

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

<script type="text/plain" title="Philosophen.java">
new Main().setup();

class Main {
   
   int[] colors = { 0xff0000, 0x00ff00, 0x0000ff, 0x9614d3, 0xf5e400 };

   void setup() {
      Fork[] forks = new Fork[5];
      for (int i = 0; i < 5; i++) {
         forks[i] = new Fork(i);
      }

      for (int i = 0; i < 5; i++) {
         new Philosopher(i, colors[i], forks[(5 + i - 1) % 5], forks[i]).start();
      }
   }

}


class Philosopher extends Thread {
   
   int color;
   Fork forkLeft;
   Fork forkRight;

   Philosopher(int number, int color, Fork forkLeft, Fork forkRight) {
      Circle circle = new Circle(600, 300, 50);
      circle.rotate(360 / 5.0 * number, 400, 300);
      circle.setFillColor(color); 
      this.color = color;
      this.forkLeft = forkLeft;
      this.forkRight = forkRight;
   }

   public void run() {
      while (true) {
         if(forkLeft.getNumber() < forkRight.getNumber()) {
            forkLeft.take(color);
            sleep(10); 
            forkRight.take(color);
         } else {
            forkRight.take(color);
            sleep(10); 
            forkLeft.take(color);
         }
         
         println("Philosopher eats", color);
         sleep(100);   // eat

         forkRight.put();
         forkLeft.put();
         
         println("Philosopher talks", color);
         sleep(10);   // talk ;-)
      }
   }

}


class Fork extends Line {
   
   static final int gray = 0x808080;
   int color = gray;
   private int number;

   Fork(int number) {
      super(500, 300, 580, 300);
      this.number = number;
      setBorderColor(color);
      rotate(360 / 10.0 + 360 / 5.0 * number, 400, 300);
   }

   synchronized void take(int newColor) {
      if(color != gray) {
         wait();
      }
      color = newColor;
      setBorderColor(newColor);
   }

   synchronized void put() {
      color = gray;
      setBorderColor(gray);
      notify();
   }

   public int getNumber() {
      return number;
   }
}
</script>

</div>

</HTML>