Navigationsleiste oben Startseite zur Inhaltsübersicht Charakterisierung des Deadlockbegriffs Deadlock-Bedingungen

  Definition des Deadlock-Begriffs


Definition

Ein Deadlock-Zustand in einem Betriebssystem läßt sich auf die folgende Art und Weise definieren:
Eine Menge von Prozessen befindet sich in einem Deadlock-Zustand, falls jeder Prozeß der Menge auf ein Ereignis wartet, daß nur ein anderer Prozeß der Menge auslösen kann.

Mit dem Ereignis ist dabei in den meisten Fällen das Freigeben von Betriebsmitteln gemeint, die von einem anderen Prozeß aus der Menge belegt sind. Da alle Prozesse warten, kann keiner jemals dieses Ereignis auslösen, das die Weiterarbeit eines anderen Prozesses ermöglichen würde. Alle Prozesse warten somit für immer, sie befinden sich in einer Deadlock-Situation.


Petri-Netz zur Deadlock-Demonstration

Kein Java?


Petri-Netze sind Modelle, die allgemein zur Darstellung dynamischer Abläufe verwendet werden können. Solche Petri-Netze bestehen aus Stellen und Transitionen, wobei man letztere mit Schaltern vergleichen kann. In einer Stelle können sogenannte Token enthalten sein. Eine Transition kann nur dann schalten, wenn sich in allen Eingangsstellen dieser Transition mindestens ein Token befindet. Ist dies der Fall und schaltet die Transition, wird aus jeder Eingangstelle genau ein Token entfernt und zu jeder Ausgangsstelle (d.h. zu jeder dieser Transition nachgelagerten Stelle) genau ein Token hinzugefügt.

Mit Hilfe solcher Petri-Netze lassen sich nun Prozeßaktivitäten in einem Betriebssystem simulieren. Jede Stellenbelegung des Petri-Netzes repräsentiert dabei einen speziellen Zustand eines Betriebssystems. Der Gesamtzustandes des Petri-Netzes ändert sich, sobald eine Transition schaltet und sich damit die Anzahl der Token in den entsprechenden Stellen ändert. Das Schalten einer Transition im Petri-Netz repräsentiert somit in gewisser Weise Prozeßaktivitäten (d.h. Belegungen und Freigaben von Betriebsmitteln durch Prozesse) in einem Betriebssystem, da sich auch durch Prozeßaktivitäten der Gesamtzustand eines Systems (nämlich eben der des Betriebssystems) ändert.

Auf diese Weise läßt sich auch die Entstehung einer Deadlocksituation simulieren. Betrachte etwa das links abgebildete Petri-Netz mit den vier Transitionen t1 bis t4 und den vier Stellen S1, S2, S3 und Ziel. In diesem Petri-Netz ist es nur durch ganz bestimmte Schaltkombinationen einiger Transitionen möglich, eine Marke in die Ziel-Stelle zu befördern. Andere Kombinationen führen dagegen zu einem Deadlock, d.h. zu einem Zustand des Petri-Netzes, in dem die Ziel-Stelle leer ist und trotzdem keine der Transitionen schalten kann. Versuche durch Betätigung der entsprechenden Buttons, diese richtigen Schaltkombinationen herauszufinden, die zum Ziel führen. Du wirst dabei feststellen, daß manche Kombinationen in einem Deadlock enden.

Dieses einfache Beispiel soll verdeutlichen, daß die Entstehung eines Deadlocks in einem Betriebssystem von der Reihenfolge abhängt, in der bestimmte Prozeßaktivitäten stattfinden. Nur wenn diese Reihenfolge vom System richtig organisiert wird, kann ein Deadlock vermieden werden. Werden dagegen zum Beispiel Zuteilungen von Betriebsmitteln an Prozesse in einer “unglücklichen“ Reihenfolge vorgenommen, kann es zu einer Verklemmung kommen.


Navigationsleiste unten nach oben Universität Oldenburg Charakterisierung des  
    Deadlockbegriffs Deadlock-Bedingungen
Letzte Änderung: 25.September 1999 © Copyright Andreas Lucks