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

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

Прочитайте:
  1. III . Изучите алгоритмы практической работы.
  2. Алгоритм 65 «Кровотечение в послеродовом периоде»
  3. Алгоритм 72 «Ожоги и травмы глаза, века, конъюнктивы»
  4. Алгоритм аудиторной работы студента
  5. Алгоритм базисной СЛР (Basic Life Support – BLS)
  6. АЛГОРИТМ ВВЕДЕНИЯ БЦЖ ВАКЦИНЫ
  7. АЛГОРИТМ ВВЕДЕНИЯ ИНСУЛИНА.
  8. Алгоритм ведения больных апластической анемией.
  9. Алгоритм ведения больных аутоиммунной гемолитической анемией.
  10. Алгоритм взвешивания беременной

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



При использовании материала ссылка на сайт medlec.org обязательна! (0.005 сек.)