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 Bearbeiten
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.
Anwendung Bearbeiten
Auch wenn der Bankieralgorithmus im Kontext von Betriebssystemen immer als elegante Lösung zur Vermeidung von Verklemmungen aufgeführt ist, sollte bedacht werden, dass dieser in der Praxis kaum Anwendung findet. Der Algorithmus berücksichtigt zum Beispiel nicht, dass die Anzahl von Prozessen sowie Ressourcen variabel ist. Des Weiteren geht der Algorithmus davon aus, dass alle zur Laufzeit von den Prozessen benötigten Ressourcen schon vorher genau bekannt sind, was in Realität nur selten der Fall ist.
Voraussetzungen Bearbeiten
Für die Ausführung des Algorithmus müssen folgende Informationen gegeben sein:
- , die Anzahl verschiedener Ressourcen.
- , die Anzahl beteiligter Prozesse.
- , die Menge der insgesamt existierenden (existing) Ressourcen.
- , die Menge der noch verfügbaren (available) Ressourcen.
- , die Menge aktuell (currently) vergebener Ressourcen an Prozess .
- , die Menge der von Prozess noch benötigten (required) Ressourcen.
Findet der Algorithmus eine Reihenfolge, in welcher die Prozesse nacheinander ohne Verklemmung abgearbeitet werden können, befindet sich das System in einem sicheren Zustand.
Implementierung Bearbeiten
Folgende Python-Funktion implementiert den Bankieralgorithmus: In einer Liste werden alle terminierten Prozesse gesammelt. Solange diese Liste noch nicht alle Prozesse enthält und keine Verklemmung aufgetreten ist, werden die Anforderungen aller noch nicht bearbeiteten Prozesse untersucht. Können alle benötigten Ressourcen eines Prozesses durch die noch verfügbaren Ressourcen abgedeckt werden (elementweise ), so wird dieser Prozess abgearbeitet und seine Ressourcen danach wieder freigegeben (). Die Reihenfolge, in welcher die Prozesse dabei bearbeitet werden spielt keine Rolle, da nur anwächst oder unverändert bleibt.
def bankierAlgorithmus(E,A,C,R): n,m = len(C), len(C[0]) beendeteProzesse = [] verklemmung = False while len(beendeteProzesse) < n and not(verklemmung): verklemmung = True for i in range(n): if i in beendeteProzesse: continue elif all([R[i][j] <= A[j] for j in range(m)]): # Angeforderte Ressourcen werden Prozess i zugewiesen # Prozess i wird beendet und gibt alle seine Ressourcen frei A = [C[i][j] + A[j] for j in range(m)] beendeteProzesse.append(i) verklemmung = False print i, A return not(verklemmung), beendeteProzesse Die Funktion gibt zurück, ob der ermittelte Zustand sicher ist (True/False), sowie die Reihenfolge, in welcher die Prozesse ablaufen können.
Beispiele Bearbeiten
Mit Verklemmung Bearbeiten
Ausgangszustand:
A = [4, 3, 42, 7] E = [8, 5, 49, 9] C = [[1, 0, 3, 0], [0, 1, 0, 1], [3, 0, 4, 1], [0, 1, 0, 0]] R = [[0, 4, 0, 0], [3, 0, 2, 1], [0, 5, 36, 3], [0, 0, 0, 9]]
Zwischenstände zur Laufzeit, nachdem jeweils Prozess ausgewählt wurde und terminiert ist:
i A [4, 3, 42, 7] 1 [4, 4, 42, 8] 0 [5, 4, 45, 8]
Verklemmung, da keine der übrigen Anforderungen ([0, 5, 36, 3], [0, 0, 0, 9]) mehr durch verfügbare Ressourcen ([5, 4, 45, 8]) abgedeckt werden können. Der Zustand des Systems wird als unsicher bezeichnet.
Ohne Verklemmung Bearbeiten
Ausgangszustand:
E = [6, 3, 4, 2] A = [1, 0, 2, 0] C = [[3, 0, 1, 1], [0, 1, 0, 0], [1, 1, 1, 0], [1, 1, 0, 1], [0, 0, 0, 0]] R = [[1, 1, 0, 0], [0, 1, 1, 2], [3, 1, 0, 0], [0, 0, 1, 0], [2, 1, 1, 0]]
Zwischenstände zur Laufzeit, nachdem jeweils Prozess ausgewählt wurde und terminiert ist:
i A [1, 0, 2, 0] 3 [2, 1, 2, 1] 4 [2, 1, 2, 1] 0 [5, 1, 3, 2] 1 [5, 2, 3, 2] 2 [6, 3, 4, 2]
Erfolg, alle Prozesse können erfolgreich in der gefundenen Reihenfolge ausgeführt werden. Der Zustand des Systems wird als sicher bezeichnet.
Einzelnachweise Bearbeiten
- Andrew S. Tanenbaum: Modern Operating Systems, 4th Edition. Pearson, 2015, ISBN 0-13-359162-X, 6.5.4, S. 454–455.