22. Проблема взаимоблокировки, траектории ресурсов, граф распределения. Стратегии устранения взаимоблокировок. (л6)

Взаимоблокировка (deadlock) – ситуация, когда процессы препятствуют друг другу входить в критические секции (осуществляют обращение к критическому ресурсу). Т.к. критические секции связаны с ресурсами, то взаимоблокировка возникает из-за захвата ресурсов. Выгружаемый р. можно изъять у процесса, а затем вернуть обратно без нарушения логики вычислений (память, процессор). Невыгружаемый р. этого не допускает (записываемый CD).

В заимоблокировка - ситуация, в которой один или несколько потоков ожидают какого-либо события, которое никогда не произойдет (тупик, дедлок или смертельное объятие). Состояние тупика может наступить не только вследствие логических ошибок, допущенных при разработке параллельных программ, но и в результате возникновения тех или иных событий в вычислительной системе (выход из строя отдельных устройств, нехватка ресурсов и т. п.). Пример тупика: пусть имеется 2 потока, каждый из которых в монопольном режиме обрабатывает собственный файл данных. Ситуация тупика возникнет, если первому потоку для продолжения работы потребуется файл второго потока и одновременно второму потоку окажется необходимым файл первого потока.

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

Могут быть выделены следующие необходимые условия тупика:

- потоки требуют предоставления им права монопольного управления ресурсами, которые им выделяются (условие взаимоисключения); - потоки удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (условие ожидания ресурсов); - ресурсы нельзя отобрать у потоков, удерживающих их, пока эти ресурсы не будут использованы для завершения работы (условие неперераспределяемости); - существует кольцевая цепь потоков, в которой каждый поток удерживает за собой один или более ресурсов, требующихся следующему потоку цепи (условие кругового ожидания).

Как результат, для обеспечения отсутствия тупиков необходимо исключить возникновение, по крайней мере, одного из рассмотренных условий.

Возникновение взаимоблокировок (Коффман, Сoffman, 1971):

- взаимное исключение; - удержание и ожидание – процесс может запрашивать ресурсы в дополнение к удержанным; - отсутствие принудительной выгрузки; - циклическое ожидание.

О бнаружение взаимоблокировки при наличии одного ресурса каждого типа:

П од одним ресурсом каждого типа, подразумевается один принтер, один сканер и один плоттер и т.д. Рассмотрим систему из 7-ми процессов и 6-ти ресурсов. Для каждого узла N в графе выполняется пять шагов.

1.Задаются начальные условия: L-пустой список, все ребра не маркированы.

2.Текущий узел добавляем вконец списка L и проверяем количество появления узла в списке. Если он встречается два раза, значит цикл и взаимоблокировка.

3.Для заданного узла смотрим, выходит ли из него хотя бы одно немаркированное ребро. Если да, то переходим к шагу 4, если нет, то переходим к шагу 5.

4.Выбираем новое немаркированное исходящее ребро и маркируем его. И переходим по нему к новому узлу и возвращаемся к шагу 3.

5.Зашли в тупик. Удаляем последний узел из списка и возвращаемся к предыдущему узлу. Возвращаемся к шагу 3. Если это первоначальный узел, значит, циклов нет, и алгоритм завершается.

Для нашего случая тупик обнаруживается в списке L=[B,T,E,V,G,U,D,T].

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

1. Исключение условий возникновения.

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

Алгоритм поиска блокировок

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

3.1. Ограничения на запуск процессов

Алгоритм проверки возможности запуска

3.2. Ограничения на выделение ресурса

Безопасное и опасное состояния системы. Алгоритм банкира.

Интегрированные стратегии – комбинация классификации ресурсов и разных стратегий.

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

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

Проверка безопасности алгоритма (алгоритм банкира). Устранение взаимоблокировок обладает тем достоинством, что при его использовании не нужны ни перераспределение, ни откат процессов, как в случае обнаружения взаимоблокировок; кроме того, этот метод накладывает меньше ограничений по сравнению с предотвращением взаимоблокировок. Однако использование этого метода требует выполнения определенных условий. Должны быть заранее указаны максимальные требования каждого процесса к ресурсам. Рассматриваемые процессы должны быть независимы, т.е. порядок их выполнения не должен ограничиваться никакими требованиями синхронизации. Должно иметься фиксированное количество распределяемых ресурсов. Ни один процесс не должен завершаться в состоянии захвата ресурсов.

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

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

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

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

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