Обход тупиков

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

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

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

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

2. Ожидания – процесс, запросивший ресурс, будет ждать, пока запрос не будет удовлетворен, продолжая удерживать все остальные ресурсы, которые он уже получил;

3. Отсутствия перераспределения – никакие ресурсы нельзя отобрать у процесса, если они ему уже выделены;

4. Кругового ожидания –существует замкнутая цепь процессов, каждый из которых ждет ресурс, удерживаемый его предшественником в этой цепи.

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

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

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

Условие отсутствия перераспределения можно исключить, позволяя ОС отнимать у процесса ресурсы. Перераспределение процессора реализуется достаточно легко, в то время как перераспределение устройств ввода/вывода крайне нежелательно.

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

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

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