Deadlockerkennung bei mehreren Exemplaren eines Betriebsmitteltyps
(Schritt 2: Reduzierung eines Betriebsmittelgraphen)
Prinzip der Reduzierung
Um in einem Betriebsmittelgraphen, der den Zustand eines Systems repräsentiert, in dem es von jedem Betriebsmitteltyp mehrere äquivalente Exemplare gibt, einen Deadlock festzustellen, versucht man, diesen Graphen zu reduzieren. Das bedeutet, daß man im Graphen zunächst nach einem Prozeß sucht, dessen Betriebsmittelanforderung im aktuellen Zustand erfüllt werden kann. Ist dies der Fall, kann man den Graphen um diesen Prozeß reduzieren, da dieser Prozeß schließlich in der Lage ist, seine Arbeit zu vollenden und danach alle von ihm belegten Betriebsmittel freigibt. Dieser Prozeß kann also nicht blockieren und kann somit auch nicht für eine eventuelle Deadlock-Situation verantwortlich sein. Reduzieren bedeutet dabei konkret, daß man alle Kanten, die mit diesem Prozeß in Verbindung stehen (d.h. sowohl die von diesem Prozeß ausgehenden als auch die, die auf diesen Prozeß zeigen) aus dem Graphen entfernt. Damit ist eine neue Ausgangssituation entstanden, in der man nun nach einem weiteren reduzierbaren Prozeß sucht.
Läßt sich der Betriebsmittelgraph in der beschriebenen Art und Weise um alle Prozesse reduzieren, so kann man daraus folgern, daß in dem Zustand, der durch die Ausgangssituation des Betriebsmittelgraphen repräsentiert worden ist, kein Deadlock vorgelegen hat. Tritt dagegen im Laufe des beschriebenen Verfahrens eine Situation ein, in der sich der Betriebsmittelgraph nicht weiter reduzieren läßt (aber noch Kanten vorhanden sind), so liegt eine Deadlock-Situation vor. Für diese Deadlock-Situation sind dabei alle die Prozesse verantwortlich, die nicht reduziert werden konnten.
Beispiel einer erfolgreichen Reduzierung
Das folgende Beispiel soll die erfolgreiche Reduzierung eines Betriebsmittelgraphen zeigen. Dabei soll die in Abbildung (a) gezeigte Ausgangssituation auf das Vorhandensein eines Deadlocks untersucht werden. Es wird deutlich, daß hier keine Deadlock-Situation vorliegt, denn alle Prozesse lassen sich durch die folgenden Schritte aus dem Betriebsmittelgraphen reduzieren:
- Zunächst läßt sich der Graph sowohl um Prozeß P2 als auch um Prozeß P4 reduzieren. Beide Prozesse belegen jeweils ein Betriebsmittel und haben ansonsten keine weiteren Anforderungen (vgl. Abbildung (a)). Sie können somit (ohne blockiert zu werden) ihre Arbeit komplett verrichten und anschließend ihre belegten Betriebsmittel freigeben.
- Nun läßt sich der Betriebsmittelgraph auch um die restlichen beiden Prozesse reduzieren. Prozeß P1 belegt ein Exemplar des Betriebsmitteltyps BM2 und benötigt noch ein Exemplar von BM1 (vgl. Abbildung (b)). Dieses Exemplar ist durch die vorherige Terminierung von P2 frei geworden. Entsprechendes gilt für Prozeß P3, der noch ein Exemplar des Betriebsmitteltyps BM2 benötigt, das wiederum durch die Terminierung von Prozeß P4 frei geworden ist. Somit können also alle Kanten aus diesem Betriebsmittelgraphen gelöscht werden, das System ist also deadlockfrei.
Beispiel eines Dedlock-Zustandes
Der links abgebildete Betriebsmittelgraph stellt dagegen eine Deadlock-Situation dar, da sich dieser Graph nicht weiter reduzieren läßt:
- Prozeß P1 benötigt, um seine Arbeit beenden zu können, ein Exemplar des Betriebsmitteltyps BM1. Davon gibt es jedoch nur ein Exmplar, das momentan von Prozeß P2 belegt wird.
- Dieser Prozeß P2 kann dieses Betriebsmittelexemplar jedoch nicht freigeben, da er selbst nicht terminieren kann. Dafür benötigt er nämlich ein Exemplar des Typs BM2, das aber wiederum nur einmal vorhanden ist und von Prozeß P3 belegt wird.
- Aber auch dieser Prozeß P3 kann seine Arbeit nicht beenden, da er dafür ein Exemplar des Betriebsmitteltyps BM3 benötigt. Die beiden Exemplare dieses Typs sind aber gerade von den Prozessen P1 bzw. P2 belegt.
Letzte Änderung: 27.September 1999 © Copyright Andreas Lucks