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 benoetigte Ressource zu erhalten, entsteht eine zyklische Wartesituation, aus der es ohne aeusseren Eingriff keinen Ausweg gibt.

Deadlocks sind ein klassisches Problem der nebenlaeufigen Programmierung und koennen sowohl in Betriebssystemen als auch in Datenbanken und Anwendungsprogrammen auftreten. Als Fachinformatiker fuer Anwendungsentwicklung wirst du beim Arbeiten mit Multithreading und Datenbanktransaktionen auf dieses Konzept stossen.

Die vier Coffman-Bedingungen

Damit ein Deadlock entstehen kann, muessen vier Bedingungen gleichzeitig erfuellt 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 erfuellt 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 muessen warten, bis die Ressource freigegeben wird. Beispiele fuer solche Ressourcen sind Drucker, Dateien im Schreibmodus oder Datenbanksperren.

2. Halten und Warten (Hold and Wait)

Ein Prozess haelt 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, waehrend er auf die zusaetzlichen wartet.

3. Keine Verdrängung (No Preemption)

Ressourcen koennen 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 naechsten Prozess in der Kette gehalten wird. Der letzte Prozess wartet auf eine Ressource, die der erste Prozess haelt. Diese zyklische Abhaengigkeit schliesst 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 haeufig verwendet, um Deadlocks und deren Loesung zu illustrieren.

Deadlocks in verschiedenen Kontexten

Deadlocks koennen 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-Geraete 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 Datensaetze oder Tabellen setzen. Wenn Transaktion A eine Zeile sperrt und auf eine andere wartet, die Transaktion B gesperrt hat, waehrend 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 koennen Deadlocks auftreten, wenn mehrere Threads um gemeinsam genutzte Ressourcen konkurrieren. Das passiert haeufig beim Arbeiten mit Locks (Sperren), Mutexen oder Semaphoren. Die Java-Dokumentation beschreibt ausfuehrlich, wie Deadlocks bei der Thread-Synchronisation entstehen koennen.

Strategien zur Behandlung von Deadlocks

Es gibt verschiedene Ansaetze, um mit Deadlocks umzugehen. Diese lassen sich in vier Kategorien einteilen: Praevention, Vermeidung, Erkennung und Ignorieren.

Deadlock-Praevention

Bei der Praevention wird das System so gestaltet, dass mindestens eine der vier Coffman-Bedingungen niemals erfuellt sein kann. Dadurch wird das Auftreten von Deadlocks strukturell unmoeglich gemacht.

• Aufheben des wechselseitigen Ausschlusses: Ressourcen werden nur dann exklusiv vergeben, wenn es unbedingt noetig ist. Lesezugriffe koennen oft parallel erfolgen.
• Alle Ressourcen auf einmal anfordern: Prozesse muessen alle benoetigten Ressourcen gleichzeitig anfordern (verhindert Hold and Wait).
• Ressourcen-Entzug erlauben: Das System kann Ressourcen bei Bedarf entziehen und spaeter neu zuteilen (hebt No Preemption auf).
• Lineare Ordnung der Ressourcen: Ressourcen werden nummeriert und duerfen nur in aufsteigender Reihenfolge angefordert werden (verhindert zyklisches Warten).

Deadlock-Vermeidung

Bei der Vermeidung werden Ressourcenanforderungen zur Laufzeit geprueft, bevor sie gewaehrt werden. Das System entscheidet dynamisch, ob eine Anforderung zu einem Deadlock fuehren koennte, und verweigert sie gegebenenfalls.

Der bekannteste Algorithmus ist der Bankier-Algorithmus von Edsger Dijkstra. Er simuliert die Ressourcenzuweisung und prueft, ob das System danach noch in einem sicheren Zustand waere. 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 prueft 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 Moeglichkeiten: einen oder mehrere Prozesse abbrechen, Ressourcen von Prozessen entziehen oder das gesamte System neu starten. Datenbanksysteme waehlen oft den Prozess (die Transaktion) zum Abbruch, der am wenigsten Arbeit verliert.

Vogel-Strauss-Algorithmus

Der sogenannte Vogel-Strauss-Algorithmus (Ostrich Algorithm) ist die einfachste Strategie: Das Problem wird ignoriert. Wenn Deadlocks selten auftreten und die Kosten fuer Praevention 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 aehnlichen Problemen verwechselt. Die wichtigsten Unterschiede solltest du kennen.

Livelock

Bei einem Livelock sind die Prozesse nicht blockiert, sondern aendern staendig 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 zurueck. Sie bewegen sich, kommen aber nicht aneinander vorbei.

Starvation (Verhungern)

Bei Starvation wird ein Prozess dauerhaft benachteiligt und erhaelt nie die benoetigten Ressourcen, obwohl diese verfuegbar 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 Loesungsstrategien 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 haelt und auf lock2 wartet, waehrend Thread 2 lock2 haelt und auf lock1 wartet. Das Programm haengt dann dauerhaft.

Loesung: 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 taeglichen Arbeit als IT-Fachkraft wirst du Deadlocks vor allem in zwei Bereichen begegnen: bei der Datenbankentwicklung und bei der Entwicklung nebenlaeufiger Anwendungen. Datenbank-Administratoren und Backend-Entwickler muessen wissen, wie sie Transaktionen so gestalten, dass Deadlocks minimiert werden. Als Fachinformatiker fuer Systemintegration kannst du bei der Analyse von Performance-Problemen oder haengenden Systemen auf Deadlocks als Ursache stossen.

Quellen und weiterfuehrende Links

• Deadlock (Informatik) - Wikipedia - Ausfuehrlicher 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