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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Распознавание тупика

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

1. Самый простой – это принудительное завершение всех процессов и запуск ОС заново;

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

3. Принудительное завершение процессов, находящихся в тупике, по одному и после каждого завершения вызов алгоритма выявления тупика до тех пор, пока тупик не исчезнет;

4. Запуск процессов, находящихся в тупике, со своих контрольных точек в предположении, что тупик больше не возникнет. Естественно, для этого должны быть контрольные точки;

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

6. Теоретически применим, если в момент, когда тупик выявлен, существует несколько пользовательских процессов, которые не находятся в тупике. Если этим процессам позволить доработать до конца и запретить образование новых процессов, то они могут освободить достаточно ресурсов, чтобы тупик исчез.

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