Обнаружение тупиков

Алгоритм страуса

Основные направления борьбы с тупиками

В связи с проблемой тупиков были выполнено много интересных исследований в области информатики и операционных систем.

Основные направления борьбы с тупиками:

1) Игнорировать данную проблему

2) Обнаружение тупиков

3) Восстановление после тупиков

4) Предотвращение тупиков за счет тщательного выделения ресурсов или нарушения одного из условий возникновения тупиков.

 

Простейший подход - игнорировать проблему тупиков. Подход Unix состоит в том, чтобы игнорировать данную проблему в предположении, что большинство пользователей предпочтут случайный тупик нелепым правилам заставляющих их иметь один процесс, один открытый файл и т.п. Здесь сталкиваемся с нежелательным выбором между строгостью и удобством.

 

Обнаружение тупика – это установление факта, что возникла тупиковая ситуация и определение процессов и ресурсов, вовлеченных в эту ситуацию. Как правило, алгоритмы обнаружения применяются, когда выполнены первые три необходимых условия возникновения тупиковой ситуации. Затем проверяется наличие режима кругового ожидания. При этом активно используются уже упоминавшиеся графы распределения ресурсов.

Рассмотрим модельную ситуацию:

· Процесс A удерживает ресурс R и ожидает ресурс S.

· Процесс B претендует на ресурс T.

· Процесс C претендует на ресурс S.

· Процесс D удерживает ресурс U и ожидает ресурсы S и T.

· Процесс E удерживает ресурс T и ожидает ресурс V.

· Процесс F удерживает ресурс W и ожидает ресурс S.

· Процесс G удерживает ресурс V и ожидает ресурс U.

Чтобы определить является ли данная ситуация тупиковой, и если да, то какие процессы в ней участвуют, можно сконструировать граф ресурсов (рис.8.2). Из рис.8.2 видно, что имеется цикл, моделирующий условие кругового ожидания, и процессы D,E,G в тупиковой ситуации

Рисунок 8.2 (а) Граф ресурсов. (б) Цикл, извлеченный из графа (a).

 

Визуально легко обнаружить наличие тупика, но нужны также формальные алгоритмы, реализуемые на компьютере. Одним из таких алгоритмов является редукция графа. Если запросы ресурсов для некоторого процесса могут быть удовлетворены, т.е. тупиковой ситуации нет, то граф можно редуцировать на этот процесс. Редукция графа на процесс изображается исключением стрелок, идущих к этому процессу от ресурсов и стрелок к ресурсам от этого процесса.