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

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

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

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

qобход тупика;

qраспознавание тупика с последующим восстановлением.

 

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

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

Определение 4.9. Предотвращение можно рассматривать как запрет существования опасных состояний.

 

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

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

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

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

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

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

 

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

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

Определение 4.10. Обход тупика можно интерпретировать как запрет входа в опасное состояние.

 

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

 

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

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

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

 

Термин «ненадежное состояние» не предполагает, что в данный момент существует или в какое-то время обязательно возникнет тупиковая ситуация. Он просто говорит о том, что в случае некоторой неблагоприятной последовательности событий система может зайти в тупик.

Имя процесса	Выделено	Запрос	Максимальная потребность	«Остаток» потребностей
А
В
С

 

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

 

Если первым будет выполнен запрос процесса В, то останется свободной еще одна единица ресурса R. Однако если процесс В запросит еще две, а не одну единицу ресурса R, а он может это сделать, то опять получится тупиковая ситуация.

Если же мы сначала выполним запрос процесса С и выделим ему не две (как у процесса В), а все три единицы ресурса R и у нас при этом даже не останется никакого резерва, то, поскольку на этом его потребности в ресурсах заканчиваются, процесс С сможет благополучно завершиться и вернуть системе все свои ресурсы. Это приведет к тому, что свободное количество ресурса R станет равно пяти. Теперь уже можно будет выполнить запрос либо процесса В, либо процесса А, но не обоих сразу.

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

 

Классическое решение этой задачи известно как алгоритм банкира Дейкстры. Алгоритм банкира напоминает процедуру принятия решения, может ли банк безопасно для себя дать взаймы денег. Принятие решения основывается на информации о потребностях клиента (текущих и максимально возможных) и учете текущего баланса банка. Несмотря на то, что этот алгоритм нигде практически не используется, он интересен с методической и академической точек зрения.

 

Алгоритм банкира Дейкстры

Пусть существует N процессов, для каждого из которых известно максимальное количество потребностей в некотором ресурсе R (обозначим эти потребности через Max(i)). Ресурсы выделяются не сразу все, а в соответствии с текущим запросом. Считается, что все ресурсы i-го процесса будут освобождены по его завершении. Количество полученных ресурсов для i-го процесса обозначим Получ(i). Остаток в потребностях i-го процесса на ресурс R обозначим через Остаток(i). Признак того, что процесс может не завершиться -- это значение false для переменной Заверш(i). Наконец, переменная Своб_рес будет означать количество свободных единиц ресурса R, а максимальное количество ресурсов в системе определено значением Всего_рес. Описание данного алгоритма приведено в листинге 4.3.

 

BEGIN

Своб_рес := Всего_рес;

For i := 1 to N do

Begin

Своб_рес := Своб_рес - Получ(i)

Остаток(i) := Max(i) - Получ(i);

Заверш(i) := false; { процесс может не завершиться }

End;

flag := true; { признак продолжения анализа }

 

While flag do

begin

flag := false;

for i := 1 to N do

begin

if ( not ( Заверш(i) )) and ( Остаток(i) <= Своб_рес )

then

begin

Заверш(i) := true;

Своб_рес := Своб_рес + Получ(i);

Flag := true

end

end

end;

If Своб_рес = Bcero_pec

then {Состояние системы безопасное

и можно выдать ресурс }

else {Состояние не безопасное

и выдавать ресурс нельзя }

END.

 

Листинг 4.3. Алгоритм банкира Дейкстры

 

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

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

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

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

Рассмотренный алгоритм примитивен, в нем учитывается только один вид ресурса, тогда как в реальных системах количество различных типов ресурсов бывает очень большим. Были опубликованы варианты этого алгоритма для большого числа различных типов системных ресурсов. Однако все равно алгоритм не получил распространения. Причин тому несколько:

- Алгоритм исходит из того, что количество распределяемых ресурсов в системе фиксировано, постоянно. Иногда это не так, например, вследствие неисправности отдельных устройств.

- Алгоритм требует, чтобы пользователи заранее указывали свои максимальные потребности в ресурсах. Это чрезвычайно трудно реализовать.

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

Обнаружение тупика с последующим восстановлением

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

Очевидно, что незаблокированный процесс (он только что получил ресурс и по­этому не заблокирован) через некоторое время освобождает все свои ресурсы и затем благополучно завершается. Освобождение ранее занятых ресурсов может «разбудить» некоторые ранее заблокированные процессы, которые, в свою оче­редь, развиваясь, смогут освободить другие ранее занятые ресурсы. Это может продолжаться до тех пор, пока либо не останется незаблокированных процессов, либо какое-то количество процессов все же останется заблокированными. В по­следнем случае (если существуют заблокированные процессы при завершении указанной последовательности действий) начальное состояние S является состоя­нием тупика, а оставшиеся процессы находятся в тупике в состоянии S. В про­тивном случае S не есть состояние тупика.

Распознавание тупика требует дальнейшего восстановления.

 

Определение 4.11. Восстановление можно интерпретировать как запрет постоянного пребывания в опасном состоянии.

 

Существуют следующие методы восстановления:

- принудительный перезапуск системы, характеризующийся потерей информа­ции обо всех процессах, существовавших до перезапуска;

- принудительное завершение процессов, находящихся в тупике;

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

- перезапуск процессов, находящихся в тупике, с некоторой контрольной точ­ки, то есть из состояния, предшествовавшего запросу на ресурс;

- перераспределение ресурсов с последующим последовательным перезапус­ком процессов, находящихся в тупике.

 

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