Тупики

Ситуация, в которой процессы ждут друг друга неопределенно долго.

Вычислительная система = множество состояний + множество процессов

Процесс – это функция, отображающая одно состояние в другое

Необходимые условия тупика:

1. Условие взаимоисключения (монопольного управления ресурсами).

2. Условие ожидания ресурсов (процесс удерживает за собой некоторый набор ресурсов, и для продолжения работы требует (ожидает) еще дополнительных ресурсов).

3. Условие неперераспределяемости ресурсов (ресурсы нельзя отобрать насильно, ресурсы освобождаются добровольно после завершения обработки).

4. Условие кругового ожидания (процессы образуют замкнутую цепь, в которой каждый следующий процесс блокирует (занимает) те ресурсы, которые необходимы предыдущему процессу).

Тупик может наступить при выполнении всех 4 условий. Это необходимые условия.

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

1. Предупреждение (предотвращение) тупиков (нарушается одно из условий – стратегия Хавендера). Минус – неэффективное использование ресурсов.

2. Обход тупика (алгоритм банкира).

3. Тупики допускаются в вычислительных системах.

Обнаружение тупика и восстановление после него.

1. Стратегия Хавендера – нарушение одного из необходимых условий.

1. Нарушать нельзя (иначе - однопрограммность).

2. Все ресурсы, необходимые для обработки, запрашиваются сразу (в одном запросе). Минус – неэффективное использование ресурсов (простаивание ресурса по времени).

3. Разрешение насильного изъятия ресурсов у процессов. Минусы:

i. Возможность потери проделанной работы процессом, у которого изъяты ресурсы.

ii. Возможность бесконечного откладывания процесса-жертвы.

4. Для всех процессов вводится упорядочение всех ресурсов по типам, запрос ресурсов возможен только в соответствие с номерами типов (в порядке, предусмотренном типами). Минусы:

i. Упорядочение ресурсов по типам может быть неудобно для некоторых процессов.

ii. Усложняется разработка приложений.

iii. Неэффективное использование ресурсов (простаивание ресурсов).

2. Алгоритм банкира – обход тупика.

Менее жесткие ограничения (по сравнению со стратегией Хавендера) => лучшее использование ресурсов.

Алгоритм:

Исходная информация:

1. Имеется K единиц ресурса.

2. Имеется N процессов.

3. Для каждого процесса известна потребность в ресурсах:

a. Максимальная потребность – MAXР.

b. Количество выделенных ресурсов – КВР.

c. Остаток потребности в ресурсах – ОР.

Проверка безопасности состояния при выделении ресурса (по запросу).

begin

сбоврес = k

for i = 1 to N do

begin

свобрес -= КВР[i]

ОР[i] = MAXР[i] - КВР[i]

тупик[i] = true

end

признак = true

do while признак

begin

признак = false

for i = 1 to N do

begin

if ОР[i] <= свобрес then

begin

свобрес += КВР[i]

признак = true

тупик[i] = false

end

end

end

if свобрес = K then

<состояние системы безопасное>

else

<состояние небезопасно>

end