Notizen

Bankieralgorithmus

tagsbetriebssysteme

Der Bankieralgorithmus (Dijkstra, 1965) wird zur Vermeidung von Verklemmungen genutzt.

Funktionsweise

Wir erweitern den Resource Allocation Graph wie folgt:

  • Claim-Kante : Prozess könnte Ressource anfordern (gestrichelte Linie)
  • Claim-Kante wird zur Anforderungskante, wenn ein Prozess die Ressource anfordert
  • Anforderungskante wird zur Zuweisungskante, wenn die Ressource dem Prozess zugeteilt wird
  • Zuweisungskante wird zur Claim-Kante, wenn die Ressource wieder freigegeben wird

Beispiel:

graph LR
    P1((P1)) -.-> R2[R2]
    P2((P2)) -.-> R2
    R1 --> P1
    P2 --> R1

Voraussetzungen

Um den Bankieralgorithmus anzuwenden, müsen folgende Voraussetzungen erfüllt sein:

  • Es gibt mehrere Instanzen jedes Ressourcentyps
  • Die Maximale Anzahl benötigter Instanzen eines Ressourcentyps eines Prozesses muss bekannt sein
  • Der Prozess muss das System in einem sicheren Zustand belassen, ansonsten muss er warten

Datenstrukturen

: Anzahl der Prozesse, : Anzahl der Ressourcentypen

  • Available - Vektor der Länge
    gibt Anzahl der verfügbaren Instanzen pro Ressourcentyp an
  • Max - Matrix
    definiert den maximalen Bedarf an Ressourcen für jeden Prozess
  • Allocation - Matrix
    definiert die derzeit reservierten Ressourcen für jeden Prozess
  • Need - Matrix
    gibt die noch benötigten Ressourcen für jeden Prozess an

Es gilt:

Beispiel

Gegeben seien folgende Allocation und Max Matrizen, sowie die Available Matrix von den Prozessen bis auf die Ressourcen , und :

Dadurch lässt sich die Need-Matrix berechnen:

Jetzt muss überprüft werden, ob der Need von einem Prozess dem Available-Vektor ist.

  • Für trifft das nicht zu: Dementsprechend wird dieser Prozess zunächst übersprungen.
  • Für trifft das zu: Dementsprechend fügen wir den Prozess an die Safe-Sequenz an: Der Available-Vektor wird mit der entsprechenden Zeile aus der Allocation-Matrix erhöht:
  • Bei trifft die Bedingung wieder nicht zu:
  • Für trifft die Bedingung wieder zu: Der Prozess wird an die Safe-Sequenz angehängt: Der Available-Vektor wird wieder aktualisiert:
  • So geht das weiter:
  • Ist man am Ende angekommen aber hat Prozesse übrig, die noch nicht in der Safe Sequenz sind, fängt man wieder von Vorne an:

Daraus folgt die Reihenfolge , die die Sicherheitsbedingungen befriedigt.

Backlinks