Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- parallelism:deadlocks:start [2025/01/12 14:50] – [Deadlocks (Verklemmungen)] Martin Pabst
+++ parallelism:deadlocks:start [2025/04/08 10:54] (aktuell) – [Aufgabe 1: Das Philosophenproblem] Martin Pabst
@@ Zeile 9: / Zeile 9: @@
 {{ :parallelism:deadlocks:rotorspielzeug_graph.svg?500 |}}
 Es kommt hier zu einem **Deadlock** (deutsch: **Verklemmung**), bei dem keines der Kinder die angestrebte Tätigkeit ausführen kann, da ihm jeweils eine Ressource ("Betriebsmittel") fehlt. \\ \\
-Auch Threads benötigen oft Ressourcen (z.B. Schreibzugriff auf einen Speicherbereich, USB-Schnittstelle des Rechners, Drucker, Netzwerkschnittstelle) zu ihrer Ausführung. Sie beantragen den Zugriff darauf beim Betriebssystem und geben ihn später wieder zurück. Damit es zu einem Deadlock kommt, müssen die vier **Coffman-Bedingungen** erfüllt sein:
+Auch Threads benötigen oft Ressourcen (z.B. Schreibzugriff auf einen Speicherbereich, USB-Schnittstelle des Rechners, Drucker, Netzwerkschnittstelle) zu ihrer Ausführung. Sie beantragen den Zugriff darauf beim Betriebssystem und geben ihn später wieder zurück. Zu einem Deadlock kommt es dann und nur dann, wenn die vier **Coffman-Bedingungen** erfüllt sind:
   - **mutual exclusion (gegenseitiger Ausschluss)**: Auf eine gegebene Ressource kann nur jeweils ein einziger Prozess Zugriff haben.
   - **hold and wait (Halten und Warten)**: Hält ein Thread eine Ressource, so kann er zugleich andere beantragen.
@@ Zeile 35: / Zeile 35: @@
 </WRAP>
+<WRAP center round todo 80%>
+Aufgabe 2:
+Bearbeiten Sie Teilaufgabe III 2. im [[https://www.isb.bayern.de/fileadmin/user_upload/Gymnasium/Leistungserhebungen/Abiturpruefung/Informatik/informatik_2016_a.pdf|Abitur 2016]].
+</WRAP>
+==== 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>
+<HTML>
+<div class="java-online" style="height: 60vh; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'Philosophen'}">
+<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) {
+         forkLeft.take(color);
+         sleep(10);
+         forkRight.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;
+   Fork(int number) {
+      super(500, 300, 580, 300);
+      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();
+   }
+}
+</script>
+</div>
+</HTML>
+[[.philosophenloesung:start|Lösung]]