23. Алгоритм поиска взаимоблокировок. (Лекция 6)

Идея – обнаружить наличие блокировки, а потом выполнить восстановление нормальной работы системы.

Стратегия обнаружения взаимоблокировок не ограничивает доступ к ресурсам и не налагает никаких ограничений на действия процесса. При обнаружении взаимоблокировок запрошенные ресурсы выделяются процессам по первому требованию. Периодически ОС выполняет алгоритм позволяющий обнаружить циклическое ожидание.

П роцесс или блокирован (0) или работает (1). Первоначально все процессы отмечены как блокированные

Шаг 1. Ищем блокированный , для которого строка матрицы запросов может быть выполнена:

Ш аг 2. Если процесс найден, то

Возвращаемся к шагу 1.

Шаг 3. Завершение, если процесс не найден.

Имеется взаимоблокировка, если хотя бы один процесс останется блокирован

На каждом шаге идет поиск процесса, потребности которого могут быть удовлетворены. Т.е. запросы процессов фактически выполняются последовательно, а после удовлетворения потребностей ресурс возвращается системе.

Пример

Вариант 1’

E={1,1} A={0,0} C={{1,1} R={{0,0}

{0,0}} {1,0}}

Начальное состояние P={0,0}

Проход 1

Найден процесс i=1, т.к.

R[1]={0,0} A={0,0}, R[1] <= A

Отмечаем процесс: P={1,0}

Возвращаем ресурсы: A={1,1}

Проход 2

Найден процесс i=2, т.к.

R[2]={1,0} A={1,1}, R[2] <= A

Отмечаем процесс: P={1,1}

Блокировки нет

Вариант 3

E={1,1} A={0,0} С={{1,0} R={{0,1}

{0,1}} {1,0}}

Начальное состояние P={0,0}

Проход 1

Процесс не найден

R[1]={0,1} A={0,0}, R[1] > A

R[2]={1,0} A={0,0}, R[2] > A

Обнаружена взаимоблокировка, поэтому надо выполнить процедуру восстановления нормальной работы системы. Восстановление:

1. Прекратить выполнение всех заблокированных процессов.

2. Вернуть каждый из заблокированных процессов в некоторую раннее определенную точку и перезапустить все процессы.

3. Последовательно прекращать работу заблокированных процессов до тех пор, пока взаимоблокировки не прекратятся. Порядок выбора заблокированных процессов должен базироваться на некотором критерии минимальной стоимости.

4. Последовательно перераспределять ресурсы пока взаимоблокировки не прекратятся. Выбор процесса осуществляется с учетом критерия минимальной стоимости. И после осуществления перераспределения вызывается алгоритм обнаружения взаимоблокировки. Процесс, ресурсы которого перераспределяются, возвращается к состоянию, в котором он находился до получения этого ресурса.

24. Алгоритм предотвращения взаимоблокировок. (Лекция 6)

Предотвращение взаимоблокировок обеспечивает меньшую параллельность вычислений, чем предотвращение.

Предотвращение 4 условий, необходимых для взаимоблокировок:

- Предотвращение условия взаимного исключения. Можно минимизировать количество процессов борющихся за ресурсы.

- Предотвращение условия удержания и ожидания. Один из способов достижения этой цели, это когда процесс должен запрашивать нужные ресурсы до начала работы. Если хоть 1 ресурс недоступен, то процессу вообще ничего не предоставляется.

- Предотвращение условия отсутствия принудительной выгрузки ресурса. Можно выгружать ресурсы, но могут быть проблемы с принтером.

- Предотвращение условия циклического ожидания.Процесс сначала должен освободить занятый ресурс, прежде чем занять новый.

Можно пронумеровать все ресурсы (и упорядочить), и процессы должны запрашивать ресурсы только по возрастающему порядку.

Запрет запуска нового процесса – новый процесс не запускается, если его требования могут привести к взаимоблокировке.

Определяются: - вектор-ресурс, т.е. общее количество ресурсов в системе. - вектор-доступность, т.е. общее количество каждого ресурса, не выделенного процессу. - матрица требования, здесь определены запросы каждого процесса на каждый из ресурс.

- матрица распределения, определяет текущее распределение ресурсов.

Процесс запускается только тогда, когда : Ri ≥ C(n+1) + сумма( по n, при к=1) Cik

Означает, что запуск процесса происходит в том случае, если м/б удовлетворены максимальные требования всех текущих процессов. Эта стратегия не оптимальна, т.к. предполагает худшее, что все процессы предъявят максимальные требования одновременно.

Запрет выделения ресурса – процесс не получает ресурс, если эта операция переведет систему в небезопасное состояние (Дейкстра, 1965 – «алгоритм банкира»). Матрица запроса – матрица требований процесса. В каждый момент времени процесс может иметь несколько выделенных ему ресурсов или не иметь ни одного. Состояние системы представляет собой текущее распределение ресурсов по процессам. Состояние можно представить как два вектора: ресурсы и доступность. И две матрицы: требования и распределения. Сначала выполняется проверка того, что запрос не превышает исходное требование процесса. Если запрос корректен, то определяем возможность удовлетворения запроса. Если нет, то процесс приостанавливается. Если ресурсов достаточно, то выполняется последняя проверка: безопасно ли выполнение запроса. Для этого процессу гипотетически выделяются ресурсы, получается новое состояние системы, которое и проверяется на безопасность использования алгоритма. Достоинства: не нужно перераспределения, не нужен откат процесса, как в случае обнаружения взаимоблокировок; накладывает меньше ограничений, чем метод предотвращения взаимоблокировок.

Ограничения метода запрета выделения ресурсов: - д/б заранее указаны максимальные требования каждого процесса; - процессы должны быть независимыми; - должно иметься фиксированное количество распределяемых ресурсов; - ни один процесс не должен завершаться в состоянии захвата ресурса.