Bankieralgorithmus - LinkFang.de





Bankieralgorithmus


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.

Anwendung

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

Für die Ausführung des Algorithmus müssen folgende Informationen gegeben sein:

  • [math]m[/math], die Anzahl verschiedener Ressourcen.
  • [math]n[/math], die Anzahl beteiligter Prozesse.
  • [math]E=\{E_1, ..., E_m\}[/math], die Menge der insgesamt existierenden (existing) Ressourcen.
  • [math]A=\{A_1, ..., A_m\}[/math], die Menge der noch verfügbaren (available) Ressourcen.
  • [math]C_i=\{C_{i1}, ..., C_{im}\}[/math], die Menge aktuell (currently) vergebener Ressourcen an Prozess [math]i[/math].
  • [math]R_i=\{R_{i1}, ..., R_{im}\}[/math], die Menge der von Prozess [math]i[/math] 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

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 [math]R_i \le A[/math]), so wird dieser Prozess abgearbeitet und seine Ressourcen danach wieder freigegeben ([math]A=A+C_i[/math]). Die Reihenfolge, in welcher die Prozesse dabei bearbeitet werden spielt keine Rolle, da [math]A[/math] nur anwächst oder unverändert bleibt.

def bankersAlgorithm(E,A,C,R):
    n,m = len(C), len(C[0])
    terminatedProcesses = []
    deadlock = False
    while len(terminatedProcesses) < n and not(deadlock):
        deadlock = True
        for i in range(n):
            if i in terminatedProcesses:
                continue
            elif all([R[i][j] <= A[j] for j in range(m)]):
                # required resources are given to process i
                # process i terminates and gives all his resources back
                A = [C[i][j] + A[j] for j in range(m)]
                terminatedProcesses.append(i)
                deadlock = False
                print i, A
    return not(deadlock), terminatedProcesses

Die Funktion gibt zurück, ob der ermittelte Zustand sicher ist (True/False), sowie die Reihenfolge in welcher die Prozesse ablaufen können.

Beispiele

Mit Verklemmung

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 [math]i[/math] 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

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 [math]i[/math] 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 [math](3,4,0,1,2)[/math] ausgeführt werden. Der Zustand des Systems wird als sicher bezeichnet[1].

Einzelnachweise

  1. Andrew S. Tanenbaum: Modern Operating Systems, 4th Edition. Pearson, 2015, ISBN 0-13-359162-X, 6.5.4, S. 454–455.

Weblinks


Kategorien: Algorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Bankieralgorithmus (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.