Тупики. Задачи операционной системы

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

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

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

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

Процесс запрашивает все нужные ресурсы сразу. До выделения – ждет.

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

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

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

возникновения тупиков:
2 .Удержание ресурсов на время ожидания следующего;
Плюс: простота реализации.
Минусы:
Как определить набор всех необходимых процессу ресурсов?
Простой свободных ресурсов.
Накапливание ресурсов приводит к высоким издержкам.

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

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

в порядке увеличения номера ресурса.

Нарушается условие возникновения тупиков:
4. Существование кольцевой цепи запросов.
Плюс: кажущаяся простота реализации.
Минусы:
Сложно вводить в систему новые ресурсы (ОС).
Кто знает «правильную» последовательность ресурсов?
Трансляторы тоже должны знать номера ресурсов, а это сложно и снижает мобильность систем.

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

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

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

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

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

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

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

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

ресурсов приведено в таблице:

T=12

реакции ОС на запрос от процесса может слабо отличаться от «бесконечного».
Кто должен определять максимальную потребность в ресурсах?
Возможен переход в однопрограммный режим.

«нереализуемое» состояние.

Основной подход к решению – построение графа распределения ресурсов и нахождение в нем циклов. Чрезвычайно затратный подход. На практике в чистом виде не используется.

процессов после устранения причины тупика.

Сложности решения:
Неочевидность тупика.
Трудно остановить процесс в произвольной точке кода.
Большие накладные расходы на реализацию сохранения результатов.
В системах с большим числом разноприоритетных процессов трудно удалить процессы с высоким приоритетом.

тупиков – при возникновении конкурирующих запросов ВСЕ ресурсы могут быть заменены на «виртуальный аналог».

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