Стратегия обнаружения и устранения дедлока (кратко, по шагам)
1) Обнаружение (периодически или при подозрении):
- Построить wait‑for‑граф $G=(V,E)$: вершины $V$ — процессы, есть дуга $P_i\to P_j$, если $P_i$ ждёт ресурс, захваченный $P_j$.
- Дедлок существует тогда и только тогда, когда в $G$ есть ориентированный цикл.
- Проверка цикла выполняется DFS или алгоритмом топологической сортировки за время $O(|V|+|E|)$.
2) Устранение (при найденном цикле):
- Выбрать «жертву(ы)» и завершить/откатить их, либо
- Принудительно отобрать ресурсы (preemption) и перераспределить, либо
- Откатить до контрольной точки (checkpoint/rollback).
- Выбор жертвы можно формализовать функцией стоимости: например $cos{t}_i=w_1\cdot R_i+w_2\cdot T_i-w_3\cdot P_i$, где $R_i$ — объём удерживаемых ресурсов, $T_i$ — время работы, $P_i$ — приоритет; минимизируем $cos{t}_i$.
Пример алгоритма предотвращения дедлока: ресурсная иерархия (ordering) и альтернативно — алгоритм банкира
A) Ресурсная иерархия (простой алгоритм предотвращения)
- Назначьте каждой типу ресурса уникальный порядок (номер) и требуйте, чтобы каждый процесс запрашивал ресурсы только в строго возрастающем порядке номеров.
- Это нарушает условие circular wait ⇒ дедлок невозможен.
Плюсы: простой, малая накладная; достаточно для многих систем.
Минусы: снижает гибкость программирования, может увеличивать время ожидания (процессы вынуждены ждать «правильного» порядка), возможны проблемы со справедливостью (долгоживущие процессы блокируют других).
B) Banker's algorithm (избежание)
- Требует заранее известной максимальной потребности каждого процесса $Max[i]$.
- Под запросом ресурса система симулирует выделение и проверяет, останется ли система в безопасном состоянии (существует последовательность процессов, которые могут завершиться). Если безопасно — даёт ресурсы, иначе — отклоняет запрос.
- Безопасность проверяется safety‑алгоритмом за примерно $O(n^2\cdot m)$ (где $n$ — число процессов, $m$ — типов ресурсов).
Плюсы: предотвращает дедлок без принудительных убийств, гарантирует завершение в безопасных последовательностях.
Минусы: требует знаний о максимальных запросах, вычислительная накладная при каждой проверке, консервативность (снижает параллелизм и загрузку), возможна задержка запросов и косвенная несправедливость (запросы отклоняются).
Влияние на производительность и справедливость
- Detection + Recovery:
- Производительность: высокая начальная загрузка (нет излишних блокировок), но периодическое обнаружение и восстановление (убийство/откат) влечёт дополнительные потери; восстановление дорогостояще.
- Справедливость: при выборе жертв возможна несправедливость/голодание; нужно эвристики для минимизации ущерба.
- Resource ordering:
- Производительность: низкие накладные на проверку, но может снижать конкурентность (процессы вынуждены ждать по порядку).
- Справедливость: простой и предсказуемый, но длительные удержания нижних ресурсов могут вредить другим процессам.
- Banker's algorithm:
- Производительность: проверка безопасности снижает пропускную способность и повышает задержки; использует больше CPU при частых запросах.
- Справедливость: избегает убийств, но может систематически отклонять запросы больших процессов, что даёт эффект неблагоприятного отношения к «жадным» процессам.
Рекомендация практического применения
- В общем‑назначенной ОС: использовать detection+recovery (детектирование через wait‑for‑граф и мягкие механизмы восстановления: откат/принятие жертвы) + доп. политика выбора жертв для минимизации несправедливости.
- В реальном времени/критичных системах: предпочесть предотвращение (ordering) или Banker's (если известны максимумы) ради гарантированного отсутствия дедлоков, несмотря на возможное снижение параллелизма.