Тупики (deadlock) и защита от них
Что такое тупик
Тупик (deadlock, взаимная блокировка) — ситуация, когда каждый процесс из группы ждёт событие, которое может вызвать только другой процесс из этой же группы. Ни один не продвигается.
Классический пример с двумя мьютексами:
Поток 1: lock(A) → ... → lock(B)
Поток 2: lock(B) → ... → lock(A)
Если оба захватили первый замок и ждут второй — вечное ожидание.
В статье Управление процессами в Linux слово "взаимная блокировка" иногда использовалось в смысле mutex (взаимное исключение).
В учебниках ОС deadlock — отдельная проблема: цикл ожиданий ресурсов.
Mutex — средство; deadlock — неправильная схема захвата.
Связано: синхронизация и гонки, планирование, управление процессами.
Ресурсы и типы
Ресурс — всё, что выделяется в единственном экземпляре или ограниченно:
- мьютексы, семафоры, блокировки файлов;
- записи в таблице процессов;
- специальные устройства (принтер, лента);
- страницы памяти (в теории — при жёстком резервировании).
| Тип | Поведение |
|---|---|
| Исчерпаемый | Счётчик: N копий (семафор на N слотов) |
| Неисчерпаемый | Один владелец (мьютекс, принтер) |
Deadlock чаще формулируют для неисчерпаемых ресурсов с захватом/освобождением.
Четыре условия Кофмана (Coffman)
Тупик возможен только если одновременно выполнены все четыре:
- Взаимное исключение — ресурс в один момент у одного исполнителя.
- Удержание и ожидание (hold and wait) — держишь один ресурс, ждёшь другой.
- Невозможность принудительного отъёма — нельзя забрать ресурс без согласия владельца (процесс не "выгнали" с mutex).
- Циклическое ожидание — цепочка — P1 ждёт P2, P2 ждёт P3, … Pn ждёт P1.
Стратегия борьбы: разрушить хотя бы одно условие — тогда deadlock невозможен (в модели).
Граф ожидания (wait-for graph)
Узлы — процессы. Дуга P1 → P2 означает: P1 ждёт ресурс, удерживаемый P2.
Граф Холта использует два типа узлов:
-
круг — процесс;
-
квадрат — ресурс;
-
ресурс → процесс — владение (захват выполнен);
-
процесс → ресурс — запрос (ожидание).
-
Если граф ацикличен — deadlock нет.
-
Цикл — deadlock (для одного экземпляра каждого ресурса).
Сценарий на двух мьютексах (Windows)
Поток T1: Wait(M1) → Wait(M2). Поток T2: Wait(M2) → Wait(M1).
| Шаг | Действие | Граф |
|---|---|---|
| 1 | T1 захватил M1 | M1→T1 |
| 2 | T2 захватил M2 | M2→T2 |
| 3 | T2 ждёт M1 | T2→M1 |
| 4 | T1 ждёт M2 | T1→M2 — цикл |
Deadlock не обязателен при каждом запуске: если планировщик не переключит между шагами 1 и 4 "неудачно", T1 успеет взять оба mutex. Значит, иногда помогает осторожное планирование, но полагаться на него нельзя.
Для нескольких экземпляров (например, 3 принтера) используют расширенные модели; в учебниках часто начинают с одного экземпляра.
Пример на псевдокоде
Процесс 1: Процесс 2:
acquire(mutex_A) acquire(mutex_B)
acquire(mutex_B) acquire(mutex_A) // оба зависли
Исправление: глобальный порядок захвата — всегда сначала A, потом B:
acquire(mutex_A)
acquire(mutex_B)
// ...
release(mutex_B)
release(mutex_A)
Это разрушает циклическое ожидание (и часто hold-and-wait при дисциплине "захвати всё сразу").
Стратегии обработки
1. Игнорировать (ostrich algorithm)
Используется там, где deadlock редок и дешевле перезапуск: некоторые embedded, прототипы. Не подходит для банковских транзакций.
Страусовый алгоритм в desktop-серверах: UNIX и Windows не предотвращают исчерпание таблиц файлов/процессов — если N процессов каждый держит часть лимита и запрашивает ещё, возможен системный тупик. Полный запрет потребовал бы жёстких квот на каждый ресурс.
2. Предотвращение (prevention)
Разрушить одно из условий Кофмана:
| Условие | Идея |
|---|---|
| Mutual exclusion | Спулинг принтера — очередь заданий, не прямой захват |
| Hold and wait | Захват всех ресурсов сразу перед работой (мало параллелизма) |
| No preemption | Отъём у процессов с низким приоритетом (редко для mutex) |
| Circular wait | Упорядочивание ресурсов (номера, lock ordering) |
На практике чаще всего — упорядочивание блокировок в коде.
Атака hold-and-wait в Windows: WaitForMultipleObjects — запросить несколько mutex одним вызовом, чтобы не держать один и ждать второй отдельно.
Атака circular wait: нумеровать ресурсы; процесс может захватывать только ресурс с большим номером, чем уже удерживаемые.
3. Избежание (avoidance) — банкир (Banker's algorithm)
ОС знает максимальную потребность каждого процесса и текущее распределение. Перед выделением ресурса проверяет: останется ли система в безопасном состоянии (существует последовательность завершения всех процессов).
- Плюс: не допускает deadlock.
- Минус: нужны точные оценки потребности; консервативно; редко в полном виде в desktop ОС.
Полезно на экзамене и для понимания безопасного состояния.
4. Обнаружение и восстановление (detection & recovery)
Периодически строят граф ожидания (для единственного экземпляра каждого ресурса — достаточно найти цикл на графе Холта). Если цикл есть:
- принудительная выгрузка — временно отобрать ресурс (если модель позволяет);
- откат (rollback) — процесс возвращается к контрольной точке до захвата ресурса;
- завершить процесс в цикле (компиляцию можно перезапустить);
- откатить транзакцию (СУБД);
СУБД и некоторые серверы детектируют deadlock на блокировках строк и жертвуют одну транзакцию (victim selection по стоимости отката).
5. Таймауты
trylock с таймаутом — не гарантия отсутствия deadlock, но практическая защита: через N мс отказ и повтор/логирование. Риск: ложные срабатывания под нагрузкой.
Deadlock и планировщик
Deadlock — не то же самое, что "все процессы в очереди Ready". CPU может быть свободен, пока процессы заблокированы на mutex. Планировщик Планирование процессора — классические алгоритмы не "чинит" deadlock — нужна политика ресурсов.
Livelock — родственная проблема: процессы не блокированы, но бесполезно перестраиваются (оба отступают по вежливости) и не продвигаются.
Starvation — процесс ждёт бесконечно из-за приоритетов, без цикла с другими (не полный deadlock).
В Linux и Windows
- Ядро отслеживает lockdep (отладка), futex с цепочками ожиданий.
- Пользовательский код — ответственность разработчика;
pthread_mutexне предотвращает deadlock. - БД: InnoDB, PostgreSQL — detection + rollback транзакции.
- Файловые блокировки:
flock,fcntl— могут участвовать в deadlock при скриптах.
Инструменты — Thread Sanitizer (частично), helgrind, анализ дампов, echo w > /proc/sysrq-trigger (экстренная диагностика ядра — только для опытных админов).
Чек-лист для разработчика
- Минимизируйте число одновременно удерживаемых блокировок.
- Один порядок захвата для всех потоков.
- Короткие критические секции — см. Гонки, критические секции и разделяемая память.
- Избегайте блокировок под другой блокировкой без схемы.
- Для иерархий — trylock + откат на уровне бизнес-логики.
- В распределённых системах — таймауты и идемпотентность повторов.
Резюме
| Термин | Смысл |
|---|---|
| Deadlock | Цикл "жду тебя, ты ждёшь меня" |
| Coffman | 4 условия — все нужны |
| Prevention | Запретить цикл (порядок lock) |
| Avoidance | Банкир — безопасное состояние |
| Detection | Найти цикл, убить/откатить |
Дальше: ввод-вывод, память и замещение страниц, чек-лист.
Практический анти-паттерн
Частая ошибка: сначала писать многопоточную логику, а порядок захвата блокировок "додумать потом".
Правильный путь: зафиксировать порядок захвата ресурсов до реализации, добавить таймауты и диагностические логи.
Если в проекте уже появились зависания без нагрузки на CPU, первым делом проверяют именно цепочки ожидания и пересечение блокировок.