Formelsammlung Lexikon Bankier-Algorithmus


Startseite	Bookmark setzen Sitemap Impressum

» Formelsammlung:

» Startseite

» Astronomie

» Biologie

» BWL

» Chemie

» Informatik

» Mathematik

» Physik

» Interaktiv:

» Forum

» Lexikon

» Mitmachen

» Links zu Uns

» Surftipps

» Informationen:

» Kontakt

» Impressum

» Über Formel-Sammlung.de

» Partnerseiten:

www.schuelerlexikon.de

» Partner:

Etiketten
Kostenlose Kochrezepte
Künstler Verzeichnis
Schilder
Spieleforum
Witze & SMS Sprüche

Bankier-Algorithmus

Sie befinden Sie in: Formelsammlung Lexikon > b > Bankier-Algorithmus

Bankier-Algorithmus

Der Bankier-Algorithmus (englisch Banker's algorithm) 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} \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)}$