Deadlock — Sperrreihenfolge-Puzzle
Ordne um, in welcher Reihenfolge Threads ihre Sperren nehmen, damit keiner ewig wartet. Ein Puzzle über die Regel der globalen Sperrreihenfolge.
Ordne jeden Thread so um, dass keine zwei ewig aufeinander warten.
- 🔒 A
- 🔒 B
- 🔒 B
- 🔒 A
So wird gespielt
- Jede Zeile ist ein Thread, die Chips sind die Sperren, die er von links nach rechts nimmt.
- Ziehe einen Chip (oder nutze die Pfeile), um die Reihenfolge der Sperren eines Threads zu ändern.
- Nehmen zwei Threads dasselbe Paar in umgekehrter Reihenfolge, können sie ewig blockieren. Die Lösung ist eine globale Reihenfolge, an die sich alle halten — drücke Ausführen zum Prüfen.
So funktioniert es
Jede Zeile ist ein Thread, jeder Chip eine Sperre, die er von links nach rechts nimmt. Nehmen zwei Threads dasselbe Paar in umgekehrter Reihenfolge, gibt es eine Verschränkung, in der jeder eine hält und auf die andere wartet — und keiner kommt je weiter. Mit „Ausführen" wird der Wait-for-Graph auf einen Zyklus geprüft; existiert einer, leuchten die schuldigen Sperren rot. Die Lösung ist die Regel echter Codebasen: eine globale Sperrreihenfolge festlegen und sie überall einhalten.
Ein Lernpuzzle. Es modelliert Hold-and-wait-Zyklen — die Deadlock-Bedingung, die man wegkonstruieren kann; echte Systeme brauchen zusätzlich Timeouts, lock-freie Strukturen und müssen an Livelock denken.
Häufig gestellte Fragen
Was verursacht hier tatsächlich einen Deadlock?
Ein Zyklus im Wait-for-Graph. Hält Thread 1 A und will B, während Thread 2 B hält und A will, warten beide ewig. Das Spiel zeichnet genau diesen Zyklus, wenn es ihn findet.
Warum hilft das Sortieren der Sperren?
Nehmen alle Threads Sperren in derselben globalen Reihenfolge, ist ein Zyklus unmöglich: Ein Thread kann nur auf eine Sperre warten, die später kommt als die gehaltenen, der Graph bleibt also azyklisch. Das ist die übliche Sperrhierarchie-Regel.
Findet man echte Deadlocks so?
Die Zyklusprüfung ist dieselbe Idee wie bei Detektoren für Lock-Order-Inversion, etwa ThreadSanitizer. Echte Werkzeuge beobachten die Reihenfolge zur Laufzeit; hier siehst du den ganzen Graphen auf einmal.