P1 R1 P2 R2 P3

W w

(б)

1

P1 1 R1 P2 R2 P3

W

(в)

Рис.2.14. Пример сокращений графа потребляемых ресурсов:

(а) исходный граф;

(б) результат редукции, начатой процессом p₁;

(в) результат редукции, начатой процессом p₂

P1 P2

1 1

1 1

R1 R2 1

Рис.2.15. Пример графа ПР для состояния системы, из которого каждый

из двух процессов может попасть в тупик

Для систем с потребляемыми ресурсами можно проверить, не находится ли конкретный процесс в тупике, алгоритм для поверки дает следующая теорема:

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

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

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

Для систем с CR-ресурсами в выгодном состоянии наличие узла в графе, представляющем состояние системы, является достаточным условием тупика, как и для систем с ресурсами типа SR.

Для систем с ресурсами двух типов для распознавания тупика можно использовать две самые общие теоремы:

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

2. Если состояние системы выгодное, то узел в графе обобщенных ресурсов является достаточным условием тупика

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

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

Существуют два общих подхода к решению задачи вывода системы из тупика:

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

– перехват ресурсов (у процессов в определенном порядке отнимаются выделенные ресурсы).

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

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

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

Самой простой стратегией является выбор процессов-“кандидатов” на завершение или перехват ресурсов в порядке увеличения цены завершения процесса или цены принудительного перераспределения выделенных ему ресурсов. Стоимость этих операций в системе может определяться, например, приоритетами процессов, “ценой” повторного запуска или оживления процессов, затратами, которые могут быть следствием нарушения нормального выполнения процессов (например, затратами на восстановление информации в БД после ее разрушения из-за прерывания транзакции). Цена перехвата ресурса может быть связана с каждой единицей ресурса.

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

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

Менее эффективные по времени выполнения схемы позволяют осуществить вывод системы из тупика за минимальную цену.

Пусть C_i - стоимость уничтожения или перераспределения ресурсов для процесса p_i. Тогда стратегия с минимальной ценой позволяет выбрать для выхода из тупика подмножество p’ множества процессов p, такое, что выполняются следующие условия:

– прекращение всех процессов, представленных вершинами из p’, или перераспределение их ресурсов устраняет тупик;

– для всех других подмножеств p’’ Ì p, для которых ликвидация соответствующих процессов или перераспределение их ресурсов выводит систему из тупика, выполняется соотношение

å C_i £ å C_i

p_i Îp’ p_i Îp’’

Минимальная цена rcmin(S) выхода из тупикового состояния S определяется соотношением

rcmin (S) = minimum (C_i + rcmin (U_i)),

где минимум (minimum) выбирается по всем процессам p_i, находящимся в тупике в состоянии S, а состояние U_i - это состояние, в которое система непосредственно переходит из состояния S после завершения процесса p_i или перераспределения его ресурсов.

Для поиска указанного множества можно использовать полный перебор (алгоритм “исчерпывающего поиска”), что крайне неэффективно.

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

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

Найти все узлы в графе.

Для каждого узла выбрать вершину R_i, представляющую ресурс, такую что для всех R_j ¹ R_i в данном узле выполняется условие:

å C_k £ å C_k

p_k: |(R_i, p_k)| > 0 p_k: |(R_j, p_k)| > 0

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

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

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