Zum Inhalt
wannacode

Deadlock

Kurz gesagt: Ein Deadlock ist ein Zustand, in dem zwei Threads je ein Lock halten und für immer auf das andere warten; eine gemeinsame Reihenfolge der Locks macht ihn unmöglich.

Problem

Die Nacht, in der die Lager stehen blieben

Der Shop hat zwei Lager: Sofia und Plovdiv. Wenn einem die Kopfhörer ausgehen, verschiebt ein System Ware aus dem anderen. Jede Umlagerung sperrt beide Lager, damit keine Stücke verloren gehen, wie in der Lektion über Sperren.

In einer Nacht um 3:12 starten zwei Umlagerungen gleichzeitig: 5 Stück von Sofia nach Plovdiv und 3 von Plovdiv nach Sofia. Das Programm bleibt stehen. Der Prozessor steht bei 0 %, im Log ist kein Fehler, und die Threads stehen einfach da und warten. Bis zum Morgen läuft keine einzige Umlagerung durch, und in beiden Lagern stauen sich die Bestellungen.

Die Idee

Jeder hält eins und wartet auf das andere

Eine Umlagerung sperrt zuerst das Lager, aus dem sie verschiebt, dann das Lager, in das sie verschiebt:

  • Umlagerung 1 (Sofia → Plovdiv) nimmt das Lock von Sofia;
  • im selben Moment nimmt Umlagerung 2 (Plovdiv → Sofia) das Lock von Plovdiv;
  • Umlagerung 1 will das Lock von Plovdiv: Umlagerung 2 hält es, also wartet sie;
  • Umlagerung 2 will das Lock von Sofia: Umlagerung 1 hält es, also wartet sie.

Jede wartet darauf, dass die andere loslässt, und keine lässt los, bevor sie bekommt, was sie will. Das Warten bildet einen Kreis. Das ist ein Deadlock: Die Threads machen keinen Fehler und stürzen nicht ab, sie bleiben einfach für immer stehen.

Das Schlimmste ist, dass es selten passiert. Die beiden Umlagerungen müssen ihr erstes Lock fast im selben Moment nehmen. Es geht also tausendmal im Test durch und bleibt um 3:12 in der Nacht stehen.

Sieh es dir an

Der Kreis

function transfer(cells, source, target, qty) {
  // eine gemeinsame Reihenfolge: zuerst die kleinere id
  const first = Math.min(source, target);
  const second = Math.max(source, target);
  lock(cells, first);
  try {
    lock(cells, second);
    try {
      cells[STOCK + source] -= qty;
      cells[STOCK + target] += qty;
    } finally {
      unlock(cells, second);
    }
  } finally {
    unlock(cells, first);
  }
}
Schritt für Schritt, in Worten
  1. Zwei Umlagerungen gleichzeitig, in zwei Workern. T1 verschiebt 5 Stück von Sofia nach Plovdiv, T2 verschiebt 3 zurück. Jede sperrt zuerst das Lager, aus dem sie nimmt.
  2. T1 nimmt das Lock von Sofia.
  3. Im selben Moment nimmt T2 das Lock von Plovdiv.
  4. Die Barriere lässt sie erst weiter, wenn beide ihr erstes Lock halten. Sie ist hier, damit der schlechte Moment bei jedem Lauf eintritt.
  5. T1 wartet auf das Lock von Plovdiv, das T2 hält. T2 wartet auf das Lock von Sofia, das T1 hält. Ein Kreis: Keiner lässt los.
  6. Nach 200 ms geben beide auf: Deadlock. Ohne das Timeout würden sie ewig warten, und das Programm würde hängen. Bestand: 500 und 300.
  7. Die Lösung: eine Reihenfolge für alle. Zuerst das Lock des Lagers mit der kleineren id: Sofia (1), dann Plovdiv (2), egal in welche Richtung umgelagert wird.
  8. Beide beginnen mit Sofia. T1 bekommt das Lock; T2 wartet, hält aber nichts.
  9. T1 nimmt auch Plovdiv, verschiebt 5 Stück und gibt beide Locks frei.
  10. Jetzt nimmt T2 Sofia, dann Plovdiv, und verschiebt 3 zurück.
  11. Beide Umlagerungen sind durchgelaufen: 498 und 302. Mit einer Reihenfolge hält keiner ein Lock, während er auf das Lock von jemandem wartet, der auf ihn wartet: Es gibt keinen Kreis.

Damit du den schlechten Moment bei jedem Lauf siehst, führt das Programm ihn absichtlich herbei. Die Barriere meet hält jede Umlagerung an, bis beide sie erreicht haben: So halten beide schon ihr erstes Lock, wenn sie das zweite wollen. Die zweite Barriere hält sie fest, bis beide es versucht haben. Ohne sie könnte eine das Lock bekommen, das die andere freigegeben hat, und die Ausgabe hinge vom Timing ab.

Auf das zweite Lock wird mit einem Timeout gewartet: höchstens 200 ms. Kommt es nicht, gibt die Umlagerung auf und gibt ihr eigenes frei.

JavaScript hat keine Locks, deshalb sind sie hier Zellen in einem SharedArrayBuffer, wie in der vorigen Lektion: 0 ist frei, 1 ist genommen. tryLock wartet mit Atomics.wait(…, die verbleibenden ms) und gibt auf, wenn die Zeit abläuft. meet ist die Barriere: Jeder Worker addiert 1 und schläft, bis es 2 sind.
// cells: [Locks, Bestände, Barrieren, Ergebnisse] in einem SharedArrayBuffer
const LOCK = 0, STOCK = 2, MEET_1 = 4, MEET_2 = 5, RESULT = 6;
const SOFIA = 0, PLOVDIV = 1;


function lock(cells, i) {
  while (Atomics.compareExchange(cells, LOCK + i, 0, 1) !== 0) {
    Atomics.wait(cells, LOCK + i, 1);
  }
}


function tryLock(cells, i, ms) {
  const deadline = Date.now() + ms;
  while (Atomics.compareExchange(cells, LOCK + i, 0, 1) !== 0) {
    const left = deadline - Date.now();
    if (left <= 0) return false;
    Atomics.wait(cells, LOCK + i, 1, left);
  }
  return true;
}


function unlock(cells, i) {
  Atomics.store(cells, LOCK + i, 0);
  Atomics.notify(cells, LOCK + i, 1);
}


function meet(cells, slot) {
  Atomics.add(cells, slot, 1);
  Atomics.notify(cells, slot);
  let n;
  while ((n = Atomics.load(cells, slot)) < 2) Atomics.wait(cells, slot, n);
}
function transfer(cells, source, target, qty) {
  lock(cells, source);
  try {
    meet(cells, MEET_1); // beide halten je ein Lock
    const got = tryLock(cells, target, 200);
    meet(cells, MEET_2); // beide haben es versucht (nur für das Beispiel)
    if (!got) return false; // hat zu lange gewartet
    try {
      cells[STOCK + source] -= qty;
      cells[STOCK + target] += qty;
      return true;
    } finally {
      unlock(cells, target);
    }
  } finally {
    unlock(cells, source);
  }
}
if (isMainThread) {
  const cells = new Int32Array(new SharedArrayBuffer(8 * 4));
  cells[STOCK + SOFIA] = 500;
  cells[STOCK + PLOVDIV] = 300;
  const jobs = [[SOFIA, PLOVDIV, 5], [PLOVDIV, SOFIA, 3]];
  const workers = jobs.map(
    (job, k) => new Worker(new URL(import.meta.url), { workerData: { cells, job, k } }),
  );
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  const done = [cells[RESULT], cells[RESULT + 1]];
  console.log(!done[0] && !done[1] ? "Deadlock: jede Umlagerung wartet auf die andere" : "beide Umlagerungen sind durchgelaufen");
  console.log(`Sofia: ${cells[STOCK + SOFIA]}, Plovdiv: ${cells[STOCK + PLOVDIV]}`);
} else {
  const { cells, job, k } = workerData;
  cells[RESULT + k] = transfer(cells, ...job) ? 1 : 0;
}
Ausgabe
Deadlock: jede Umlagerung wartet auf die andere
Sofia: 500, Plovdiv: 300

Ohne das Timeout würde das Programm hängen und nie etwas ausgeben. Das Timeout behebt den Deadlock nicht, es fängt ihn ab: Die Umlagerung weiß, dass sie nicht durchgelaufen ist, und kann es noch einmal versuchen oder Alarm schlagen.

Die Idee

Eine Reihenfolge für alle

Der Kreis schließt sich, weil die beiden Umlagerungen in verschiedener Reihenfolge sperren: eine Sofia, dann Plovdiv, die andere umgekehrt. Die Lösung ist, dass alle in derselben Reihenfolge sperren, egal in welche Richtung umgelagert wird. Zum Beispiel nach der Lagernummer: die kleinere id zuerst.

Dann beginnen beide Umlagerungen mit Sofia. Wer dessen Lock bekommt, geht weiter zu Plovdiv. Die andere wartet noch auf das erste Lock und hält nichts, blockiert also niemanden. Ein Kreis kann sich nicht schließen: Jeder wartet nur auf ein Lock mit größerer id als die, die er schon hält.

function transfer(cells, source, target, qty) {
  // eine gemeinsame Reihenfolge: zuerst die kleinere id
  const first = Math.min(source, target);
  const second = Math.max(source, target);
  lock(cells, first);
  try {
    lock(cells, second);
    try {
      cells[STOCK + source] -= qty;
      cells[STOCK + target] += qty;
    } finally {
      unlock(cells, second);
    }
  } finally {
    unlock(cells, first);
  }
}

Tausend Umlagerungen von 2 Stück in die eine Richtung und tausend von 1 in die andere, gleichzeitig:

if (isMainThread) {
  const cells = new Int32Array(new SharedArrayBuffer(8 * 4));
  cells[STOCK + SOFIA] = 5000;
  cells[STOCK + PLOVDIV] = 3000;
  const jobs = [[SOFIA, PLOVDIV, 2], [PLOVDIV, SOFIA, 1]];
  const workers = jobs.map(
    (job) => new Worker(new URL(import.meta.url), { workerData: { cells, job } }),
  );
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  const [sofia, plovdiv] = [cells[STOCK + SOFIA], cells[STOCK + PLOVDIV]];
  console.log(`Sofia: ${sofia}, Plovdiv: ${plovdiv}`);
  console.log(`Gesamt: ${sofia + plovdiv}`);
} else {
  const { cells, job } = workerData;
  for (let i = 0; i < 1000; i++) transfer(cells, ...job);
}
Ausgabe
Sofia: 4000, Plovdiv: 4000
Gesamt: 8000
Hier ist ein Lager nur eine Zahl (0 oder 1), die Reihenfolge ergibt sich also mit Math.min und Math.max.

Der Bestand stimmt bei jedem Lauf, und die Summe ist 8000, wie am Anfang. Die Locks schützen die Stücke, und die Reihenfolge verhindert, dass das Programm stehen bleibt.

Probier es aus

Sag die Ausgabe voraus

Drei Lager: Sofia (1), Plovdiv (2), Varna (3). Die Funktion gibt nur aus, in welcher Reihenfolge sie sperren würde. Was gibt sie aus?

const NAMES = ["Sofia", "Plovdiv", "Varna"];
const SOFIA = 0, PLOVDIV = 1, VARNA = 2;


function transfer(source, target) {
  const first = Math.min(source, target);
  const second = Math.max(source, target);
  console.log(`${NAMES[first]}, dann ${NAMES[second]}`);
}


transfer(PLOVDIV, SOFIA);
transfer(SOFIA, VARNA);
transfer(VARNA, PLOVDIV);
Antwort

Probier es aus

Ergänze

first ist die kleinere Zahl. Wie bekommst du die größere?
const first = Math.min(source, target);
const second = Math.(source, target);

Probier es aus

Finde den Fehler

Die Umlagerungen sperren schon nach id, und wochenlang gibt es kein Problem. Dann fügt jemand eine nächtliche Prüfung hinzu, die beide Lager addiert. Seitdem bleibt das Programm manchmal wieder stehen. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Sieh es dir an

Wenn eine Reihenfolge nicht möglich ist: probieren und zurückweichen

Manchmal weißt du nicht im Voraus, welches Lock du brauchen wirst. Dann nimmst du statt einer Reihenfolge probieren und zurückweichen (tryLock mit Backoff): Nimm das erste, probiere das zweite ohne zu warten. Klappt es nicht, gib alles frei, warte kurz und fang von vorn an. Keiner hält beim Warten ein Lock, also gibt es keinen Kreis.

function transfer(cells, source, target, qty) {
  while (true) {
    lock(cells, source);
    try {
      if (tryLock(cells, target, 0)) {
        try {
          cells[STOCK + source] -= qty;
          cells[STOCK + target] += qty;
          return;
        } finally {
          unlock(cells, target);
        }
      }
    } finally {
      unlock(cells, source);
    }
    // alles freigeben und gleich noch einmal versuchen
    Atomics.wait(cells, MEET_1, 0, Math.random() * 2);
  }
}

Mit denselben zwei Umlagerungen (je 300 in jede Richtung) stimmt das Ergebnis wieder genau:

Ausgabe
Sofia: 4700, Plovdiv: 3300
Gesamt: 8000

Die Wartezeit ist zufällig, und das ist wichtig. Weichen beide Umlagerungen gleich lange zurück, können sie immer wieder im selben Rhythmus zusammenprallen: Beide arbeiten, und keiner kommt voran. Das nennt man Livelock. Die zufällige Wartezeit durchbricht den Rhythmus. Atomics.wait auf einer Zelle, die niemand aufweckt, ist hier einfach eine Pause im Worker.

Genauer, für Neugierige

Die vier Coffman-Bedingungen. Ein Deadlock entsteht nur, wenn vier Dinge zugleich gelten:

  1. gegenseitiger Ausschluss: Ein Lock kann nur einer halten;
  2. Halten und Warten: Ein Thread hält ein Lock, während er auf ein anderes wartet;
  3. kein Entzug: Niemand kann ein Lock mit Gewalt wegnehmen;
  4. zyklisches Warten: Das Warten bildet einen Kreis.

Nimm eine weg, und ein Deadlock kann nicht entstehen. Eine Reihenfolge beseitigt den Kreis (4). Zurückweichen beseitigt „Halten und Warten“ (2). Die atomaren Operationen und unveränderlichen Objekte aus der vorigen Lektion beseitigen oft das Lock selbst (1).

Datenbanken gehen es auf einem dritten Weg an. Sie suchen den Kreis selbst und brechen eine der Transaktionen mit dem Fehler „deadlock detected“ ab. Code, der mit einer Datenbank arbeitet, muss also bereit sein, die Transaktion zu wiederholen.

So ist es in den anderen Sprachen: ReentrantLock.tryLock(time) in Java (synchronized hat kein Timeout); Monitor.TryEnter(object, time) in C# (lock hat kein Timeout); Lock.acquire(timeout=…) in Python; in JavaScript gibt es Locks nur zwischen Workern, geschrieben mit Atomics.wait mit Timeout. In async-Code auf einem Thread gibt es keine Locks, aber ein Kreis ist trotzdem möglich: Zwei Funktionen, die jeweils auf das Promise der anderen mit await warten, warten ewig, und das Programm endet einfach, ohne etwas auszugeben.

Übung

Drei Wallets im Kreis

Löse die Aufgabe in deinem Editor.

Drei Wallets mit je 1000 € und drei Threads. Der erste verschiebt 5 € von Wallet 1 zu Wallet 2, der zweite von 2 zu 3, der dritte von 3 zu 1, jeweils 1000-mal. Das ist ein Kreis: Ohne eine Reihenfolge bleibt das Programm früher oder später stehen. Schreibe transfer so, dass es nicht stehen bleiben kann, und gib die Wallets und die Summe aus:

Ausgabe
Wallet 1: 1000 €
Wallet 2: 1000 €
Wallet 3: 1000 €
Gesamt: 3000 €

Weitere Aufgaben

  • Abfangen. Entferne die Reihenfolge und setze ein Timeout auf das zweite Lock. Zähle, wie viele Umlagerungen aufgegeben haben, und wiederhole sie, bis alle durchgelaufen sind.
  • Die Prüfung. Füge einen Thread hinzu, der die drei Wallets 1000-mal unter ihren Locks addiert. Die Summe muss immer 3000 € sein. In welcher Reihenfolge sperrt er?
  • Ohne id. Wenn die Objekte keine Nummer haben, wonach kann man sie sonst ordnen? (Tipp: der Index der Zelle im Array, und was passiert, wenn zwei Objekte denselben haben.)

Test

Teste dich

1. Wann geraten zwei Threads in einen Deadlock?
2. Alle Umlagerungen sperren die Lager nach id, von der kleineren zur größeren. Können drei Umlagerungen Sofia → Plovdiv, Plovdiv → Varna und Varna → Sofia stecken bleiben?
3. Warum hängt das Programm deadlock in der Lektion nicht?
4. Zwei Umlagerungen geben bei einem Misserfolg auf, warten 1 ms und versuchen es noch einmal. Beide prallen wieder zusammen, immer wieder. Wie heißt das, und wie behebst du es?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·