Deadlocks erkennen

Die vierte der gerade beschriebenen Bedingungen (Circular wait condition) 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.

Betriebsmittelgraph

Das folgende Video veranschaulicht diese beiden Schritte:

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

Wenn (mindestens ein) Zyklus im Graphen vorhanden ist, dann liegt ein Deadlock vor.

video

YouTube

Wenn Sie dieses Element öffnen, werden Inhalte von externen Dienstleistern geladen und dadurch Ihre IP-Adresse an diese übertragen.

Inhalt ansehen und nicht erneut fragen

 Med. 31: Deadlocks erkennen mit Hilfe eines Betriebsmittelgraphen (09:46)

http://youtu.be/mhrohwfGQU0

CC-BY

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

Aufgabe 1

Aufgabe

 Aufg. 142: Deadlocks erkennen mit Hilfe eines Betriebsmittelgraphen

Mache dich mit dem Tutorial Deadlock-Algorithmen der Universität Oldenburg vertraut und vollziehe insbesondere die beiden Schritte Konstruktion und Überprüfung des Betriebsmittelgraphen nach!

Aufgabe 2

Aufgabe

 Aufg. 143: 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 konstruieren 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 erläutert, 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.

Es ist jetzt also klar, dass ein Betriebssystem die folgenden beiden Dinge tun muss, um einen gegebenenfalls vorhandenen Deadlock-Zustand zu erkennen:

1. Konstruiere den aktuellen Betriebsmittelgraphen,
   d.h. repräsentiere ihn als interne Datenstruktur.
   
   
2. Überprüfe den Graphen auf einen Zyklus,
   d.h. überprüfe die interne Datenstruktur entsprechend.

Falls ein Zyklus erkannt wird, so liegt ein Deadlock vor, und es können auch die beteiligten Prozesse und Ressourcen identifiziert werden.

Falls kein Zyklus erkannt wird, so besteht die Gewissheit, dass "alles in Ordnung" ist, d.h. es liegt kein Deadlock vor.

Aufgabe 3

Aufgabe

 Aufg. 144: Was tun bei erkanntem Deadlock?

Was sollte das Betriebssystem tun, wenn es einen Deadlock erkannt und die zugehörigen Prozesse und Betriebsmittel identifiziert hat?

Überlege, recherchiere und diskutiere in deiner Lerngruppe! Schätze für jeden Vorschlag auch die möglichen Folgen ab.

Aufgabe 4

Aufgabe

 Aufg. 145: Wie oft nach einem Deadlock suchen?

Wie oft sollte ein Betriebssystem die Suche nach einem eventuell existenten Deadlock durchführen?

• Einmal pro Sekunde?
• Einmal pro Minute?
• Einmal pro Stunde?
• Einmal am Tag?
• etc.

Die pragmatischte Antwort lautet immer: "Es kommt darauf an!"

Dann erläutere doch mal: Worauf kommt es an?

• Welche Situationen oder Einsatzzwecke für Betriebssysteme sind vorstellbar, bei denen eine Suche nach Deadlocks in kürzeren oder längeren Zeitabständen durchgeführt werden sollte?
• Welche Vor- oder Nachteile hat eine (zu) häufige oder (zu) seltene Suche?

Vielleicht liefert die Antwort auf die letzte Aufgabe ja auch Gründe für das nächste Thema: Deadlocks ignorieren.

---

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