Категории
Хирургия
Алгоритм обнаружения тупика по наличию замкнутой цепочки запросов просмотров - 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 = К1 означает, что существует замкнутая цепь взаимоисключающих и ожидающих процессов, то есть выполняются все четыре условия существования тупика.
Стоит отметить, что для описанного нами примера можно построить модель Холта; ее изображение приведено на рис. 7.14. На этом рисунке пронумерованы дуги запросов, которые процессы последовательно генерировали в соответствии с нашим примером Из рисунка сразу видно, что в результате такой последовательности запросов образовалась замкнутая цепочка: (8, 5, 6, 2, 7, 3), что и говорит о существовании тупика.