Deadlock (Verklemmung)

Ein Deadlock (deutsch: Verklemmung) ist ein Zustand in einem Computersystem, bei dem zwei oder mehr Prozesse oder Threads sich gegenseitig blockieren. Jeder beteiligte Prozess wartet auf eine Ressource, die ein anderer Prozess bereits exklusiv belegt hat. Da keiner der Prozesse seine gehaltene Ressource freigeben kann, ohne zuerst die benötigte Ressource zu erhalten, entsteht eine zyklische Wartesituation, aus der es ohne äußeren Eingriff keinen Ausweg gibt.

Deadlocks sind ein klassisches Problem der nebenläufigen Programmierung und können sowohl in Betriebssystemen als auch in Datenbanken und Anwendungsprogrammen auftreten. Als Fachinformatiker für Anwendungsentwicklung wirst du beim Arbeiten mit Multithreading und Datenbanktransaktionen auf dieses Konzept stoßen.

Die vier Coffman-Bedingungen

Damit ein Deadlock entstehen kann, müssen vier Bedingungen gleichzeitig erfüllt sein. Diese wurden 1971 von Edward G. Coffman, Jr. und seinen Kollegen erstmals systematisch beschrieben und sind seitdem als Coffman-Bedingungen bekannt. Wenn mindestens eine dieser Bedingungen nicht erfüllt ist, kann kein Deadlock auftreten.

1. Wechselseitiger Ausschluss (Mutual Exclusion)

Mindestens eine Ressource muss exklusiv von einem Prozess genutzt werden. Das bedeutet, dass zu einem Zeitpunkt nur ein einziger Prozess auf diese Ressource zugreifen kann. Andere Prozesse müssen warten, bis die Ressource freigegeben wird. Beispiele für solche Ressourcen sind Drucker, Dateien im Schreibmodus oder Datenbanksperren.

2. Halten und Warten (Hold and Wait)

Ein Prozess hält bereits mindestens eine Ressource und wartet gleichzeitig auf weitere Ressourcen, die von anderen Prozessen belegt sind. Der Prozess gibt seine bereits gehaltenen Ressourcen nicht frei, während er auf die zusätzlichen wartet.

3. Keine Verdrängung (No Preemption)

Ressourcen können einem Prozess nicht gewaltsam entzogen werden. Ein Prozess muss seine Ressourcen freiwillig freigeben. Das Betriebssystem oder ein anderer Prozess kann die Ressource nicht einfach wegnehmen, um sie einem anderen zuzuteilen.

4. Zyklisches Warten (Circular Wait)

Es existiert eine Kette von Prozessen, bei der jeder Prozess auf eine Ressource wartet, die vom nächsten Prozess in der Kette gehalten wird. Der letzte Prozess wartet auf eine Ressource, die der erste Prozess hält. Diese zyklische Abhängigkeit schließt den Kreis und macht die Verklemmung perfekt.

Anschauliches Beispiel

Stell dir zwei Personen vor, die an einem Tisch sitzen. Zum Essen braucht jeder eine Gabel und ein Messer. Person A nimmt die Gabel, Person B nimmt das Messer. Jetzt wartet Person A auf das Messer (das Person B hat) und Person B wartet auf die Gabel (die Person A hat). Keiner kann essen, keiner will sein Besteck loslassen. Das ist ein klassischer Deadlock.

In der Informatik ist dieses Szenario als Dining Philosophers Problem (Problem der speisenden Philosophen) bekannt und wird häufig verwendet, um Deadlocks und deren Lösung zu illustrieren.

Deadlocks in verschiedenen Kontexten

Deadlocks können in unterschiedlichen Bereichen der IT auftreten. Je nach Kontext unterscheiden sich die betroffenen Ressourcen und die Strategien zur Behandlung.

Betriebssysteme

In Betriebssystemen konkurrieren Prozesse um Ressourcen wie Speicher, CPU-Zeit, E/A-Geräte oder Dateien. Wenn mehrere Prozesse gleichzeitig auf exklusive Ressourcen zugreifen wollen, kann es zu Deadlocks kommen. Moderne Betriebssysteme wie Linux und Windows verwenden verschiedene Strategien, um Deadlocks zu vermeiden oder zu erkennen.

Datenbanken

In Datenbanksystemen entstehen Deadlocks typischerweise bei konkurrierenden Transaktionen, die Sperren (Locks) auf Datensätze oder Tabellen setzen. Wenn Transaktion A eine Zeile sperrt und auf eine andere wartet, die Transaktion B gesperrt hat, während B auf die Zeile von A wartet, entsteht ein Deadlock. Die meisten Datenbanksysteme wie PostgreSQL erkennen solche Situationen automatisch und brechen eine der Transaktionen ab.

Multithreading

Bei der parallelen Programmierung mit Threads können Deadlocks auftreten, wenn mehrere Threads um gemeinsam genutzte Ressourcen konkurrieren. Das passiert häufig beim Arbeiten mit Locks (Sperren), Mutexen oder Semaphoren. Die Java-Dokumentation beschreibt ausführlich, wie Deadlocks bei der Thread-Synchronisation entstehen können.

Strategien zur Behandlung von Deadlocks

Es gibt verschiedene Ansätze, um mit Deadlocks umzugehen. Diese lassen sich in vier Kategorien einteilen: Prävention, Vermeidung, Erkennung und Ignorieren.

Deadlock-Prävention

Bei der Prävention wird das System so gestaltet, dass mindestens eine der vier Coffman-Bedingungen niemals erfüllt sein kann. Dadurch wird das Auftreten von Deadlocks strukturell unmöglich gemacht.

• Aufheben des wechselseitigen Ausschlusses: Ressourcen werden nur dann exklusiv vergeben, wenn es unbedingt nötig ist. Lesezugriffe können oft parallel erfolgen.
• Alle Ressourcen auf einmal anfordern: Prozesse müssen alle benötigten Ressourcen gleichzeitig anfordern (verhindert Hold and Wait).
• Ressourcen-Entzug erlauben: Das System kann Ressourcen bei Bedarf entziehen und später neu zuteilen (hebt No Preemption auf).
• Lineare Ordnung der Ressourcen: Ressourcen werden nummeriert und dürfen nur in aufsteigender Reihenfolge angefordert werden (verhindert zyklisches Warten).

Deadlock-Vermeidung

Bei der Vermeidung werden Ressourcenanforderungen zur Laufzeit geprüft, bevor sie gewährt werden. Das System entscheidet dynamisch, ob eine Anforderung zu einem Deadlock führen könnte, und verweigert sie gegebenenfalls.

Der bekannteste Algorithmus ist der Bankier-Algorithmus von Edsger Dijkstra. Er simuliert die Ressourcenzuweisung und prüft, ob das System danach noch in einem sicheren Zustand wäre. Allerdings setzt dieser Algorithmus voraus, dass die maximalen Ressourcenanforderungen aller Prozesse im Voraus bekannt sind.

Deadlock-Erkennung und -Behebung

Bei diesem Ansatz werden Deadlocks zugelassen, aber das System prüft periodisch, ob einer aufgetreten ist. Dazu wird typischerweise ein Resource Allocation Graph (Ressourcen-Zuteilungsgraph) verwendet. Wenn ein Zyklus in diesem Graphen erkannt wird, liegt ein Deadlock vor.

Zur Behebung gibt es mehrere Möglichkeiten: einen oder mehrere Prozesse abbrechen, Ressourcen von Prozessen entziehen oder das gesamte System neu starten. Datenbanksysteme wählen oft den Prozess (die Transaktion) zum Abbruch, der am wenigsten Arbeit verliert.

Vogel-Strauß-Algorithmus

Der sogenannte Vogel-Strauß-Algorithmus (Ostrich Algorithm) ist die einfachste Strategie: Das Problem wird ignoriert. Wenn Deadlocks selten auftreten und die Kosten für Prävention oder Erkennung hoch sind, kann es wirtschaftlich sinnvoller sein, gelegentlich einen manuellen Neustart in Kauf zu nehmen. Diesen Ansatz verwenden viele Desktop-Betriebssysteme.

Unterschied zu verwandten Konzepten

Deadlocks werden manchmal mit ähnlichen Problemen verwechselt. Die wichtigsten Unterschiede solltest du kennen.

Livelock

Bei einem Livelock sind die Prozesse nicht blockiert, sondern ändern ständig ihren Zustand als Reaktion aufeinander, ohne jemals Fortschritt zu machen. Stell dir zwei Menschen vor, die sich in einem Gang begegnen: Beide weichen zur gleichen Seite aus, dann wieder zur anderen, dann wieder zurück. Sie bewegen sich, kommen aber nicht aneinander vorbei.

Starvation (Verhungern)

Bei Starvation wird ein Prozess dauerhaft benachteiligt und erhält nie die benötigten Ressourcen, obwohl diese verfügbar werden. Im Gegensatz zum Deadlock machen andere Prozesse durchaus Fortschritt, nur der verhungernde Prozess nicht. Dies passiert oft bei unfairen Scheduling-Algorithmen.

Das Erkennen des genauen Problems ist wichtig, da die Lösungsstrategien unterschiedlich sind.

Praktisches Beispiel in Java

Das folgende Java-Beispiel zeigt, wie ein Deadlock entstehen kann. Zwei Threads versuchen, zwei Locks in unterschiedlicher Reihenfolge zu erhalten.

public class DeadlockExample {
    private static final Object lock1 = new Object();
    private static final Object lock2 = new Object();

    public static void main(String[] args) {
        Thread thread1 = new Thread(() -> {
            synchronized (lock1) {
                System.out.println("Thread 1: haelt lock1");
                try { Thread.sleep(100); } catch (InterruptedException e) {}
                synchronized (lock2) {
                    System.out.println("Thread 1: haelt lock1 und lock2");
                }
            }
        });

        Thread thread2 = new Thread(() -> {
            synchronized (lock2) {
                System.out.println("Thread 2: haelt lock2");
                try { Thread.sleep(100); } catch (InterruptedException e) {}
                synchronized (lock1) {
                    System.out.println("Thread 2: haelt lock2 und lock1");
                }
            }
        });

        thread1.start();
        thread2.start();
    }
}

Thread 1 sperrt zuerst lock1, dann lock2. Thread 2 macht es genau umgekehrt. Wenn beide Threads gleichzeitig laufen, kann es passieren, dass Thread 1 lock1 hält und auf lock2 wartet, während Thread 2 lock2 hält und auf lock1 wartet. Das Programm hängt dann dauerhaft.

Lösung: Konsistente Lock-Reihenfolge

Der einfachste Weg, diesen Deadlock zu vermeiden, ist eine konsistente Reihenfolge beim Anfordern der Locks. Wenn beide Threads zuerst lock1 und dann lock2 anfordern, kann kein zyklisches Warten entstehen.

Deadlocks in der IT-Praxis

In der täglichen Arbeit als IT-Fachkraft wirst du Deadlocks vor allem in zwei Bereichen begegnen: bei der Datenbankentwicklung und bei der Entwicklung nebenläufiger Anwendungen. Datenbank-Administratoren und Backend-Entwickler müssen wissen, wie sie Transaktionen so gestalten, dass Deadlocks minimiert werden. Als Fachinformatiker für Systemintegration kannst du bei der Analyse von Performance-Problemen oder hängenden Systemen auf Deadlocks als Ursache stoßen.

Quellen und weiterführende Links

• Deadlock (Informatik) - Wikipedia - Ausführlicher deutschsprachiger Artikel
• Oracle Java Tutorial: Deadlock - Offizielle Java-Dokumentation zu Deadlocks
• PostgreSQL: Explicit Locking - Sperrmechanismen und Deadlock-Erkennung in PostgreSQL
• Microsoft SQL Server: Deadlocks Guide - Umfassende Anleitung zu Deadlocks in SQL Server