Navigationsleiste oben Startseite zur Inhaltsübersicht Datenstrukturen Übung zum Bankier-Algorithmus

  Deadlockvermeidung mit dem Bankier-Algorithmus
  (Ablauf des Bankier-Algorithmus)



Die Schritte des Algorithmus

Ablauf Bankier-Algorithmus

Um einen Systemzustand auf seine Sicherheit zu überprüfen, wird dieser Zustand zunächst probeweise vom Bankier-Algorithmus hergestellt, d.h. durch die entsprechenden Änderungen in den Datenstrukturen des Algorithmus wird dieser Systemzustand simuliert. Die Sicherheitsüberprüfung dieses simulierten Zustandes läuft dann in den folgenden Schritten ab, die schematisch in der nebenstehenden Abbildung dargestellt sind:
  1. Der Algorithmus sucht nach einem Prozeß, dessen Restanforderung an Betriebsmitteln sich mit den aktuell frei im System verfügbaren Betriebsmitteln erfüllen läßt. Dazu wird die Anforderungsmatrix durchlaufen und nach einem Prozeß gesucht, bei dem alle Einträge kleiner oder gleich den entsprechenden Einträgen im Betriebsmittelrestvektor sind.


  2. Findet der Algorithmus einen solchen Prozeß, so bekommt dieser die von ihm angeforderten Betriebsmittel zugeteilt. Die entsprechende Anzahl an Betriebsmitteln jedes Typs wird also im Betriebsmittelrestvektor abgezogen (da diese Betriebsmittel nun nicht mehr frei sind) und in der Belegungsmatrix in der Zeile des entsprechenden Prozesses zu den bereits belegten Betriebsmitteln hinzuaddiert. Gleichzeitig werden die Werte in der Anforderungsmatrix auf Null gesetzt, da die Anforderungen nun erfüllt worden sind.


  3. Da der ausgewählte Prozeß nun alle von ihm benötigten Betriebsmittel erhalten hat, kann er seine Aufgabe komplett verrichten, danach alle von ihm belegten Betriebsmittel wieder freigeben und schließlich terminieren. Das bedeutet, daß alle Betriebsmittel (d.h. die zuletzt zugewiesenen und die, die er bereits davor belegt hatte) dieses Prozesses aus der Belegungsmatrix gelöscht und zum Betriebsmittelrestvektor hinzuaddiert werden. Die Betriebsmittel sind nun wieder für andere Prozesse verfügbar. Der terminierte Prozeß wird schließlich als abgearbeitet markiert und seine Werte aus den Matrizen gelöscht. Er spielt für den weiteren Verlauf des Algorithmus keine Rolle mehr.


  4. Somit ist eine neue Ausgangssituation entstanden, in der der Algorithmus wieder bei Schritt 1 beginnt, d.h. es wird nun unter den jetzt noch nicht als abgearbeitet markierten Prozessen nach dem nächsten Prozeß gesucht, dessen Anforderung erfüllbar ist.

Lassen sich mit diesem Verfahren die Anforderungen aller Prozesse erfüllen und somit alle Prozesse ohne Probleme beenden, so ist der untersuchte Zustand sicher. Bricht der Algorithmus dagegen ab, bevor alle Prozesse als abgearbeitet markiert wurden (d.h. es tritt eine Situation ein, in der der Algorithmus unter den noch unmarkierten Prozessen keinen mit einer erfüllbaren Anforderung findet), so meldet er als Ergebnis einen unsicheren Zustand. Eine Betriebsmittelzuteilung, die zum ursprünglichen (simulierten) Anfangszustand führen würde, müßte also abgeleht werden, damit ein Deadlock garantiert vermieden werden kann.


Navigationsleiste unten nach oben Universität Oldenburg Datenstrukturen Übung zum Bankier-Algorithmus
Letzte Änderung: 27.September 1999 © Copyright Andreas Lucks