Лекция ОС - Тупики

никогда не реализуется (клинч, дедлок).
Задачи ОС:
Предотвращение;
Обход;
Обнаружение.
Примеры тупиков.









Proc.

Proc. 2

R 1

R 2

Транспортная пробка

Кольцевая цепь запросов

но оно откладывается на неопределенное время. Например, из-за приоритета.
Ресурсы бывают:
перераспределяемые

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

нарушить одно из необходимых условий его возникновения.
Принципы Хавендера:
Процесс запрашивает все

Если процессу не выделяется очередной ресурс, он должен отдать уже выделенные.

Вводим линейную упорядоченность на типы ресурсов. Процесс может запросить ресурсы только в порядке увеличения номера ресурса.

Условие монопольного управления Хавендер не нарушает.

условие возникновения тупиков:
2 .Удержание ресурсов на время ожидания следующего;
Плюс: простота

Если процессу не выделяется очередной ресурс, он должен отдать уже выделенные.

Нарушается условие возникновения тупиков:
3. Ресурсы у процесса нельзя отобрать, отдает их сам (неперераспределение);
Плюс: ???.
Минусы:
Как сохранить промежуточные результаты работы процесса?
Возможность бесконечного откладывания (дефицитный ресурс).

только в порядке увеличения номера ресурса.
Нарушается условие возникновения тупиков:
4. Существование

Вывод – принципы Хавендера носят скорее теоретический характер.
На практике они используются как вспомогательные элементы стратегий.

может их возвратить.
Дейкстра предложил алгоритм обхода тупиков, если все условия

Алгоритм банкира – ресурсы процессу можно выдавать только в том случае, если состояние системы останется надежным.
Надежное состояние – ОС гарантирует всем процессам завершение в конечное время.
Введем следующие обозначения:

M(i) – максимальная потребность i-го процесса в ресурсе;

L(i) – текущая величина ресурса, выделенного i-му процессу;

С(i) – текущая потребность в ресурсе, C(i)=M(i)-L(i);

Т – суммарный ресурс, имеющийся в системе;

а – остаточный ресурс, а=Т-∑L(i);

процесса.
Распределение ресурсов приведено в таблице:
T=12

системы.

системе.
Время реакции ОС на запрос от процесса может слабо отличаться

ожидающих «нереализуемое» состояние.
Основной подход к решению – построение графа распределения

некоторых процессов после устранения причины тупика.
Сложности решения:
Неочевидность тупика.
Трудно остановить процесс

возникновения тупиков – при возникновении конкурирующих запросов ВСЕ ресурсы могут

Особенности решения:
Алгоритмически простое решение.
Формально, не боится большого числа процессов.
Сложность возврата из «виртуального мира» в реальный в случае иерархической виртуальности.

только одна проблема – как вернуть красную машину из виртуального