Bankieralgorithmus

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der Bankieralgorithmus (englisch Banker's algorithm) geht auf Edsger W. Dijkstra (1965) zurück und wird zum Erkennen einer Verklemmung (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 möglich – nacheinander abgearbeitet und die belegten zu 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ührung der Prozesse trotzdem eine Verklemmung entstehen.

[Bearbeiten] Begriff: Bankieralgorithmus

Wie einem Bankier nur eine begrenzte Anzahl an Geld zur Verfügung steht um die Wünsche seiner Kunden zu befriedigen, so steht einem Betriebssystem auch nur eine begrenzte Anzahl von Betriebsmitteln zur Verfügung. Der Bankier hält deswegen immer noch so viel Geld in seinem Tresor zurück, damit 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.

[Bearbeiten] 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 eine Verklemmung auftreten kann, oder nicht.

[Bearbeiten] 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\}$

[Bearbeiten] 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)}$