Zum Inhalt
wannacode

Atomare Operationen und unveränderliche Objekte

Kurz gesagt: Eine atomare Operation (etwa +1 oder Compare-and-set) läuft in einem Stück, ohne dass ein anderer Thread dazwischenfunkt, und schützt gemeinsame Daten ohne Lock; ein unveränderliches Objekt ändert sich überhaupt nie.

Problem

Ein Lock für ein einziges +1

Ein Flash-Sale: 100 Kopfhörer zum halben Preis, um 10:00. Die Produktseite wird tausende Male pro Sekunde geöffnet, und jedes Öffnen erhöht den Seitenaufruf-Zähler. Aus der Lektion über Sperren weißt du, wie man keine Erhöhungen verliert: ein Lock um views++.

Das ist richtig. Aber jeder Thread stellt sich für ein einziges +1 vor dem Lock an. Ein Thread, der das Lock nicht bekommt, wird oft schlafen gelegt und später vom Betriebssystem geweckt. Das kostet viel mehr als die Addition selbst.

Das zweite Problem ist schlimmer. Das letzte Stück wird mit „wenn eins da ist, um 1 verringern“ gekauft. Das sind zwei Schritte, und dazwischen kann ein anderer Thread dasselbe Stück nehmen.

Die Idee

Ein unteilbarer Schritt

Der Prozessor hat Befehle, die eine Speicherzelle in einem unteilbaren Schritt lesen, ändern und schreiben. Kein anderer Thread kann dazwischenkommen. Das ist eine atomare Operation. Es gibt kein Lock, niemand steht an und niemand schläft.

In Java liegen sie in java.util.concurrent.atomic. AtomicInteger hält ein int, und incrementAndGet() ist das atomare +1 und gibt den neuen Wert zurück. Es gibt auch addAndGet, getAndIncrement und AtomicLong für long.

Sieh es dir an

Der Seitenaufruf-Zähler

Vier Threads mit je 100.000 Aufrufen:

AtomicInteger views = new AtomicInteger();
Runnable visitor = () -> {
    for (int i = 0; i < 100_000; i++) {
        views.incrementAndGet();
    }
};
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) {
    Thread thread = new Thread(visitor);
    threads.add(thread);
    thread.start();
}
for (Thread thread : threads) thread.join();
System.out.println("Aufrufe: " + views.get());
Ausgabe
Aufrufe: 400000

400.000 bei jedem Lauf. Ohne das atomare +1 wäre es weniger und jedes Mal anders, wie in der Lektion über Race Conditions.

Genauer, für Neugierige

LongAdder. Wenn viele Threads denselben AtomicInteger erhöhen, treffen alle auf eine Speicherzelle, und die Prozessoren reichen sie herum. LongAdder zählt in mehreren Zellen (eine pro Gruppe von Threads) und addiert sie erst bei sum(). Unter hoher Last ist er schneller, liefert aber nicht nach jeder Erhöhung den Wert. Er passt zu Zählern, die nur am Ende gelesen werden:

LongAdder views = new LongAdder();
Runnable visitor = () -> {
    for (int i = 0; i < 100_000; i++) {
        views.increment();
    }
};
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) {
    Thread thread = new Thread(visitor);
    threads.add(thread);
    thread.start();
}
for (Thread thread : threads) thread.join();
System.out.println("Aufrufe: " + views.sum());
Ausgabe
Aufrufe: 400000

Wie viel schneller als ein Lock ist das? Das hängt von der Maschine ab und davon, wie viele Threads um eine Zelle kämpfen. Ohne Kampf ist ein atomares +1 ein paar Nanosekunden. Ein Lock ohne Kampf ist nahe daran. Der Unterschied kommt mit vielen Threads: Dann legt das Lock Threads schlafen, während die atomare Operation nur wiederholt.

Die Idee

Prüfen und ändern: Compare-and-set

Kaufen ist nicht nur −1. Es ist „wenn mindestens eins da ist, um 1 verringern“. Die Prüfung und die Änderung müssen ein Schritt sein.

Dafür gibt es eine allgemeinere atomare Operation: Compare-and-set (CAS). Du gibst ihr zwei Zahlen: was du dort vermutest und was du dort haben willst. Sie ändert den Wert nur, wenn er noch so ist, wie du denkst, und sagt dir, ob es geklappt hat. Hat ein anderer Thread ihn inzwischen geändert, fasst CAS nichts an und antwortet „nein“.

Dann ist Kaufen eine Schleife:

  1. den Bestand lesen;
  2. ist er 0, ablehnen;
  3. CAS: „Wenn es noch so viel ist, mach eins weniger daraus“;
  4. schlägt CAS fehl, hat inzwischen jemand gekauft: zurück zu 1.
In Java ist das compareAndSet(expected, new), das true oder false zurückgibt.

Sieh es dir an

Die letzten drei Kopfhörer

class FlashSale {
    private final AtomicInteger stock;


    FlashSale(int items) {
        stock = new AtomicInteger(items);
    }


    boolean tryBuy() {
        while (true) {
            int left = stock.get();
            if (left == 0) return false; // ausverkauft
            if (stock.compareAndSet(left, left - 1)) {
                return true;
            }
            // jemand hat stock geändert: noch einmal lesen
        }
    }


    int stock() {
        return stock.get();
    }
}
Schritt für Schritt, in Worten
  1. Die letzten 3 Kopfhörer: Der Bestand ist 3. Threads A und B rufen tryBuy() gleichzeitig auf.
  2. A liest den Bestand: left = 3.
  3. B liest ihn, bevor A etwas geändert hat: ebenfalls 3.
  4. B: compareAndSet(3, 2). „Wenn es noch 3 ist, mach 2 daraus.“ Es ist noch 3, also wird 2 geschrieben. B hat gekauft.
  5. A versucht dasselbe: „wenn es noch 3 ist …“. Jetzt ist es 2, also wird nichts geschrieben, und die Antwort ist false. Nichts geht verloren.
  6. A wartet nicht und gibt nicht auf: Die Schleife läuft weiter, und A liest noch einmal: 2. Kein Thread hat geschlafen.
  7. A: „wenn es noch 2 ist, mach 1 daraus“. Es ist noch 2: 1 wird geschrieben. Auch A hat gekauft.
  8. Zwei Käufer, zwei verkauft, Bestand 1. Es gibt kein Lock: Der Prozessor prüft und schreibt in einem Schritt, und wer verliert, wiederholt nur die Schleife.

Niemand wartet: Der Thread, der verloren hat, wiederholt nur zwei Zeilen. Das nennt man lock-free. Hundert Stück bei 160 Versuchen:

FlashSale sale = new FlashSale(100);
AtomicInteger sold = new AtomicInteger();
AtomicInteger refused = new AtomicInteger();
Runnable buyers = () -> {
    for (int i = 0; i < 40; i++) {
        if (sale.tryBuy()) sold.incrementAndGet();
        else refused.incrementAndGet();
    }
};
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) {
    Thread thread = new Thread(buyers);
    threads.add(thread);
    thread.start();
}
for (Thread thread : threads) thread.join();
System.out.println("Verkauft: " + sold.get());
System.out.println("Abgelehnt: " + refused.get());
System.out.println("Bestand: " + sale.stock());
Ausgabe
Verkauft: 100
Abgelehnt: 60
Bestand: 0

Wie oft die Schleife durchlaufen wurde, ist bei jedem Lauf anders, deshalb gibt das Programm es nicht aus. Die Summen sind immer gleich: 100 verkauft, 60 abgelehnt, 0 im Bestand.

Probier es aus

Sag die Ausgabe voraus

Hier sind die zwei „Threads“ nacheinander in einem Thread geschrieben, damit die Reihenfolge bei jedem Lauf dieselbe ist wie in der Szene. Was gibt es aus?

AtomicInteger stock = new AtomicInteger(3);
int seenByA = stock.get();
int seenByB = stock.get();
System.out.println("B: " + stock.compareAndSet(seenByB, seenByB - 1));
System.out.println("A: " + stock.compareAndSet(seenByA, seenByA - 1));
seenByA = stock.get();
System.out.println("A noch einmal: " + stock.compareAndSet(seenByA, seenByA - 1));
System.out.println("Bestand: " + stock.get());
Antwort

Probier es aus

Ergänze

Womit vergleicht das CAS beim Kaufen?

if (stock.compareAndSet(, left - 1)) {

Probier es aus

Finde den Fehler

Ein Kollege hat das Kaufen vereinfacht. Jede Zeile für sich ist sicher, und trotzdem werden im Sale 103 Kopfhörer von 100 verkauft. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Problem

Die Preisliste, die sich mittendrin ändert

Um 10:00 startet der Admin die Aktion: Kopfhörer von 60 auf 48 €, Hülle von 15 auf 12 €, Kabel von 5 auf 4 €. Gleichzeitig berechnen die Kassen Warenkörbe. Liegen die Preise in einem gemeinsamen Dictionary und ändern sich einzeln, kann eine Kasse den neuen Preis der Kopfhörer und den alten der Hülle lesen:

// Admin
prices.put("headphones", 48);
prices.put("case", 12);
prices.put("cable", 4);


// Checkout, gleichzeitig
int total = 0;
for (String item : cart) total += prices.get(item);

Der Warenkorb kostet 68 €: eine Summe, die zu keinem Zeitpunkt stimmte. Nicht mit den alten Preisen (80 €), nicht mit den neuen (64 €). Und eine HashMap oder ein Dictionary, das ein Thread ändert, während ein anderer liest, kann sogar eine Exception auslösen oder einen falschen Wert liefern.

Die Idee

Nicht ändern, ganz ersetzen

Die Preisliste wird oft gelesen und selten geändert. Dann ändere sie nie. Mach sie zu einem unveränderlichen Objekt: Einmal erstellt, bleibt sie gleich. Für die Aktion macht der Admin eine neue Preisliste und tauscht eine Referenz: „Die aktuelle Preisliste ist diese.“

  • Ein Objekt, das niemand ändert, können beliebig viele Threads ohne jeden Schutz lesen.
  • Das Einzige, was geteilt wird, ist die Referenz, und sie zu tauschen ist ein atomarer Schritt.
  • Die Kasse nimmt die Referenz einmal zu Beginn des Warenkorbs und berechnet den ganzen Warenkorb damit. Sie sieht die ganze alte oder die ganze neue Preisliste, nie eine Mischung.

Ein record mit Map.copyOf ist unveränderlich: Die Felder sind final, und Map.copyOf macht eine Kopie, die sich nicht ändern lässt. AtomicReference hält die aktuelle Preisliste: set tauscht sie und get liest sie, sodass jeder Thread die zuletzt geschriebene sieht.

record PriceList(int version, Map<String, Integer> prices) {
    PriceList {
        prices = Map.copyOf(prices); // eine unveränderliche Kopie
    }


    int total(List<String> cart) {
        int sum = 0;
        for (String item : cart) sum += prices.get(item);
        return sum;
    }
}
Map<String, Integer> regular = Map.of("headphones", 60, "case", 15, "cable", 5);
Map<String, Integer> promo = Map.of("headphones", 48, "case", 12, "cable", 4);
List<String> cart = List.of("headphones", "case", "cable");
AtomicReference<PriceList> current =
        new AtomicReference<>(new PriceList(1, regular));
AtomicInteger mixed = new AtomicInteger();


Thread admin = new Thread(() -> {
    for (int v = 2; v <= 1001; v++) {
        Map<String, Integer> prices = v % 2 == 0 ? promo : regular;
        current.set(new PriceList(v, prices)); // ein neuer Schnappschuss, eine Referenz
    }
});
Thread checkout = new Thread(() -> {
    for (int i = 0; i < 100_000; i++) {
        PriceList list = current.get(); // ein Schnappschuss für den ganzen Warenkorb
        int total = list.total(cart);
        if (total != 80 && total != 64) mixed.incrementAndGet();
    }
});
admin.start();
checkout.start();
admin.join();
checkout.join();
PriceList last = current.get();
System.out.println("Geprüfte Summen: 100000");
System.out.println("Gemischte Summen: " + mixed.get());
System.out.println("Letzte Version: " + last.version() + ", Summe " + last.total(cart) + " €");
Ausgabe
Geprüfte Summen: 100000
Gemischte Summen: 0
Letzte Version: 1001, Summe 80 €
Die Kasse hat zehntausende Warenkörbe geprüft, während sich die Preisliste tausendmal geändert hat, und keine einzige Summe ist gemischt. Wie viele Warenkörbe nach der alten und wie viele nach der neuen Liste liefen, ist bei jedem Lauf anders, deshalb gibt das Programm es nicht aus.
Genauer, für Neugierige

So funktionieren auch „Copy-on-write“-Collections: CopyOnWriteArrayList in Java, ImmutableList in C#. Jede Änderung macht eine neue Kopie, und das Lesen braucht kein Lock. Das lohnt sich bei vielen Lesevorgängen und wenigen Schreibvorgängen. Wird oft geschrieben, wird das Kopieren teuer.

Unveränderlichkeit ist nur ehrlich, wenn sie bis ganz nach unten reicht. Ein Objekt mit einem final-Feld, das auf eine veränderbare Liste zeigt, ist nicht unveränderlich: Die Liste lässt sich von außen ändern. Deshalb steht dort Map.copyOf und nicht die Map, die hineingereicht wurde.

So ist es in den anderen Sprachen: record und Map.copyOf mit AtomicReference in Java; record mit ImmutableDictionary und Volatile oder Interlocked.Exchange in C#; eine frozen-Dataclass, ein tuple oder MappingProxyType und Zuweisung in Python; Object.freeze und Nachrichten zwischen Workern in JavaScript.

Die Idee

Wenn atomar nicht reicht

Eine Reservierung verschiebt ein Stück vom Bestand in die Zahl der Reservierten. Die Regel ist, dass beide zusammen immer 10.000 sind. Zwei atomare Variablen halten sie nicht ein:

AtomicInteger stock = new AtomicInteger(10);
AtomicInteger reserved = new AtomicInteger(0);


void reserve() {
    stock.decrementAndGet();    // jede Zeile ist atomar,
    reserved.incrementAndGet(); // beide zusammen nicht
}

Zwischen den beiden Zeilen sieht der Prüfer insgesamt 9.999. Atomar schützt einen Wert. Geht es in der Regel um mehrere Werte zusammen, brauchst du ein Lock um alle Änderungen und um die Prüfung:

class Warehouse {
    private final Object lock = new Object();
    private int stock;
    private int reserved;


    Warehouse(int stock) {
        this.stock = stock;
    }


    boolean reserve() {
        synchronized (lock) { // beide oder keine
            if (stock == 0) return false;
            stock--;
            reserved++;
            return true;
        }
    }


    int audit() {
        synchronized (lock) {
            return stock + reserved;
        }
    }


    String report() {
        synchronized (lock) {
            return "Bestand: " + stock + ", reserviert: " + reserved;
        }
    }
}
Warehouse warehouse = new Warehouse(10_000);
AtomicInteger broken = new AtomicInteger();
Runnable reserver = () -> {
    while (warehouse.reserve()) { }
};
Runnable auditor = () -> {
    for (int i = 0; i < 50_000; i++) {
        if (warehouse.audit() != 10_000) broken.incrementAndGet();
    }
};
List<Thread> threads = List.of(new Thread(reserver), new Thread(reserver), new Thread(auditor));
for (Thread thread : threads) thread.start();
for (Thread thread : threads) thread.join();
System.out.println(warehouse.report());
System.out.println("Fehlerhafte Prüfungen: " + broken.get());
Ausgabe
Bestand: 0, reserviert: 10000
Fehlerhafte Prüfungen: 0
Genauer, für Neugierige

Ein anderer Weg ohne Lock: beide Werte in einem unveränderlichen Objekt (Bestand, Reserviert) und der Tausch mit einem CAS auf die Referenz (AtomicReference.compareAndSet). Ein neues Objekt mit beiden neuen Werten ersetzt das alte auf einen Schlag. Das verbindet die zwei Ideen dieser Lektion, aber das Lock ist meist klarer.

Was wann zu benutzen ist:

  • ein Wert, ein Zähler oder ein Flag: eine atomare Operation;
  • einen Wert prüfen und ändern: eine CAS-Schleife;
  • Daten, die viel gelesen und selten geändert werden: ein unveränderliches Objekt und ein Tausch der Referenz;
  • mehrere zusammenhängende Werte: ein Lock.

Übung

Ein Gutschein mit begrenzter Einlösezahl

Löse die Aufgabe in deinem Editor.

Der Gutschein „SPRING20“ kann 50-mal eingelöst werden. Acht Threads mit je 10 Kunden versuchen gleichzeitig, ihn einzulösen. Schreibe Coupon mit tryUse() so, dass der Gutschein nie öfter als 50-mal eingelöst wird. Ohne Lock: mit einer Compare-and-set-Schleife. Gib aus, wie oft er eingelöst wurde, wie viele Ablehnungen es gab und wie viele Einlösungen übrig sind:

Ausgabe
Eingelöst: 50
Abgelehnt: 30
Übrig: 0

Weitere Aufgaben

  • Das Maximum. Halte die größte Bestellung des Tages fest, während viele Threads Bestellungen hinzufügen. Tipp: eine CAS-Schleife, die nur schreibt, wenn die neue größer ist.
  • Zwei Aktionen. Gib der Preisliste eine Version und lass zwei Admins gleichzeitig veröffentlichen. Wie verhinderst du, dass die Aktion des einen Admins verloren geht? (Tipp: Tausche die Referenz nur mit CAS, wenn die Version noch die ist, die du gelesen hast.)
  • Der Prüfer ohne Lock. Lege den Bestand und die Zahl der Reservierten in ein unveränderliches Objekt und tausche es mit CAS. Prüfe, dass der Prüfer weiterhin immer 10.000 sieht.

Test

Teste dich

1. Der Bestand ist 6. Ein Thread ruft CAS auf: „Wenn es 5 ist, mach 4 daraus.“ Was passiert?
2. tryBuy hat „wenn der Bestand > 0 ist“ und dann „um 1 verringern“. Beide Zeilen sind atomar. Warum verkauft es trotzdem mehr, als da ist?
3. Die Kassen lesen die Preisliste tausende Male pro Sekunde, und sie ändert sich einmal am Tag. Wie teilst du sie am besten?
4. Du reservierst ein Stück: Der Bestand sinkt um 1, und die Zahl der Reservierten steigt um 1. Der Prüfer kontrolliert, dass die Summe immer 10.000 ist. Was brauchst du?

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