Коротко: да — есть взаимная блокировка между процессами P1, P2 и P3. Причина: образуется цикл захвата/ожидания $P1\to P2\to P3\to P1$. $P4$ простаивает и не участвует.
Детектирование (обход графа ресурсов / wait‑for граф)
- Построить Resource‑Allocation Graph: вершины — процессы и ресурсы, ребра типа «владеет» и «запрашивает». Для однокопийных ресурсов цикл ⇔ дедлок.
- Для многокопийных ресурсов строят wait‑for граф (вершины — процессы, ребро $P_i\to P_j$ если $P_i$ ждёт ресурс(ы), которые держит $P_j$). Дедлок ⇔ в wait‑for графе есть цикл.
- Алгоритм обнаружения цикла: DFS/поиск в глубину; сложность примерно $O(V+E)$.
- Практически: периодически (или при событии) сканировать граф и искать циклы; при найденном цикле — сигнал дедлока.
Метод банкомата (Banker’s algorithm) — избегание, не обнаружение
- Требует заранее известных максимальных требований каждого процесса. Хранит векторы Available, Allocation, Max, Need = Max − Allocation.
- Перед выделением ресурса проверяет, не приведёт ли выделение к небезопасному состоянию: выполняет safety‑проверку (имитирует последовательность завершений, пока можно «удовлетворить» некоторый процесс потребностями ≤ Available).
- Если остаётся безопасная последовательность — выделяет, иначе отклоняет (или заставляет ждать).
- Плюсы: предотвращает дедлок заранее (если применим). Минусы: требует точных максимумов, плох для динамических/непредсказуемых систем; может снижать параллелизм и пропускную способность.
Восстановление от дедлока (после обнаружения)
1. Принудительное завершение процессов:
- Убить один или несколько процессов из цикла до разрыва дедлока.
- Минусы: потеря работы, возможны неконсистентные состояния, требует отката/рестарта.
2. Препемпция ресурсов (отобрать у процесса):
- Требует механизм безопасного отката или чекпойнтов; может быть дорогой по времени/памяти.
- Может привести к Starvation — нужно приоритеты/учёт отмен.
3. Комбинации: циклически отбирать ресурсы/убивать с учётом стоимости восстановления (например, жертвуем процесс с наименьшей стоимости отката).
4. Алгоритм восстановления обычно выбирает минимальный набор действий, разрывающий все циклы, с учётом стоимости (время работы, важность, ресурсы).
Плюсы/минусы стратегий в условиях ограниченных ресурсов
- Обнаружение + восстановление (detect + recover):
+ Не требует заранее известных максимумов; применимо в динамике.
− Восстановление дорого (убийство или откат), возможны потери работы; периодичность детекта влияет на задержки.
- Banker's (avoidance):
+ Гарантирует отсутствие дедлоков при соблюдении условий; более предсказуемо.
− Неприменимо, если нельзя заранее задать Max; снижает параллелизм в условиях дефицита ресурсов.
- Препемпция предпочтительна, если есть дешёвые чекпойнты/откат; завершение процессов — когда откат невозможен или ресурсы критически ограничены.
- В системах с малыми ресурсами часто практичен гибрид: простое детектирование + селективное убивание/препемпция по метрикам (приоритет/стоимость), поскольку Banker's слишком консервативен, а частое восстановление дорого.
Рекомендация практику:
- Если можно заранее задать и доверять Max — использовать Banker's (избегание).
- Иначе — поддерживать wait‑for граф + периодический детектор; при дедлоке применять стратегию восстановления на основе стоимости (сначала прерывать/отодвигать процессы с наименьшей стоимостью восстановления или с низкими приоритетами), и по возможности внедрить чекпойнты для дешёвой препемпции.