Navigationsleiste oben Startseite zur Inhaltsübersicht Konstruktion eines Betriebsmittelgraphen Deadlock-Beseitigung

  Deadlockerkennung bei einem Exemplar jedes Betriebsmitteltyps
  (Schritt 2:  Überprüfung eines Betriebsmittelgraphen auf Zyklen)



Bedeutung eines Zyklus

Aus einem Betriebsmittelgraphen, der die aktuelle Situation von Prozessen und Betriebsmitteln in einem Betriebssystem grafisch visualisiert (d.h. der angibt, welche Betriebsmittel jeder Prozeß aktuell belegt bzw. anfordert), läßt sich ermitteln, ob im System eine Deadlocksituation vorliegt. Bei Systemen mit einem Exemplar jedes Betriebsmitteltyps ist dies nämlich genau dann der Fall, wenn im Graphen ein Zyklus vorhanden ist. In diesem Fall sind nämlich alle Bedingungen, die für das Auftreten eines Deadlocks notwendig sind, erfüllt.

Der Betriebsmittelgraph ist insbesondere dabei behilflich, die letzte dieser Bedingungen, die zyklische Wartebedingung (circular wait) zu überprüfen (Die übrigen drei Bedingungen werden als implizit gegeben vorausgesetzt).


Beispiel für einen Zyklus

Die folgende Abbildung zeigt einen Betriebsmittelgraphen, in dem ein Zyklus vorliegt. Die beteiligten Kanten sind in dieser Abbildung hervorgehoben:

Beispiel eines Zyklus


Zyklenerkennung durch Tiefensuche

Es gibt mehrere verschiedene, unterschiedlich aufwendige Algorithmen, die in der Lage sind, Zyklen in gerichteten Graphen zu erkennen (siehe z.B. [Ottmann 90] im Quellenverzeichnis dieses Programms). Exemplarisch soll hier nur ein Verfahren angedeutet werden, das als Tiefensuche bezeichnet wird.

Dabei werden nacheinander alle Knoten des Betriebsmittelgraphen betrachtet und jeweils untersucht, ob man auf irgendeinem der vom aktuellen Knoten ausgehenden Pfade zu diesem Knoten zurück gelangt. Ist dies der Fall, d.h. auf einem dieser Pfade ist der jeweilige Ausgangsknoten wieder erreichbar, so liegt ein Zyklus und damit eine Deadlock-Situation vor.


Navigationsleiste unten nach oben Universität Oldenburg Konstruktion eines Betriebsmittelgraphen Deadlock-Beseitigung
Letzte Änderung: 26.September 1999 © Copyright Andreas Lucks