Navigationsleiste oben Startseite zur Inhaltsübersicht zurück zum Haupttext

  Deadlockverhinderung auf Basis der Deadlockbedingungen


Bemerkung

Damit ein Deadlock auftreten kann, müssen vier bestimmte Bedingungen erfüllt sein. Trifft auch nur eine dieser Bedingungen nicht zu, ist keine Deadlock-Situation möglich. Um das Auftreten eines Deadlocks zu verhindern, könnte man also dafür sorgen, daß mindestens eine dieser vier Bedingungen nicht eintreten kann. Diese Art der Verhinderung eines Deadlocks läßt sich bei jeder der vier Bedingungen unterschiedlich durchführen [vgl. Brause 96; Tanenbaum 94], man sieht aber, daß keine dieser Maßnahmen wirklich ideal ist:


Wechselseitigen Ausschluß verhindern

Wenn die Betriebsmittel niemals einem Prozeß exklusiv zugeteilt werden, kann kein Deadlock entstehen. Man muß also versuchen, die Konkurrenz für ein Betriebsmittel abzuschaffen. Beim Drucken ist dies z.B. durch den Einsatz von Spooling möglich. Nur ein einziger Prozeß, der sog. Drucker-Dämon, erhält dauerhaft den Drucker zugeteilt. Alle anderen Prozesse, die Daten auf dem Drucker ausgeben wollen, übergeben diese Daten dem Drucker-Dämon in dessen Warteschlange. Dieser arbeitet die Warteschlange dann stellvertretend für die Prozesse ab und legt sich schlafen, sobald die Warteschlange leer ist.

Das Verfahren ist nicht unproblematisch. Zum einen läßt sich dieses Verfahren nicht bei allen Betriebsmitteltypen anwenden, zum anderen ist das Deadlock-Problem im Prinzip nur vorverlagert, und zwar vom Drucker zum Druckerpuffer im Massenspeicher (der als endlicher Speicherplatz ebenfalls ein Betriebsmittel darstellt). Wenn wir nämlich z.B. zwei Prozesse haben, deren Pufferbedarf jeweils die Hälfte des verfügbaren Pufferplatzes überschreitet, so schreibt jeder Prozeß seine Daten in den Puffer, bis dieser voll ist. Ein Auftrag wird aber erst nach der vollständigen übermittlung vom Puffer in die Warteschlange des Dämons eingehängt, so daß die Warteschlange leer bleibt (schließlich konnte keiner der Prozesse seinen Auftrag vollständig in den Puffer schreiben). Die beiden Prozesse warten aber auf die übertragung der Daten aus dem Puffer in die Warteschlange, damit der Puffer wieder frei wird und sie den Rest ihres Auftrags übertragen können. Somit liegt wieder eine Verklemmung vor.


Verhindern zusätzlicher Anforderungen

Die Belegungs- und Wartebedingung kann verhindert werden, indem man dafür sorgt, daß Prozesse, die bereits Betriebsmittel belegt haben, keine weiteren Betriebsmittel mehr anfordern. Die einfachste Möglichkeit dafür wäre natürlich, jedem Prozeß nur ein einziges Betriebsmittel zu gestatten. Dies ist aber natürlich für die Praxis nicht akzeptabel.
Weiterhin könnte man die Anforderung neuer Betriebsmittel verhindern, indem man einem Prozeß von Anfang an alle Betriebsmittel zuteilt, die er benötigt. Aber auch dies ist problematisch, da erstens nicht immer von vornherein bekannt ist, welche Betriebsmittel ein Prozeß im Laufe seiner Arbeit benötigt und zweitens die Betriebsmittelauslastung mangelhaft ist. Schließlich belegt ein Prozeß auf diese Art für seine gesamte Lebenszeit eine Menge von Betriebsmitteln, auch wenn er sie nur für einem minimalen Zeitabschnitt benötigt. Für andere Prozesse stehen diese Betriebsmittel während dieser gesamten Zeit nicht zur Verfügung, obwohl sie u.U. momentan vom belegenden Prozeß gar nicht verwendet werden.


Vorzeitiger Betriebsmittelentzug

Maßnahmen, um die dritte Bedingung der Ununterbrechbarkeit unmöglich zu machen, sind problematisch. Einem Prozeß vorzeitig ein Betriebsmittel zu entziehen, ist in vielen Fällen sehr schwierig, oft sogar unmöglich. Man denke nur an einen Prozeß, der bereits begonnen hat, seine Daten auf einem Drucker auszugeben. Hier läßt sich der Drucker nicht einfach entziehen, ohne dies im Programm explizit mit zu berücksichtigen.

Zyklen durchbrechen

Das zyklische Warten von Prozessen kann z.B. durch eine sog. Linearisierung der Betriebsmittelanforderungen geschehen. Dabei werden alle Betriebsmittel durchnumeriert und einem Prozeß nur gestattet, zusätzlich Betriebsmittel mit einer höheren Nummer zu belegen als er bereits hat. Die Folge ist, daß auf diese Weise kein Prozeß auf ein früher durch einen anderen Prozeß bereits belegtes Betriebsmittel mit einer kleineren Nummer warten kann. Es ist ja im Prinzip nicht verfügbar.
Das Problem bei dieser Methode besteht nur darin, daß man nur schwer eine Ordnung der Betriebsmittel findet, die für alle Anwendungen sinnvoll ist.

Navigationsleiste unten nach oben Universität Oldenburg zurück zum Haupttext
Letzte Änderung: 22.Juli 1999 © Copyright Andreas Lucks