Приведу конкретный пример, покажу обнаружение deadlock по алгоритму Банкера и графу ресурсов, затем — стратегии предотвращения и восстановления.
1) Пример состояния (реальные числа)
- Всего ресурсов: $Total=(2,1)$ (R1 — $2$ экземпляра, R2 — $1$ экземпляр).
- Матрица выделения (Allocation), строки — $P1,P2,P3$, столбцы — $R1,R2$:
Allocation=(101001) Allocation=\begin{pmatrix}
1 & 0\\
1 & 0\\
0 & 1
\end{pmatrix}
Allocation= 110 001 (т.е. $P1$ держит $(1,0)$, $P2$ — $(1,0)$, $P3$ — $(0,1)$).
- Матрица потребностей/запросов (Request/Need):
Request=(010110) Request=\begin{pmatrix}
0 & 1\\
0 & 1\\
1 & 0
\end{pmatrix}
Request= 001 110 (т.е. $P1$ просит $(0,1)$, $P2$ — $(0,1)$, $P3$ — $(1,0)$).
Вычислим Available:
$$\sum Allocation=(2,1),Available=Total-\sum Allocation=(2,1)-(2,1)=(0,0).$$
2) Обнаружение deadlock алгоритмом Банкера (без дальнейшего распределения)
Алгоритм безопасности пытаетcя найти процесс с $Need\le Available$.
Проверяем потребности:
- $P1$: $(0,1)\le (0,0)$? — нет (1>0).
- $P2$: $(0,1)\le (0,0)$? — нет.
- $P3$: $(1,0)\le (0,0)$? — нет.
Ни один процесс не может получить требуемые ресурсы, значит система небезопасна и в данном состоянии имеет взаимная блокировка (deadlock).
3) Обнаружение deadlock по графу ресурсов (Resource Allocation Graph)
Построим RAG:
- Узлы процессов: $P1,P2,P3$.
- Узлы ресурсов: $R1,R2$ (R1 с двумя экземплярами).
- Ребра выделения: $R1\to P1$, $R1\to P2$, $R2\to P3$.
- Ребра запроса: $P1\to R2$, $P2\to R2$, $P3\to R1$.
В графе есть цикл, например
$$P1\to R2\to P3\to R1\to P1,$$ (и аналогично через $P2$). Для одноэкземплярных ресурсов цикл deadlock; при нескольких экземплярах цикл — необходимое, но не всегда достаточное условие. В нашем примере цикл действительно соответствует deadlock (совпадает с выводом Банкера).
4) Пример восстановления из deadlock (конкретный шаг)
Один из простых способов — принудительно завершить (абортировать) процесс. Допустим, убиваем $P2$, освобождается его выделение $(1,0)$:
$$Availabl{e}_{new}=(0,0)+(1,0)=(1,0).$$ Теперь $P3$ имеет Need $(1,0)\le (1,0)$ — может продолжить, выполнится и освободит $(0,1)$, тогда Available станет $(1,1)$. После этого $P1$ (или $P2$ если бы не убили) сможет получить требуемые ресурсы и завершиться. Это один из вариантов восстановления; выбор процесса для убийства обычно делается по стоимости/приоритетам.
5) Стратегии предотвращения и восстановления (кратко)
- Предотвращение:
- Устранить одно из условий Coffman:
- Запрет hold-and-wait: требовать, чтобы процесс запрашивал все ресурсы одновременно (one-shot) или освобождал удерживаемые перед новым запросом.
- Ввести строгий порядок захвата ресурсов (маркировать ресурсы и требовать захватывать в возрастающем порядке) — предотвращает циклы.
- Разрешить освобождение/преквизицию (preemption) — позволить отбирать ресурсы у процессов.
- Ограничивать максимальные потребности (использовать Банкер заранее: запросы разрешать только если состояние останется безопасным).
- Обнаружение + восстановление:
- Периодически запускать детектор (Банкер требует известные максимумы) или анализ RAG; при обнаружении deadlock:
- Преквизацияция (preempt) — отбирать ресурсы и откатывать процессы до безопасного состояния.
- Убить (abort) минимальным набором процессов до устранения цикла (выбирать по стоимости/приоритету).
- Откат (rollback) транзакций до контрольных точек.
- Практические замечания:
- Банкер применим, если процессы заранее объявляют свои максимальные требования.
- Для многократных экземпляров RAG-цикл не всегда означает deadlock — нужно детализировать по количествам (Банкер или алгоритмы обнаружения со счетчиками).
Вывод: в приведённом примере оба метода (Банкера и RAG) обнаруживают взаимоблокировку; предотвратить можно введением порядка захвата или отказом от hold-and-wait, восстанавливать — преквизацией, откатом или завершением процессов (с выбором по стоимости).