Navigationsleiste oben Startseite zur Inhaltsübersicht Inhaltsübersicht Definition Deadlock

  Charakterisierung des Deadlockbegriffs


Einführung

In einem Computersystem gibt es eine Reihe verschiedener Betriebsmittel, die von Prozessen, die diese Betriebsmittel zur Erfüllung ihrer jeweiligen Aufgabe benötigen, angefordert werden können. Dabei gibt es bestimmte Betriebsmitteltypen (sogenannte ununterbrechbare Betriebsmittel), die, wenn sie einem Prozeß zugeteilt worden sind, diesem nicht einfach temporär wieder entzogen werden können. Für den entsprechenden Prozeß würden dadurch Nachteile entstehen, denn er müßte seine bisherigen Berechnungen abbrechen und später neu beginnen. Drucker sind ein Beispiel für solche ununterbrechbaren Betriebsmittel. Würde man einem Prozeß während des Ausdruckens seiner Daten den Drucker temporär entziehen und den Drucker zwischenzeitlich einem anderen Prozeß zuteilen, würde dabei ein unbrauchbares Ergebnis entstehen. Die Ausgaben beider Prozesse würden sich auf dem Papier vermischen.

Aus diesem Grund muß das Betriebssystem Mechanismen zur Verfügung stellen, um einem Prozeß für eine gewisse Zeitspanne den exklusiven Zugriff auf ein solches ununterbrechbares Betriebsmittel zu ermöglichen. Hat ein Prozeß ein solches Betriebsmittel belegt, ist es für die Dauer dieser Belegung für andere Prozesse nicht verfügbar. Jeder Prozeß, der ein Betriebsmittel verwenden möchte, muß sich dabei an den folgenden Ablauf halten:

  1. Anforderung des vom Prozeß benötigten Betriebsmittels


  2. Zuteilung dieses Betriebsmittels an den Prozeß durch das System


  3. Benutzung des Betriebsmittels durch den Prozeß


  4. Freigabe des Betriebsmittels durch den Prozeß
Fordert ein Prozeß ein Betriebsmittel an, das momentan von einem anderen Prozeß belegt wird (das also momentan nicht frei verfügbar ist), geht dieser Prozeß in einen Wartezustand über. Dieser dauert so lange, bis das von ihm benötigte Betriebsmittel frei ist und dem Prozeß zugeteilt werden kann. Bis zu diesem Zeitpunkt ist er blockiert und kann seine Berechnungen nicht fortsetzen.

Notation

Graphen-Erläuterung
(a)

Graphen-Erläuterung
(b)



Um den aktuellen Zustand eines Computersystems grafisch darstellen zu können, wird in der Literatur eine spezielle Schreibweise verwendet. Anforderungen und Belegungen von Betriebsmitteln durch Prozesse werden dabei durch gerichtete Graphen dargestellt, wobei die Knoten für Prozesse (dargestellt durch Kreise) und Betriebsmittel (dargestellt durch Vierecke) stehen. Eine Kante verbindet immer einen Prozeß und ein Betriebsmittel, wobei die Richtung dieser Kante ausdrückt, in welchem Verhältnis diese beiden Komponenten zueinander stehen.

Dabei sind die folgenden Beziehungen zwischen einem Prozeß und einem Betriebsmittel möglich, die in der nebenstehenden Abbildung dargestellt sind:

  • eine gerichtete Kante von einem Prozeß zu einem Betriebsmittel (siehe Abb. (a)) bedeutet, daß der Prozeß dieses Betriebsmittel anfordert. Zum besseren Verständnis ist die Kante hier zusätzlich mit einem “f“ (=fordert) beschriftet.


  • eine gerichtet Kante von einem Betriebsmittel zu einem Prozeß (siehe Abb. (b)) bedeutet, daß der Prozeß dieses Betriebsmittel belegt. Entsprechend ist diese Kante mit einem “b“ (=belegt von) beschriftet.

Das Deadlock-Problem

Deadlock-Beispiel



Die oben angesprochene Tatsache, daß einige Betriebsmittel zu bestimmten Zeitpunkten nur exklusiv von einem einzigen Prozeß belegt werden können, kann in Computersystemen, in denen gleichzeitig mehrere Prozesse aktiv sind, zu Problemen führen. Man stelle sich die folgende Situation vor, die in der nebenstehenden Abbildung illustriert wird: in einem (hier sehr einfach dargestellten) System gebe es zwei Prozesse A und B und zwei ununterbrechbare Betriebsmittel: einen Drucker und ein Bandgerät. Beide Prozesse wollen jeweils eine Datei vom Bandgerät lesen und diese Datei auf dem Drucker ausgeben. Damit dies möglich ist, braucht jeder Prozeß gleichzeitig exklusiven Zugriff sowohl auf den Drucker als auch auf das Bandgerät. Nun trete die folgende Situation ein: Prozeß A fordert zunächst das Bandgerät an und bekommt es vom System zugeteilt. Doch bevor er den Drucker, den er ebenfalls zur Erfüllung seiner Aufgabe benötigt, belegen kann, wird dieser Prozeß B zugeteilt. Dieser möchte ebenfalls beide Betriebsmittel belegen und hat zunächst den Drucker angefordert und auch erhalten. Prozeß A muß aus diesem Grund auf die Freigabe des Druckers durch Prozeß B warten, bevor er seine Arbeit fortsetzen kann. Prozeß B wird den Drucker aber nicht freigeben, da er seinerseits auf das Freiwerden des von Prozeß A belegten Bandgerätes wartet und somit ebenfalls blockiert ist.

In diesem Beispiel ist somit die Situation eingetreten, daß beide Prozesse ewig aufeinander warten. Beide fordern ein Betriebsmittel an, das der jeweils andere Prozeß belegt. Da aber keiner der Prozesse sein bereits belegtes Betriebsmittel vor Beendigung seiner Aufgabe freigibt, sondern beide davon ausgehen, daß der jeweils andere Prozeß diese verklemmte Situation auflöst, wird dieses System ewig verklemmt bleiben. Es ist ein Deadlock aufgetreten.

Deadlock-Situationen kommen nicht nur im Zusammenhang mit Computersystemen vor, sondern sind Bestandteil unseres täglichen Lebens, wie diese Beispiele verdeutlichen.


Navigationsleiste unten nach oben Universität Oldenburg zurück zur Inhaltsübersicht Definition Deadlock
Letzte Änderung: 25.September 1999 © Copyright Andreas Lucks