Navigationsleiste oben Startseite zur Inhaltsübersicht sichere Zustände Ablauf des Algorithmus

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



Verwendete Matrizen und Vektoren
Belegungsmatrix Belegungsmatrix


Anforderungsmatrix Anforderungsmatrix


Betriebsmittelvektor Betriebsmittelvektor


Betriebsmittelrestvektor Betriebsmittelrestvektor



Bei der Sicherheitsüberprüfung eines Systemzustandes prüft der Bankier-Algorithmus, ob mit den verfügbaren Betriebsmitteln alle aktuellen Prozesse ihre Arbeit beenden können, d.h. ob die gesamten Anforderungen aller Prozesse bis zu ihrer Terminierung erfüllt werden können. Diese Aussage macht eine Grundvoraussetzung des Bankier-Algorithmus deutlich: damit der Algorithmus eine solche Sicherheitsüberprüfung durchführen kann, muß er von allen Prozessen von vornherein wissen, wieviele Betriebsmittel jeder Prozeß von jedem Betriebsmitteltyp bis zu seiner Terminierung benötigt. Nur wenn diese Voraussetzung gegeben ist, funktioniert dieses Verfahren.

Der Algorithmus speichert diese Daten zu jedem Prozeß in speziellen Datenstrukturen ab, mit deren Hilfe er die Sicherheitsüberprüfung eines Zustandes durchführt. Zu diesen Datenstrukturen zählen:

  • die Belegungsmatrix
  • die Anforderungsmatrix
  • der Betriebsmittelvektor
  • der Betriebsmittelrestvektor

In der Belegungsmatrix ist für jeden Prozeß gespeichert, wieviele Betriebsmittel er von jedem Betriebsmitteltyp derzeit belegt. Die Anforderungsmatrix hat das gleiche Format wie die Belegungsmatrix und gibt für jeden Prozeß an, wie viele Betriebsmittel jedes Betriebsmitteltyps er bis zu seiner Terminierung noch benötigt. Addiert man also diese beiden Matrizen, so würde man für jeden Prozeß seine gesamte Anforderung erhalten, d.h. man könnte ablesen, wie viele Exemplare jedes Betriebsmitteltyps jeder Prozeß insgesamt während seiner gesamten Lebensdauer benötigt. Der Betriebsmittelvektor gibt an, wie viele Exemplare jedes Betriebsmitteltyps insgesamt im System zur Verfügung stehen (unabhängig davon, ob sie gerade von Prozessen belegt sind oder nicht). Im Betriebsmittelrestvektor sind dagegen nur die derzeit freien Betriebsmittel jedes Typs dargestellt, d.h. hier ist angegeben, wie viele Exemplare von jedem Betriebsmitteltyp zur Zeit von keinem Prozeß belegt werden und deshalb für eine Belegung durch einen Prozeß zur Verfügung stehen. Dieser Betriebsmittelrestvektor ergibt sich dabei, indem man die Summe von jeder Spalte der Belegungsmatrix bildet (wodurch man ermittelt hat, wieviele Exemplare jedes Betriebsmitteltyps von Prozessen belegt sind) und den sich dadurch ergebenden Vektor von den insgesamt verfügbaren Betriebsmitteln, also vom Betriebsmittelvektor, abzieht.

Diese Bedeutung dieser Matrizen und Vektoren wird durch die nebenstehenden Abbildungen verdeutlicht, in der beispielhaft ein konkreter Systemzustand (eines Systems mit fünf Prozessen A,B,C,D und E und vier Betriebsmitteltypen BM1 bis BM4) angegeben ist.


Navigationsleiste unten nach oben Universität Oldenburg sichere Zustände Ablauf des Algorithmus
Letzte Änderung: 27.September 1999 © Copyright Andreas Lucks