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

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

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

264_______________________ Глава 8, Проблема тупиков и методы борьбы с ними

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

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

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

- Условие кругового ожидания можно исключить, предотвращая образование цепи запросов. Это можно обеспечить с помощью принципа иерархического выделе-нияресурсов. Все ресурсы образуют некоторую иерархию. Процесс, затребовав­ший ресурс на одном уровне, может затем потребовать ресурсы только на более высоком уровне. Он может освободить ресурсы на данном уровне, только пос­ле освобождения всех ресурсов на всех более высоких уровнях. После того как процесс получил, а потом освободил ресурсы данного уровня, он может запро­сить ресурсы на том же самом уровне. Пусть имеются процессы Пр1 и Пр2, которые могут иметь доступ к ресурсам R1 и R2, причем R2 находится на более высоком уровне иерархии. Если процесс Пр1 захватил ресурс R1, то процесс Пр2 не может захватить ресурс R2, так как доступ к нему проходит через дос­туп к ресурсу R1, который уже захвачен процессом Пр1. Таким образом, созда­ние замкнутой цепи исключается. Иерархическое выделение ресурсов часто не дает никакого выигрыша, если порядок использования ресурсов, определенный в описании процессов, отличается от порядка уровней иерархии. В этом случае ресурсы будут расходоваться крайне неэффективно.

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

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

Обход тупика можно интерпретировать как запрет входа в опасное состояние. Если ни одно из упомянутых четырех условий не исключено, то вход в опасное состоя­ние можно предотвратить при наличии у системы информации о последователь­ности запросов, связанных с каждым параллельным процессом. Доказано [54], что если вычисления находятся в любом неопасном состоянии, то существует, по край­ней мере, одна последовательность состояний, которая обходит опасное состоя-

Методы борьбы с тупиками____________________________________________ 265

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

Рассмотрим следующий пример. Пусть имеется система из трех вычислительных процессов, потребляющих некоторый ресурс R типа SR; который выделяется дис­кретными взаимозаменяемыми единицами, причем существует всего десять еди­ниц этого ресурса. В табл. 8.2 приведены сведения о текущем распределении про­цессами этого ресурса R, об их текущих запросах на этот ресурс и о максимальных потребностях процессов в ресурсе R.

Таблица 8.2.Пример распределения ресурсов

Имя процесса Выделено Запрос Максимальная Остаток