17. Дайте определение тупика.

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

Говорят, что процесс находится в состоянии тупика (дедлока или клинча), если он ожидает некоторого события, которое не может произойти без вмешательства извне, то есть если не будут приняты “чрезвычайные меры”. Например, процесс оказывается заблокированным в результате таких запросов на ресурсы, которые не могут быть удовлетворены, если не перераспределить принудительно ресурсы, “отобрав” их у других процессов, или не снять с выполнения эти процессы до нормального их завершения, процесс может быть также заблокирован в результате ожидания сигнала, который не может быть ему передан другим процессом.

17. Сформулируйте задачи, связанные с проблемой тупика, кратко охарактеризуйте подходы к решению.

проблема тупика – глобальная системная проблема, в рамках которой решаются следующие задачи:

– предотвращение тупиков;

– обход тупиков;

– распознавание тупиков;

– вывод системы из тупика и восстановление ее работоспособности.

Цель предотвращения тупика – создание таких условий функционирования системы, которые полностью исключают саму возможность возникновения тупика.

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

решение задачи предотвращения тупика основывается на знании необходимых условий возникновения тупика в системе

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

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

Если оказалось, что система все-таки попала в тупик, то необходимо уметь распознать эту ситуацию. Цель задачи распознавания тупика – установить сам факт возникновения тупиковой ситуации и определить объекты системы (процессы и ресурсы), вовлеченные в нее, то есть определить причины, приведшие к тупику.

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

Все методы предотвращения тупиков имеют одну цель – обеспечение условий, при которых все состояния в системе будут безопасными.

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

Первый метод состоит в том, что все ресурсы в системе отдаются в распоряжение одного процесса. Фактически это означает организацию однопрограммного режима работы ВС, что означает неэффективное ее функционирование.

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

Третий подход к решению задачи предотвращения тупиков состоит в реа-лизации стратегии упорядочения ресурсов.

Все ресурсы делятся на классы

K1, K2, ... , Kk

так, что ресурс из класса Ki может быть выделен процессу только тогда, когда этому процессу не распределены уже ресурсы из классов

Ki, Ki+1, ... , Kk

(при k=1 получается описанный выше вариант).

Классификация ресурсов выполняется в соответствии с их свойствами и естественным порядком запросов на них от выполняющихся процессов. Самые дорогие ресурсы выделяются обычно в старшие классы.

В операционной системе, в которой реализовано предотвращение тупиков, ресурсы могут быть классифицированы, например, следующим образом:

K1 – файлы, открываемые процессом, K2 – оперативная память ВС, запрашиваемая динамически, K3 – устройства ввода/вывода.