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.
Das folgende Video veranschaulicht diese beiden Schritte:
Wenn (mindestens ein) Zyklus im Graphen vorhanden ist, dann liegt ein Deadlock vor.
Wenn Sie dieses Element öffnen, werden Inhalte von externen Dienstleistern geladen und dadurch Ihre IP-Adresse an diese übertragen.
Ein Betriebsmittelgraph wird in gängiger Literatur alternativ auch Belegungs-Anforderungs-Graph genannt.
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!
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:
Zeichne den Betriebsmittelgraph! Achte dabei auf die Pfeilrichtungen!
Offensichtlich liegt hier ein Deadlock vor.
Wie man sieht, hilft der Betriebsmittelgraph tatsächlich bei der Erkennung eines Deadlocks. Aber:
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:
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.
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:
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.
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.
Wie oft sollte ein Betriebssystem die Suche nach einem eventuell existenten Deadlock durchführen?
Die pragmatischte Antwort lautet immer: "Es kommt darauf an!"
Dann erläutere doch mal: Worauf kommt es an?
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