Категории

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

просмотров - 196

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

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

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

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

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

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

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

7. Использовать Г в качестве смещения в 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) Имеет следующий вид:

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

j - 3,1 - 5, К - 1, Г" 3, К'= 2, К'<> J, в связи с этим берем К = 2, Г= 2, К'- 3. В этом случае К' = J, то есть тупик определœен. Таблица заблокированных про­цессов (PWTBL) теперь имеет следующий вид.

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

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