Кратко — как обнаружить и как восстановить.
1) Обнаружение
- Для одноэкземплярных ресурсов (как в задаче): строят wait‑for‑graph, вершины — процессы, есть ребро $P_i\to P_j$ если $P_i$ ждёт ресурс, который удерживает $P_j$. Нахождение цикла в этом графе (DFS или поиск сильных компонент) указывает на взаимную блокировку. Сложность поиска цикла: $O(n+e)$ (n — число процессов, e — число рёбер).
Применение к примеру: ребра $P1\to P2$, $P2\to P3$, $P3\to P1$ → цикл $P1\to P2\to P3\to P1$ → deadlock.
- Для многократных экземпляров ресурсов: используют алгоритм обнаружения взаимной блокировки, похожий на safety‑проверку Банковского алгоритма:
- Пусть Work = Available, Finish[i]=false для всех процессов.
- Найти процесс $i$ с $Reques{t}_i\le Work$ и $Finish[i]=false$; если найден — выполнить $Work:=Work+Allocatio{n}_i$, $Finish[i]:=true$; повторять.
- В конце все процессы с $Finish[i]=false$ находятся в deadlock.
Сложность примерно $O(n\cdot m)$ (n — процессы, m — типы ресурсов) или $O(n^2)$ в развертке.
2) Восстановление (алгоритмы и оценка)
- Аборт всех процессов в цикле:
- Плюсы: простое и гарантированно исправляет.
- Минусы: высокий потерянный объём работы, возможны побочные эффекты на данные.
- Поочерёдное прерывание (abort one by one) с выбором «жертвы» по эвристике (минимальная стоимость отмены, наименьший приоритет, наименьший удерживаемый ресурс и т.п.):
- Плюсы: минимизирует общие потери, можно подобрать по политике.
- Минусы: может потребоваться несколько итераций, сложность оценки стоимости.
- Принудительное отнятие ресурсов (preemption) + откат/повторная попытка:
- Плюсы: не нужно убивать процесс целиком, гибче.
- Минусы: требуется поддержка отката (чекпойнты), может приводить к инверсии приоритетов и голоданию.
- Откат процесса к контрольной точке (rollback):
- Плюсы: меньше потерь, можно вернуть в консистентное состояние.
- Минусы: нужен механизм чекпойнтов, накладные расходы на хранение состояний.
- Изменение приоритета/реципиента ресурсов (preemption + приоритеты):
- Плюсы: можно освободить ресурсы менее важными задачами.
- Минусы: риск голодания низкоприоритетных задач, сложность выбора.
- Комбинированные стратегии (панель: детектировать периодически, при deadlock — попытаться preempt/rollback для нескольких кандидатов, если не помогает — убивать):
- Баланс между накладными расходами и потерями работы.
3) Практический пример восстановления в данной схеме
- Самый простой метод: прервать один процесс из цикла, скажем $P3$. Тогда $R3$ освобождается → $P2$ получает $R3$, завершается и освобождает $R2$ → $P1$ получает $R2$ и завершается. Deadlock снят.
- Альтернатива: выбрать жертву по минимальной стоимости (например процесс с наименьшим выполненным временем или наименьшим количеством удерживаемых ресурсов).
Рекомендация: для систем с критичностью данных — предпочесть preemption/rollback с чекпойнтами; для простых систем с невысокой ценой прерывания — поочерёдный abort с выборе жертвы по эвристике. Для предотвращения — использовать стратегии избегания (например Banker's) если возможны прогнозируемые запросы.