1. Einführung: Das Philosophenproblem und Coffmans vier Bedingungen (1971)

1965 formulierte der niederländische Informatiker Edsger W. Dijkstra das berühmte Problem der speisenden Philosophen (Dining Philosophers Problem): Fünf Philosophen \(P_0 \dots P_4\) sitzen an einem runden Tisch; zwischen je zwei Tellern liegt eine einzelne Gabel (\(F_0 \dots F_4\)). Zum Essen benötigt jeder Philosoph gleichzeitig seine linke Gabel \(F_i\) und seine rechte Gabel \(F_{(i+1)\bmod 5}\). Greifen alle fünf Philosophen im exakt selben Moment nach ihrer linken Gabel \(F_i\), hält jeder eine Gabel fest und wartet bis in alle Ewigkeit darauf, dass sein rechter Nachbar die zweite Gabel freigibt – das gesamte System steht still. Dieser Zustand heißt Deadlock (Verklemmung).

Formal befindet sich eine nichtleere Prozessmenge \(D \subseteq \mathcal{P}\) im Deadlock, wenn jeder Prozess \(P_i \in D\) dauerhaft auf ein Ereignis (wie die Freigabe einer Ressource) wartet, das ausschließlich von einem anderen Prozess \(P_j \in D\) derselben Wartemenge ausgelöst werden kann.

1971 bewiesen Edward G. Coffman Jr., M. J. Elphick und Arie Shoshani, dass ein Ressourcen-Deadlock nur eintreten kann, wenn vier notwendige Bedingungen gleichzeitig erfüllt sind:

1. Wechselseitiger Ausschluss (Mutual Exclusion): Mindestens eine Ressource wird exklusiv (nicht teilbar) von einem Prozess belegt.
2. Halten und Warten (Hold and Wait): Ein Prozess hält bereits mindestens eine Ressource, während er blockiert auf weitere, von anderen Prozessen gehaltene Ressourcen wartet.
3. Keine Präemption (No Preemption): Zugeteilte Ressourcen können einem Prozess nicht gewaltsam entzogen werden, sondern werden nur freiwillig freigegeben.
4. Zyklisches Warten (Circular Wait): Es existiert eine geschlossene Kette wartender Prozesse \(\{P_0, P_1, \dots, P_{k-1}\}\), sodass jeder \(P_i\) auf eine von \(P_{(i+1)\bmod k}\) gehaltene Ressource wartet.

Da alle vier Bedingungen einzeln notwendig sind, gilt: Wird auch nur eine einzige dieser vier Bedingungen durch das Systemdesign logisch ausgeschlossen, ist ein Deadlock mathematisch zu \(100\,\%\) unmöglich.

2. Ressourcenallokationsgraph (RAG) und die Zyklensätze (Holt, 1972)

1972 modellierte Richard C. Holt Ressourcenanforderungen als gerichteten bipartiten Ressourcenallokationsgraphen (RAG) \(G = (V, E)\) mit Knotenmenge \(V = \mathcal{P} \cup \mathcal{R}\) (Prozessknoten \(P_i\) und Ressourcentypknoten \(R_j\) mit je \(W_j \ge 1\) identischen Instanzen) sowie Anforderungskanten \(P_i \to R_j\) und Zuweisungskanten \(R_j \to P_i\).

Zwischen gerichteten Zyklen in \(G\) und Deadlocks gelten drei fundamentale Sätze:

• Satz 1 (Zyklenfreiheit impliziert Deadlock-Freiheit): Enthält \(G\) keinen gerichteten Zyklus (ist \(G\) ein DAG), befindet sich kein Prozess im Deadlock.
• Satz 2 (Notwendige und hinreichende Bedingung bei Einzelinstanzen): Besitzt jeder Ressourcentyp genau eine Instanz (\(\forall j, W_j = 1\)), so gilt: Gerichteter Zyklus in \(G \iff\) Deadlock.
• Satz 3 (Nicht-Hinreichendheit bei Mehrfachinstanzen): Besitzt mindestens ein Ressourcentyp mehrere Instanzen (\(\exists j, W_j > 1\)), ist ein gerichteter Zyklus zwar eine notwendige, aber KEINE hinreichende Bedingung für einen Deadlock!

  flowchart TD
    subgraph RAG_Single["Fall A: Einzelinstanz-RAG (Zyklus <==> Deadlock garantiert)"]
        PA1(("P1 (Blockiert)")) -->|"Fordert an"| RA1["R1 (1 Instanz: ●)"]
        RA1 -->|"Zugewiesen"| PA2(("P2 (Blockiert)"))
        PA2 -->|"Fordert an"| RA2["R2 (1 Instanz: ●)"]
        RA2 -->|"Zugewiesen"| PA1
    end

    subgraph RAG_Multi["Fall B: Mehrfachinstanz-RAG (Zyklus P1->R1->P3->R2->P1, aber KEIN Deadlock!)"]
        PB1(("P1 (Blockiert)")) -->|"Fordert an"| RB1["R1 (2 Instanzen: ●●)"]
        RB1 -->|"Instanz #1"| PB3(("P3 (Blockiert)"))
        PB3 -->|"Fordert an"| RB2["R2 (2 Instanzen: ●●)"]
        RB2 -->|"Instanz #1"| PB1
        RB1 -->|"Instanz #2"| PB2(("P2 (LÄUFT: Keine Anforderung!)"))
        RB2 -->|"Instanz #2"| PB4(("P4 (LÄUFT: Keine Anforderung!)"))
    end

In Fall B existiert zwar der Zyklus \(P_1 \to R_1 \to P_3 \to R_2 \to P_1\), doch die Prozesse \(P_2\) und \(P_4\) haben Ausgangsgrad \(0\) (Senken), laufen ungehindert weiter und lösen den Zyklus durch Freigabe ihrer Instanzen von \(R_1\) bzw. \(R_2\) auf!

3. Strategie 1 (Deadlock-Prävention): Widerspruchsbeweis der totalen Sperrordnung

In Betriebssystemkernen (z. B. Linux lockdep) und Multithreading-Anwendungen wird Bedingung 4 (Zyklisches Warten) durch eine totale Sperrordnung (Total Lock Ordering) eliminiert: Jedem Mutex \(L \in \mathcal{L}\) wird ein eindeutiger globaler Rang \(\phi(L) \in \mathbb{N}\) zugewiesen. Ein Thread, der bereits die Sperrmenge \(\mathcal{H}\) hält, darf eine neue Sperre \(L_{\text{new}}\) nur anfordern, wenn ihr Rang strikt größer ist:

【Widerspruchsbeweis】: Angenommen, es entsteht ein zyklischer Wartekreis \(\{P_0, P_1, \dots, P_{k-1}\}\) (\(k \ge 2\)), wobei \(P_i\) die Sperre \(L_i\) hält und auf die von \(P_{(i+1)\bmod k}\) gehaltene Sperre \(L_{(i+1)\bmod k}\) wartet. Da jeder Thread die Sperrordnung befolgt, gilt entlang des gesamten Zyklus:

Da keine natürliche Zahl strikt kleiner als sie selbst sein kann, liegt ein Widerspruch (\(\bot\)) vor! Ob beim Banktransfer (immer das Konto mit der kleineren ID zuerst sperren) oder bei den speisenden Philosophen (\(P_4\) greift zuerst zur rechten Gabel \(F_0\) statt \(F_4\), da \(0 < 4\)) – zyklisches Warten ist damit mathematisch ausgeschlossen. \(\blacksquare\)

4. Strategie 2 (Deadlock-Vermeidung): Dijkstras Bankieralgorithmus (5×3-Matrix-Trace)

Lässt sich die Sperrreihenfolge nicht statisch festlegen, fordert Dijkstras Bankieralgorithmus (1965 / Habermann, 1969) vorab die Deklaration des Maximalbedarfs \(\mathbf{Max}\) und prüft vor jeder Zuteilung in \(O(m \cdot n^2)\) Schritten, ob der Zielzustand ein sicherer Zustand (Safe State) mit mindestens einer sicheren Ausführungsfolge (Safe Sequence) bleibt (wobei gilt: \(\text{Deadlock} \subsetneq \text{Unsicherer Zustand}\)).

Für \(n=5\) Prozesse \(\{P_0 \dots P_4\}\) und \(m=3\) Ressourcentypen mit \(\mathbf{Total} = (A=10, B=5, C=7)\) ergibt sich zum Zeitpunkt \(t_0\) bei belegten Ressourcen \((7,2,5)\) der freie Vektor \(\mathbf{Available} = (10,5,7) - (7,2,5) = \mathbf{(3, 3, 2)}\):

Mit der sicheren Folge \(\langle P_1, P_3, P_4, P_0, P_2 \rangle\) ist \(t_0\) sicher. Fordert \(P_1\) nun \((1,0,2)\) an, bleibt \(\mathbf{Available}=(2,3,0) \ge \mathbf{Need}_1=(0,2,0)\) sicher (sofort genehmigt). Fordert danach jedoch \(P_0\) den Vektor \((0,2,0)\) an, sinkt \(\mathbf{Available}\) auf \((2,1,0)\), womit kein einziger Prozess mehr seinen \(\mathbf{Need}\) decken kann (unsicherer Zustand): Der Bankieralgorithmus lehnt die Zuteilung ab und blockiert \(P_0\)!

5. Strategie 3 & 4 (Erkennung, Wait-Die/Wound-Wait, Vogel-Strauß) & Livelock vs. Starvation

Relationale Datenbanken (PostgreSQL, MySQL InnoDB) nutzen einen Wait-For-Graphen (WFG) und suchen mittels \(O(|V|+|E|)\)-Tiefensuche (DFS) nach Zyklen, um bei einem Deadlock die Transaktion mit dem kleinsten Undo-Log als Opfer (Victim) zurückzurollen (MySQL prüft sofort beim Blockieren; PostgreSQL erst nach deadlock_timeout = 1s). Verteilte Datenbanken (wie Google Spanner) vermeiden globale WFGs durch die zeitstempelbasierten Protokolle Wait-Die (nicht-präemptiv) und Wound-Wait (präemptiv, weniger Neustarts) nach Rosenkrantz et al. (1978), wobei abgebrochene Transaktionen ihren ursprünglichen Startzeitstempel \(\text{TS}(T_i)\) behalten, um Verhungern (Starvation) auszuschließen. Für extrem seltene Betriebssystem-Tabellenengpässe nutzen UNIX/Windows den Vogel-Strauß-Algorithmus (Ostrich Algorithm) und ignorieren das Problem zugunsten maximaler Alltagsgeschwindigkeit.

  flowchart TD
    Req["Verteilte Transaktion Ti fordert eine von Tj gehaltene Sperre an"] --> Cmp{"Startzeitstempel-Vergleich: TS(Ti) < TS(Tj) ?<br/>(Ist Anforderer Ti ÄLTER als Halter Tj?)"}
    Cmp -->|"Ja: Ti ist ÄLTER (Older)"| WD1["[Wait-Die (nicht-präemptiv)]: Älteres Ti WARTET auf jüngeres Tj (Alt -> Jung)<br/>[Wound-Wait (präemptiv)]: Älteres Ti VERWUNDET (bricht ab) Tj & übernimmt Sperre!"]
    Cmp -->|"Nein: Ti ist JÜNGER (Younger)"| WD2["[Wait-Die (nicht-präemptiv)]: Jüngeres Ti STIRBT (Abbruch, Retry mit altem TS)<br/>[Wound-Wait (präemptiv)]: Jüngeres Ti WARTET geduldig auf älteres Tj (Jung -> Alt)"]

Abschließend die präzise Abgrenzung der drei Liveness-Fehler: