Deadlock — головоломка о порядке блокировок
Переставьте порядок захвата блокировок так, чтобы потоки не могли ждать друг друга вечно. Головоломка о правиле глобального порядка блокировок.
Переставьте порядок в потоках так, чтобы они не могли ждать друг друга вечно.
- 🔒 A
- 🔒 B
- 🔒 B
- 🔒 A
Как играть
- Каждая строка — поток, а фишки — блокировки, которые он захватывает слева направо.
- Перетащите фишку (или используйте стрелки), чтобы изменить порядок захвата блокировок.
- Если два потока берут одну пару в противоположном порядке, они могут замереть навсегда. Решение — единый глобальный порядок для всех потоков. Нажмите «Запустить» для проверки.
Как это работает
Каждая строка — поток, каждая фишка — блокировка, которую он захватывает, слева направо. Если два потока берут одну и ту же пару блокировок в противоположном порядке, существует чередование, при котором каждый держит одну и ждёт другую, и оба замирают навсегда. Нажмите «Запустить» — граф ожидания проверяется на цикл, и виновные блокировки подсвечиваются красным. Решение — то же правило, что принимают настоящие кодовые базы: выбрать единый глобальный порядок блокировок и следовать ему во всех потоках.
Обучающая головоломка. Она моделирует циклы hold-and-wait — то условие взаимоблокировки, которое можно устранить проектированием; в реальных системах есть ещё таймауты, lock-free структуры и livelock.
Частые вопросы
Что на самом деле вызывает взаимоблокировку?
Цикл в графе ожидания. Если поток 1 держит A и хочет B, а поток 2 держит B и хочет A, оба ждут вечно. Игра рисует именно этот цикл, когда находит его.
Почему сортировка блокировок помогает?
Если все потоки захватывают блокировки в одном глобальном порядке, цикл невозможен: поток может ждать только блокировку, которая идёт позже уже удерживаемых, поэтому граф ожидания остаётся ациклическим. Это стандартное правило иерархии блокировок.
Так ли ищут взаимоблокировки на практике?
Проверка на цикл — та же идея, что используют детекторы инверсии порядка блокировок вроде ThreadSanitizer. Настоящие инструменты наблюдают порядок во время выполнения, а здесь весь граф виден сразу.