Messer und Bretter: Deadlock

Fünfte Nacht, elf Uhr. In der Küche ist es merkwürdig still. Minho hält das Messer in der Hand und starrt aufs Schneidebrett, Sua drückt das Brett an sich und starrt aufs Messer. Beide sagen immer nur: „Ich bin gleich fertig, dann kriegst du's.“

Herr Tak hört auf, Lauchzwiebeln zu schneiden, und murmelt: „Wenn beide nur rumstehen, wird keiner fertig.“

Chefin Yoon Seoyeon hält den Timer an ihrem Hals an. „Legt beide ab. Das ist nicht passiert, weil jemand zu langsam war. Das ist passiert, weil es keine Regel gibt.“

5-1. Zwei Köche, die aufeinander warten (7 Min.)

Wie die Herdplatten-Regel von gestern Nacht sind auch Messer und Brett Locks, die immer nur eine Person gleichzeitig benutzen kann. Minho greift in der Reihenfolge Messer → Brett zu, Sua in der Reihenfolge Brett → Messer.

import threading
import time

knife = threading.Lock()
board = threading.Lock()

def minho():
    with knife:              # nimmt das Messer
        time.sleep(0.1)
        with board:          # wartet aufs Brett
            print("minho done")

def sua():
    with board:              # nimmt das Brett
        time.sleep(0.1)
        with knife:          # wartet aufs Messer
            print("sua done")

a = threading.Thread(target=minho, daemon=True)
b = threading.Thread(target=sua, daemon=True)
a.start(); b.start()
a.join(timeout=1); b.join(timeout=1)
print("alive:", a.is_alive(), b.is_alive())
# alive: True True

• Selbst nach einer Sekunde Warten sind beide Threads noch am Leben. Sie arbeiten aber nicht, sondern hängen fest, weil jeder darauf wartet, dass der andere loslässt. Das ist ein Deadlock (eine Verklemmung).
• join(timeout=1) wartet höchstens eine Sekunde und kehrt dann zurück. Weil die Threads mit daemon=True gestartet wurden, endet das Programm trotzdem ganz normal. Wenn du selbst mit Deadlocks experimentierst, bau dir immer so einen Notausgang ein.
• time.sleep(0.1) sorgt dafür, dass beide ihr erstes Werkzeug fast gleichzeitig greifen. In echten Programmen entsteht diese Lücke nur sehr selten, und genau das macht den Deadlock zu einem besonders fiesen Bug, der „nur manchmal“ auftritt.

Damit das Programm selbst merkt, dass es feststeckt, nimmst du acquire(timeout=...). Es liefert True, wenn es den Lock bekommt, und False, wenn es ihn in der Zeit nicht bekommt. Bei with lock: kannst du kein Zeitlimit angeben, also rufst du hier acquire und release selbst auf.

knife = threading.Lock()   # neues Messer, neues Brett
board = threading.Lock()

def cook(name, first, second, patience):
    with first:
        time.sleep(0.1)
        if second.acquire(timeout=patience):   # höchstens patience Sekunden warten
            second.release()
            print(name, "done")
        else:
            print(name, f"gave up after {patience}s")

a = threading.Thread(target=cook, args=("minho", knife, board, 1.0))
b = threading.Thread(target=cook, args=("sua", board, knife, 0.5))
a.start(); b.start()
a.join(); b.join()
# sua gave up after 0.5s
# minho done

Sua gibt nach 0,5 Sekunden auf und legt das Brett ab. Minho, der noch wartet, schnappt sich das Brett und kocht fertig. Es reicht, wenn einer nachgibt, und der Deadlock löst sich. Warum das so ist, erklären die vier Bedingungen im nächsten Abschnitt.

5-2. Die vier Bedingungen für einen Deadlock (8 Min.)

Ein Deadlock entsteht nur, wenn die folgenden vier Bedingungen alle gleichzeitig erfüllt sind. Umgekehrt heißt das: Brichst du nur eine davon, kann kein Deadlock entstehen.

• Gegenseitiger Ausschluss ist der Grund, warum es Locks überhaupt gibt, deshalb bricht man ihn normalerweise nicht. Hätten wir genug Messer, müssten wir gar nicht erst sperren.
• In der Praxis bricht man am häufigsten das zyklische Warten. Greifen alle in derselben Reihenfolge zu, kann kein Kreis entstehen.
• Danach kommt die Methode, Halten und Warten und Keine Verdrängung zusammen zu brechen: Wer nach einer gewissen Zeit nicht zum Zug kommt, legt freiwillig ab, was er schon hält.

5-3. Lösung 1: Alle greifen in derselben Reihenfolge zu (8 Min.)

Die Chefin schreibt eine Regel an die Tafel: „Jedes Werkzeug bekommt eine Nummer. Messer 1, Brett 2. Gegriffen wird immer mit der kleineren Nummer zuerst.“

Greifen Minho und Sua beide zuerst nach dem Messer, wartet nur derjenige aufs Brett, der das Messer schon hat. Wer das Messer nicht bekommen hat, wartet mit leeren Händen, also kann kein Kreis entstehen. Verlassen wir uns bei dieser Regel nicht auf das Gedächtnis der Leute, sondern packen sie in eine Funktion.

from contextlib import contextmanager

KNIFE = (1, threading.Lock())   # (Nummer, Lock)
BOARD = (2, threading.Lock())

@contextmanager
def hold(*tools):
    ordered = sorted(tools, key=lambda t: t[0])   # kleinste Nummer zuerst
    for _, lock in ordered:
        lock.acquire()
    try:
        yield
    finally:
        for _, lock in reversed(ordered):        # beim Loslassen umgekehrt
            lock.release()

done = []

def minho():
    for _ in range(100):
        with hold(KNIFE, BOARD):
            time.sleep(0)
    done.append("minho")

def sua():
    for _ in range(100):
        with hold(BOARD, KNIFE):     # anders hingeschrieben, aber gleich gegriffen
            time.sleep(0)
    done.append("sua")

ts = [threading.Thread(target=f, daemon=True) for f in (minho, sua)]
for t in ts: t.start()
for t in ts: t.join(timeout=2)
print(sorted(done), [t.is_alive() for t in ts])
# ['minho', 'sua'] [False, False]

• Auch wenn Sua hold(BOARD, KNIFE) schreibt: hold sortiert nach Nummer, also wird tatsächlich in der Reihenfolge Messer → Brett gegriffen.
• Selbst wenn beide je 100-mal abwechselnd zugreifen, bleibt nichts ein einziges Mal hängen. Daran ändert auch time.sleep(0) nichts, das jedes Mal Gelegenheit gibt, den Platz zu wechseln.
• Die Nummern kannst du selbst festlegen. Brauchst du sie nur innerhalb des Programms, geht auch ein Wert, der garantiert nicht doppelt vorkommt, etwa id(lock). Entscheidend ist, dass der gesamte Code dasselbe Kriterium verwendet.
• Die Reihenfolge beim Loslassen spielt für Deadlocks keine Rolle. Wenn du dir aber angewöhnst, in umgekehrter Reihenfolge loszulassen, liest sich der Code leichter.

Sobald irgendwo mehr als ein Lock gebraucht wird, schreib diese Regel in einen Kommentar ganz oben im Code oder in die Doku. In dem Moment, in dem jemand Neues die Reihenfolge nicht kennt und andersherum greift, ist der Deadlock wieder da.

5-4. Lösung 2: Ablegen, wenn es hakt (7 Min.)

Manchmal lässt sich keine Reihenfolge festlegen, nämlich dann, wenn man vorher nicht weiß, welche Locks man brauchen wird. Dann gilt die Regel: „Wenn ich es nach einer gewissen Zeit nicht bekomme, lege ich auch das ab, was ich schon halte, und fange von vorne an.“

import random

tries = {}

def polite_cook(name, first, second):
    tries[name] = 0
    while True:
        tries[name] += 1
        with first:
            time.sleep(0.05)
            if second.acquire(timeout=0.1):     # wenn nicht innerhalb von 0,1 s
                try:
                    return                       # beides gegriffen: Gericht fertig
                finally:
                    second.release()
        # beim Verlassen von with wurde first abgelegt
        time.sleep(random.uniform(0, 0.1))       # zufällig kurz warten, dann neu versuchen

a = threading.Thread(target=polite_cook, args=("minho", knife, board))
b = threading.Thread(target=polite_cook, args=("sua", board, knife))
a.start(); b.start()
a.join(); b.join()
print(tries)
# z. B.: {'minho': 2, 'sua': 3}  (bei jedem Lauf anders)

Nach ein paar Zusammenstößen werden am Ende beide fertig. Nimmst du hier random.uniform(0, 0.1) heraus, kann ein neues Problem auftauchen: der Livelock.

Das ist wie bei zwei Leuten, die sich im Flur begegnen und immer wieder zur selben Seite ausweichen. Anders als beim Deadlock sind beide eifrig in Bewegung, aber keiner kocht je ein Gericht fertig. Mischst du eine zufällige Pause hinein, bewegt sich irgendwann einer zuerst, und der Kreislauf bricht.

Bei echten Threads schwankt der Zeitpunkt der Ausführung immer ein wenig, deshalb lässt sich ein Livelock mit einem kurzen Beispiel kaum zuverlässig nachstellen. Genau das macht ihn gefährlicher: Er zeigt sich nur an Tagen mit hoher Last. Wenn du Lösung 2 verwendest, bau unbedingt die zufällige Pause mit ein.

5-5. Fünf Köche und fünf Messer (6 Min.)

In der Informatik gibt es ein berühmtes Problem: das Philosophenproblem (die speisenden Philosophen). Fünf Personen sitzen an einem runden Tisch, zwischen je zweien liegt eine Gabel. Wer essen will, braucht beide Gabeln links und rechts. In die Küche übertragen: fünf Köche und fünf Messer an einer runden Arbeitsplatte.

N = 5

def service(ordered):
    knives = [threading.Lock() for _ in range(N)]   # fünf Messer
    meals = [0] * N

    def cook(i):
        left, right = i, (i + 1) % N
        if ordered:
            first, second = min(left, right), max(left, right)
        else:
            first, second = left, right
        for _ in range(3):
            with knives[first]:
                time.sleep(0.05)          # kurz mit dem ersten Messer in der Hand
                with knives[second]:
                    meals[i] += 1

    ts = [threading.Thread(target=cook, args=(i,), daemon=True) for i in range(N)]
    for t in ts: t.start()
    for t in ts: t.join(timeout=1)
    return sum(t.is_alive() for t in ts), meals

print("left first:", service(ordered=False))
print("small first:", service(ordered=True))
# left first: (5, [0, 0, 0, 0, 0])
# small first: (0, [3, 3, 3, 3, 3])

• Alle greifen zuerst links: Nehmen alle fünf gleichzeitig ihr linkes Messer, liegt das rechte immer schon in der Hand des Nachbarn. Das Warten wird zu einem Kreis, der einmal um alle fünf herumläuft, und auch nach einer Sekunde hängen alle fünf Threads fest.
• Kleinere Nummer zuerst: Die Köche 0 bis 3 (im Code wird ab 0 gezählt) greifen wie gehabt zuerst links, nur Koch 4 greift jetzt zuerst rechts (Messer 0). Damit ist der Kreis an einer Stelle durchbrochen, und alle kochen ihre drei Gerichte fertig.

Der Versuchsaufbau unten zeigt diese Situation Schritt für Schritt. Würden wir echte Threads auf dem Server in einen Deadlock schicken, kämen sie nie wieder heraus, deshalb läuft ausgerechnet dieser Aufbau als Simulation. Die Zahl über einem Messer ist die Nummer des Kochs, der es gerade hält.

• Alle greifen zuerst links: Im ersten Schritt hält jeder der fünf ein Messer, und die rote Deadlock-Warnung erscheint. Danach ändert sich nichts mehr, so oft du auch drückst.
• Zuerst das Messer mit der kleineren Nummer: Koch 5 will zuerst Messer 1 nehmen und muss warten. Dadurch bleibt Messer 5 frei, und Koch 4 fängt im zweiten Schritt an zu kochen. Schaltest du „Automatisch abspielen“ ein, wächst die Zahl der fertigen Gerichte bei allen gleichmäßig.
• Ablegen, wenn es hakt: Die ersten beiden Schritte sehen wie ein Deadlock aus, und auch die Warnung erscheint. Im dritten Schritt legen die wartenden Köche ihre Messer ab, und Koch 5 schnappt sich ein freies Messer und beginnt zu kochen. Denk daran: Würden alle im exakt gleichen Takt ablegen und wieder zugreifen, könnte daraus ein Livelock werden.

5-6. Die stillstehende Küche untersuchen: faulthandler (4 Min.)

Wenn ein Programm hängt und du nicht weißt, wo, hilft dir faulthandler aus der Standardbibliothek. Es gibt aus, in welcher Zeile jeder Thread gerade steht. Speichere den Code unten als stuck.py und führ ihn aus.

import faulthandler
import threading
import time

knife = threading.Lock()
board = threading.Lock()

def minho():
    with knife:
        time.sleep(0.1)
        with board:
            pass

def sua():
    with board:
        time.sleep(0.1)
        with knife:
            pass

faulthandler.dump_traceback_later(1)        # steht es nach 1 s noch hier, alle Threads ausgeben
crew = [threading.Thread(target=f, name=f.__name__, daemon=True) for f in (minho, sua)]
for t in crew: t.start()
for t in crew: t.join(timeout=2)
faulthandler.cancel_dump_traceback_later()  # rechtzeitig fertig? dann Auftrag löschen

Timeout (0:00:01)!
Thread 0x00009560 [sua] (most recent call first):
  File "stuck.py", line 17 in sua
  ...
Thread 0x0000a670 [minho] (most recent call first):
  File "stuck.py", line 11 in minho
  ...

Die Ausgabe ist gekürzt (Adressen und Pfade sind bei jedem Lauf anders). Sua hängt in Zeile 17 bei with knife:, Minho in Zeile 11 bei with board:. Auf einen Blick siehst du, wer auf was wartet.

• faulthandler.dump_traceback_later(timeout): plant ein, nach timeout Sekunden die Position aller Threads auf die Standardfehlerausgabe zu schreiben. Mit repeat=True wiederholt es sich, mit exit=True beendet es nach der Ausgabe das Programm.
• faulthandler.dump_traceback(all_threads=True): gibt ohne Planung sofort aus. Praktisch, um mitten in einer langen Aufgabe den Zustand festzuhalten.
• Bleiben deine Tests ab und zu hängen, setz dump_traceback_later an den Anfang des Testlaufs. Dann bleibt an dem Tag, an dem es passiert, der Täter zurück.

Küchenschluss (10 Min.)

Das Ziel für heute Nacht war, dass drei Köche, die sich Messer und Brett teilen, je 100-mal kochen, ohne ein einziges Mal hängen zu bleiben. Herr Tak braucht sogar drei Werkzeuge, inklusive Pfanne. Gibst du jedem Werkzeug eine Nummer und lässt alle über hold greifen, ist es egal, wer was in welcher Reihenfolge hinschreibt.

PAN = (3, threading.Lock())
meals = {}

def cook(name, *tools):
    for _ in range(100):
        with hold(*tools):            # immer das Werkzeug mit der kleineren Nummer zuerst
            time.sleep(0)
            meals[name] = meals.get(name, 0) + 1

crew = [threading.Thread(target=cook, args=a, daemon=True) for a in [
    ("minho", KNIFE, BOARD), ("sua", BOARD, KNIFE), ("tak", PAN, BOARD, KNIFE)]]
for t in crew: t.start()
for t in crew: t.join(timeout=3)
print([meals[n] for n in ("minho", "sua", "tak")], sum(t.is_alive() for t in crew))
# [100, 100, 100] 0

Alle drei je 100-mal, hängen geblieben ist niemand. Die Chefin schreibt neben die Regel an der Tafel noch eine Zeile: „Messer 1, Brett 2, Pfanne 3. Kleinere Nummer zuerst.“

„Heute standen wir wegen der Werkzeuge still. Morgen stehen wir wegen der Leute still. Wenn die Bestellungen nur so reinprasseln: Wer entscheidet dann, wer welche Bestellung macht?“

Übungen

1. Lösch im ersten Beispiel aus 5-1 das time.sleep(0.1) und führ es mehrmals aus. Gibt es jedes Mal einen Deadlock? Schreib in einem Satz auf, warum ein „Bug, der nur manchmal hängt“ gefährlicher ist.
2. Prüf mit print, dass in service aus 5-5 bei ordered=True nur Koch 4 in einer anderen Reihenfolge greift. Erklär mit den vier Bedingungen, warum sich der Deadlock schon löst, wenn nur ein einziger Koch seine Reihenfolge ändert.
3. Wähl im Versuchsaufbau „Ablegen, wenn es hakt“, lass es mit „Automatisch abspielen“ 24 Schritte laufen und vergleich die Zahl der fertigen Gerichte mit „Zuerst das Messer mit der kleineren Nummer“.