Atomare Operationen und unveränderliche Objekte

Code in:JavaC#PythonJavaScript

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 JavaScript liegen atomare Operationen in Atomics und arbeiten auf einem Int32Array (oder einem anderen Array von Ganzzahlen) über einem SharedArrayBuffer: dem Speicher, den mehrere Worker sehen. Atomics.add(array, index, 1) ist das atomare +1. Du hast es in der Lektion über Threads gesehen. In gewöhnlichem async-Code auf einem Thread brauchst du nichts: Dort kann niemand views++ unterbrechen.

Sieh es dir an

Der Seitenaufruf-Zähler

Vier Threads mit je 100.000 Aufrufen:

import { Worker, isMainThread, workerData } from "node:worker_threads";
import { once } from "node:events";

if (isMainThread) {
  const views = new Int32Array(new SharedArrayBuffer(4));
  const workers = [1, 2, 3, 4].map(
    () => new Worker(new URL(import.meta.url), { workerData: views }),
  );
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  console.log(`Aufrufe: ${views[0]}`);
} else {
  for (let i = 0; i < 100_000; i++) {
    Atomics.add(workerData, 0, 1);
  }
}

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

Atomics arbeitet nur auf Arrays von Ganzzahlen über einem SharedArrayBuffer. Gewöhnliche Objekte, Arrays und Zahlen werden nicht zwischen Workern geteilt: postMessage kopiert sie. In JavaScript gibt es geteilten Zustand also nur dort, wo du ihn ausdrücklich verlangt hast.

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 JavaScript ist das Atomics.compareExchange(array, index, expected, new). Es gibt den Wert zurück, den es gefunden hat. Ist das der erwartete, hat die Änderung stattgefunden.

Sieh es dir an

Die letzten drei Kopfhörer

// cells: Int32Array über einem SharedArrayBuffer
const STOCK = 0, SOLD = 1, REFUSED = 2;

function tryBuy(cells) {
  while (true) {
    const left = Atomics.load(cells, STOCK);
    if (left === 0) return false; // ausverkauft
    const was = Atomics.compareExchange(
      cells, STOCK, left, left - 1);
    if (was === left) return true;
    // jemand hat stock geändert: noch einmal lesen
  }
}

Schritt für Schritt, in Worten

1. Die letzten 3 Kopfhörer: Der Bestand ist 3. Worker 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(…, 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 Worker 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:

if (isMainThread) {
  const cells = new Int32Array(new SharedArrayBuffer(12));
  cells[STOCK] = 100;
  const workers = [1, 2, 3, 4].map(
    () => new Worker(new URL(import.meta.url), { workerData: cells }),
  );
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  console.log(`Verkauft: ${cells[SOLD]}`);
  console.log(`Abgelehnt: ${cells[REFUSED]}`);
  console.log(`Bestand: ${cells[STOCK]}`);
} else {
  for (let i = 0; i < 40; i++) {
    if (tryBuy(workerData)) Atomics.add(workerData, SOLD, 1);
    else Atomics.add(workerData, REFUSED, 1);
  }
}

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?

const stock = new Int32Array(new SharedArrayBuffer(4));
stock[0] = 3;
let seenByA = Atomics.load(stock, 0);
const seenByB = Atomics.load(stock, 0);
const b = Atomics.compareExchange(stock, 0, seenByB, seenByB - 1) === seenByB;
console.log(`B: ${b}`);
let a = Atomics.compareExchange(stock, 0, seenByA, seenByA - 1) === seenByA;
console.log(`A: ${a}`);
seenByA = Atomics.load(stock, 0);
a = Atomics.compareExchange(stock, 0, seenByA, seenByA - 1) === seenByA;
console.log(`A noch einmal: ${a}`);
console.log(`Bestand: ${Atomics.load(stock, 0)}`);

Antwort

B: true
A: true
A noch einmal: true
Bestand: 0

B: true
A: true
A noch einmal: false
Bestand: 1

B: true
A: false
A noch einmal: true
Bestand: 1

Prüfen

Probier es aus

Ergänze

Womit vergleicht das CAS beim Kaufen?

const was = Atomics.compareExchange(
  cells, STOCK, , left - 1);

Prüfen

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.

1function tryBuy(cells) {2 if (Atomics.load(cells, STOCK) > 0) {3 Atomics.sub(cells, STOCK, 1);4 return true;5 }6 return false;7}

Prüfen

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;
await saveToLog(); // eine Pause zwischen zwei Änderungen
prices.case = 12;
prices.cable = 4;

// Checkout, während der Pause
const total = cart.reduce((sum, item) => sum + prices[item], 0);

Der Warenkorb kostet 68 €: eine Summe, die zu keinem Zeitpunkt stimmte. Nicht mit den alten Preisen (80 €), nicht mit den neuen (64 €). In JavaScript gibt es einen Thread, aber ein await mitten in der Änderung lässt anderen Code das halb geänderte Objekt lesen.

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.

Zwischen Workern werden überhaupt keine Objekte geteilt. postMessage sendet eine Kopie, das „Veröffentlichen“ einer neuen Preisliste ist also eine Nachricht an jede Kasse. In einem Thread schützt Object.freeze davor, sie versehentlich zu ändern. Der Versuch, ein eingefrorenes Objekt in einem Modul zu ändern, wirft einen TypeError.

function priceList(version, prices) {
  return Object.freeze({ version, prices: Object.freeze({ ...prices }) });
}

function total(list, cart) {
  return cart.reduce((sum, item) => sum + list.prices[item], 0);
}

import { Worker, isMainThread, parentPort } from "node:worker_threads";
import { once } from "node:events";

const cart = ["headphones", "case", "cable"];

if (isMainThread) {
  const regular = { headphones: 60, case: 15, cable: 5 };
  const promo = { headphones: 48, case: 12, cable: 4 };
  const checkout = new Worker(new URL(import.meta.url));
  for (let v = 1; v <= 3; v++) {
    checkout.postMessage(priceList(v, v % 2 === 0 ? promo : regular));
    const [line] = await once(checkout, "message");
    console.log(line);
  }
  checkout.postMessage(null);
  await once(checkout, "exit");
  const last = priceList(3, regular);
  try {
    last.prices.headphones = 1;
  } catch (error) {
    console.log(`Eingefroren: ${error.constructor.name}`);
  }
} else {
  parentPort.on("message", (list) => {
    if (list === null) return parentPort.close();
    parentPort.postMessage(`Version ${list.version}: ${total(list, cart)} €`);
  });
}

Ausgabe

Version 1: 80 €
Version 2: 64 €
Version 3: 80 €
Eingefroren: TypeError

Jede Kasse bekommt ihre eigene Kopie und rechnet damit. Niemand sonst kann diese Kopie ändern, also kann es keine gemischten Summen geben.

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 Object.freeze auch auf dem verschachtelten Objekt prices: freeze geht nur eine Ebene tief.

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:

function reserve(cells) {
  Atomics.sub(cells, STOCK, 1);    // jede Zeile ist atomar,
  Atomics.add(cells, RESERVED, 1); // 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:

// cells: [Lock, Bestand, reserviert] in einem SharedArrayBuffer
const LOCK = 0, STOCK = 1, RESERVED = 2;

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

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

function reserve(cells) {
  lock(cells); // beide oder keine
  try {
    if (cells[STOCK] === 0) return false;
    cells[STOCK]--;
    cells[RESERVED]++;
    return true;
  } finally {
    unlock(cells);
  }
}

function audit(cells) {
  lock(cells);
  try {
    return cells[STOCK] + cells[RESERVED];
  } finally {
    unlock(cells);
  }
}

if (isMainThread) {
  const cells = new Int32Array(new SharedArrayBuffer(12));
  cells[STOCK] = 10_000;
  const roles = ["reserver", "reserver", "auditor"];
  const workers = roles.map(
    (role) => new Worker(new URL(import.meta.url), { workerData: { cells, role } }),
  );
  const report = once(workers[2], "message");
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  const [broken] = await report;
  console.log(`Bestand: ${cells[STOCK]}, reserviert: ${cells[RESERVED]}`);
  console.log(`Fehlerhafte Prüfungen: ${broken}`);
} else if (workerData.role === "reserver") {
  while (reserve(workerData.cells)) {}
} else {
  let broken = 0;
  for (let i = 0; i < 50_000; i++) {
    if (audit(workerData.cells) !== 10_000) broken++;
  }
  parentPort.postMessage(broken);
}

Ausgabe

Bestand: 0, reserviert: 10000
Fehlerhafte Prüfungen: 0

JavaScript hat keine Locks, deshalb ist hier eines mit Atomics geschrieben: compareExchange nimmt das Lock (0 → 1), und Atomics.wait schläft, solange es genommen ist. Das tut lock in den anderen Sprachen.

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. 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 tryUse(cells) 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?

Nichts wird geschrieben, und die Antwort ist „fehlgeschlagen“: Der Thread muss noch einmal lesen4 wird geschriebenDer Thread schläft, bis der Wert 5 wird

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?

Zwischen der Prüfung und dem Verringern kann ein anderer Thread das letzte Stück nehmen: Jeder Schritt ist unteilbar, aber beide zusammen nichtDas kann nicht passieren: Wenn jede Zeile atomar ist, ist die ganze Methode sicherWeil atomare Operationen manchmal Erhöhungen verlieren

3. Die Kassen lesen die Preisliste tausende Male pro Sekunde, und sie ändert sich einmal am Tag. Wie teilst du sie am besten?

Ein gemeinsames Dictionary, in dem der Admin die Preise einzeln ändertEin unveränderliches Objekt: Der Admin macht eine neue Preisliste und tauscht eine Referenz; jede Kasse liest die ganze alte oder die ganze neueEin Lock um jedes Lesen eines Preises

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?

Ein Lock um beide Änderungen und um die PrüfungZwei atomare VariablenNichts: Die Summe wird am Ende berechnet

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Async, await und Threads · Warum Threads · Race Condition · Sperren
• Geht weiter in: Deadlock · Producer und Consumer · Nebenläufigen Code testen
• Aufgaben zum Thema: Nebenläufigkeit und Race Conditions