Race Condition
Kurz gesagt: Eine Race Condition ist ein Fehler, bei dem das Ergebnis davon abhängt, wie sich Threads verzahnen: left-- sind drei Schritte (lesen, abziehen, schreiben), also können zwei Threads einen Verkauf verlieren.
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 Threads. Jeder verkauft 100.000 Stück und ruft für jedessell() auf:class Stock { private int left;
Stock(int left) { this.left = left; }
void sell() { left--; // lesen, 1 abziehen, schreiben }
int left() { return left; }}Stock stock = new Stock(200_000);Runnable checkout = () -> { for (int i = 0; i < 100_000; i++) { stock.sell(); }};Thread a = new Thread(checkout);Thread b = new Thread(checkout);a.start();b.start();a.join();b.join();System.out.println("Bestellungen: " + 2 * 100_000);System.out.println("Verkauft laut Lager:");System.out.println(200_000 - stock.left());Die Kunden haben für 200.000 Bestellungen bezahlt. So viele Verkäufe zählt das Lager in fünf Läufen:
Verkauft laut Lager: 108435Verkauft laut Lager: 129196Verkauft laut Lager: 117263Verkauft laut Lager: 118496Verkauft laut Lager: 118057Die Idee
left-- sind drei Schritte
left-- eine Zeile. Der Prozessor macht es in drei Schritten, so als hättest du sie ausgeschrieben:class Stock { private int left;
Stock(int left) { this.left = left; }
void sell() { int seen = left; // 1. lesen int after = seen - 1; // 2. 1 abziehen left = after; // 3. schreiben }
int left() { return left; }}Schritt für Schritt, in Worten
- Es sind noch 5 Stück übrig. Kasse A und Kasse B verkaufen im selben Moment je eins.
- Kasse A liest den Bestand: 5.
- Kasse B liest, bevor A geschrieben hat: ebenfalls 5.
- Kasse A zieht in der eigenen Variable 1 ab: 4.
- Kasse B macht dasselbe von der eigenen 5 aus: ebenfalls 4.
- Kasse A schreibt 4. Ein Verkauf, 4 übrig: bis hierhin stimmt es.
- Kasse B schreibt ebenfalls 4, über die 4 von A. Zwei Verkäufe, und der Bestand ist 4, nicht 3.
- 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.
- Lesen: den Bestand in eine eigene Variable.
- Abziehen: 1 von deiner Kopie.
- 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
left-- JVM-Anweisungen: getfield, iconst_1, isub, putfield (das Feld lesen, rechnen, das Feld schreiben). javap -c Stock zeigt sie. Der JIT-Compiler ersetzt sie später vielleicht durch Maschinenbefehle, aber Lesen und Schreiben bleiben getrennt.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:
int left = 5;int seenA = left; // A liestint seenB = left; // B liestleft = seenA - 1; // A schreibtint seenC = left; // C liestleft = seenB - 1; // B schreibtleft = seenC - 1; // C schreibtSystem.out.println("Verkäufe: 3");System.out.println("Bestand: " + left);A und B lesen 5. A schreibt 4. C liest die 4, die gerade geschrieben wurde. B schreibt 4 (seine eigene 5 minus 1), und C schreibt 3. Drei Verkäufe, und der Bestand ist 3 statt 2: Nur der Verkauf von B ging verloren, weil B las, bevor A schrieb.
Die Idee
„Bei mir funktioniert es“
Dasselbe Programm, mit weniger Verkäufen pro Kasse:
Stock stock = new Stock(2_000);Runnable checkout = () -> { for (int i = 0; i < 1_000; i++) { stock.sell(); }};Thread a = new Thread(checkout);Thread b = new Thread(checkout);a.start();b.start();a.join();b.join();System.out.println("Bestellungen: " + 2 * 1_000);System.out.println("Verkauft laut Lager:");System.out.println(2_000 - stock.left());Verkauft laut Lager: 2000Verkauft laut Lager: 2000Verkauft laut Lager: 2000Verkauft laut Lager: 2000Verkauft laut Lager: 2000Das 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 { private int left;
Stock(int left) { this.left = left; }
boolean buy() { if (left > 0) { // Prüfen: Ist noch einer da? pause(100); // die Karte wird belastet, ~100 ms left--; // Handeln: den Artikel nehmen return true; } return false; }
int left() { return left; }
private static void pause(int ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } }}Stock stock = new Stock(1);boolean[] bought = new boolean[2];Thread first = new Thread(() -> bought[0] = stock.buy());Thread second = new Thread(() -> bought[1] = stock.buy());first.start();second.start();first.join();second.join();int sold = (bought[0] ? 1 : 0) + (bought[1] ? 1 : 0);System.out.println("Bestand vorher: 1");System.out.println("Verkauft:");System.out.println(sold);System.out.println("Bestand nachher:");System.out.println(stock.left());Verkauft: 2, bestand nachher: -1Verkauft: 2, bestand nachher: -1Verkauft: 2, bestand nachher: -1Verkauft: 2, bestand nachher: -1Verkauft: 2, bestand nachher: -1Beide bestehen die Prüfung: Während der erste zahlt, sieht der zweite dieselbe 1. Beide haben bezahlt, und der Bestand steht bei -1. Hier tritt die Race Condition jedes Mal auf, weil zwischen Prüfung und Handlung volle 100 ms liegen.
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() 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.
Nach dem Lesen. Wenn beide Threads 1001 lesen, bevor einer 1002 schreibt, geben beide 1001 zurück. Zwei Bestellungen mit einer Nummer: Eine überschreibt die andere in der Datenbank oder landet beim falschen Kunden. Es ist dasselbe „lesen, ändern, schreiben“.
Die Idee
Wann es eine Race Condition geben kann
Es braucht drei Dinge gleichzeitig:
- Gemeinsame Daten: etwas, das mehrere Threads sehen können (der Bestand, der Zähler, die Nummer).
- Mindestens ein Thread ändert sie. Wenn alle nur lesen, kann nichts schiefgehen.
- 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. Ohne synchronized oder volatile verspricht die JVM nicht, dass ein Thread einen von einem anderen geschriebenen Wert je sieht. Eine Schleife while (!done) { } hört vielleicht nie auf, weil der JIT done nur einmal gelesen hat. 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 50.000 Kopfhörer zu 3 €. Jede Kasse zählt ihre Verkäufe in einer eigenen Variable, und der Umsatz ist geteilt: ein Revenue-Objekt mit einer Methode add(euros), die total += euros macht. Gib die Verkäufe jeder Kasse und den Umsatz aus. Führe das Programm mehrmals aus.
Kasse 1: 50000 VerkäufeKasse 2: 50000 VerkäufeUmsatz (€):300000Die 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 ein Hotel mit einer Methode „Zimmer 12 buchen, wenn es frei ist“ und lasse zwei Gäste gleichzeitig laufen, mit einer Pause von 100 ms zwischen Prüfung und Schreiben. Wie viele Gäste bekommen das Zimmer?
Test