Ein Verfahren oder Mechanismus, der das Vorhandensein von Deadlocks erkennt — Zustände, in denen ein oder mehrere Prozesse/Threads dauerhaft blockiert sind, weil jeder auf Ressourcen wartet, die von anderen gehalten werden, sodass ohne Intervention kein Fortschritt mehr möglich ist.

Prinzip

Die Erkennung modelliert Ressourcen­konkurrenz mittels Graphen (Wait‑For‑Graphen oder Resource‑Allocation‑Graphen) und nutzt Zykluserkennung oder Zustandsraum‑Analyse, um zirkuläres Warten zu identifizieren. Erkennung ist eine von drei Strategien (Vermeidung, Avoidance, Erkennung+Wiederherstellung); praktische Detektoren tauschen Vollständigkeit gegen Kosten, laufen periodisch oder auf Abruf und müssen abstrakte Zyklen in konkrete Wiederherstellungsaktionen überführen.

Demonstration

Konkrete Beispiele: Betriebssysteme, die Wait‑For‑Graphen bauen und Zyklen detektieren, um ein Opfer zum Beenden oder Präemptieren auszuwählen; Datenbanksysteme, die auf Sperren warten und eine Transaktion abbrechen, um den Zyklus zu brechen; statische Analysetools, die mögliche Deadlocks in Multithread‑Code approximativ durch Modellierung von Sperranketten finden.

Fehlanwendung

Zu glauben, Erkennung sei gleichbedeutend mit Lösung — Erkennung meldet nur, dass ein Deadlock existiert, und muss durch Wiederherstellung (Beenden, Rollback, Präemption) ergänzt werden. Konservative statische Analysen können Fehlalarme produzieren; Livelock und Starvation sind unterschiedliche Probleme und werden oft fälschlich der Deadlock‑Erkennung zugeordnet.

Konsequenz

Effektive Deadlock‑Erkennung ermöglicht gezielte Wiederherstellungsmaßnahmen (Rollback, Ressourcenpräemption, Thread‑Terminierung) und liefert Erkenntnisse für Systemdesign und Tuning, verursacht jedoch Überwachungsaufwand und erfordert eine wohlüberlegte Politik zur Opferauswahl, um Störungen zu minimieren.

Umkehrung

Deadlock‑Vermeidung oder ‑Prävention (z. B. globale Ressourcenreihenfolge, Bankieralgorithmus, nur sichere Allokationen) macht Erkennung und Wiederherstellung überflüssig, kann jedoch die Parallelität einschränken oder konservative Überprovisionierung erforderlich machen.

Abgrenzung

Gilt für Systeme mit wechselseitig ausschließbaren Ressourcen und blockierender Erwerbssemantik (Locks, Semaphoren, I/O‑Kanäle); schließt Fortschrittsanomalien aus, die keine zirkulären Wartezustände sind (Starvation, Livelock), und Modelle, in denen Ressourcen während des Wartens nicht gehalten werden (reiner Nachrichtenaustausch ohne Blockieren), sofern sich keine Wait‑For‑Relation ableiten lässt.

Semantische Spannung

Spannung zwischen run‑time Detektion (reaktiv, im Normalfall oft günstiger) und Prävention/Avoidance (proaktiv, kann Parallelität hemmen). Ebenso Spannung zwischen präziser dynamischer Erkennung und konservativen statischen Analysen, die Fehlalarme gegen Sicherheit tauschen.

Synthese

Deadlock‑Erkennung ist die Laufzeit‑ oder Analysezeit‑Identifikation zyklischer Ressourcen‑Wartebedingungen mittels Wait‑For‑ oder Resource‑Allocation‑Graphen; sie ist Teil des größeren Entwurfsraums von Prävention, Vermeidung und Wiederherstellung und bietet ein pragmatisches Mittel, blockierende Zyklen zu entdecken, damit kontrollierte Wiederherstellungsstrategien den Fortschritt wiederherstellen können.