Navigationsleiste oben Startseite zur Inhaltsübersicht Problemstellung Datenstrukturen

  Deadlockvermeidung mit dem Bankier-Algorithmus
  (Sichere, unsichere und Deadlock-Zustände)



Einführung

Das Ziel des Bankier-Algorithmus ist die Feststellung, ob ein untersuchter Zustand eines Systems sicher ist oder nicht. Es stellt sich also zunächst einmal die Frage, wann ein Zustand als sicher einzustufen ist. Vereinfacht ausgedrückt ist ein Zustand sicher, wenn sich von diesem Zustand aus mit den derzeit freien (d.h. von keinem Prozeß belegten) Betriebsmitteln und den Betriebsmitteln, die jeweils von den einzelnen Prozessen nach ihrer Terminierung freigegeben werden, die Betriebsmittelanforderungen aller Prozesse, die sich derzeit im System befinden, erfüllt werden können. Kurz: alle aktuellen Prozesse können alle Betriebsmittel, die sie bis zu ihrer Terminierung benötigen, zugeteilt bekommen, ihre Aufgabe erfüllen und dann terminieren.

Formaler ausgedrückt befindet sich ein System in einem sicheren Zustand, falls es mindestens eine sichere Sequenz gibt, in der alle aktuellen Prozesse abgearbeitet (also ihre Anforderungen erfüllt) werden können. In diesem Fall gilt für jeden Prozeß Pk einer solchen Frequenz P1,..., Pn, daß dessen Betriebsmittelanforderungen mit den vorher schon freien zuzüglich der vom Vorgängerprozeß Pk-1 freigegebenen Betriebsmittel erfüllt werden konnten.

Es wird also davon ausgegangen, daß jeder Prozeß dieser Sequenz Betriebsmittel anfordert, diese irgendwann vom System erhält und somit die von ihm zu leistende Aufgabe erfüllen kann. Ist dies geschehen, gibt der Prozeß alle seine Betriebsmittel (also die zuletzt angeforderten und die, die er schon vorher belegt hatte) wieder frei und stellt sie somit einem anderen Prozeß zur Verfügung.

Ist zu einem Zeitpunkt des Algorithmus die Anforderung eines Prozesses Pj mit den aktuell verfügbaren Betriebsmitteln nicht erfüllbar, so muß es also mindestens einen anderen Prozeß Pk geben, dessen Anforderung befriedigt werden kann (d.h. Pj wird vorerst zurückgestellt). Läßt sich ein solcher alternativer Prozeß nicht finden, bricht der Algorithmus ab und meldet eine unsicheren Zustand. Lassen sich auf diese Weise dagegen alle Prozesse beenden, ist der Zustand sicher.


Deadlockzustand versus unsicherer Zustand

Dabei muß jedoch klargestellt werden, daß die beiden Ausdrücke unsicherer Zustand und Deadlock-Zustand keinesfalls die gleiche Bedeutung haben. Zwar ist jeder Deadlock-Zustand ein unsicherer Zustand, das bedeutet aber nicht, daß ein unsicherer Zustand immer ein Deadlock-Zustand sein muß. Vielmehr kann ein unsicherer Zustand zu einem Deadlock führen, was aber allein vom Verhalten der Prozesse abhängt. Ein unsicherer Zustand besagt lediglich, daß es von diesem Zustand aus durch bestimmte Zuteilungsreihenfolgen von Betriebsmitteln an Prozesse zu einem Deadlock kommen kann. Diese Zuteilungsreihenfolgen müssen aber schließlich nicht eintreten, so daß auch von einem unsicheren Zustand aus alle Prozesse beendet werden können. Deadlockzustände bilden also nur eine Teilmenge der unsicheren Zustände, wie auch die nebenstehende Abbildung verdeutlicht. Der Bankier-Algorithmus will allerdings jedes Deadlock-Risiko vermeiden. Deshalb ist für ihn die Tatsache, daß von einem Zustand aus ein Deadlock überhaupt möglich ist, schon ein ausreichender Grund, diesen Zustand auf jeden Fall zu vermeiden. Deshalb werden alle unsicheren Zustände vermieden, auch wenn sie u.U. gar nicht zu einem Deadlock führen würden.


Veranschaulichung

Im folgenden Diagramm sollen sichere, unsichere und Deadlock-Zustände voneinander abgegrenzt werden. In diesem Diagramm wird das Fortschreiten zweier Prozesse P! und P2 dargestellt. Der Ablauf von P1 ist dabei durch die horizontal, der von P2 durch vertikal verlaufenden Pfeile dargestellt. Das Eindringen der Prozesse in die mit M1 bzw. M2 gekennzeichneten Bereiche bedeutet, daß die Prozesse in diesen Bereichen jeweils die Betriebsmittel M1 bzw. M2 belegen. Aus diesem Grund ist ein Eindringen in die schraffierten Bereiche nicht möglich, weil dort die Betriebsmittel doppelt belegt wären.


Ablauf zweier Prozesse


Mit dieser Abbildung soll der Übergang von einem sicheren in einen unsicheren Zustand verdeutlicht werden. Eine Verklemmung tritt auf, wenn die Fortschrittslinie den Punkt A erreicht. Hier möchte P1 das Betriebsmittel M2 belegen, das sich aber im Besitz von P2 befindet, und P2 will M1 belegen, das wiederum zur Zeit von P1 bekegt wird. Somit liegt in diesem Punkt ein Deadlock vor. Dieser Deadlock kann dadurch vermieden werden, indem verhindert wird, daß die Fortschrittslinie in den unsicheren (grau hinterlegten) Bereich eindringt. Ist dies nämlich der Fall, wird die Linie irgendwann unweigerlich den Punkt A erreichen. Schließlich kann die Linie nur noch oben bzw. nach rechts weiterlaufen (da es sich in diesem Diagramm um Zeitachsen handelt). Um einen Deadlock zu vermeiden, muß Prozeß P2 im Punkt B also die Zuteilung des Betriebsmittels M2 verweigert werden (die Linie dringt dadurch nicht in den unsicheren Bereich ein).Stattdessen setzt zunächst Prozeß P1 seine komplette Arbeit fort und gibt danach beide Betriebsmittel frei. Erst dann erhält P2 die geforderten Betriebsmittel und kann seine Arbeit ebenfalls problemlos beenden. Dieser Ablauf ist durch die gestrichelte Linie angedeutet.


Navigationsleiste unten nach oben Universität Oldenburg Problemstellung Datenstrukturen
Letzte Änderung: 26.September 1999 © Copyright Andreas Lucks