Locks und Mutexe in JavaScript

Problem

Wie man die andere Kasse aufhält

In der Lektion „Race Condition“ hat der Verkauf Verkäufe verloren: Zwei Threads machten gleichzeitig „lesen, abziehen, schreiben“, und einer überschrieb den anderen. Die drei Schritte müssen ein Ganzes sein: Solange ein Thread drin ist, muss der andere draußen warten.

Genau das macht ein Lock.

Die Idee

Das Lock

Ein Lock (Mutex, von „mutual exclusion“) ist ein Objekt mit einem Besitzer. Ein Thread nimmt es, erledigt seine Arbeit und gibt es frei. Ein anderer Thread, der es währenddessen verlangt, wartet. Der Code zwischen Nehmen und Freigeben ist der kritische Abschnitt: Höchstens ein Thread ist darin.

JavaScript hat kein fertiges Lock zwischen Workern, also baust du eines aus Atomics auf einem SharedArrayBuffer. shop[0] ist das Lock: 0 ist frei, 1 ist belegt. Atomics.compareExchange macht „wenn es 0 ist, setze 1“ als einen unteilbaren Schritt, also nimmt es nur ein Worker. Die anderen schlafen in Atomics.wait, bis unlock sie weckt:

// state[0]: 0 ist frei, 1 ist belegt.
function lock(state) {
  while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {
    Atomics.wait(state, 0, 1);  // schläft, solange belegt ist
  }
}

function unlock(state) {
  Atomics.store(state, 0, 0);
  Atomics.notify(state, 0, 1);  // weckt einen der Wartenden
}

// shop[0] ist das Lock, shop[1] ist der Bestand.
function sell(shop) {
  lock(shop);
  shop[1]--;
  unlock(shop);
}

Die zwei Worker aus der letzten Lektion, je 100.000 Verkäufe:

if (isMainThread) {
  const shop = new Int32Array(new SharedArrayBuffer(8));
  shop[1] = 200_000;
  const checkouts = [1, 2].map(
    () => new Worker(new URL(import.meta.url), { workerData: shop }),
  );
  await Promise.all(checkouts.map((worker) => once(worker, "exit")));
  console.log(`Bestellungen: ${2 * 100_000}`);
  console.log("Verkauft laut Lager:");
  console.log(200_000 - shop[1]);
} else {
  for (let i = 0; i < 100_000; i++) {
    sell(workerData);
  }
}

Bestellungen: 200000
Verkauft laut Lager:
200000

Genau, bei jedem Lauf. Das Lock ist eine Zahl im gemeinsamen Speicher: Beide Kassen sperren dasselbe.

Sieh es dir an

Der letzte Artikel, repariert

Die Prüfung „ist einer da“ und das Nehmen liegen im selben kritischen Abschnitt. Wenn jemand drin ist und prüft, kann der andere nicht prüfen, bevor der erste genommen hat:

// state[0]: 0 ist frei, 1 ist belegt.
function lock(state) {
  while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {
    Atomics.wait(state, 0, 1);  // schläft, solange belegt ist
  }
}

function unlock(state) {
  Atomics.store(state, 0, 0);
  Atomics.notify(state, 0, 1);  // weckt einen der Wartenden
}

// shop[0] ist das Lock, shop[1] ist der Bestand.
function reserve(shop) {
  lock(shop);
  try {
    if (shop[1] === 0) {
      return false;   // keiner mehr da: ablehnen
    }
    shop[1]--;        // einer ist da: nehmen
    return true;
  } finally {
    unlock(shop);
  }
}

Schritt für Schritt, in Worten

Es sind noch 3 Stück übrig, und 4 Käufer rufen im selben Moment reserve() auf.
Durch lock(shop) kommt nur einer, die anderen drei warten davor. Käufer 1 geht hinein, sieht 3 und nimmt eins: 2 übrig.
Käufer 1 geht hinaus und gibt das Lock frei. Käufer 2 geht hinein, sieht 2 und nimmt eins: 1 übrig.
Käufer 2 geht hinaus und gibt das Lock frei. Käufer 3 geht hinein, sieht 1 und nimmt eins: 0 übrig.
Käufer 4 geht als letzter hinein und sieht 0: abgelehnt. Niemand sah eine Zahl, die ein anderer gerade ändert.
3 verkauft, 1 abgelehnt, 0 auf Lager: richtig. Der Preis: Die Käufer haben am Drehkreuz aufeinander gewartet.

Vier Käufer, drei Artikel, alle auf einmal:

if (isMainThread) {
  const shop = new Int32Array(new SharedArrayBuffer(8));
  shop[1] = 3;
  const buyers = Array.from({ length: 4 }, () =>
    new Worker(new URL(import.meta.url), { workerData: shop }));
  const results = await Promise.all(
    buyers.map(async (buyer) => (await once(buyer, "message"))[0]),
  );
  console.log(`Verkauft: ${results.filter((ok) => ok).length}`);
  console.log(`Abgelehnt: ${results.filter((ok) => !ok).length}`);
  console.log(`Bestand: ${shop[1]}`);
} else {
  parentPort.postMessage(reserve(workerData));
}

Verkauft: 3
Abgelehnt: 1
Bestand: 0

Und hier sind die zwei Käufer aus der letzten Lektion, die den letzten Artikel kauften. Das Belasten der Karte (~100 ms) kommt nach dem Lock: Der Artikel ist reserviert, und die Karte wird belastet, ohne dass der andere wartet:

if (isMainThread) {
  const shop = new Int32Array(new SharedArrayBuffer(8));
  shop[1] = 1;
  const buyers = [1, 2].map(
    () => new Worker(new URL(import.meta.url), { workerData: shop }),
  );
  const bought = await Promise.all(
    buyers.map(async (buyer) => (await once(buyer, "message"))[0]),
  );
  const sold = bought.filter((ok) => ok).length;
  console.log("Bestand vorher: 1");
  console.log(`Verkauft: ${sold}`);
  console.log(`Abgelehnt: ${2 - sold}`);
  console.log(`Bestand: ${shop[1]}`);
} else {
  const ok = reserve(workerData);
  if (ok) {
    Atomics.wait(new Int32Array(new SharedArrayBuffer(4)), 0, 0, 100);   // die Karte wird belastet, ~100 ms
  }
  parentPort.postMessage(ok);
}

Bestand vorher: 1
Verkauft: 1
Abgelehnt: 1
Bestand: 0

Einer verkauft, einer abgelehnt, 0 auf Lager. Bei jedem Lauf.

Probier es aus

Vergiss die Freigabe nicht

Du rufst lock und unlock selbst auf, also steht die Freigabe in finally. Sonst lässt eine Exception im kritischen Abschnitt das Lock für immer belegt:

// state[0]: 0 ist frei, 1 ist belegt.
function lock(state) {
  while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {
    Atomics.wait(state, 0, 1);  // schläft, solange belegt ist
  }
}

function unlock(state) {
  Atomics.store(state, 0, 0);
  Atomics.notify(state, 0, 1);  // weckt einen der Wartenden
}

function sell(shop) {
  lock(shop);
  try {
    shop[1]--;
  } finally {
    unlock(shop);
  }
}

Was gibt das Lock frei?

function sell(shop) {
  lock(shop);
  try {
    shop[1]--;
  } finally {
    
  }
}

Probier es aus

Das Lock, das nicht sperrt

Ein Kollege hat ein Lock hinzugefügt, aber die Kassen verlieren trotzdem Verkäufe. Welche Zeile ist falsch?

Wähle die Zeile mit dem Fehler.

new SharedArrayBuffer(4) macht bei jedem Aufruf ein neues Lock, und zwar nur im Speicher dieses Workers. Jeder nimmt sein eigenes freies Lock, und niemand wartet auf jemanden. Das Lock lebt im gemeinsamen Speicher, einmal erzeugt: shop[0], wie in lock(shop).

Die Idee

Was ein Lock kostet

Ein Lock funktioniert, indem es Threads aufeinander warten lässt. Je länger ein Thread drin bleibt, desto länger warten die anderen. Das ist die Contention (Konkurrenz) um das Lock.

Ein Shop mit 10 Artikeln und vier Bestellungen auf einmal. Jede Bestellung nimmt einen Artikel und sendet eine E-Mail (~200 ms), und Network aus der Lektion „Warum Threads“ zählt die Warterunden:

// Fragt einen Dienst über das Netzwerk: Die Antwort kommt nach ~200 ms.
function call(net, service, answer) {
  if (Atomics.add(net, 0, 1) === 0) Atomics.add(net, 1, 1);   // niemand wartet: eine neue Runde
  Atomics.wait(new Int32Array(new SharedArrayBuffer(4)), 0, 0, 200);
  Atomics.sub(net, 0, 1);
  return `${service}: ${answer}`;
}

// shop[0] ist das Lock, shop[1] ist der Bestand.

// Schlecht: Die E-Mail geht raus, während das Lock gehalten wird.
function orderSlow(shop, net, customer) {
  lock(shop);
  try {
    shop[1]--;
    call(net, "E-Mail", customer);
  } finally {
    unlock(shop);
  }
}

// Gut: Unter dem Lock liegt nur der Bestand.
function order(shop, net, customer) {
  lock(shop);
  try {
    shop[1]--;
  } finally {
    unlock(shop);
  }
  call(net, "E-Mail", customer);
}

Bei orderSlow liegt die E-Mail unter dem Lock:

if (isMainThread) {
  const shop = new Int32Array(new SharedArrayBuffer(8));
  const net = new Int32Array(new SharedArrayBuffer(8));
  shop[1] = 10;
  const orders = [1, 2, 3, 4].map((c) => new Worker(new URL(import.meta.url), {
    workerData: { shop, net, customer: `Kunde ${c}` },
  }));
  await Promise.all(orders.map((order) => once(order, "exit")));
  console.log(`Bestellungen: 4, bestand: ${shop[1]}`);
  console.log(`Warterunden: ${net[1]}`);
} else {
  orderSlow(workerData.shop, workerData.net, workerData.customer);
}

Bestellungen: 4, bestand: 6
Warterunden: 4

Vier Runden: Die E-Mails gehen einzeln raus, und der letzte Kunde wartet etwa 800 ms. Bei order liegt nur der Bestand unter dem Lock:

if (isMainThread) {
  const shop = new Int32Array(new SharedArrayBuffer(8));
  const net = new Int32Array(new SharedArrayBuffer(8));
  shop[1] = 10;
  const orders = [1, 2, 3, 4].map((c) => new Worker(new URL(import.meta.url), {
    workerData: { shop, net, customer: `Kunde ${c}` },
  }));
  await Promise.all(orders.map((order) => once(order, "exit")));
  console.log(`Bestellungen: 4, bestand: ${shop[1]}`);
  console.log(`Warterunden: ${net[1]}`);
} else {
  order(workerData.shop, workerData.net, workerData.customer);
}

Bestellungen: 4, bestand: 6
Warterunden: 1

Derselbe Bestand, eine Runde. Die Regeln:

Nur die gemeinsamen Daten unter das Lock. Rechne, formatiere und warte draußen. Drinnen nur lesen und schreiben.
Warte nie unter einem Lock: Netzwerk, Festplatte, Datenbank, sleep. Nimm, was du brauchst, gib das Lock frei und warte dann.
Ein Lock für ein Datenstück. Der Bestand und der Umsatz sind getrennt: jedes mit eigenem Lock, damit Kassen, die nur eines von beiden anfassen, nicht aufeinander warten.

Genauer, für Neugierige

Dieses Lock ist das einfachste: Es ist nicht fair (ein geweckter Worker kann seine Runde verpassen) und nicht reentrant. In echtem Code nimmt man eine fertige Bibliothek.
Atomics.wait darf im Haupt-Thread des Browsers nicht aufgerufen werden: Er darf nicht schlafen. In Node geht es.
In einem Thread mit async brauchst du ein Lock nur um await herum. Das ist die Lektion „async ist kein Thread“.

Ein Lock ist nicht der einzige Weg. Für einen Zähler gibt es atomare Operationen, die Threads gar nicht warten lassen, und Daten, die niemand ändert, brauchen kein Lock: die Lektion „Atomare Operationen und unveränderliche Objekte“. Und zwei Locks, die zwei Threads in unterschiedlicher Reihenfolge nehmen, können das Programm für immer anhalten: die Lektion „Deadlock“.

Übung

Der Umsatz und eine Bestellung mit mehreren Artikeln

Löse die Aufgaben in deinem Editor.

Der Umsatz. Repariere die Aufgabe aus der letzten Lektion: zwei Kassen mit je 500.000 Verkäufen zu 3 €, und revenue[1] += 3 steht zwischen lock(revenue) und unlock(revenue), und das Lock ist revenue[0]. Führe das Programm mehrmals aus: Der Umsatz muss jedes Mal derselbe sein.

Kasse 1: 50000 Verkäufe
Kasse 2: 50000 Verkäufe
Umsatz (€):
300000

Eine Bestellung mit mehreren Artikeln. Es sind 5 Artikel auf Lager. Schreibe reserve(shop, count): Wenn mindestens count da sind, nimmt es sie und gibt true zurück, sonst nimmt es nichts und gibt false zurück. Drei Kunden wollen gleichzeitig je 2 Artikel, jeder in seinem eigenen Worker.

Bestellt: 3
Angenommen: 2
Abgelehnt: 1
Bestand: 1

Weitere Aufgaben

Der Preis eines Locks. Führe die zwei Kassen mit je 1.000.000 Verkäufen mit und ohne Lock aus und miss die Zeit. Wie viel langsamer ist es mit dem Lock? Und mit 8 Kassen?
Zwei Locks. Füge dem Bestand einen Umsatz mit eigenem Lock hinzu. Ein Verkauf zieht vom Bestand ab und addiert zum Umsatz. Bleiben die beiden zusammen, wenn jemand den Bestand und den Umsatz zwischen den beiden Locks liest? - tryLock. Schreibe tryLock(state), das das Lock mit einem compareExchange nimmt, wenn es frei ist, und false zurückgibt, ohne zu schlafen, wenn es belegt ist.

Test

Teste dich

1. Zwei Worker rufen sell(shop) auf, das shop[1]-- zwischen lock(shop) und unlock(shop) ausführt. Was macht der zweite, wenn das Lock belegt ist?Er geht sofort hinein, weil der Code derselbe istEr wirft eine ExceptionEr schläft in Atomics.wait, bis der erste unlock aufruft

2. Die Prüfung „sind Artikel da“ liegt unter dem Lock, und das Abziehen steht in einem eigenen Block unter demselben Lock. Zwei Leute kaufen den letzten Artikel. Was passiert?Es ist richtig: Beide Blöcke sind gesperrtDer zweite wartet immer, bis der erste bezahlt hatSie können trotzdem zwei verkaufen: Zwischen den beiden Blöcken ist das Lock frei

3. Unter dem Lock liegen das Abziehen vom Bestand und das Senden einer E-Mail (~200 ms). Vier Bestellungen kommen auf einmal. Wie lange wartet die letzte?Etwa 200 ms: Die E-Mails gehen zusammen rausFast nichts: Das Lock ist schnellEtwa 800 ms: Die E-Mails gehen einzeln raus

4. Was passiert, wenn shop[1]-- zwischen lock(shop) und unlock(shop) ohne try/finally eine Exception wirft?Nichts: Die Exception stoppt nur diesen WorkerDas Lock bleibt für immer belegt, und die anderen Worker schlafen für immerDas Lock gibt sich selbst frei

Sperren

Cookies