Сценарий: три процесса $A,B,C$ и два ресурса $R1,R2$: $A$ держит $R1$ и ждёт $R2$; $B$ держит $R2$ и ждёт $R1$; $C$ ждёт $R1$.
Детектирование:
- Построить граф распределения ресурсов: assignment edges $R1\to A$, $R2\to B$; request edges $A\to R2$, $B\to R1$, $C\to R1$.
- Свести к wait‑for‑graph (вершины — процессы): добавить $A\to B$ (A ждёт ресурс у B), $B\to A$, $C\to A$.
- Найти циклы (DFS/Tarjan). Сложность поиска цикла: $\mathrm{O}(n+e)$, где $n$ — число процессов, $e$ — число рёбер.
- Интерпретация: найден цикл $A\leftrightarrow B$ — взаимоблокировка между $A$ и $B$; $C$ блокирован косвенно (ждёт у участника цикла).
Разрешение (варианты и пример):
- Завершение процесса (terminate victim): выбрать жертву по критерию стоимости (мин. работа, мин. удерживаемые ресурсы, приоритет) и убить её. Пример: завершить $B$ → освобождён $R2$ → $A$ получает $R2$, завершает и освобождает $R1$ → $C$ продолжает.
- Откат (rollback): вернуть жертву к контрольной точке, освободив ресурсы; требует чекпоинтов.
- Принудительное изъятие ресурсов (preemption): вытребовать ресурсы у владельца и передать другому, с механизмом восстановления состояния.
- Комбинации; следить за возможной голодной смертью жертв (starvation).
Заранее (prevention/avoidance) vs динамическая (detection+recovery)
- Заранее (например, deadlock prevention или Banker's algorithm):
- Достоинства: гарантированно отсутствуют взаимоблокировки; предсказуемость поведения.
- Недостатки: требует заранее известной информации (максимальных потребностей) или строгих ограничений; снижает параллелизм и загрузку ресурсов; сложнее реализовать для динамических систем.
- Динамическая детекция + восстановление:
- Достоинства: большая гибкость и лучшая загрузка ресурсов; не требуется полная предсказуемость потребностей.
- Недостатки: накладные расходы на детекцию (периодические проверки или поддержание графа), стоимость восстановления (убийство/откат процессов), риск голодания и временной нестабильности системы.
Рекомендация: для систем с жёсткими требованиями к надёжности и предсказуемости — стратегии заранее; для общих ОС и систем с динамическими нагрузками — детекция и восстановление, с внимательным выбором политики выбора жертвы и предотвращением голодания.