Banker's Algorithmus

Der Bankieralgorithmus (englisch Banker's algorithm) geht auf Edsger W. Dijkstra (1965) zurück und wird zur Vermeidung von Verklemmungen (deadlock) genutzt. Dazu werden die verfügbaren Ressourcen und die Prozesse aufgelistet. Die Ressourcen gliedern sich in gesamte Ressourcen und verfügbare Ressourcen. Die Prozesse erhalten ebenfalls zwei Eigenschaften: Zum einen die Ressourcen, die bereits besetzt werden, zum anderen die noch benötigten Ressourcen.

Dann werden alle Prozesse – sofern die Ausführung möglich ist – nacheinander abgearbeitet und die belegten den verfügbaren Ressourcen zugeführt. Nach Ausführung des Algorithmus steht fest, ob eine Verklemmung vermeidbar ist oder nicht. Kommt der Bankieralgorithmus zu einem erfolgreichen Ende, kann unter Umständen durch unbedachte Ausführungsreihenfolge der Prozesse trotzdem eine Verklemmung entstehen.

Namensursprung

Wie einem Bankier nur eine begrenzte Menge Geld zur Verfügung steht, um die Wünsche seiner Kunden zu befriedigen, so steht einem Betriebssystem nur eine begrenzte Anzahl von Betriebsmitteln zur Verfügung. Der Bankier hält deswegen immer so viel Geld in seinem Tresor zurück, dass er noch von mindestens einem Kunden das komplette Kreditlimit erfüllen kann. Dieser eine Kunde (Prozess) kann dann sein Geschäft erfolgreich zum Abschluss bringen und das verwendete Geld wieder zurück auf die Bank bringen. Nun kann es ein anderer Kunde haben.

Voraussetzungen

Gegeben sind vor Ausführung des Algorithmus folgende Informationen:

• m Ressourcen
• n Threads / Prozesse (mit belegten Ressourcen)
• sowie die noch benötigten Ressourcen der Prozesse

Gesucht wird die Information, ob eine Verklemmung auftreten kann, oder nicht.

Formale Beschreibung

$E=(E_1, ..., E_m) \ \Rightarrow$ Gesamtressourcen

$A=(A_1, ..., A_m) \ \Rightarrow$ Verfügbare Ressourcen

$C_i=(C_{i1}, ..., C_{im}) \ \Rightarrow$ von Prozess i belegte Ressourcen (werden nach Prozessdurchführung freigegeben)

$R_i=(R_{i1}, ..., R_{im}) \ \Rightarrow$ von Prozess i benötigte Ressourcen (müssen für einen Prozessstart vorhanden sein)

Alle Prozesse i sind nicht markiert.

$\mathbf{while\ } \left(\ \exists \mathbf{\ unmarkiertes\ i} \and \forall j \mid 1 \leq j \leq m: R_{ij} \leq A_j\ \right) \left\{ \right.$

$\ \Rightarrow\mathbf{\ i\ kann\ abgearbeitet\ werden}$

$\ \Rightarrow\mathbf{\ Ressourcen\ freigeben:}\ A_j = A_j + C_{ij}$

$\ \Rightarrow\mathbf{\ i\ markieren}$

$\left. \right\}$

$\mathbf{if\ } \left(\mathbf{\ alle\ i\ markiert\ } \right) \left\{ \right.$

$\ \Rightarrow\mathbf{\ sicherer\ Zustand}$

$\left. \right\}\mathbf{\ else\ }\left\{ \right.$

$\ \Rightarrow\mathbf{\ schlechter\ Zustand}$

$\left. \right\}$

Beispiel

$\mathbf{E=(8,5,49,9)}$

$\mathbf{C_1=(1,0,3,0)}$ $\mathbf{R_1=(0,4,0,0)}$

$\mathbf{C_2=(0,1,0,1)}$ $\mathbf{R_2=(3,0,2,1)}$

$\mathbf{C_3=(3,0,4,1)}$ $\mathbf{R_3=(0,5,36,3)}$

$\mathbf{C_4=(0,1,0,0)}$ $\mathbf{R_4=(0,0,0,9)}$

Start des Algorithmus

$\mathbf{A_0=(4,3,42,7)}$

1. Schritt: Prozess 2 ausführen

$\mathbf{A_1=(4,4,42,8)}$

2. Schritt: Prozess 1 ausführen

$\mathbf{A_2=(5,4,45,8)}$

3. Schritt: Kein Prozess mehr ausführbar

da $\mathbf{R_{3i} > A_{3i} \ \and\ R_{4i} > A_{3i},\ i=[1, 4]}$

also keiner der verbliebenen Prozesse (Prozess 3 und 4) mehr mit den verfügbaren Betriebsmitteln ($\mathbf{A_3}$) zur Ausführung gebracht werden kann. Der Algorithmus gibt folgerichtig DEADLOCK bzw. »schlechter Zustand« zurück.