Deadlock: erkennen, verhindern und auflösen

Stell dir zwei Threads vor. Thread A besitzt lock1 und fordert lock2 an. Gleichzeitig besitzt Thread B lock2 und fordert lock1 an. Beide warten darauf, dass der andere sein Lock freigibt. Das geschieht aber erst, nachdem der jeweilige Thread weiterarbeiten konnte.

Nicht jede mögliche ungünstige Reihenfolge führt tatsächlich zum Deadlock. Gibt A lock1 frei, bevor B lock2 belegt, kann der Ablauf problemlos enden. Entscheidend ist also der konkrete Zustand zur Laufzeit.

Vier Bedingungen müssen gleichzeitig vorliegen, damit ein Deadlock nach dem Coffman-Modell möglich ist. Fehlt mindestens eine, kann in diesem Modell kein Deadlock entstehen.

1. Mutual Exclusion – wechselseitiger Ausschluss: Mindestens eine benötigte Ressource ist exklusiv nutzbar.
2. Hold and Wait – Belegen und Warten: Ein Prozess hält bereits eine Ressource, während er eine weitere anfordert.
3. No Preemption – kein erzwungener Entzug: Eine belegte Ressource wird nur vom haltenden Prozess freigegeben; das System entzieht sie nicht einfach.
4. Circular Wait – zyklisches Warten: Es gibt eine geschlossene Kette. Jeder Prozess wartet auf eine Ressource des nächsten, und der letzte wartet auf eine Ressource des ersten.

Im Lock-Beispiel sind alle vier Bedingungen erfüllt: Die Locks sind exklusiv. Beide Threads halten je ein Lock und warten auf das zweite. Das gehaltene Lock wird nicht entzogen. A wartet auf B und B auf A.

Eine feste Erwerbsreihenfolge verändert genau diesen entscheidenden Punkt. Wenn alle Threads stets zuerst lock1 und danach lock2 anfordern, kann keine Kette entstehen, in der einer die Reihenfolge umkehrt. Circular Wait ist ausgeschlossen.

Ein Betriebsmittelzuteilungsgraph stellt Prozesse und Ressourcen als zwei verschiedene Arten von Knoten dar. Seine gerichteten Kanten haben eine feste Bedeutung:

• Prozess → Ressource: Der Prozess fordert die Ressource an und wartet darauf.
• Ressource → Prozess: Die Ressource ist dem Prozess zugeteilt.

Bei mehreren Instanzen eines Ressourcentyps ist die Bewertung vorsichtiger. Ein Zyklus ist dann ein Warnsignal, aber nicht immer ein Beweis: Eine weitere Instanz könnte von einem Prozess außerhalb des Zyklus freigegeben werden. Dadurch könnte ein wartender Prozess enden und den Kreis auflösen.

Gegenmaßnahmen setzen an unterschiedlichen Zeitpunkten an. Deshalb ist es wichtig, die Strategien nicht zu vermischen.

Prävention: eine Bedingung unmöglich machen

Bei der Prävention wird das System so entworfen, dass mindestens eine Coffman-Bedingung nicht erfüllt werden kann. Beispiele sind:

• Ressourcen gemeinsam nutzbar machen, sofern das fachlich möglich ist;
• alle benötigten Ressourcen auf einmal anfordern;
• entziehbare oder virtualisierte Ressourcen verwenden;
• alle Ressourcen in einer festen globalen Reihenfolge anfordern.

Die feste Reihenfolge ist oft besonders praktikabel. Sie verhindert Circular Wait, kann aber die Gestaltung einschränken. Alle Ressourcen auf einmal anzufordern kann Wartezyklen ebenfalls vermeiden, bindet jedoch möglicherweise Ressourcen, die erst später benötigt werden.

Vermeidung: nur sichere Zuteilungen erlauben

Bei der Vermeidung bleiben die Coffman-Bedingungen grundsätzlich möglich. Das System prüft vor einer Zuteilung, ob danach noch eine Reihenfolge existiert, in der alle Prozesse ihren maximalen Restbedarf erhalten, enden und ihre Ressourcen freigeben können. Dann ist der Zustand sicher.

Ein unsicherer Zustand ist noch nicht automatisch ein Deadlock. Er bedeutet: Unter der angenommenen maximalen Nachfrage ist keine garantiert erfolgreiche Reihenfolge mehr bekannt. Vermeidungsverfahren wie der Bankieralgorithmus lassen eine Anforderung deshalb warten. Dafür muss der maximale Bedarf im Voraus bekannt sein.

Erkennen und anschließend auflösen

Ein System kann Deadlocks zunächst zulassen, regelmäßig nach Wartezyklen suchen und einen gefundenen Deadlock auflösen. Mögliche Eingriffe sind:

• einen beteiligten Prozess oder eine Transaktion abbrechen;
• eine geeignete Ressource entziehen;
• einen Prozess auf einen früheren Sicherungszustand zurücksetzen.

Diese Eingriffe können Arbeit oder Daten kosten. Die Opferwahl muss daher berücksichtigen, welcher Abbruch wenig Schaden verursacht und ob ein konsistenter Zustand wiederhergestellt werden kann. Derselbe Prozess sollte nicht ständig zum Opfer werden, sonst droht Starvation.

Drei Probleme können Fortschritt verhindern, aber aus verschiedenen Gründen.

Beim Livelock ändern Prozesse ihren Zustand, lösen aber das Problem nicht. Zwei Personen in einem schmalen Gang weichen beispielsweise immer gleichzeitig auf dieselbe Seite aus. Beide sind aktiv, doch niemand kommt vorbei.

Bei Starvation, auch Verhungern genannt, werden Ressourcen zwar frei und andere Prozesse machen Fortschritt. Ein bestimmter Prozess erhält die benötigte Ressource wegen einer unfairen Auswahl jedoch immer wieder nicht.