Deadlocks

{{#index:Deadlock|Verklemmung|Deadlock-Zustand|Zustand, Deadlock}} Deadlocks sind eine unangenehme Sache, sie sollten besser nicht auftreten. Zunächst die Definition:

Definition: Deadlock-Zustand

Definition

Eine Menge von Prozessen befindet sich nach Tanenbaum 2009 in einem Deadlock-Zustand, wenn jeder Prozess aus der Menge auf ein Ereignis wartet, das nur ein anderer Prozess aus der Menge auslösen kann.

Wenn sich mehrere Prozesse in einem Deadlock-Zustand befinden, so sagt man auch vereinfachend: Es ist ein Deadlock aufgetreten.

In der realen Welt gibt es eine schöne Analogie zum Deadlock-Zustand von Prozessen:

Aus der Praxis

Wenn du dir vorstellen kannst, dass ein Auto im Strassenverkehr einen Prozess repräsentiert, dann zeigt dieses Bild einen Deadlock-Zustand einer Menge von Autos. (Hier gibt es eine kleine Sammlung mit ähnlichen Fotos.)

In Anbetracht dieser Bilder kannst du überlegen, ob die Menge der Prozesszustände noch um einen ergänzt werden sollte. Welcher Zustand ist damit gemeint?

Lösung

Aufgabe 1

Aufgabe

 Aufg. : Deadlock-Philosophen

Mandl 2013 geht am Ende von Kapitel 6.2.2 auf das Philosophenproblem und eine dabei bestehende Deadlock-Gefahr ein.

Erläutere:

• Unter welcher Bedingung tritt bei den speisenden Philosophen ein Deadlock-Zustand ein?
• Welche Rolle spielt eine atomare Aktion dabei?

Vier Bedingungen für einen Deadlock

Eine grundlegende Arbeit über System Deadlocks veröffentlichten E.G. Coffman, Jr.; M.J. Elphick und A. Shoshani im Jahre 1971 in der Zeitschrift Computing Surveys, Vol. 3, No. 2; (hier ist ein alternativer Link zu diesem Dokument).

Sie beschreiben darin vier Bedingungen, welche allesamt eingetreten sein müssen, und damit einen Deadlock-Zustand verursacht haben:

1. Mutal exclusion condition
   Eine Ressource steht einem Prozess nur exklusiv zur Verfügung, sie kann also nicht gleichzeitig von mehreren Prozessen belegt werden.
2. Wait for condition
   Prozesse warten und behalten dabei die Kontrolle über bereits zugewiesene Ressourcen solange, bis sie alle Ressourcen zugesprochen bekommen haben, um schließlich ihre Arbeit fortführen zu können.
3. No preemtion condition
   Zugewiesene Ressourcen können einem Prozess nicht gewaltsam wieder entrissen werden.
4. Circular wait condition
   Es gibt eine zyklische Kette von Prozessen, die bereits eine oder mehrere Ressourcen zugeweisen bekommen haben, und die gleichzeitig auf weitere Resourcen warten, welche bereits dem jeweils nächsten Prozess in der Kette zugesprochen wurden.

Deadlocks erkennen

Die vierte der gerade beschriebenen Bedingungen liefert eine Möglichkeit, nach der ein bereits eingetretener Deadlock-Zustand auf einem System entdeckt werden kann. Man realisiert dies durch die Konstruktion eines speziellen Graphen, der anschließend untersucht wird. Die folgenden Aufgaben beschäftigen sich damit.

Aufgabe 2

{{#index:Betriebsmittelgraph|Belegungs-Anforderungs-Graph|Zyklus im Betriebsmittelgraph|Konstruktion Betriebsmittelgraph}}

Aufgabe

 Aufg. : Deadlocks erkennen mit Hilfe eines Betriebsmittelgraphen

Die Universität Oldenburg stellt ein Tutorial Deadlock-Algorithmen bereit, bei dem u.a. auf die Erkennung eines Deadlock-Zustands eingegangen wird. Insbesondere kann die Erkennung mit Hilfe zweier Schritte erfolgen:

• Schritt 1: Konstruktion eines Betriebsmittelgraphen
• Schritt 2: Überprüfung eines Betriebsmittelgraphen auf Zyklen

Mache dich mit diesem Tutorial vertraut!

Ein Betriebsmittelgraph wird in gängiger Literatur alternativ auch Belegungs-Anforderungs-Graph genannt.

Aufgabe 3

Aufgabe

 Aufg. : Zeichne den Betriebsmittelgraph und erkenne den Deadlock!

Gegeben seien die Prozesse P1 bis P5 und die Ressourcen Drucker, Plotter, Modem, Magnetbandlaufwerk sowie Diskettenlaufwerk und CD-ROM-Laufwerk. Jede Ressource sei genau einmal vorhanden.

Aktuell besteht folgende Ressourcenzuteilung und -anforderung:

• P1 belegt Plotter und fordert Diskettenlaufwerk an.
• P2 belegt Magnetbandlaufwerk und fordert Plotter und Modem an.
• P3 belegt Modem und fordert Drucker an.
• P4 belegt Drucker und fordert CD-ROM-Laufwerk an.
• P5 belegt Diskettenlaufwerk und fordert Magnetbandlaufwerk an.

Zeichne den Betriebsmittelgraph! Achte dabei auf die Pfeilrichtungen!

Offensichtlich liegt hier ein Deadlock vor.

• Woran ist dies im Betriebsmittelgraphen erkennbar?
• Welche Prozesse sind daran beteiligt?

Wie man sieht, hilft der Betriebsmittelgraph tatsächlich bei der Erkennung eines Deadlocks. Aber:

Hinweis

Wenn du die letzte Aufgabe zum Betriebsmittelgraphen durchgeführt hast, dann hast du (ein Mensch!) den Deadlock erkannt.

Eigentlich ist es aber die Aufgabe des Betriebssystems einen Deadlock zu erkennen!

Die Frage ist also:

Frage

Kann ein Betriebssystem auch einen Betriebsmittelgraphen konstuieren und einen Zyklus darin erkennen?

Die Antwort ist: ja, das geht!

Prof. Dr. Holger Schlingloff vom Institut für Informatik der Humboldt-Universität zu Berlin geht darauf in seinem Aufsatz Zyklensuche (hier auch als PDF) ein.

Hinweis

Es wird an dieser Stelle nicht näher darauf eingegangen, wie die Graphenkonstruktion (bzw. -repräsentation) im Rechner, sowie die anschließende Zyklensuche abläuft.

Es sei aber darauf verwiesen, dass diese Tätigkeit eine Reihe anderer Dinge benutzt, die für Studierende an Hochschulen üblicherweise in Vorlesungen zur Mathematik oder zu Algorithmen und Datenstrukturen behandelt werden.

Falls du diese Vorlesungen bereits gehört hast, kommen dir diese Stichwörter vielleicht bekannt vor: Adjazenzmatrix, Nachbarschaftsliste, Rekursion, Tiefensuche, Breitensuche.

Nachdem jetzt also klar ist, dass die Forschung der vergangenen Jahrzehnte die nötigen Möglichkeiten entwickelt hat, um (Betriebsmittel-) Graphen in einem Rechner (und damit vom Betriebssystem) zu repräsentieren, um diesen anschließend auf Zyklen zu untersuchen, kann man noch einige praktische Überlegungen in Zusammenhang mit Betriebssystemen anstellen.

Deadlocks ignorieren

Eine durchaus gängige Methode im Umgang mit Deadlocks ist das Ignorieren:

Aus der Praxis

"Es gibt keine Deadlocks, weil ich daran glaube, dass es keine Deadlocks gibt!", sagt das Betriebssystem.

Rechtfertigen kann man diese Haltung, wenn die Wahrscheinlichkeit des Auftretens eines Deadlocks gering ist, und gleichzeitig die Folgen eines aufgetretenen Deadlocks "nicht dramatisch" sind (wie immer man "dramatisch" dann auch definieren möchte).

Allgemein ist davon auszugehen, dass die automatische Erkennung und Behandlung von Deadlocks sehr aufwendig, und damit sehr teuer ist.

---

_{Diese Seite steht unter der Creative Commons Namensnennung 3.0 Unported Lizenz http://i.creativecommons.org/l/by/3.0/80x15.png}