Заключване

Код на:JavaC#PythonJavaScript

Накратко: Ключалката (lock, mutex) пуска само един Worker наведнъж в критичната секция; в JavaScript се прави с Atomics върху SharedArrayBuffer.

Проблем

Как да спреш другата каса

В урока „Race condition“ разпродажбата губеше продажби: две нишки правеха „прочети, извади, запиши“ наведнъж и едната презаписваше другата. Трите стъпки трябва да са едно цяло: докато една нишка е вътре, другата да чака отвън.

Точно това прави ключалката.

Идеята

Ключалката

Ключалката (mutex, от „mutual exclusion“, взаимно изключване) е обект с един собственик. Нишката я взима, прави своето и я пуска. Друга нишка, която я поиска междувременно, чака. Кодът между взимането и пускането е критичната секция: в нея е най-много една нишка.

JavaScript няма готова ключалка между Worker-и, затова я правиш от Atomics върху SharedArrayBuffer. shop[0] е ключалката: 0 е свободна, 1 е заета. Atomics.compareExchange прави „ако е 0, сложи 1“ като една неделима стъпка, затова само един Worker я взима. Другите спят в Atomics.wait, докато unlock не ги събуди:

// state[0]: 0 е свободно, 1 е заето.
function lock(state) {
  while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {
    Atomics.wait(state, 0, 1);  // спи, докато е заето
  }
}

function unlock(state) {
  Atomics.store(state, 0, 0);
  Atomics.notify(state, 0, 1);  // събуди една от чакащите
}

// shop[0] е ключалката, shop[1] е наличността.
function sell(shop) {
  lock(shop);
  shop[1]--;
  unlock(shop);
}

Двата Worker-а от миналия урок, по 100 000 продажби:

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(`Поръчки: ${2 * 100_000}`);
  console.log("Продадени според склада:");
  console.log(200_000 - shop[1]);
} else {
  for (let i = 0; i < 100_000; i++) {
    sell(workerData);
  }
}

Изход

Поръчки: 200000
Продадени според склада:
200000

Точно, при всяко пускане. Ключалката е едно число в общата памет: двете каси заключват една и съща.

Виж го

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

Проверката „има ли“ и вземането са в една и съща критична секция. Ако някой е вътре и проверява, другият не може да провери, преди първият да е взел:

// state[0]: 0 е свободно, 1 е заето.
function lock(state) {
  while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {
    Atomics.wait(state, 0, 1);  // спи, докато е заето
  }
}

function unlock(state) {
  Atomics.store(state, 0, 0);
  Atomics.notify(state, 0, 1);  // събуди една от чакащите
}

// shop[0] е ключалката, shop[1] е наличността.
function reserve(shop) {
  lock(shop);
  try {
    if (shop[1] === 0) {
      return false;   // няма: отказ
    }
    shop[1]--;        // има: взимам бройката
    return true;
  } finally {
    unlock(shop);
  }
}

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

1. Остават 3 бройки, а 4 купувачи викат reserve() в един и същ момент.
2. През lock(shop) минава само един, другите трима чакат пред него. Влиза купувач 1: вижда 3 и взима една. Остават 2.
3. Купувач 1 излиза и пуска ключалката. Влиза купувач 2: вижда 2 и взима една. Остават 1.
4. Купувач 2 излиза и пуска ключалката. Влиза купувач 3: вижда 1 и взима една. Остават 0.
5. Купувач 4 влиза последен и вижда 0: отказ. Никой не видя число, което друг тъкмо сменя.
6. 3 продадени, 1 отказ, наличност 0: вярно. Цената: купувачите се чакаха един друг пред турникета.

Четирима купувачи, три бройки, всички наведнъж:

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(`Продадени: ${results.filter((ok) => ok).length}`);
  console.log(`Отказани: ${results.filter((ok) => !ok).length}`);
  console.log(`Наличност: ${shop[1]}`);
} else {
  parentPort.postMessage(reserve(workerData));
}

Изход

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

А ето двамата купувачи от миналия урок, които купуваха последната бройка. Таксуването на картата (~100 ms) е след ключалката: бройката е запазена, а картата се таксува, без другият да чака:

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("Наличност преди: 1");
  console.log(`Продадени: ${sold}`);
  console.log(`Отказани: ${2 - sold}`);
  console.log(`Наличност: ${shop[1]}`);
} else {
  const ok = reserve(workerData);
  if (ok) {
    Atomics.wait(new Int32Array(new SharedArrayBuffer(4)), 0, 0, 100);   // таксуването на картата, ~100 ms
  }
  parentPort.postMessage(ok);
}

Изход

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

Един продаден, един отказан, наличност 0. При всяко пускане.

Пробвай

Не забравяй да пуснеш

lock и unlock викаш сам, затова пускането е във finally. Иначе изключение в критичната секция оставя ключалката заета завинаги:

// state[0]: 0 е свободно, 1 е заето.
function lock(state) {
  while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {
    Atomics.wait(state, 0, 1);  // спи, докато е заето
  }
}

function unlock(state) {
  Atomics.store(state, 0, 0);
  Atomics.notify(state, 0, 1);  // събуди една от чакащите
}

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

Какво пуска ключалката?

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

Провери

Пробвай

Ключалката, която не заключва

Колегата е добавил ключалка, но касите пак губят продажби. Кой ред е грешен?

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

1// state[0]: 0 е свободно, 1 е заето.2function lock(state) {3 while (Atomics.compareExchange(state, 0, 0, 1) !== 0) {4 Atomics.wait(state, 0, 1); // спи, докато е заето5 }6}78function unlock(state) {9 Atomics.store(state, 0, 0);10 Atomics.notify(state, 0, 1); // събуди една от чакащите11}1213// shop[1] е наличността.14function sell(shop) {15 const state = new Int32Array(new SharedArrayBuffer(4));16 lock(state);17 shop[1]--;18 unlock(state);19}

Провери

Идеята

Колко струва ключалката

Ключалката работи, като кара нишките да се чакат. Колкото повече стои вътре една нишка, толкова повече чакат другите. Това е борбата за ключалката (contention).

Магазин с 10 бройки и четири поръчки наведнъж. Всяка поръчка вади бройка и праща имейл (~200 ms), а Network от урока „Защо нишки“ брои кръговете чакане:

// Пита услуга по мрежата: отговорът идва след ~200 ms.
function call(net, service, answer) {
  if (Atomics.add(net, 0, 1) === 0) Atomics.add(net, 1, 1);   // никой не чака: нов кръг
  Atomics.wait(new Int32Array(new SharedArrayBuffer(4)), 0, 0, 200);
  Atomics.sub(net, 0, 1);
  return `${service}: ${answer}`;
}

// shop[0] е ключалката, shop[1] е наличността.

// Лошо: имейлът тръгва, докато ключалката е взета.
function orderSlow(shop, net, customer) {
  lock(shop);
  try {
    shop[1]--;
    call(net, "имейл", customer);
  } finally {
    unlock(shop);
  }
}

// Добре: под ключалката е само наличността.
function order(shop, net, customer) {
  lock(shop);
  try {
    shop[1]--;
  } finally {
    unlock(shop);
  }
  call(net, "имейл", customer);
}

С orderSlow имейлът е под ключалката:

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: `клиент ${c}` },
  }));
  await Promise.all(orders.map((order) => once(order, "exit")));
  console.log(`Поръчки: 4, наличност: ${shop[1]}`);
  console.log(`Кръгове чакане: ${net[1]}`);
} else {
  orderSlow(workerData.shop, workerData.net, workerData.customer);
}

Изход

Поръчки: 4, наличност: 6
Кръгове чакане: 4

Четири кръга: имейлите тръгват един по един, а последният клиент чака около 800 ms. С order под ключалката е само наличността:

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: `клиент ${c}` },
  }));
  await Promise.all(orders.map((order) => once(order, "exit")));
  console.log(`Поръчки: 4, наличност: ${shop[1]}`);
  console.log(`Кръгове чакане: ${net[1]}`);
} else {
  order(workerData.shop, workerData.net, workerData.customer);
}

Изход

Поръчки: 4, наличност: 6
Кръгове чакане: 1

Същата наличност, един кръг. Правилата:

• Под ключалката само общите данни. Пресмятай, форматирай и чакай отвън. Вътре само прочети и запиши.
• Никога чакане под ключалка: мрежа, диск, база данни, sleep. Вземи каквото трябва, пусни ключалката и тогава чакай.
• Една ключалка за едни данни. Наличността и оборотът са отделни: всяко със своя ключалка, за да не се чакат касите, които пипат само едното.

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

• Тази ключалка е най-простата: не е честна (събуденият Worker може да изпусне реда си) и не е повторно влизаща. В истински код ползваш готова библиотека.
• Atomics.wait не може да се вика в главната нишка на браузъра: тя не бива да спи. В Node може.
• В една нишка с async ключалка трябва само около await. Това е урокът „async не е нишка“.

Ключалката не е единственият начин. За един брояч има атомарни операции, които изобщо не карат нишките да се чакат, а данни, които никой не променя, не искат ключалка: урокът „Атомарни операции и неизменими обекти“. А две ключалки, които две нишки взимат в различен ред, могат да спрат програмата завинаги: урокът „Deadlock“.

Упражнение

Оборотът и поръчката от много бройки

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

Оборотът. Поправи задачата от миналия урок: две каси по 500 000 продажби по 3 €, а revenue[1] += 3 е между lock(revenue) и unlock(revenue), а ключалката е revenue[0]. Пусни програмата няколко пъти: оборотът трябва да е един и същ всеки път.

Очакваш

Каса 1: 50000 продажби
Каса 2: 50000 продажби
Оборот (€):
300000

Поръчка от няколко бройки. В склада има 5 бройки. Напиши reserve(shop, count): ако има поне count, взима ги и връща истина, иначе не взима нищо и връща лъжа. Трима клиенти искат по 2 бройки наведнъж, всеки в своя Worker.

Очакваш

Поръчани: 3
Приети: 2
Отказани: 1
Наличност: 1

Още задачи

• Цената на ключалката. Пусни двете каси по 1 000 000 продажби с ключалка и без нея и засечи времето. Колко по-бавно е с ключалка? А с 8 каси?
• Две ключалки. Добави оборот към склада, със своя ключалка. Продажбата вади от наличността и добавя към оборота. Пази ли двете заедно, ако някой прочете наличност и оборот между двете ключалки? - tryLock. Напиши tryLock(state), който с един compareExchange взима ключалката, ако е свободна, и връща false, без да спи, ако е заета.

Тест

Провери се

1. Два Worker-а викат sell(shop), който прави shop[1]-- между lock(shop) и unlock(shop). Какво прави вторият, когато ключалката е заета?

Влиза веднага, защото кодът е същиятХвърля изключениеСпи в Atomics.wait, докато първият извика unlock

2. Проверката „има ли бройки“ е под ключалката, а изваждането е в отделен блок под същата ключалка. Двама купуват последната бройка. Какво става?

Може пак да продадат две: между двата блока ключалката е свободнаВторият винаги чака първия да платиВярно е: и двата блока са заключени

3. Под ключалката е изваждането от наличността и изпращането на имейл (~200 ms). Четири поръчки идват наведнъж. Колко чака последната?

Около 800 ms: имейлите се пращат един по единПочти нищо: ключалката е бързаОколо 200 ms: имейлите вървят наведнъж

4. Какво става, ако shop[1]-- хвърли изключение между lock(shop) и unlock(shop) без try/finally?

Ключалката остава заета завинаги и другите Worker-и спят вечноКлючалката се пуска самаНищо: изключението спира само този Worker

Провери

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

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

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