Navigationsleiste oben Startseite zur Inhaltsübersicht Übung Deadlockerkennung Graph-Konstruktion

  Deadlockerkennung bei mehreren Exemplaren eines Betriebsmitteltyps
  (Einführung)



Problemstellung

Eines der möglichen Verfahren der Deadlockbehandlung ist die Erkennung und anschließende Beseitigung von Verklemmungen im System. Bei diesem Verfahren der Deadlockerkennung wird dabei speziell von Systemen ausgegangen, in denen es von jedem Betriebsmitteltyp mehrere äquivalente Exemplare geben kann (z.B. drei Drucker, zwei Scanner, fünf Festplatten usw.). Äquivalent bedeutet dabei, daß jedes Exemplar eines Betriebsmitteltyps die Anforderung eines Prozesses nach diesem Betriebsmitteltyp in der gleichen Weise erfüllen kann. Fordert ein Prozeß also z.B. einen Drucker an, kann jeder Drucker dieses Systems diese Anforderung erfüllen.

Treten in einem solchen System verdächtige Symptome auf, die auf eine Deadlock-Situation hindeuten, so kann dieses Verfahren verwendet werden, um festzustellen, ob wirklich ein Deadlock für diese verdächtigen Symptome verantwortlich ist. Solche verdächtigen Symptome können dabei z.B. die folgenden sein:

  • Es gibt viele wartende Prozesse im System, was normalerweise darauf hindeuten würde, daß der Prozessor gerade einem anderen Prozeß zugeteilt ist. Dies ist aber nicht der Fall, denn der Prozessor ist unbeschäftigt


  • Viele Prozesse müssen verdächtig lange auf ein Betriebsmittel warten.
Mit Hilfe dieses Verfahrens der Deadlockerkennung läßt sich nun herausfinden, ob ein Deadlock vorliegt (und falls dies der Fall ist, welche Prozesse für diese Deadlock-Situation verantwortlich sind). Wurden diese Informationen ermittelt, kann die Verklemmung schließlich unter Umständen mit Hilfe verschiedener Deadlock-Beseitigungsverfahren aufgelöst werden.

Unterschiede zu anderen Erkennungsverfahren

Diese Variante der Deadlockerkennung hat gewisse Ähnlichkeiten mit dem Verfahren der Deadlockerkennung in Systemen, in denen es nur ein einziges Exemplar jedes Betriebsmitteltyps gibt (dieses Verfahren wird hier beschrieben). Wie dieses Verfahren beginnt auch diese Variante damit, einen Betriebsmittelgraphen zu konstruieren, der die Basis für die Deadlockerkennung darstellt. In den genannten Systemen mit nur einem Exemplar pro Betriebsmitteltyp ist es dann ausreichend, für die Feststellung einer Deadlock-Situation diesen Graphen auf Zyklen zu untersuchen. Ein Zyklus in einem solchen System besagt nämlich, daß alle Prozesse, die sich in diesem Zyklus befinden, jeweils auf ein Betriebsmittel warten, das der jeweils nächste Prozeß in dieser geschlossenen Kette belegt. Somit blockieren sich diese Prozesse gegenseitig.

Auch in den hier betrachteten Systemen mit mehreren Exemplaren eines Betriebsmittels tritt ein Deadlock auf, wenn sich mehrere Prozesse gegenseitig blockieren. Bei einem Deadlock liegt also auch bei diesem Verfahren ein Zyklus im Betriebsmittelgraphen vor. Der entscheidende Unterschied zum oben beschriebenen Verfahren ist jedoch, daß bei dieser Variante ein Zyklus im Graph existieren kann, aber trotzdem kein Deadlock vorliegen muß. Der Grund dafür ist, daß von jedem Betriebsmitteltyp unter Umständen mehrere Exemplare existieren. Damit kann ein Prozeß auf ein anderes, äquivalentes Betriebsmittel ausweichen und muß nicht auf das Freiwerden eines bestimmten Exemplares warten.

Aus diesem Grund ist für die Erkennung einer Deadlock-Situation die Überprüfung des Betriebsmittelgraphen auf Zyklen nicht ausreichend. Zyklen sind nur eine notwendige, jedoch keinesfalls eine hinreichende Bedingung für einen Deadlock. Deshalb wird in Systemen mit mehreren Exemplaren eines Betriebsmitteltyps ein anderes Verfahren zur Identifizierung möglicher Deadlocks angewendet, daß als Betriebsmittelgraph-Reduzierung bezeichnet wird.


Ablauf des Verfahrens

Insgesamt besteht das Verfahren der Deadlockerkennung in Systemen mit mehreren Exemplaren eines Betriebsmitteltyps somit aus den folgenden beiden Teilschritten:
  • Schritt 1:  Konstruktion eines Betriebsmittelgraphen


  • Schritt 2:  Reduzierung dieses Betriebsmittelgraphen

Navigationsleiste unten nach oben Universität Oldenburg Übung Deadlockerkennung Graph-Konstruktion
Letzte Änderung: 27.September 1999 © Copyright Andreas Lucks