Алгоритм обнаружения тупика 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, в противном случае - к ш Проверить, вся ли таблица PWTBL просмотрена. Если да, то перейти к ш.6, в противном случае - к ш Присвоить К:= К' и перейти к ш Сделать вывод о наличии тупика с последующим восстановлением. Конец алгоритма

Пример Последовательность событий: 1 Процесс Р2 занимает ресурс R1. 2 Процесс Р3 занимает ресурс R2. 3 Процесс Р3 занимает ресурс R3. 4 Процесс Р1 занимает ресурс R4. Таблица распределения ресурсов RATBL Ресурсы Процессы

Пример Алгоритм по шагам 1 Пусть Р1 обращается к R1, тогда J = 1, I = 1, 2 Пусть Р2 обращается к R2, тогда J =2, I =2, 3 К не ждет ресурса, поэтому Р2 блокируется по R2. К =3. К' = J, тупик определен. К не ждет никакого I, поэтому Р1 блокируется по R1. К=2. 4 Пусть Р3 обращается к R4. Тогда J=3, I = 4,К = 1, I = 1, К = 2, К'<> J, поэтому К = 2, I = 2,К = 3.

Таблица заблокированных процессов PWTBL Процесс Ресурс

P1P1 R1R1 R4R4 R2R2 R3R3 P2P2 P3P3 Граф распределения ресурсов Замкнутая цепочка: (5, 1, 6, 2, 7, 4)