Алгоритм обнаружения тупика по наличию замкнутой цепочки запросов

Итак, распознавание тупика может быть основано на анализе модели распреде­ления ресурсов. Один из алгоритмов, основанный на методе обнаружения замкнутой цепи запросов, был разработан сотрудниками фирмы IBM; этот алгоритм использовался в одной из ОС этой компании. Он использует информацию о состоянии системы, содержащуюся в двух таблицах: таблице текущего распреде­ления (назначения) ресурсов RATBL и «таблице» заблокированных процессов PWTBL (для каждого вида ресурса может быть свой список заблокированных процессов). При каждом запросе на получение или освобождении ресурсов содержимое этих таблиц модифицируется, а при запросе – анализируется в соответствии со следующим алгоритмом, который описан по пунктам [49].

1 Запрос от процесса J на занятый ресурс I.

2 Поместить номер ресурса I в PWTBL в строке с номером процесса J.

3 Использовать I в качестве смещения в RATBL, чтобы найти номер процес­са К, который владеет ресурсом.

4 Использовать К в качестве смещения в PWTBL.

5 Проверить, ждёт ли процесс К освобождения какого-либо ресурса I’. Если нет, то перейти к шагу 6, в противном случае – к шагу 7.

6 Перевести J в состояние ожидания и выйти из алгоритма.

7 Использовать I’ в качестве смещения в RATBL, чтобы найти номер блоки­рующего его процесса К'.

8 Проверить К' = J. Если нет, то перейти к шагу 9, в противном случае – к ша­гу 11.

9 Проверить, вся ли таблица PWTBL просмотрена. Если да, то перейти к ша­гу 6, в противном случае – к шагу 10.

10 Присвоить К:= К' и перейти к шагу 4.

11 Вывод о наличии тупика с последующим восстановлением.

12 Конец алгоритма.

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

1 Процесс Р1 занимает ресурс R1.

2 Процесс Р2 занимает ресурс R3.

3 Процесс РЗ занимает ресурс R2.

4 Процесс Р2 занимает ресурс R4.

5 Процесс Р1 занимает ресурс R5.

В результате таблица распределения ресурсов (RATBL) имеет следующий вид:

Таблица 7.3. Таблица распределения ресурсов RATBL

1 Пусть процесс Р1 пытается занять ресурс R3, поэтому в соответствии с описанным алгоритмом J = 1, I = 3, К = 2. Процесс К не ждёт никакого ресурса I’, поэтому процесс Р1 блокируется по ресурсу R3.

2 Далее, пусть процесс Р2 пытается занять ресурс R2.

J = 3, I = 2, К = 3.

Процесс К не ждёт никакого ресурса, поэтому процесс Р2 блокируется по ре­сурсу R2.

3 И наконец, пусть процесс РЗ пытается обратиться к ресурсу R5.

J = 3, I = 5, К = 1, I’ = 3, К’ = 2, K'< > J, поэтому берём К = 2, I’ = 2, К' = 3.

В этом случае К' = J, то есть тупик определён. Таблица заблокированных про­цессов (PWTBL) теперь имеет следующий вид.

Таблица 7.4, Таблица заблокированных процессов PWTBL

Равенство J = К' означает, что существует замкнутая цепь взаимоисключающих и ожидающих процессов, то есть выполняются все четыре условия существова­ния тупика.

Для описанного нами примера можно построить модель Холта; её изображение приведено на рис. 7.14. На этом рисунке пронумерованы дуги запросов, которые процессы последовательно генерировали в соответствии с нашим примером. Из рисунка сразу видно, что в результате такой последовательности запросов образовалась замкнутая цепочка: (8, 5, 6, 2, 7, 3), что и говорит о существовании ту­пика.

Рис. 7.14. Граф распределения ресурсов

Распознавание тупика требует дальнейшего восстановления.

Восстановление можно интерпретировать как запрет постоянного пребывания в опасном состоянии. Существуют следующие методы восстановления:

¨ принудительный перезапуск системы, характеризующийся потерей информа­ции обо всех процессах, существовавших до перезапуска;

¨ принудительное завершение процессов, находящихся в тупике;

¨ принудительное последовательное завершение процессов, находящихся в ту­пике, с последующим вызовом алгоритма распознавания после каждого завершения до исчезновения тупика;

¨ перезапуск процессов, находящихся в тупике, с некоторой контрольной точки, то есть из состояния, предшествовавшего запросу на ресурс;

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

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

Контрольные вопросы и задачи

Вопросы для проверки

1 Что такое тупиковое состояние? Перечислите условия, при которых возникает тупик.

2 Что является причиной возникновения тупиков на SR–pecypcax?

3 Приведите пример графа повторно используемых ресурсов. Что позволяет сделать эта модель Холта?

4 Приведите пример теоретико-множественного описания сети Петри.

5 Что такое маркировка сети Петри? Что представляет собой пространство воз­можных состояний сети Петри?

6 Приведите пример графического представления сети Петри.

7 Что представляет собой «предотвращение тупика»? Как его можно реализовать?

8 Что представляет собой «обход тупика»? Приведите алгоритм банкира Дейкстры.

9 Что такое «опасное состояние»? Приведите пример опасного состояния на мо­дели состояний системы.

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

11 Изложите алгоритм обнаружения тупика по наличию замкнутой цепочки за­просов.