Bankieralgorithmus

Beschreibung

Der Banker's Algorithmus wird zum Erkennen einer Deadlock-Situation 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 möglich - nacheinander abgearbeitet und die belegten zu den verfügbaren Ressourcen zugeführt. Nach Ausführung des Algorithmus steht fest, ob ein Deadlock vermeidbar ist oder nicht. Kommt der Banker Algorithmus zu einem erfolgreichen Ende, kann unter Umständen durch "unbedachte" Ausführung der Prozesse trotzdem ein Deadlock entstehen.

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 dann die Information, ob ein Deadlock 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
$R_{i}=(R_{i1},...,R_{im})\ \Rightarrow$ von Prozess i benötigte Ressourcen
alle Prozesse i sind nicht markiert.

$\mathbf {while\ } \left(\ \exists \mathbf {\ unmarkiertes\ i} \land \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 {\ schlechterZustand}

$\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)}$