Атомарни операции и неизменими обекти

Код на:JavaC#PythonJavaScript

Накратко: Атомарната операция (например +1 или compare-and-set) се изпълнява наведнъж, без друга нишка да я прекъсне, и пази споделени данни без ключалка; неизменимият обект изобщо не се променя.

Проблем

Ключалка за едно +1

Флаш разпродажба: 100 слушалки на половин цена, в 10:00. Страницата на продукта се отваря хиляди пъти в секунда, а всяко отваряне увеличава брояча на изгледите. От урока за ключалките знаеш как да не се губят увеличения: ключалка около views++.

Това е правилно. Но всяка нишка застава на опашка пред ключалката заради едно-единствено +1. Нишка, която не получи ключалката, често бива приспана и после събудена от операционната система. Това струва много повече от самото събиране.

Втората беда е по-лоша. Последната бройка се купува с „ако има, намали с 1“. Това са две стъпки, а между тях друга нишка може да вземе същата бройка.

Идеята

Неделима стъпка

Процесорът има команди, които прочитат, сменят и записват една клетка от паметта с една неделима стъпка. Никоя друга нишка не може да се намеси по средата. Това е атомарна операция (atomic). Не трябва ключалка, никой не чака на опашка и никой не заспива.

В JavaScript атомарните операции са в Atomics и работят върху Int32Array (или друг масив от цели числа) върху SharedArrayBuffer: паметта, която виждат няколко Worker-а. Atomics.add(масив, място, 1) е атомарното +1. Видя го в урока за нишките. В обикновен async код в една нишка не трябва нищо: там views++ никой не може да прекъсне.

Виж го

Броячът на изгледите

Четири нишки, всяка с по 100 000 изгледа:

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(`Изгледи: ${views[0]}`);
} else {
  for (let i = 0; i < 100_000; i++) {
    Atomics.add(workerData, 0, 1);
  }
}

Изход

Изгледи: 400000

400 000 при всяко пускане. Без атомарното +1 щеше да е по-малко и различно всеки път, както в урока за race condition.

По-точно, за любопитните

Atomics работи само върху масиви от цели числа над SharedArrayBuffer. Обикновените обекти, масиви и числа не се делят между Worker-ите: postMessage ги копира. Затова в JavaScript споделеното състояние е само там, където си го поискал изрично.

Колко по-бързо е от ключалка? Зависи от машината и от това колко нишки се бият за една клетка. Без борба атомарното +1 е няколко наносекунди. Ключалката без борба е близо до него. Разликата идва при много нишки: тогава ключалката приспива, а атомарната операция само повтаря.

Идеята

Провери и смени: compare-and-set

Купуването не е само −1. То е „ако има поне една, намали с 1“. Проверката и смяната трябва да са една стъпка.

За това има по-обща атомарна операция: compare-and-set (CAS, „сравни и смени“). Казваш ѝ две числа: какво мислиш, че има, и какво искаш да има. Тя сменя стойността само ако тя е още тази, която мислиш, и казва дали е успяла. Ако друга нишка я е сменила междувременно, CAS не пипа нищо и отговаря „не“.

Тогава купуването е цикъл:

1. прочети наличността;
2. ако е 0, отказ;
3. CAS: „ако е още толкова, направи я с 1 по-малко“;
4. ако CAS не успее, някой е купил междувременно: върни се на 1.

В JavaScript това е Atomics.compareExchange(масив, място, очаквано, ново). Той връща стойността, която е намерил. Ако тя е очакваната, смяната е станала.

Виж го

Последните три слушалки

// cells е Int32Array върху SharedArrayBuffer
const STOCK = 0, SOLD = 1, REFUSED = 2;

function tryBuy(cells) {
  while (true) {
    const left = Atomics.load(cells, STOCK);
    if (left === 0) return false; // разпродадено
    const was = Atomics.compareExchange(
      cells, STOCK, left, left - 1);
    if (was === left) return true;
    // друг е сменил stock: прочети пак
  }
}

Стъпка по стъпка, с думи

1. Последните 3 слушалки: наличността е 3. Worker A и Worker B викат tryBuy() едновременно.
2. A прочита наличността: left = 3.
3. B я прочита, преди A да е сменила нещо: също 3.
4. B: compareExchange(…, 3, 2). „Ако още е 3, направи го 2.“ Още е 3, затова се записва 2. B купи.
5. A пробва същото: „ако още е 3…“. Вече е 2, затова нищо не се записва и отговорът е false. Нищо не е загубено.
6. A не чака и не се отказва: цикълът се завърта и A прочита пак: 2. Нито един Worker не е заспивал.
7. A: „ако още е 2, направи го 1“. Още е 2: записва се 1. A също купи.
8. Двама купувачи, две продадени, наличност 1. Ключалка няма: процесорът проверява и записва с една стъпка, а който загуби, само повтаря цикъла.

Никой не чака: нишката, която загуби, само повтаря два реда. Това се казва lock-free (без ключалка). Сто купувачи на 160 опита:

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(`Продадени: ${cells[SOLD]}`);
  console.log(`Отказани: ${cells[REFUSED]}`);
  console.log(`Наличност: ${cells[STOCK]}`);
} else {
  for (let i = 0; i < 40; i++) {
    if (tryBuy(workerData)) Atomics.add(workerData, SOLD, 1);
    else Atomics.add(workerData, REFUSED, 1);
  }
}

Изход

Продадени: 100
Отказани: 60
Наличност: 0

Колко пъти се е завъртял цикълът, е различно при всяко пускане. Затова програмата не го печата. Сборът е винаги един и същ: 100 продадени, 60 отказа, 0 на склад.

Пробвай

Предвиди изхода

Тук двете „нишки“ са написани една след друга в една нишка, за да е редът същият като в сцената при всяко пускане. Какво ще отпечата?

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 отново: ${a}`);
console.log(`Наличност: ${Atomics.load(stock, 0)}`);

Отговор

B: true
A: true
A отново: false
Наличност: 1

B: true
A: false
A отново: true
Наличност: 1

B: true
A: true
A отново: true
Наличност: 0

Провери

Пробвай

Попълни

Срещу какво сравнява CAS при купуването?

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

Провери

Пробвай

Намери грешката

Колега е опростил купуването. Всеки ред сам е безопасен, а при разпродажбата пак се продават 103 слушалки от 100. На кой ред е грешката?

Избери реда с грешката.

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

Провери

Проблем

Ценоразписът, който се сменя по средата

В 10:00 администраторът пуска промоцията: слушалки от 60 на 48 €, калъф от 15 на 12 €, кабел от 5 на 4 €. В същото време касите смятат колички. Ако цените са в един общ речник и се сменят една по една, касата може да прочете новата цена на слушалките и старата на калъфа:

// администраторът
prices.headphones = 48;
await saveToLog(); // пауза между две промени
prices.case = 12;
prices.cable = 4;

// касата, по време на паузата
const total = cart.reduce((sum, item) => sum + prices[item], 0);

Количката излиза 68 €: сума, която не е била вярна в нито един момент. Не по старите цени (80 €), не по новите (64 €). В JavaScript нишката е една, но await по средата на промяната дава на друг код да прочете наполовина сменения обект.

Идеята

Не променяй, а смени целия

Ценоразписът се чете много пъти и се сменя рядко. Тогава не го променяй никога. Направи го неизменим обект (immutable): веднъж създаден, той остава същият. За промоцията администраторът прави нов ценоразпис и сменя една референция: „текущият ценоразпис е този“.

• Обект, който никой не променя, се чете от колкото искаш нишки без никаква защита.
• Единственото общо нещо е референцията, а смяната ѝ е една атомарна стъпка.
• Касата взима референцията веднъж, в началото на количката, и смята цялата количка по нея. Тя вижда целия стар или целия нов ценоразпис, никога смес.

Между Worker-и обекти изобщо не се делят. postMessage праща копие, затова „публикуването“ на нов ценоразпис е съобщение до всяка каса. В една нишка Object.freeze пази от промяна по погрешка. Опитът да смениш замразен обект в модул хвърля 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(`Замразен: ${error.constructor.name}`);
  }
} else {
  parentPort.on("message", (list) => {
    if (list === null) return parentPort.close();
    parentPort.postMessage(`Версия ${list.version}: ${total(list, cart)} €`);
  });
}

Изход

Версия 1: 80 €
Версия 2: 64 €
Версия 3: 80 €
Замразен: TypeError

Всяка каса получава свое копие и смята по него. Копието никой друг не може да промени, затова смесени суми няма как да има.

По-точно, за любопитните

Така работят и колекциите „копирай при запис“: CopyOnWriteArrayList в Java, ImmutableList в C#. Всяка промяна прави ново копие, а четенето е без ключалка. Струва си, когато се чете много, а се пише рядко. Ако се пише често, копирането става скъпо.

Неизменимостта е честна само докато е до дъно. Обект с final поле, което сочи променлив списък, не е неизменим: списъкът може да се смени отвън. Затова Object.freeze е и на вложения обект prices: freeze е само едно ниво.

Как е в другите езици: record и Map.copyOf с AtomicReference в Java; record с ImmutableDictionary и Volatile или Interlocked.Exchange в C#; frozen dataclass, tuple или MappingProxyType и присвояване в Python; Object.freeze и съобщения между Worker-и в JavaScript.

Идеята

Когато атомарното не стига

Резервацията мести бройка от наличността в резервираните. Правилото е, че двете заедно са винаги 10 000. Две атомарни променливи не го пазят:

function reserve(cells) {
  Atomics.sub(cells, STOCK, 1);    // всеки ред е атомарен,
  Atomics.add(cells, RESERVED, 1); // двата заедно не са
}

Между двата реда ревизорът вижда 9 999 общо. Атомарното пази една стойност. Когато правилото е за няколко стойности заедно, трябва ключалка около всички промени и около проверката:

// cells: [ключалка, наличност, резервирани] в 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); // двете или нито една
  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(`Наличност: ${cells[STOCK]}, резервирани: ${cells[RESERVED]}`);
  console.log(`Счупени проверки: ${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);
}

Изход

Наличност: 0, резервирани: 10000
Счупени проверки: 0

В JavaScript ключалки няма, затова тук е написана от Atomics: compareExchange взима ключалката (0 → 1), а Atomics.wait спи, докато е заета. Това е същото, което lock прави в другите езици.

По-точно, за любопитните

Друг начин без ключалка: двете стойности в един неизменим обект (наличност, резервирани), а смяната с CAS върху референцията. Нов обект с двете нови стойности замества стария наведнъж. Това съчетава двете идеи от урока, но ключалката обикновено е по-ясна.

Кога кое:

• една стойност, брояч или флаг: атомарна операция;
• проверка и смяна на една стойност: цикъл с CAS;
• данни, които се четат много и се сменят рядко: неизменим обект и смяна на референцията;
• няколко свързани стойности: ключалка.

Упражнение

Купон с ограничен брой

Реши задачата в редактора си.

Купонът „SPRING20“ може да се ползва 50 пъти. Осем нишки, всяка с по 10 клиента, опитват да го ползват едновременно. Напиши tryUse(cells) така, че купонът никога да не се ползва повече от 50 пъти. Без ключалка: с цикъл compare-and-set. Отпечатай колко пъти е ползван, колко отказа е имало и колко остават:

Изход

Използвани: 50
Отказани: 30
Остават: 0

Още задачи

• Максимумът. Пази най-голямата поръчка на деня, докато много нишки добавят поръчки. Подсказка: CAS цикъл, който записва само ако новата е по-голяма.
• Две промоции. Направи ценоразписа с версия и пусни двама администратори, които публикуват едновременно. Как да не се загуби промоцията на единия? (Подсказка: смени референцията с CAS само ако версията е още тази, която си прочел.)
• Ревизорът без ключалка. Сложи наличността и резервираните в един неизменим обект и смени го с CAS. Провери, че ревизорът пак вижда винаги 10 000.

Тест

Провери се

1. Наличността е 6. Нишка вика CAS „ако е 5, направи го 4“. Какво става?

Нищо не се записва, а отговорът е „не успя“: нишката трябва да прочете пакНишката заспива, докато стойността стане 5Записва се 4

2. В tryBuy има „ако наличността е > 0“ и после „намали с 1“. И двата реда са атомарни. Защо пак се продава повече, отколкото има?

Защото атомарните операции понякога губят увеличенияНе може: щом всеки ред е атомарен, целият метод е безопасенМежду проверката и намаляването друга нишка може да вземе последната бройка: всяка стъпка е неделима, но двете заедно не са

3. Касите четат ценоразписа хиляди пъти в секунда, а той се сменя веднъж на ден. Какъв е най-добрият начин да го делят?

Един общ речник, в който администраторът сменя цените една по еднаНеизменим обект: администраторът прави нов ценоразпис и сменя една референция; всяка каса чете целия стар или целия новКлючалка около всяко четене на цена

4. Резервираш бройка: наличността пада с 1, а резервираните растат с 1. Ревизорът проверява, че сборът е винаги 10 000. Какво трябва?

Две атомарни променливиКлючалка около двете промени и около проверкатаНищо: сборът се смята след края

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Async, await и нишки · Защо нишки · Race condition · Заключване
• Продължава в: Deadlock · Производител и потребител · Как се тества конкурентен код
• Задачи по темата: Нишки и race conditions