Алгоритм обнаружения тупика в системе по наличию замкнутой цепочки запросов.
Алгоритм обнаружения тупика по наличию замкнутой
цепочки запросов
Алгоритм был разработан сотрудниками фирмы IBM и использовался в одной из ОС этой компании. Он использует информацию о состоянии системы, содержащуюся в двух таблицах:
1) RATBL - таблица текущего распределения (назначения) ресурсов;
2) PWTBL - таблица заблокированных процессов (для каждого вида ресурса может быть свой список заблокированных процессов).
При каждом запросе на получение или освобождении ресурсов содержимое этих таблиц модифицируется, а при запросе - анализируется в соответствии со следующим алгоритмом.
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 Сделать вывод о наличии тупика с последующим восстановлением.
Конец алгоритма.
Пример 5.6. Рассмотрим следующую последовательность событий.
1 Процесс Р2 занимает ресурс R1.
2 Процесс Р3 занимает ресурс R2.
3 Процесс Р3 занимает ресурс R3.
4 Процесс Р1 занимает ресурс R4.
Таблица распределения ресурсов (RATBL) будет иметь вид таблицы 5.2.
Таблица 5.2 - Таблица распределения ресурсов RATBL
Ресурсы |
Процессы |
1 |
2 |
2 |
3 |
3 |
3 |
4 |
1 |
Выполним алгоритм по шагам.
1 Пусть процесс Р1 пытается занять ресурс R1, тогда J = 1, I = 1, К=2. Процесс К не ждет никакого ресурса I¢, поэтому процесс Р1 блокируется по ресурсу R1.
2 Пусть процесс Р2 пытается занять ресурс R2, тогда J =2, I =2, К =3.
3 Процесс К не ждет никакого ресурса, поэтому процесс Р2 блокируется по ресурсу R2.
4 Теперь пусть процесс Р3 пытается обратиться к ресурсу R4. Тогда J=3, I = 4, К = 1, I¢ = 1, К¢= 2, К'<> J, поэтому берем К = 2, I¢ = 2, К¢ = 3.
В этом случае К' = J, то есть тупик определен. Таблица заблокированных процессов (PWTBL) теперь имеет вид таблицы 5.3.
Таблица 5.3 - Таблица заблокированных процессов PWTBL
Процесс |
Ресурс |
1 |
1 |
2 |
2 |
3 |
4 |
Равенство J = К' означает, что существует замкнутая цепь взаимоисключающих и ожидающих процессов, то есть выполняются все четыре условия существования тупика.
Модель Холта для описанного примера приведена на рисунке 5.7. На рисунке пронумерованы дуги запросов, которые процессы последовательно генерировали в соответствии с примером. Из рисунка сразу видно, что в результате такой последовательности запросов образовалась замкнутая цепочка: (5, 1, 6, 2, 7, 4), что и говорит о существовании тупика.
Рисунок 5.7 - Граф распределения ресурсов