Deadlock

Deadlocks sind der Horror in Datenbanken und Multi-Threaded Apps. Der Server "hängt". CPU ist auf 0%, aber keine Antwort kommt. Lösung oft: Neustart. Vermeidung: Ganz strikte Regeln: "Jeder muss erst den Drucker, dann den Scanner anfordern." (Globale Ordnung). Wenn sich alle dran halten, gibt es keinen Stau.

1. Coffman-Bedingungen

Damit ein Deadlock entsteht, müssen 4 Dinge gleichzeitig wahr sein (1971):

1. Mutual Exclusion: Nur einer darf die Ressource nutzen.
2. Hold and Wait: Einer hat was und wartet auf mehr.
3. No Preemption: Man kann nichts gewaltsam wegnehmen (Raub).
4. Circular Wait: A wartet auf B, B wartet auf A (Kreis). Breche eine dieser Regeln, und der Deadlock ist unmöglich.

2. Livelock

Der böse Bruder. Zwei Leute im Gang weichen beide gleichzeitig nach links aus. Dann beide nach rechts. Sie bewegen sich (CPU 100%), kommen aber trotzdem nicht aneinander vorbei. Das System "arbeitet", macht aber keinen Fortschritt.

1. Resource Allocation Graph (Wait-for-Graph)

Die Informatik beweist Deadlocks mathematisch über gerichtete Graphen. Prozesse sind Knoten ($P_1, P_2$), Ressourcen sind Knoten ($R_1, R_2$). Ein Pfeil von $P_1$ nach $R_1$ bedeutet "Request". Ein Pfeil von $R_1$ nach $P_1$ bedeutet "Assignment" (Allocation). Exisitiert in diesem bipartite Graph ein geschlossener Zirkel (Cycle), ist das System theoretisch im Deadlock-Gefahrenbereich. Viele relationale Datenbanken generieren diesen Graphen in Intervallen (z.B. alle 1000ms). Findet der Graph-Traversal-Algorithmus einen Cycle, wählt der Scheduler gnadenlos den Process mit der geringsten Priorität (oder Transactions-Kosten) und wirft ein SIGKILL (bzw. ein Lock-Timeout Exception).

2. Lock Ordering (Hierarchic Allocation)

Wie vermeidet man Zirkel präventiv? Durch globale Dominanzstrukturen. Wenn man Entwicklern verbietet, dynamische Locks kreuz und quer anzufordern, bricht man die vierte Coffman-Bedingung (Circular Wait). Man führt eine globale Ordnung ein: Lock(User), Lock(Account), Lock(Transaction). Der Kernel (oder das Framework) diktiert: "Ressourcen dürfen streng nur in lexikografischer oder hierarchischer Reihenfolge gelockt werden". Versucht Thread B Lock(Account) vor Lock(User) zu rufen, während Thread A bereits Lock(User) hält, reiht sich Thread B sauber ein oder blockt sofort. Circular Dependencies werden durch dieses DAG (Directed Acyclic Graph) Design auf Architekturlevel mathematisch unmöglich.

3. Spinlocks und Priority Inversion

Ein toxischer Nebeneffekt von echten harten Locks (Mutex) im Real-Time Computing (Mars Pathfinder Desaster). Ein unwichtiger Hintergrund-Prozess $P_{Low}$ hält ein Lock über den System-Bus. Ein kritischer Prozess $P_{High}$ wacht auf und will ans Lock, blockt aber. Nun startet ein mittlerer Prozess $P_{Medium}$ ohne Lock-Bedarf. Da er höhere Prio hat als $P_{Low}$, drängt er den $P_{Low}$ vom CPU-Core weg. Folge: $P_{Low}$ kann sein Lock niemals freigeben, $P_{Medium}$ rechnet fröhlich, und der top-prio $P_{High}$ hängt fest. Das ist ein Deadlock durch Priority Inversion. Die Lösung ist Priority Inheritance: $P_{Low}$ erbt kurzzeitig die gigantisch hohe Prio von $P_{High}$, wird sofort fertig, gibt das Lock ab und fällt auf Prio Low zurück.