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 C# liegen sie in der Klasse Interlocked. Interlocked.Increment(ref views) ist das atomare +1 auf einem gewöhnlichen int-Feld oder einer Variablen und gibt den neuen Wert zurück. Es gibt auch Interlocked.Add, Interlocked.Decrement und Versionen für long.

Sieh es dir an

Der Seitenaufruf-Zähler

Vier Threads mit je 100.000 Aufrufen:

int views = 0;
var threads = new List<Thread>();
for (int t = 0; t < 4; t++)
{
    var thread = new Thread(() =>
    {
        for (int i = 0; i < 100_000; i++)
        {
            Interlocked.Increment(ref views);
        }
    });
    threads.Add(thread);
    thread.Start();
}
foreach (var thread in threads) thread.Join();
Console.WriteLine($"Aufrufe: {views}");
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

An einem eigenen Platz zählen. Wenn viele Threads dasselbe Feld erhöhen, treffen alle auf eine Speicherzelle, und die Prozessoren reichen sie herum. Wird der Wert erst am Ende gebraucht, ist es schneller, wenn jeder Thread in einer lokalen Variablen zählt und am Ende ein einziges Interlocked.Add macht. Java hat dafür eine fertige Klasse: LongAdder.

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 C# ist das Interlocked.CompareExchange(ref field, new, expected). Achte auf die Reihenfolge: Der neue Wert steht vor dem erwarteten. Die Methode gibt den Wert zurück, den sie gefunden hat. Ist das der erwartete, hat die Änderung stattgefunden. Volatile.Read liest das Feld so, dass du den letzten Wert siehst, den ein anderer Thread geschrieben hat.

Sieh es dir an

Die letzten drei Kopfhörer

class FlashSale
{
    private int stock;


    public FlashSale(int items)
    {
        stock = items;
    }


    public bool TryBuy()
    {
        while (true)
        {
            int left = Volatile.Read(ref stock);
            if (left == 0) return false; // ausverkauft
            int was = Interlocked.CompareExchange(
                ref stock, left - 1, left);
            if (was == left) return true;
            // jemand hat stock geändert: noch einmal lesen
        }
    }


    public int Stock => Volatile.Read(ref stock);
}
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: CompareExchange(…, 2, 3). „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:

var sale = new FlashSale(100);
int sold = 0, refused = 0;
var threads = new List<Thread>();
for (int t = 0; t < 4; t++)
{
    var thread = new Thread(() =>
    {
        for (int i = 0; i < 40; i++)
        {
            if (sale.TryBuy()) Interlocked.Increment(ref sold);
            else Interlocked.Increment(ref refused);
        }
    });
    threads.Add(thread);
    thread.Start();
}
foreach (var thread in threads) thread.Join();
Console.WriteLine($"Verkauft: {sold}");
Console.WriteLine($"Abgelehnt: {refused}");
Console.WriteLine($"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?

int stock = 3;
int seenByA = Volatile.Read(ref stock);
int seenByB = Volatile.Read(ref stock);
bool b = Interlocked.CompareExchange(ref stock, seenByB - 1, seenByB) == seenByB;
Console.WriteLine($"B: {b}");
bool a = Interlocked.CompareExchange(ref stock, seenByA - 1, seenByA) == seenByA;
Console.WriteLine($"A: {a}");
seenByA = Volatile.Read(ref stock);
a = Interlocked.CompareExchange(ref stock, seenByA - 1, seenByA) == seenByA;
Console.WriteLine($"A noch einmal: {a}");
Console.WriteLine($"Bestand: {stock}");
Antwort

Probier es aus

Ergänze

Womit vergleicht das CAS beim Kaufen?

int was = Interlocked.CompareExchange(
    ref stock, 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["headphones"] = 48;
prices["case"] = 12;
prices["cable"] = 4;


// Checkout, gleichzeitig
int total = cart.Sum(item => prices[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 ImmutableDictionary (aus System.Collections.Immutable) ist unveränderlich: Die Properties sind nur lesbar, und das Dictionary lässt sich nicht ändern. Die aktuelle Preisliste ist eine gewöhnliche Variable. Volatile.Write tauscht sie und Volatile.Read liest sie, sodass jeder Thread die zuletzt geschriebene sieht. Interlocked.Exchange tauscht die Referenz ebenfalls und gibt die alte zurück.

record PriceList(int Version, ImmutableDictionary<string, int> Prices)
{
    public int Total(List<string> cart) => cart.Sum(item => Prices[item]);
}
var regular = new Dictionary<string, int> { ["headphones"] = 60, ["case"] = 15, ["cable"] = 5 }.ToImmutableDictionary();
var promo = new Dictionary<string, int> { ["headphones"] = 48, ["case"] = 12, ["cable"] = 4 }.ToImmutableDictionary();
var cart = new List<string> { "headphones", "case", "cable" };
var current = new PriceList(1, regular);
int mixed = 0;


var admin = new Thread(() =>
{
    for (int v = 2; v <= 1001; v++)
    {
        var prices = v % 2 == 0 ? promo : regular;
        Volatile.Write(ref current, new PriceList(v, prices)); // ein neuer Schnappschuss, eine Referenz
    }
});
var checkout = new Thread(() =>
{
    for (int i = 0; i < 100_000; i++)
    {
        var list = Volatile.Read(ref current); // ein Schnappschuss für den ganzen Warenkorb
        int total = list.Total(cart);
        if (total != 80 && total != 64) Interlocked.Increment(ref mixed);
    }
});
admin.Start();
checkout.Start();
admin.Join();
checkout.Join();
Console.WriteLine("Geprüfte Summen: 100000");
Console.WriteLine($"Gemischte Summen: {mixed}");
Console.WriteLine($"Letzte Version: {current.Version}, Summe {current.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.

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:

int stock = 10;
int reserved = 0;


void Reserve()
{
    Interlocked.Decrement(ref stock);    // jede Zeile ist atomar,
    Interlocked.Increment(ref reserved); // 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 readonly object sync = new object();
    private int stock;
    private int reserved;


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


    public bool Reserve()
    {
        lock (sync) // beide oder keine
        {
            if (stock == 0) return false;
            stock--;
            reserved++;
            return true;
        }
    }


    public int Audit()
    {
        lock (sync)
        {
            return stock + reserved;
        }
    }


    public string Report()
    {
        lock (sync)
        {
            return $"Bestand: {stock}, reserviert: {reserved}";
        }
    }
}
var warehouse = new Warehouse(10_000);
int broken = 0;
ThreadStart reserver = () =>
{
    while (warehouse.Reserve()) { }
};
ThreadStart auditor = () =>
{
    for (int i = 0; i < 50_000; i++)
    {
        if (warehouse.Audit() != 10_000) Interlocked.Increment(ref broken);
    }
};
var threads = new List<Thread> { new Thread(reserver), new Thread(reserver), new Thread(auditor) };
foreach (var thread in threads) thread.Start();
foreach (var thread in threads) thread.Join();
Console.WriteLine(warehouse.Report());
Console.WriteLine($"Fehlerhafte Prüfungen: {broken}");
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 (Interlocked.CompareExchange auf die Referenz). 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 ·