Довідка та теорія
У задачі про філософів, що обідають, п'ять філософів
сидять навколо столу з однією виделкою між кожною
парою. Філософ мусить тримати обидві сусідні виделки,
щоб їсти, тож виделки — спільні ресурси, які потребують
координації.
Наївна — взаємне блокування
Кожен бере ліву виделку, потім чекає на
праву. Якщо всі схоплять ліву одночасно, кожен
тримає одну виделку й чекає вічно — взаємне блокування
через кругове очікування.
Упорядкування ресурсів
Пронумеруйте виделки; завжди беріть виделку з
меншим номером першою. Один філософ тягнеться за
тією самою виделкою, що й сусід, і програє, розриваючи цикл.
Арбітр / офіціант
Центральний офіціант надає дозвіл брати виделки, обмежуючи кількість філософів, які суперничають одночасно, і серіалізуючи доступ, тож цикл не утворюється.
Обмеження до 4 за столом
Дозвольте щонайбільше чотирьом із п'яти тягнутися за
виделками. За чотирьох філософів і п'яти виделок принаймні один
завжди може взяти обидві — розриваючи
утримання-й-очікування.
Умови Коффмана
Взаємне блокування потребує всіх чотирьох: взаємне виключення, утримання-й-очікування, відсутність витіснення та кругове очікування. Кожна стратегія тут усуває одну з них.
Поширені запитання
Що таке задача про філософів, що обідають?
Це класична головоломка конкурентності Едсгера Дейкстри: п'ять філософів сидять навколо столу з однією виделкою між кожною парою. Філософу потрібні обидві сусідні виделки, щоб їсти, тож виделки моделюють спільні ресурси, які треба координувати без взаємного блокування чи голодування.
Чому наївне рішення взаємно блокується?
Якщо кожен філософ спершу бере ліву виделку, а потім чекає на праву, усі п'ятеро можуть тримати по одній виделці й чекати вічно на іншу. Це кругове очікування задовольняє всі чотири умови Коффмана, спричиняючи взаємне блокування.
Які чотири умови Коффмана для взаємного блокування?
Взаємне блокування вимагає одночасного виконання взаємного виключення, утримання-й-очікування, відсутності витіснення та кругового очікування. Порушення будь-якої з них запобігає блокуванню — саме це й роблять стратегії в цій симуляції.
Як упорядкування ресурсів запобігає взаємному блокуванню?
Якщо виделки пронумеровані й кожен філософ завжди бере виделку з меншим номером першою, умова кругового очікування не може утворитися. Принаймні один філософ візьме дві виделки й поїсть, розриваючи цикл.
Як працює рішення з арбітром (офіціантом)?
Центральний офіціант надає дозвіл брати виделки. Дозволяючи лише безпечній кількості філософів тягнутися за виделками одночасно, арбітр серіалізує суперництво й гарантує, що кругове очікування не утвориться.
Чому обмеження до чотирьох місць допомагає?
Коли лише чотирьом із п'яти філософів дозволено сидіти й тягнутися за виделками одночасно, завжди вистачає виделок, щоб принаймні один філософ узяв обидві й поїв. Це розриває утримання-й-очікування на рівні столу.
Яка різниця між взаємним блокуванням і голодуванням?
Взаємне блокування означає, що жоден філософ узагалі не може просунутися. Голодування означає, що система прогресує, але конкретному філософу постійно не щастить і він ніколи не їсть. Хороше рішення уникає обох.
Через які стани проходить філософ?
Кожен філософ циклічно проходить роздуми, потім голод і спробу взяти виделки, потім їжу, коли обидві виделки в руках, перш ніж відпустити виделки й знову думати.
Як працює детектор взаємного блокування?
Простий детектор сигналізує про взаємне блокування, коли кожен філософ голодний і тримає одну виделку, чекаючи на іншу, тож жоден не може продовжити. У цій симуляції детектор піднімає попередження, коли всі п'ятеро застрягли.
Чи актуальна задача про філософів, що обідають, досі?
Так. Вона моделює реальні конкурентні системи, де потоки змагаються за кілька блокувань, як-от бази даних та ядра операційних систем. Ті самі методи впорядкування блокувань і арбітражу, що розв'язують її, застосовують у промисловому ПЗ.