Zum Inhalt
wannacode

Race Condition

Kurz gesagt: Eine Race Condition ist ein Fehler, bei dem das Ergebnis von der Reihenfolge der Ausführung abhängt: Zwei Worker verlieren einen Verkauf, und ein await zwischen Prüfung und Kauf lässt selbst in einem Thread zwei Käufer durch.

Problem

Der Verkauf wird falsch gezählt

Freitag, Flash-Sale. Kopfhörer zum halben Preis, und die Bestellungen strömen herein. Zwei Kassen verkaufen aus einem Lager: Jeder Verkauf zieht 1 vom Bestand ab.

Die Kassen sind zwei Worker (die Lektion „Async, await und Threads“). Der Bestand liegt in einem SharedArrayBuffer, einem gemeinsamen Speicher, den beide sehen. Jeder verkauft 1.000.000 Stück:
// stock ist ein Int32Array in einem SharedArrayBuffer:
// gemeinsamer Speicher für die Worker.
function sell(stock) {
  stock[0]--;   // lesen, 1 abziehen, schreiben
}
if (isMainThread) {
  const stock = new Int32Array(new SharedArrayBuffer(4));
  stock[0] = 2_000_000;
  const checkouts = [1, 2].map(
    () => new Worker(new URL(import.meta.url), { workerData: stock }),
  );
  await Promise.all(checkouts.map((worker) => once(worker, "exit")));
  console.log(`Bestellungen: ${2 * 1_000_000}`);
  console.log("Verkauft laut Lager:");
  console.log(2_000_000 - stock[0]);
} else {
  for (let i = 0; i < 1_000_000; i++) {
    sell(workerData);
  }
}

Die Kunden haben für 2.000.000 Bestellungen bezahlt. So viele Verkäufe zählt das Lager in fünf Läufen:

Ausgabe von fünf Läufen (die dritte Zeile)
Verkauft laut Lager: 2000000
Verkauft laut Lager: 1003506
Verkauft laut Lager: 994022
Verkauft laut Lager: 1004855
Verkauft laut Lager: 1018607
Meist zählt das Lager etwa die Hälfte. In einem der fünf Läufe stimmt es: Da war ein Worker fertig, bevor der andere gestartet ist. Die Artikel, die weg sind, glaubt das Lager zu „haben“: Morgen verkauft der Shop sie an jemanden und erstattet dann das Geld.

Die Idee

stock[0]-- sind drei Schritte

Im Code ist stock[0]-- eine Zeile. Der Prozessor macht es in drei Schritten, so als hättest du sie ausgeschrieben:

// stock ist ein Int32Array in einem SharedArrayBuffer:
// gemeinsamer Speicher für die Worker.
function sell(stock) {
  const seen = stock[0];     // 1. lesen
  const after = seen - 1;    // 2. 1 abziehen
  stock[0] = after;          // 3. schreiben
}
Schritt für Schritt, in Worten
  1. Es sind noch 5 Stück übrig. Worker A und Worker B verkaufen im selben Moment je eins.
  2. Worker A liest den Bestand: 5.
  3. Worker B liest, bevor A geschrieben hat: ebenfalls 5.
  4. Worker A zieht in der eigenen Variable 1 ab: 4.
  5. Worker B macht dasselbe von der eigenen 5 aus: ebenfalls 4.
  6. Worker A schreibt 4. Ein Verkauf, 4 übrig: bis hierhin stimmt es.
  7. Worker B schreibt ebenfalls 4, über die 4 von A. Zwei Verkäufe, und der Bestand ist 4, nicht 3.
  8. Ein Verkauf geht verloren: Beide lasen dieselbe Zahl, bevor eine schrieb. Das ist eine Race Condition, und das Lager zeigt jetzt einen Artikel, der schon verkauft ist.
  1. Lesen: den Bestand in eine eigene Variable.
  2. Abziehen: 1 von deiner Kopie.
  3. Schreiben: die Kopie zurück.

Zwei Threads können sich zwischen je zwei Schritten abwechseln. Wenn beide 5 lesen, bevor einer schreibt, schreiben beide 4. Zwei Verkäufe, und der Bestand sinkt um eins.

Wenn das Ergebnis davon abhängt, welcher Thread welchen Schritt zuerst macht, ist das eine Race Condition. Die drei Schritte „lesen, ändern, schreiben“ auf gemeinsamen Daten sind ihre häufigste Form.

Genauer, für Neugierige
stock[0]-- auf einem Int32Array liest aus dem gemeinsamen Speicher, zieht in einem Register ab und schreibt. Dazwischen kann der andere Worker, der auf einem anderen Kern läuft, dieselbe Zahl lesen. Bei einem gewöhnlichen JavaScript-Objekt kann das nicht passieren: Objekte werden zwischen Workern nicht geteilt, sondern kopiert.

Probier es aus

Drei Kassen, 5 auf Lager

Hier sind drei Kassen, von Hand in einer der möglichen Reihenfolgen verzahnt. Jede liest in eine eigene Variable und schreibt dann 1 weniger:

let left = 5;
const seenA = left;    // A liest
const seenB = left;    // B liest
left = seenA - 1;      // A schreibt
const seenC = left;    // C liest
left = seenB - 1;      // B schreibt
left = seenC - 1;      // C schreibt
console.log("Verkäufe: 3");
console.log(`Bestand: ${left}`);
Antwort

Die Idee

„Bei mir funktioniert es“

Dasselbe Programm, mit weniger Verkäufen pro Kasse:

if (isMainThread) {
  const stock = new Int32Array(new SharedArrayBuffer(4));
  stock[0] = 2_000;
  const checkouts = [1, 2].map(
    () => new Worker(new URL(import.meta.url), { workerData: stock }),
  );
  await Promise.all(checkouts.map((worker) => once(worker, "exit")));
  console.log(`Bestellungen: ${2 * 1_000}`);
  console.log("Verkauft laut Lager:");
  console.log(2_000 - stock[0]);
} else {
  for (let i = 0; i < 1_000; i++) {
    sell(workerData);
  }
}
Ausgabe von fünf Läufen (die dritte Zeile)
Verkauft laut Lager: 2000
Verkauft laut Lager: 2000
Verkauft laut Lager: 1929
Verkauft laut Lager: 2000
Verkauft laut Lager: 2000
Viermal richtig und einmal ein Verlust. Ein Worker startet langsam, deshalb ist meist einer mit seinen 1000 Verkäufen fertig, bevor der andere begonnen hat. Meist.

Das macht eine Race Condition so tückisch:

  • der Test besteht auf dem Laptop und fällt auf dem Server mit 64 Kernen und tausenden Kunden durch;
  • der Fehler kommt „manchmal“ und wiederholt sich nicht, wenn du ihn suchst;
  • füge eine Print-Zeile hinzu, die Reihenfolge der Threads ändert sich, und der Fehler verschwindet.

Ein Test ohne Verlust beweist nichts. Sicherheit beweist man durch die Art, wie der Code geschrieben ist: welche Daten geteilt werden und wer sie schützt.

Problem

Der letzte Artikel

Ein Artikel ist übrig. Zwei Käufer klicken im selben Moment auf „Kaufen“. buy prüft, ob einer da ist, belastet die Karte (etwa 100 ms) und nimmt erst dann den Artikel:

class Stock {
  constructor(left) {
    this.left = left;
  }


  async buy() {
    if (this.left > 0) {   // Prüfen: Ist noch einer da?
      await sleep(100);    // die Karte wird belastet, ~100 ms
      this.left--;         // Handeln: den Artikel nehmen
      return true;
    }
    return false;
  }
}
const stock = new Stock(1);
const bought = await Promise.all([stock.buy(), stock.buy()]);
console.log("Bestand vorher: 1");
console.log("Verkauft:");
console.log(bought.filter((ok) => ok).length);
console.log("Bestand nachher:");
console.log(stock.left);
Ausgabe
Bestand vorher: 1
Verkauft:
2
Bestand nachher:
-1

Hier gibt es einen Thread, und der Fehler ist derselbe. await sleep(100) lässt den anderen Aufruf laufen, während der erste auf die Bank wartet. Er erreicht die Prüfung, solange left noch 1 ist. In einem Thread ist die Reihenfolge jedes Mal gleich, also tritt der Fehler auch jedes Mal auf. Mehr dazu steht in der Lektion „async ist kein Thread“.

Das ist die zweite Form einer Race Condition: Prüfen, dann handeln (Check-then-act). Die Entscheidung wird auf einem Wert getroffen, den jemand anderes ändern kann, bevor die Entscheidung ausgeführt wird. Sie ist überall: „Ist ein Zimmer frei“, „Ist der Benutzername frei“, „Ist Geld auf dem Konto“.

Probier es aus

Bestellnummern

Jede Bestellung bekommt eine Nummer: 1001, 1002, 1003… Die Kassen sind Threads und rufen gleichzeitig take(next) auf. Manchmal bekommen zwei Bestellungen dieselbe Nummer. Nach welcher Zeile muss der andere Thread hereinkommen, damit das passiert?

Wähle die Zeile mit dem Fehler.

Die Idee

Wann es eine Race Condition geben kann

Es braucht drei Dinge gleichzeitig:

  1. Gemeinsame Daten: etwas, das mehrere Threads sehen können (der Bestand, der Zähler, die Nummer).
  2. Mindestens ein Thread ändert sie. Wenn alle nur lesen, kann nichts schiefgehen.
  3. Nichts ordnet den Zugriff: Die Threads gehen in ihre Schritte, wann immer sie an der Reihe sind.

Nimm eines der drei weg, und es gibt keine Race Condition:

  • Nicht teilen. Jeder Thread zählt in seiner eigenen Variable, und am Ende werden die Ergebnisse addiert. So liefen die 1000 Rechnungen in „Warum Threads“: Jeder Teil rechnet seinen eigenen.
  • Nicht ändern. Ein Objekt, das niemand ändert, können beliebig viele Threads lesen. Das ist die Lektion „Atomare Operationen und unveränderliche Objekte“.
  • Den Zugriff ordnen. Immer nur ein Thread in den drei Schritten. Das ist das Lock, die nächste Lektion: „Sperren“.
Genauer, für Neugierige

Es gibt auch ein leiseres Problem: die Sichtbarkeit. In einem SharedArrayBuffer sieht ein gewöhnliches Lesen den Schreibvorgang eines anderen Workers vielleicht nicht rechtzeitig. Atomics.load und Atomics.store garantieren es. Das Lock löst auch das: Was ein Thread vor der Freigabe geschrieben hat, sieht der nächste, nachdem er es genommen hat.

Wie es in anderen Sprachen ist: In Java und C# verliert count++ genau wie hier. In Python verliert es wegen des GIL seltener, aber es verliert. In JavaScript verliert es zwischen Workern auf einem SharedArrayBuffer, und in einem Thread gibt es eine Race Condition nur zwischen zwei await.

Übung

Der Umsatz des Verkaufs

Löse die Aufgabe in deinem Editor.

Der Umsatz. Zwei Kassen verkaufen je 500.000 Kopfhörer zu 3 €. Jede Kasse zählt ihre Verkäufe in einer eigenen Variable, und der Umsatz ist geteilt: ein Int32Array in einem SharedArrayBuffer, wo jeder Worker revenue[0] += 3 ausführt. Gib die Verkäufe jeder Kasse und den Umsatz aus. Führe das Programm mehrmals aus.

Erwartet
Kasse 1: 500000 Verkäufe
Kasse 2: 500000 Verkäufe
Umsatz (€):
3000000

Die Verkäufe der Kassen stimmen bei jedem Lauf: Jede zählt in ihrer eigenen Variable. Der Umsatz ist kleiner und jedes Mal anders. Die Lösung steht in der nächsten Lektion.

Weitere Aufgaben

  • Wie viel geht verloren. Führe den Verkauf mit 2, 4 und 8 Kassen aus. Geht mit mehr Kassen mehr verloren?
  • Finde das Geteilte. Nimm ein Programm mit Threads, das du geschrieben hast, und liste die Daten auf, die mehr als ein Thread anfasst. Welche davon ändert ein Thread? - Freies Zimmer. Schreibe eine async-Methode „Zimmer 12 buchen, wenn es frei ist“ mit await sleep(100) zwischen Prüfung und Schreiben und lasse zwei Gäste mit Promise.all laufen. Wie viele Gäste bekommen das Zimmer?

Test

Teste dich

1. Zwei Worker rufen je einmal stock[0]-- auf einem SharedArrayBuffer auf, wo der Wert 5 ist. Was kann am Ende darin stehen?
2. Der Test mit zwei Threads zu je 1000 Verkäufen besteht 100 von 100 Läufen. Was sagt dir das?
3. Eine async-Funktion prüft this.left > 0, dann await sleep(100), dann this.left--. Zwei Aufrufe mit Promise.all, 1 auf Lager. Was passiert?
4. Welche dieser Situationen kann KEINE Race Condition haben?

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