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

Deadlock

Накратко: Deadlock е състояние, в което две нишки държат по една ключалка и всяка чака другата завинаги; общ ред на заключване го прави невъзможен.

Проблем

Нощта, в която складовете спряха

Магазинът има два склада: София и Пловдив. Когато в единия свършат слушалки, система мести стока от другия. Всеки превод заключва двата склада, за да не се загубят бройки, както в урока за ключалките.

Една нощ в 3:12 два превода тръгват наведнъж: 5 бройки от София към Пловдив и 3 от Пловдив към София. Програмата спира. Процесорът е на 0%, грешка в лога няма, а нишките стоят и чакат. До сутринта нито един превод не минава, а поръчките в двата склада се трупат.

Идеята

Всеки държи едно и чака друго

Преводът заключва първо склада, откъдето мести, после склада, където мести:

  • превод 1 (София → Пловдив) взима ключа на София;
  • превод 2 (Пловдив → София) в същия момент взима ключа на Пловдив;
  • превод 1 иска ключа на Пловдив: държи го превод 2, затова чака;
  • превод 2 иска ключа на София: държи го превод 1, затова чака.

Всеки чака другия да пусне, а никой не пуска, докато не получи своето. Чакането прави кръг. Това е deadlock (мъртва хватка): нишките не грешат и не падат, а просто спират завинаги.

Най-лошото е, че става рядко. Двата превода трябва да вземат първата си ключалка почти в един и същ момент. Затова минава хиляди пъти на теста и спира в 3:12 през нощта.

Виж го

Кръгът

function transfer(cells, source, target, qty) {
  // общ ред: първо по-малкото id
  const first = Math.min(source, target);
  const second = Math.max(source, target);
  lock(cells, first);
  try {
    lock(cells, second);
    try {
      cells[STOCK + source] -= qty;
      cells[STOCK + target] += qty;
    } finally {
      unlock(cells, second);
    }
  } finally {
    unlock(cells, first);
  }
}
Стъпка по стъпка, с думи
  1. Два превода наведнъж, в два Worker-а. T1 мести 5 бройки от София в Пловдив, T2 мести 3 обратно. Всеки заключва първо склада, от който взима.
  2. T1 взима ключа на София.
  3. В същия момент T2 взима ключа на Пловдив.
  4. Бариерата ги пуска нататък чак когато и двата държат първия си ключ. Тя е тук, за да се случва лошият момент при всяко пускане.
  5. T1 чака ключа на Пловдив, който държи T2. T2 чака ключа на София, който държи T1. Кръг: никой не пуска.
  6. След 200 ms и двата се отказват: deadlock. Без таймаута щяха да чакат вечно и програмата щеше да увисне. Наличност: 500 и 300.
  7. Поправката: един ред за всички. Първо ключът на склада с по-малкото id: София (1), после Пловдив (2), в каквато и посока да е преводът.
  8. И двата започват от София. T1 взима ключа, T2 чака, но не държи нищо.
  9. T1 взима и Пловдив, мести 5 бройки и пуска двата ключа.
  10. Сега T2 взима София, после Пловдив, и мести 3 обратно.
  11. И двата превода минаха: 498 и 302. С един ред никой не държи ключ, докато чака ключ на някого, който чака него: кръг няма.

За да видиш лошия момент при всяко пускане, програмата го прави нарочно. Бариерата meet спира всеки превод, докато и двата не стигнат до нея: така и двата вече държат първия си ключ, когато искат втория. Втората бариера ги държи, докато и двата са опитали. Без нея единият можеше да получи ключа, пуснат от другия, и изходът щеше да зависи от времето.

Втората ключалка се чака с таймаут: най-много 200 ms. Ако не дойде, преводът се отказва и пуска своята.

Ключалки в JavaScript няма, затова тук те са клетки в SharedArrayBuffer, както в предишния урок: 0 е свободна, 1 е заета. tryLock чака с Atomics.wait(…, оставащите ms) и се отказва, когато времето изтече. meet е бариерата: всеки Worker добавя 1 и спи, докато не станат 2.
// cells: [ключалки, наличности, бариери, резултати] в SharedArrayBuffer
const LOCK = 0, STOCK = 2, MEET_1 = 4, MEET_2 = 5, RESULT = 6;
const SOFIA = 0, PLOVDIV = 1;


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


function tryLock(cells, i, ms) {
  const deadline = Date.now() + ms;
  while (Atomics.compareExchange(cells, LOCK + i, 0, 1) !== 0) {
    const left = deadline - Date.now();
    if (left <= 0) return false;
    Atomics.wait(cells, LOCK + i, 1, left);
  }
  return true;
}


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


function meet(cells, slot) {
  Atomics.add(cells, slot, 1);
  Atomics.notify(cells, slot);
  let n;
  while ((n = Atomics.load(cells, slot)) < 2) Atomics.wait(cells, slot, n);
}
function transfer(cells, source, target, qty) {
  lock(cells, source);
  try {
    meet(cells, MEET_1); // всеки държи по една
    const got = tryLock(cells, target, 200);
    meet(cells, MEET_2); // двата опитаха (за примера)
    if (!got) return false; // чакал е твърде дълго
    try {
      cells[STOCK + source] -= qty;
      cells[STOCK + target] += qty;
      return true;
    } finally {
      unlock(cells, target);
    }
  } finally {
    unlock(cells, source);
  }
}
if (isMainThread) {
  const cells = new Int32Array(new SharedArrayBuffer(8 * 4));
  cells[STOCK + SOFIA] = 500;
  cells[STOCK + PLOVDIV] = 300;
  const jobs = [[SOFIA, PLOVDIV, 5], [PLOVDIV, SOFIA, 3]];
  const workers = jobs.map(
    (job, k) => new Worker(new URL(import.meta.url), { workerData: { cells, job, k } }),
  );
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  const done = [cells[RESULT], cells[RESULT + 1]];
  console.log(!done[0] && !done[1] ? "deadlock: всеки превод чака другия" : "и двата превода минаха");
  console.log(`София: ${cells[STOCK + SOFIA]}, Пловдив: ${cells[STOCK + PLOVDIV]}`);
} else {
  const { cells, job, k } = workerData;
  cells[RESULT + k] = transfer(cells, ...job) ? 1 : 0;
}
Изход
deadlock: всеки превод чака другия
София: 500, Пловдив: 300

Без таймаута програмата щеше да увисне и никога да не отпечата нищо. Таймаутът не оправя deadlock-а, а го хваща: преводът знае, че не е минал, и може да опита пак или да вдигне тревога.

Идеята

Един ред за всички

Кръгът се затваря, защото двата превода заключват в различен ред: единият София, после Пловдив, другият обратно. Поправката е всички да заключват в един и същ ред, независимо накъде мести преводът. Например по номера на склада: първо по-малкото id.

Тогава и двата превода започват от София. Който вземе ключа ѝ, продължава към Пловдив. Другият чака още на първия ключ и не държи нищо, затова никого не спира. Кръг не може да се затвори: всеки чака само ключ с по-голямо id от тези, които вече държи.

function transfer(cells, source, target, qty) {
  // общ ред: първо по-малкото id
  const first = Math.min(source, target);
  const second = Math.max(source, target);
  lock(cells, first);
  try {
    lock(cells, second);
    try {
      cells[STOCK + source] -= qty;
      cells[STOCK + target] += qty;
    } finally {
      unlock(cells, second);
    }
  } finally {
    unlock(cells, first);
  }
}

Хиляда превода по 2 бройки в едната посока и хиляда по 1 в другата, едновременно:

if (isMainThread) {
  const cells = new Int32Array(new SharedArrayBuffer(8 * 4));
  cells[STOCK + SOFIA] = 5000;
  cells[STOCK + PLOVDIV] = 3000;
  const jobs = [[SOFIA, PLOVDIV, 2], [PLOVDIV, SOFIA, 1]];
  const workers = jobs.map(
    (job) => new Worker(new URL(import.meta.url), { workerData: { cells, job } }),
  );
  await Promise.all(workers.map((worker) => once(worker, "exit")));
  const [sofia, plovdiv] = [cells[STOCK + SOFIA], cells[STOCK + PLOVDIV]];
  console.log(`София: ${sofia}, Пловдив: ${plovdiv}`);
  console.log(`Общо: ${sofia + plovdiv}`);
} else {
  const { cells, job } = workerData;
  for (let i = 0; i < 1000; i++) transfer(cells, ...job);
}
Изход
София: 4000, Пловдив: 4000
Общо: 8000
Тук складът е само номер (0 или 1), затова редът е Math.min и Math.max.

Наличностите са точни при всяко пускане, а сборът е 8000, колкото в началото. Ключалките пазят бройките, а редът пази програмата да не спре.

Пробвай

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

Три склада: София (1), Пловдив (2), Варна (3). Функцията само печата в какъв ред би заключила. Какво ще отпечата?

const NAMES = ["София", "Пловдив", "Варна"];
const SOFIA = 0, PLOVDIV = 1, VARNA = 2;


function transfer(source, target) {
  const first = Math.min(source, target);
  const second = Math.max(source, target);
  console.log(`${NAMES[first]}, после ${NAMES[second]}`);
}


transfer(PLOVDIV, SOFIA);
transfer(SOFIA, VARNA);
transfer(VARNA, PLOVDIV);
Отговор

Пробвай

Попълни

first е по-малкият номер. Как се взима по-големият?
const first = Math.min(source, target);
const second = Math.(source, target);

Пробвай

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

Преводите вече заключват по id и седмици наред няма проблем. После някой добавя нощна ревизия, която сумира двата склада. От тогава програмата пак спира понякога. На кой ред е грешката?

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

Виж го

Когато редът не е възможен: опитай и отстъпи

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

function transfer(cells, source, target, qty) {
  while (true) {
    lock(cells, source);
    try {
      if (tryLock(cells, target, 0)) {
        try {
          cells[STOCK + source] -= qty;
          cells[STOCK + target] += qty;
          return;
        } finally {
          unlock(cells, target);
        }
      }
    } finally {
      unlock(cells, source);
    }
    // пусни всичко и опитай пак след малко
    Atomics.wait(cells, MEET_1, 0, Math.random() * 2);
  }
}

Със същите два превода (по 300 във всяка посока) резултатът пак е точен:

Изход
София: 4700, Пловдив: 3300
Общо: 8000

Чакането е случайно, и това е важно. Ако двата превода отстъпват за едно и също време, могат да се блъскат отново и отново в един ритъм: и двата работят, а никой не напредва. Това се казва livelock. Случайното чакане разваля ритъма. Atomics.wait върху клетка, която никой не буди, тук е просто пауза в Worker-а.

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

Четирите условия на Coffman. Deadlock става само ако са изпълнени четири неща наведнъж:

  1. взаимно изключване: ключалката може да е само у един;
  2. държи и чака: нишката държи една ключалка, докато чака друга;
  3. без отнемане: никой не може да вземе ключалката насила;
  4. кръгово чакане: чакането прави кръг.

Махни едно и deadlock не може да стане. Общият ред маха кръга (4). Отстъпването маха „държи и чака“ (2). Атомарните операции и неизменимите обекти от предишния урок често махат самата ключалка (1).

Базите данни се справят по трети начин. Те търсят кръга сами и убиват едната транзакция с грешка „deadlock detected“. Затова кодът, който работи с база, трябва да е готов да повтори транзакцията.

Как е в другите езици: ReentrantLock.tryLock(време) в Java (synchronized няма таймаут); Monitor.TryEnter(обект, време) в C# (lock няма таймаут); Lock.acquire(timeout=…) в Python; в JavaScript ключалки има само между Worker-и, написани с Atomics.wait с таймаут. В async код в една нишка ключалки няма, но кръг пак е възможен: две функции, които await-ват обещанието една на друга, чакат вечно, а програмата просто свършва, без да отпечата нищо.

Упражнение

Три портфейла в кръг

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

Три портфейла с по 1000 € и три нишки. Първата мести по 5 € от портфейл 1 в портфейл 2, втората от 2 в 3, третата от 3 в 1, всяка по 1000 пъти. Това е кръг: без общ ред програмата заседва рано или късно. Напиши transfer така, че да не може да заседне, и отпечатай портфейлите и сбора:

Изход
Портфейл 1: 1000 €
Портфейл 2: 1000 €
Портфейл 3: 1000 €
Общо: 3000 €

Още задачи

  • Хвани го. Махни реда и сложи таймаут на втората ключалка. Брой колко превода са се отказали и ги опитай пак, докато минат всички.
  • Ревизията. Добави нишка, която 1000 пъти сумира трите портфейла под ключалките им. Сборът трябва да е винаги 3000 €. В какъв ред заключва тя?
  • Без id. Ако обектите нямат номер, по какво друго може да се подредят? (Подсказка: номерът на клетката в масива, и какво става, ако два обекта имат еднакъв.)

Тест

Провери се

1. Кога две нишки заседват в deadlock?
2. Всички преводи заключват складовете по id, от по-малкото към по-голямото. Могат ли три превода София → Пловдив, Пловдив → Варна и Варна → София да заседнат?
3. Защо програмата с deadlock в урока не увисва?
4. Два превода се отказват при неуспех, чакат 1 ms и опитват пак. И двата пак се блъскат, отново и отново. Как се казва това и как се оправя?

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