Към съдържанието
wannacode

Race condition

Накратко: Race condition е бъг, при който резултатът зависи от реда на изпълнение: две Worker нишки губят продажба, а await между проверката и покупката пуска двама купувачи дори в една нишка.

Проблем

Разпродажбата брои криво

Петък, разпродажба. Слушалките са на половин цена и поръчките валят. Две каси продават от един склад: всяка продажба вади 1 от наличността.

Касите са два Worker-а (урокът „Async, await и нишки“). Наличността е в SharedArrayBuffer, обща памет, която двата виждат. Всеки продава по 1 000 000 бройки:
// stock е Int32Array в SharedArrayBuffer:
// обща памет за Worker-ите.
function sell(stock) {
  stock[0]--;   // прочети, извади 1, запиши
}
if (isMainThread) {
  const stock = new Int32Array(new SharedArrayBuffer(4));
  stock[0] = 2_000_000;
  const checkouts = [1, 2].map(
    () => new Worker(new URL(import.meta.url), { workerData: stock }),
  );
  await Promise.all(checkouts.map((worker) => once(worker, "exit")));
  console.log(`Поръчки: ${2 * 1_000_000}`);
  console.log("Продадени според склада:");
  console.log(2_000_000 - stock[0]);
} else {
  for (let i = 0; i < 1_000_000; i++) {
    sell(workerData);
  }
}

Клиентите са платили 2 000 000 поръчки. Ето колко продадени брои складът в пет пускания:

Изход от пет пускания (третият ред)
Продадени според склада: 2000000
Продадени според склада: 1003506
Продадени според склада: 994022
Продадени според склада: 1004855
Продадени според склада: 1018607
Обикновено складът брои около половината. В едно от петте пускания брои вярно: тогава единият Worker е свършил, преди другият да тръгне. Бройките, които ги няма, складът ги „има“: утре магазинът ще ги продаде на някого и после ще му върне парите.

Идеята

stock[0]-- е три стъпки

В кода stock[0]-- е един ред. Процесорът го прави на три стъпки, както ако го разпишеш:

// stock е Int32Array в SharedArrayBuffer:
// обща памет за Worker-ите.
function sell(stock) {
  const seen = stock[0];     // 1. прочети
  const after = seen - 1;    // 2. извади 1
  stock[0] = after;          // 3. запиши
}
Стъпка по стъпка, с думи
  1. Остават 5 бройки. Worker A и Worker B продават по една в един и същ момент.
  2. Worker A прочита наличността: 5.
  3. Worker B прочита, преди A да е записала: също 5.
  4. Worker A изважда 1 в своята променлива: 4.
  5. Worker B прави същото от своето 5: също 4.
  6. Worker A записва 4. Една продажба, остават 4: дотук е вярно.
  7. Worker B също записва 4, върху 4 на A. Две продажби, а наличността е 4, не 3.
  8. Една продажба е изгубена: двете прочетоха едно и също число, преди някоя да запише. Това е race condition, а складът показва бройка, която вече е продадена.
  1. Прочети наличността в своя променлива.
  2. Извади 1 от своето копие.
  3. Запиши копието обратно.

Две нишки могат да се редуват между всеки две стъпки. Ако и двете прочетат 5, преди някоя да запише, и двете записват 4. Две продажби, а наличността намалява с една.

Когато резултатът зависи от това коя нишка коя стъпка прави първа, това е race condition (състезание). Трите стъпки „прочети, промени, запиши“ върху общи данни са най-честата форма.

По-точно, за любопитните
stock[0]-- върху Int32Array прочита от общата памет, изважда в регистър и записва. Между тях другият Worker, който върви на друго ядро, може да прочете същото число. В обикновен JavaScript обект това не може да стане: обектите не се делят между Worker-ите, а се копират.

Пробвай

Три каси, наличност 5

Ето три каси, разменени на ръка, в един от възможните редове. Всяка прочита в своя променлива, после записва с 1 по-малко:

let left = 5;
const seenA = left;    // A прочита
const seenB = left;    // B прочита
left = seenA - 1;      // A записва
const seenC = left;    // C прочита
left = seenB - 1;      // B записва
left = seenC - 1;      // C записва
console.log("Продажби: 3");
console.log(`Наличност: ${left}`);
Отговор

Идеята

„При мен работи“

Същата програма, но с по-малко продажби на каса:

if (isMainThread) {
  const stock = new Int32Array(new SharedArrayBuffer(4));
  stock[0] = 2_000;
  const checkouts = [1, 2].map(
    () => new Worker(new URL(import.meta.url), { workerData: stock }),
  );
  await Promise.all(checkouts.map((worker) => once(worker, "exit")));
  console.log(`Поръчки: ${2 * 1_000}`);
  console.log("Продадени според склада:");
  console.log(2_000 - stock[0]);
} else {
  for (let i = 0; i < 1_000; i++) {
    sell(workerData);
  }
}
Изход от пет пускания (третият ред)
Продадени според склада: 2000
Продадени според склада: 2000
Продадени според склада: 1929
Продадени според склада: 2000
Продадени според склада: 2000
Четири пъти вярно и веднъж загуба. Worker-ът тръгва бавно, затова обикновено единият свършва 1000-те си продажби, преди другият да е започнал. Обикновено.

Затова race condition е коварен:

  • тестът минава на лаптопа и пада на сървъра с 64 ядра и хиляди клиенти;
  • грешката идва „понякога“ и не се повтаря, когато я търсиш;
  • добавиш ли ред за отпечатване, редът на нишките се сменя и грешката изчезва.

Липсата на загуба в тест не доказва нищо. Безопасността се доказва с това как е написан кодът: кои данни са общи и кой ги пази.

Проблем

Последната бройка

Една бройка е останала. Двама купувачи натискат „Купи“ в един и същ момент. buy проверява дали има, таксува картата (около 100 ms) и чак тогава взима бройката:

class Stock {
  constructor(left) {
    this.left = left;
  }


  async buy() {
    if (this.left > 0) {   // проверка: има ли?
      await sleep(100);    // картата се таксува ~100 ms
      this.left--;         // действие: взимам бройката
      return true;
    }
    return false;
  }
}
const stock = new Stock(1);
const bought = await Promise.all([stock.buy(), stock.buy()]);
console.log("Наличност преди: 1");
console.log("Продадени:");
console.log(bought.filter((ok) => ok).length);
console.log("Наличност след:");
console.log(stock.left);
Изход
Наличност преди: 1
Продадени:
2
Наличност след:
-1

Тук нишката е една, а грешката е същата. await sleep(100) пуска другото извикване, докато първото чака банката. То стига до проверката, когато left още е 1. В една нишка редът е един и същ всеки път, затова и грешката е всеки път. Повече за това е в урока „async не е нишка“.

Това е втората форма на race condition: проверка, после действие (check-then-act). Решението се взима по стойност, която друг може да смени, преди решението да се изпълни. Тя е навсякъде: „има ли свободна стая“, „свободно ли е потребителското име“, „има ли пари в сметката“.

Пробвай

Номерата на поръчките

Всяка поръчка получава номер: 1001, 1002, 1003… Касите са нишки и викат take(next) едновременно. Понякога две поръчки получават един и същ номер. След кой ред другата нишка трябва да влезе, за да стане това?

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

Идеята

Кога може да има race condition

Трябват три неща наведнъж:

  1. Общи данни: нещо, което виждат няколко нишки (наличността, броячът, номерът).
  2. Поне една нишка ги променя. Ако всички само четат, няма какво да се обърка.
  3. Нищо не подрежда достъпа: нишките влизат в стъпките си когато им дойде редът.

Махни едно от трите и race condition няма:

  • Не дели. Всяка нишка брои в своя променлива, а накрая резултатите се събират. Така ставаше с 1000-те фактури в „Защо нишки“: всяка част смята своето.
  • Не променяй. Обект, който никой не променя, може да се чете от колкото искаш нишки. Това е урокът „Атомарни операции и неизменими обекти“.
  • Подреди достъпа. Само една нишка наведнъж в трите стъпки. Това е ключалката, следващият урок: „Заключване“.
По-точно, за любопитните

Има и по-тиха беда: видимостта. В SharedArrayBuffer обикновеното четене може да не види запис от друг Worker навреме. Atomics.load и Atomics.store го гарантират. Ключалката решава и това: каквото една нишка е записала, преди да я пусне, следващата го вижда, след като я вземе.

Как е в другите езици: в Java и C# count++ губи както тук. В Python губи по-рядко заради GIL, но губи. В JavaScript губи между Worker-и върху SharedArrayBuffer, а в една нишка race condition има само между два await.

Упражнение

Оборотът на разпродажбата

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

Оборотът. Две каси продават по 500 000 слушалки по 3 €. Всяка каса брои своите продажби в своя променлива, а оборотът е общ: Int32Array в SharedArrayBuffer, в който всеки Worker прави revenue[0] += 3. Отпечатай продажбите на всяка каса и оборота. Пусни програмата няколко пъти.

Очакваш
Каса 1: 500000 продажби
Каса 2: 500000 продажби
Оборот (€):
3000000

Продажбите на касите са верни при всяко пускане: всяка брои в своята променлива. Оборотът е по-малък и различен всеки път. Поправката е в следващия урок.

Още задачи

  • Колко се губи. Пусни продажбата с 2, 4 и 8 каси. Губи ли се повече с повече каси?
  • Намери общото. Вземи програма с нишки, която си писал, и изброй данните, които повече от една нишка пипа. Кои от тях някоя нишка променя? - Свободна стая. Напиши async метод „резервирай стая 12, ако е свободна“ с await sleep(100) между проверката и записа и пусни двама гости с Promise.all. Колко гости получават стаята?

Тест

Провери се

1. Два Worker-а викат по веднъж stock[0]-- върху SharedArrayBuffer, където е 5. Какво може да е накрая?
2. Тестът с две нишки по 1000 продажби минава 100 пъти от 100. Какво значи това?
3. Async функция проверява this.left > 0, после await sleep(100), после this.left--. Два извиквания с Promise.all, в склада 1. Какво става?
4. Кое от тези НЕ може да има race condition?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·