Betriebsmittelzuteilungsgraph: Deadlocks erkennen

Betriebsmittel (auch Ressourcen) sind Teile eines Computers, die Prozesse zur korrekten Ausführung brauchen, zum Beispiel Festplatte, Arbeitsspeicher oder Drucker. Der Graph hat zwei Sorten von Knoten: Prozessknoten und Ressourcenknoten. Dazu kommen Kanten, also Pfeile. Ein solcher Graph heißt auf Englisch Resource Allocation Graph, kurz RAG. In dieser Lektion nennen wir ihn Betriebsmittelzuteilungsgraph.

Es gibt zwei Arten von Kanten. Die eine Art sagt „hält“, die andere sagt „wartet auf“. Wie die Pfeile dafür zeigen, lernst du im nächsten Abschnitt. Zuerst zeichnest du nur die Situation auf: Jeder Prozess und jedes Betriebsmittel bekommt einen Knoten.

Zur Zeichenweise: In dieser Lektion zeichnen wir Prozesse als Kreise und Ressourcen als Quadrate. Das ist nur unsere Darstellungsregel. Manche Ressourcen erlauben mehr als einen Zugriff pro Zeiteinheit. Dann erstellst du für jeden Zugriff eine einzelne Ressource, die nur einen Zugriff pro Zeiteinheit erlaubt.

Die Richtung der Kante sagt dir, ob ein Prozess eine Ressource hat oder auf sie wartet. Der Graph ist gerichtet, also ist die Pfeilspitze wichtig.

Zeigt die Kante von einer Ressource R zu einem Prozess P, dann hält P die Ressource R. Zeigt die Kante von einem Prozess P zu einer Ressource R, dann wartet P darauf, dass R frei wird.

Merke dir: Beim Halten beginnt der Pfeil bei der Ressource und zeigt zum Prozess. Beim Warten beginnt er beim wartenden Prozess und zeigt zur Ressource. Derselbe Pfeil in Gegenrichtung hätte also eine ganz andere Bedeutung.

Ein Zyklus ist ein Weg entlang der Kanten, der dort endet, wo er angefangen hat. Dabei darfst du jede Kante nur einmal benutzen. Knoten dürfen mehrfach vorkommen. In einem gerichteten Graphen läufst du nur in Pfeilrichtung, so ein Zyklus heißt gerichteter Zyklus.

So gehst du vor: Wähle einen Knoten und folge den Pfeilen. Kommst du irgendwann zum Startknoten zurück, hast du einen Zyklus. Findest du von keinem Startknoten aus einen Weg zurück, ist der Graph azyklisch.

Die Regel heißt: Wenn im Graphen kein Zyklus existiert, kann kein Deadlock auftreten. Der Grund: Ein Deadlock ist eine zyklische Wartesituation zwischen mehreren Prozessen. Jeder wartet auf ein Betriebsmittel, das ein anderer beteiligter Prozess schon exklusiv belegt hat. Ohne Kreis aus Warten gibt es das nicht. Ein Graph ohne Zyklus darf trotzdem Kanten für „hält“ und „wartet auf“ haben. Es fehlt nur der geschlossene Kreis.

Achtung bei der Umkehrung: Ein Zyklus im Graphen zeigt einen möglichen Deadlock. Dass jeder Zyklus sicher einen Deadlock bedeutet, folgt aus der Regel nicht. Das klären wir hier nicht.

Nach Coffman et al. sind vier Bedingungen zusammen hinreichend für die Möglichkeit einer Verklemmung: Der Zugriff auf ein Betriebsmittel ist exklusiv (Mutual Exclusion). Prozesse fordern Betriebsmittel an und behalten zugleich andere (Hold and Wait). Betriebsmittel werden nur von den Prozessen selbst freigegeben (No Preemption). Und mindestens zwei Prozesse sind bei den Betriebsmitteln zirkulär voneinander abhängig (Circular Wait). Diese zirkuläre Wartesituation ist ein Kreis aus Warten.

Man spricht von einer Verhinderung, wenn mindestens eine dieser vier Bedingungen nicht erfüllt wird.

Eine Möglichkeit ist die feste Reihenfolge, auch Ressourcenhierarchie genannt. Die Betriebsmittel werden linear geordnet, also nummeriert. Sie werden nur in dieser definierten Reihenfolge angefordert oder zugeteilt. Eine feste Reihenfolge schließt die zirkuläre Wartesituation aus und verhindert so den Deadlock.

Die Idee für zwei Prozesse (ausgedachte Überlegung): Beide fordern zuerst die niedriger nummerierte Ressource an. Wer sie nicht bekommt, hält noch nichts und blockiert den anderen nicht. So entsteht kein Kreis aus Warten. Das ist kein allgemeiner Beweis.

Das Beispiel unten zeigt die Idee ebenfalls. Dort sitzen fünf Philosophen am Tisch und brauchen für jede Mahlzeit zwei Gabeln. Ohne feste Reihenfolge kann es passieren, dass alle ihre linke Gabel nehmen und dann auf die rechte warten. Mit der Nummerierung können nicht mehr alle zuerst die niedrigere Gabel nehmen.