Алгоритм обнаружения тупика по наличию замкнутой цепочки запросов
Итак, распознавание тупика может быть основано на анализе модели распределения ресурсов. Один из алгоритмов, основанный на методе обнаружения замкнутой цепи запросов, был разработан сотрудниками фирмы 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), что и говорит о существовании тупика.
1. Пусть процесс Р1 пытается занять ресурс R3, поэтому в соответствии с опи санным алгоритмом J = 1,1 = 3, К = 2. Процесс К не ждет никакого ресурса Г, поэтому процесс Р1 блокируется по ресурсу R3.
2. Далее, пусть процесс Р2 пытается занять ресурс R2. J =3, I =2, К =3.
Процесс К не ждет никакого ресурса, поэтому процесс Р2 блокируется по ресурсу R2.
Распознавание тупика требует дальнейшего восстановления.
Восстановление можно интерпретировать как запрет постоянного пребывания
в опасном состоянии. Существуют следующие методы восстановления:
Q принудительный перезапуск системы, характеризующийся потерей информации обо всех процессах, существовавших до перезапуска; Q принудительное завершение процессов, находящихся в тупике;
Q принудительное последовательное завершение процессов, находящихся в тупике, с последующим вызоврм алгоритма распознавания после каждого завершения до исчезновения тупика;
Q перезапуск процессов, находящихся в тупике, с некоторой контрольной точки, то есть из состояния, предшествовавшего запросу на ресурс;
Q перераспределение ресурсов с последующим последовательным перезапуском процессов, находящихся в тупике.
Основные издержки восстановления составляют потери времени на повторные вычисления, которые могут оказаться весьма существенными. К сожалению, в ряде случаев восстановление может стать невозможным: например, исходные данные, поступившие с каких-либо датчиков, могут уже измениться, а предыдущие значения будут безвозвратно потеряны.
Контрольные вопросы и задачи
Вопросы для проверки
1. Что такое тупиковое состояние? Перечислите условия, при которых возника ет тупик.
2. Что является причиной возникновения тупиков на SR-pecypcax?
3. Приведите пример графа повторно используемых ресурсов. Что позволяет сделать эта модель Холта?
4. Приведите пример теоретико-множественного описания сети Петри.
5. Что такое маркировка сети Петри? Что представляет собой пространство воз можных состояний сети Петри?
6. Приведите пример графического представления сети Петри.
7. Что представляет собой «предотвращение тупика»? Как его можно реализо вать?
8. Что представляет собой «обход тупика»? Приведите алгоритм банкира Дейк- стры.
9. Что такое «опасное состояние»? Приведите пример опасного состояния на мо дели состояний системы.
10. Изложите метод обнаружения тупика посредством редукции графа повторно- используемых ресурсов.
11. Изложите алгоритм обнаружения тупика по наличию замкнутой цепочки за просов.
Дата добавления: 2015-01-18 | Просмотры: 916 | Нарушение авторских прав
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|