АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

Итак, распознавание тупика может быть основано на анализе модели распреде­ления ресурсов. Один из алгоритмов, основанный на методе обнаружения замк­нутой цепи запросов, был разработан сотрудниками фирмы 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), что и говорит о существовании ту­пика.

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 | Просмотры: 920 | Нарушение авторских прав