Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- parallelism:deadlocks:start [2025/01/05 09:50] – Martin Pabst
+++ parallelism:deadlocks:start [2025/04/08 10:54] (aktuell) – [Aufgabe 1: Das Philosophenproblem] Martin Pabst
@@ Zeile 8: / Zeile 8: @@
 Die verfahrene Situation lässt sich auf übersichtliche Weise in einem **resource allocation graph** (deutsch: **Betriebsmittelzuteilungsgraph**) veranschaulichen:
 {{ :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.
+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. 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.
+  - **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.
+Hier noch ein Beispiel für einen resource allocation graph mit deadlock:
+{{ :parallelism:deadlocks:resource_allocation_graph.svg?500 |}}
 </WRAP>
+<WRAP center round todo 80%>
+**Aufgabe 1:** \\
+  * a) Stellen Sie dar, inwiefern die vier Coffman-Bedingungen im obigen Beispiel von Klaus und Lena erfüllt sind.
+  * b) Der Vater sagt zu Max: "Du bist der ältere, also gibst Du Lena jetzt den Startgriff, damit sie 5 Minuten lang mit dem Rotor spielen kann. Danach bist du 5 Minuten dran." \\ Welche der Coffman-Bedingungen hat der Vater damit außer Kraft gesetzt?
+</WRAP>
+===== Strategien, um Deadlocks zu verhindern =====
+<WRAP center round info 80%>
+Da Deadlocks nur dann auftreten können, wenn **alle vier Coffman-Bedingungen erfüllt** sind, reicht es, eine davon außer Kraft zu setzen, um Deadlocks sicher zu verhindern. Hier ein paar mögliche Strategien dazu:
+  * **hold and wait** kann ausgeschlossen werden, wenn jeder Thread zu Beginn alle Ressourcen anfordern muss, die er benötigt, und ihm das Betriebssystem nur entweder alle Ressourcen auf einmal zuspricht (und den Thread dann startet) oder keine Ressourcen zuspricht und den Thread so lange warten lässt, bis alle benötigten Ressourcen zur Verfügung stehen. Natürlich schränkt das die Möglichkeit zur nebenläufigen Ausführung möglichst vieler Threads etwas ein.
+  * **cyclic waiting** kann ausgeschlossen werden, indem die Ressourcen durchnummeriert werden und nur in der Reihenfolge dieser Nummerierung angefordert werden dürfen.
+  * **mutual exclusion** kann ausgeschlossen werden, wenn ein Betriebsmittel, das eigentlich nur ein Thread gleichzeitig benutzen kann (z.B. ein Drucker) mit einer Warteschlange versehen wird, in die die Threads ihre Aufträge an dieses Betriebsmittel ablegen können und ein eigener Thread die Warteschlange der Reihen nach abarbeitet.
+  * Der Ausschluss von **non-preemption** ist schwer machbar, kann aber beispielsweise beim Arbeitsspeicher umgesetzt werden, indem lange nicht verwendete Speicherbereiche des RAM in einen Massenspeicher (z.B. SSD) ausgelagert und nur bei Bedarf wieder zurückgeholt werden ("swapping").
+</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]]