Взаимоблокировки в распределенных системах, их обнаружение и предотвращение.

. Принципы взаимного блокирования.

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

Все взаимоблокировки предполагают наличие конфликта в борьбе за ресурс между 2мя и более процессами. Ресурсы: повторно используемые; расходуемые.

Условия осуществления взаимоблокировок:

- взаимное исключение

- удержание и ожидание

- отсутствие перераспределения

- циклическое ожидание.

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

Предотвращение взаимоблокировок.

Два метода: Косвенный метод (предотвращение одного из трёх первых условий возникновения взаимоблокировок: взаимное исключение, удержание и ожидание, отсутствие перераспределения), Прямой (предотвращение циклического ожидания).

Избежать взаимоисключения невозможно. Если доступ к ресурсам д.б. исключительным, то ОС должна поддерживать взаимоисключение.

Удержании и ожидание. Избегается, потребовав чтоб процесс запрашивал все ресурсы одновременно и блокировать процесс, пока запрос не будет полностью удовлетворён. Метод не эффективен (долгое время ожидания; ресурсы могут оставаться неиспользуемыми долгое время, когда они могли бы использоваться другими процессами; может быть неизвестно заранее какие ресурсы могут понадобиться процессу)

Отсутствие перераспределений. 2 пути:

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

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

Циклическое ожидание. Избегается путем упорядочивания ресурсов.

Устранение взаимоблокировок.

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

Имеется 2-а подхода:

- не запускать процесс, если его запросы могут привести к взаимоблокировки.

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

a. Запрещение запуска процесса

Определяются:

- вектор-ресурс, т.е. общее количество ресурсов в системе

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

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

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

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

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

b. Запрет выделения ресурса. В каждый момент времени процесс может иметь несколько выделенных ему ресурсов или не иметь ни одного. Состояние системы представляет собой текущее распределение ресурсов по процессам. Состояние можно представить как два вектора: ресурсы и доступность. И две матрицы: требования и распределения.

Сначала выполняется проверка того, что запрос не превышает исходное требование процесса. Если запрос корректен, то определяем возможность удовлетворения запроса. Если нет, то процесс приостанавливается. Если ресурсов достаточно, то выполняется последняя проверка: безопасно ли выполнение запроса. Для этого процессу гипотетически выделяются ресурсы, получается новое состояние системы, которое и проверяется на безопасность использования алгоритма.

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

Ограничения метода запрета выделения ресурсов:

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

Обнаружение взаимоблокировок.

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

a. Алгоритм обнаружения. Используются: матрица распределения и вектор доступности, матрица запросов Q такая, что q_ij представляет собой количество ресурса типа j, затребованных процессом i.

Алгоритм:

1.Помечают все процессы, у которых строки матрицы распределения состоят из нулей.

2.Временный вектор W инициализирует значением вектора доступности.

3.Находим индекс i, такой что процесс i в настоящий момент не помечен и i строка матрицы не превышает временной интервал W. Если такой строки нет, то алгоритм прекратит свою работу.

4.Если строка имеется, то процесс i помечается и добавляется следующее условие:W_k=W_k+A_ik, далее возврат к шагу №3.

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

b. Восстановление Подходы к решению этой проблемы:

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

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

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

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