Задача про філософів у їдальні: Заїдання, Голодування та Як Це Уникнути

Уважно мінімальна затримка (Deadlock)

Edsger Dijkstra сформулював проблему п’яти філософів у 1965 році (спочатку це було про стрічкові накопичувачі; обставини з філософами, які сидять навколо столу, стали популярними пізніше, завдяки Тоні Хоуру), щоб ілюструвати затримку (deadlock) та голодування з найпростішою конфігурацією: п’ять філософів сидять навколо круглого столу, між кожною парою сусідніх філософів лежить один вил, і кожному філософу потрібно тримати обидва сусідні вили для їжі. Кожен філософ чергує між думками та їжею, а вил може утримувати лише один філософ одночасно – це ресурс з взаємним виключенням, подібно до замка, рядка бази даних або буфера спільного пам’яті в реальній паралельній системі.

Наївне застрявання

Звісно, реалізація передбачає, що кожен філософ піднімає свою ліву виделку, потім праву, їсть і кладе обидві назад. Якщо всі філософи одночасно беруть ліву виделку, то всі п'ять виделок утримуються, і кожен філософ чекає назавжди на праву виделку, яка ніколи не буде віддана – застрявання (deadlock). Це класичне зображення чотирьох умов Коффмана, які повинні виконуватися одночасно для виникнення застрягання: взаємний доступ (виделка служить лише одному філософу), утримання та очікування (утримуючи ліву виделку, чекають на праву), відсутність примусового захоплення (ніхто не може змусити виделку відійти від філософа) і циклічне очікування (кожен філософ чекає на свого сусіда справа, утворюючи цикл).

// наївне: застрягає, якщо кожен філософ одночасно бере ліву pickUp(leftFork); pickUp(rightFork); // блокується назавжди, якщо тримач правої виделки // чекає на свою власну праву виделку (цикл) eat(); putDown(leftFork); putDown(rightFork); Порушення однієї з чотирьох умов запобігає застряганню, і кожен класичний розв’язок порушує іншу.

// naive: deadlocks if every philosopher grabs left simultaneously
pickUp(leftFork);
pickUp(rightFork);   // blocks forever if right fork's holder is
                      // itself waiting on ITS right fork (a cycle)
eat();
putDown(leftFork);
putDown(rightFork);

Впорядкування ресурсів руйнує цикл

Найпростішим рішенням є безпосереднє розривання циклічної очікувальної ситуації: присвоїти виделки номерами від 0 до 4 і вимагати, щоб кожен філософ першим підіймав виделку з нижчим номером незалежно від того, на якій стороні він знаходиться. Таким чином, філософ між виделами 4 і 0 бере виделку 0 першою, а не виделку 4 – це єдина асиметрія, необхідна для запобігання циклічному очікуванню. Цей метод використовується в реальних двигунах баз даних та менеджерах блоків: завжди отримувати блоки у фіксованому глобальному порядку, і цикличної очікувальної ситуації не може виникнути незалежно від кількості конкуруючих потоків.

// resource (fork) ordering — breaks circular wait
const [first, second] = leftFork.id < rightFork.id
  ? [leftFork, rightFork] : [rightFork, leftFork];
pickUp(first);
pickUp(second);
eat();
putDown(second);
putDown(first);

Арбітр і обмеження паралелізму

Друге класичне рішення руйнує ситуацію з очікування-тримання: введено арбітра (офіціанта, як у нараді), від якого філософ повинен отримувати дозвіл перед захопленням будь-якої вилки. Арбітр надає дозвіл лише тоді, коли обидві вилки вільні, роблячи це атомарно. Оскільки жоден філософ ніколи не тримає одну вилку, чекаючи на іншу, застрявання (deadlock) структурно неможливе – але це відбувається за рахунок єдиної глобальної точки синхронізації, яка може стати вузьким місцем при інтенсивному використанні, що є класичною компромісною угодою щодо централізованого блокування.

Третє рішення обмежує паралелізм безпосередньо: дозволяється не більше чотирьох із п’яти філософів одночасно сидіти. З лише чотирма кандидатами на п'ять вилок, гарантовано, що принаймні один філософ матиме обидві сусідні вилки вільними, що руйнує застрявання без необхідності центрального арбітра або порядку вилок – це аналог контролю доступу з точки зору теорії паралелізму.

Затримка проти голодування та живелок

Це три окремі режими відмови, які варто розглядати окремо. Затримка (deadlock) – це ситуація, коли набір процесів у циклі чекає один на одного, нічого не відбувається. Голодування (starvation) – це коли процес постійно втрачає доступ до необхідного ресурсу, навіть якщо система в цілому продовжує прогресувати, наприклад, якщо політика планування завжди віддає перевагу філософам-сусідів. Живелок (livelock) – це коли процеси активно змінюють стан у відповідь один на одного, але при цьому не роблять жодного реального прогресу – два філософи повторювано піднімають та опускають вилку, щоб бути ввічливими один до одного, назавжди. Правильне рішення проблеми філософів із столом має усунути всі три ці режими, а не лише затримку; порядок ресурсів і арбітр обидва це роблять, але наївна схема пріоритетів може усунути затримку, дозволяючи при цьому одному несприятливому філософу голодувати.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Dining Philosophers і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.