Deadlock — головоломка про порядок блокувань
Переставте порядок захоплення блокувань так, щоб потоки не чекали одне на одного вічно. Головоломка про правило глобального порядку блокувань.
Переставте порядок у потоках, щоб жоден не чекав іншого вічно.
- 🔒 A
- 🔒 B
- 🔒 B
- 🔒 A
Як грати
- Кожен рядок — потік, а фішки — блокування, які він захоплює зліва направо.
- Перетягніть фішку (або скористайтесь стрілками), щоб змінити порядок захоплення блокувань.
- Якщо два потоки беруть ту саму пару в протилежному порядку, вони можуть завмерти назавжди. Розв’язок — єдиний глобальний порядок для всіх. Натисніть «Запустити» для перевірки.
Як це працює
Кожен рядок — потік, кожна фішка — блокування, яке він захоплює зліва направо. Якщо два потоки беруть ту саму пару в протилежному порядку, існує чергування, за якого кожен тримає одне і чекає інше, і обидва завмирають назавжди. Натисніть «Запустити» — граф очікування перевіряється на цикл, і винні блокування підсвічуються червоним. Розв’язок — те саме правило, що ухвалюють справжні кодові бази: обрати єдиний глобальний порядок блокувань і дотримуватись його всюди.
Навчальна головоломка. Вона моделює цикли hold-and-wait — умову взаємоблокування, яку можна усунути проєктуванням; у справжніх системах є ще тайм-аути, lock-free структури та livelock.
Часті запитання
Що насправді спричиняє взаємоблокування?
Цикл у графі очікування. Якщо потік 1 тримає A і хоче B, а потік 2 тримає B і хоче A, обидва чекають вічно. Гра малює саме цей цикл.
Чому сортування блокувань допомагає?
Якщо всі потоки захоплюють блокування в одному глобальному порядку, цикл неможливий: потік може чекати лише на блокування, що йде пізніше за вже утримувані, тож граф лишається ациклічним.
Чи так шукають справжні взаємоблокування?
Перевірка на цикл — та сама ідея, що в детекторів інверсії порядку блокувань на кшталт ThreadSanitizer. Справжні інструменти спостерігають порядок під час виконання, а тут увесь граф видно одразу.