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:

$m$ , die Anzahl verschiedener Ressourcen.
$n$ , die Anzahl beteiligter Prozesse.
$E=\{E_{1},...,E_{m}\}$ , die Menge der insgesamt existierenden (existing) Ressourcen.
$A=\{A_{1},...,A_{m}\}$ , die Menge der noch verfügbaren (available) Ressourcen.
$C_{i}=\{C_{i1},...,C_{im}\}$ , die Menge aktuell (currently) vergebener Ressourcen an Prozess $i$ .
$R_{i}=\{R_{i1},...,R_{im}\}$ , die Menge der von Prozess $i$ 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 $R_{i}\leq A$ ), so wird dieser Prozess abgearbeitet und seine Ressourcen danach wieder freigegeben ( $A=A+C_{i}$ ). Die Reihenfolge, in welcher die Prozesse dabei bearbeitet werden spielt keine Rolle, da $A$ 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

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