Модель пространства состояний системы

Приведем еще одну формальную модель (она подробно рассмотрена в работе [54]). Эта модель очень проста, однако она позволяет сформулировать, что нам нужно делать, чтобы не попасть в тупиковое состояние.

' Напомним, что деревом в теории графов называют граф, не имеющий циклов.

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

Пусть состояние операционной системы сводится к состоянию различных ресур­сов в системе (свободны они или выделены какому-нибудь процессу). Состояние системы изменяется процессами, когда они запрашивают, приобретают или осво­бождают ресурсы — это единственно возможные действия (точнее, мы принимаем во внимание только такие действия). Если процесс не блокирован в данном состо­янии, он может изменить это состояние на новое. Однако так как в общем случае невозможно знать априори, какой путь может избрать произвольный процесс в своей программе (это неразрешимая проблема!), то новое состояние может быть любым из конечного числа возможных. Следовательно, процессы нами будут трак­товаться как недетерминированные объекты. Введенные ограничения на извест­ные понятия приводят нас к нескольким формальным определениям.

□ Система есть пара , где

— множество состояний системы

— множество процессов

□ Процесс Р_; есть частичная функция, отображающая состояние системы в непу­
стые подмножества ее же состояний. Это обозначается так:

Если процесс Р; определен на состоянии S, то область значений обозначается как . Если , то мы говорим, что может изменить состояние S,. в

состояние S_k посредством операции, и используем обозначение Наконец, запись означает, что для некоторо-

го i, или для некоторых i и S_k, причем

Другими словами, система может быть переведена посредством n > О операций с помощью m > 0 различных процессов из состояния S_t. в состояние S_w. Мы говорим, что процесс заблокирован в данном состоянии, если он не может из­менить состояние, то есть в этом состоянии процесс не может ни требовать, ни получать, ни освобождать ресурсы. Поэтому справедливо следующее. Процесс Р_: заблокирован в состоянии S,,, если не существует ни одного состояния

,такого что , причем

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

Процесс находится в тупике в состоянии , если для всех состояний , таких что , процесс Р, блокирован в состоянии

Приведем пример. Определим систему :

формальные модели для изучения проблемы тупиковых ситуаций_______________ 261

Некоторые возможные последовательности изменений для этой системы таковы:

Последовательность может быть реализована, например, следующим

образом: или же

Заметим, что процесс находится в тупике как в состоянии , так и в состоянии ; для последнего случая или и процесс не оказыва-

ется заблокированным ни в , ни в

Диаграмма переходов этой системы изображена на рис. 8.7.

Рис. 8.7. Пример системы <!!!!!!!!!!!!!!!!!!!!о, я> на четыре состояния

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

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

Состояние есть безопасное состояние, если для всех , таких что не является тупиковым состоянием.

Рассмотрим еще один пример системы . Граф ее состояний приведен на

рис. 8.8. Здесь состояния S₂ и S₃ являются безопасными; из них система никогда не сможет попасть в тупиковое состояние. Состояния S, и S₄ могут привести как к безопасным состояниям, так и к опасному состоянию S₅. Состояния S₆ и S₇ явля­ются тупиковыми.

Наконец, в качестве еще одной простейшей системы вида <!!!!!!!!!!!а, п> приведем пример тупика с ресурсами типа SR, уже рассмотренный нами ранее и проиллюстриро­ванный рис. 8.3. Для этого определим состояния процессов Pj и Р₂, которые ис­пользуют ресурсы R, и R₂ (табл. 8.1).

Пусть состояние системы означает, что процесс находится в состоянии , а процесс Р₂ — в состоянии . Возможные изменения в пространстве состояний

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

этой системы изображены на рис. 8.9. Вертикальными стрелками показаны воз­можные переходы из одного состояния в другое для процесса Р,, а горизонтальны­ми — для процесса Р₂. В данной системе имеется три опасных состояния: S₂₂, S₂₃ и S₃₂. Попав в любое из них, мы неминуемо перейдем в тупиковое состояние S₃₃.

Рис. 8.8. Пример системы <а, !!!!!!!!!!п> с безопасными, опасными и тупиковым состояниями

Рис. 8.9. Модель системы из двух процессов

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

Таблица 8.1. Состояния процессов Р, и Р₂ при использовании ресурсов R, и R₂

Р, Описание Р₂ Описание

0 Не держит никаких ресурсов 0 Не держит никаких ресурсов

1 Запросил ресурс R_2l не держит 1 Запросил ресурс R,, не держит
никаких ресурсов никаких ресурсов

2 Держит ресурс R₂ 2 Держит ресурс R,

3 Запросил ресурс R,, держит ресурс R₂ 3 Запросил ресурс R₂, держит ресурс R,

4 Держит ресурсы R, и R₂ 4 Держит ресурсы R, и R₂

5 Держит ресурс R₂ после освобождения 5 Держит ресурс R₂ после освобождения
ресурса R, ресурса R,

Теперь, когда мы знаем понятия надежного, опасного и безопасного состояний, можно рассмотреть методы борьбы с тупиками.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Потребность потребностей

А 2 3 6 1

В 3 2 7 2

С______________ 2__________ 3_________ 5________________ _0________________________

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

Обнаружение тупика

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

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

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

Обнаружение тупика посредством редукции графа повторно используемых ресурсов

Наиболее благоприятные условия для незаблокированного процесса Р_; могут быть представлены редукцией (сокращением) графа повторно используемых ресурсов (см. описание модели Холта ранее в разделе «Понятие тупиковой ситуации при выполнении параллельных вычислительных процессов»). Редукция графа может быть описана следующим образом.

- Граф повторно используемых ресурсов сокращается процессом Р_:, который не является ни заблокированной, ни изолированной вершиной, путем удаления всех ребер, входящих в вершину Р_: и выходящих из P_h Эта процедура является эквивалентной приобретению процессом Р, неких ресурсов, на которые он ра­нее выдавал запросы, а затем освобождению всех его ресурсов. Тогда Pj стано­вится изолированной вершиной.

- Граф повторно используемых ресурсов несокращаем (не редуцируется), если

он не может быть сокращен ни одним процессом. - Граф ресурсов типа SR является полностью сокращаемым, если существует

последовательность сокращений, которая удаляет все дуги графа.

Лемма: для ресурсов типа SR порядок сокращений дуг графа повторно используе­мых ресурсов несуществен; все последовательности ведут к одному и тому же не­сокращаемому графу.

Допустим, что лемма неверна. Тогда должно существовать некоторое состояние S, которое сокращается до некоторого несокращаемого состояния S, с помощью пос­ледовательности seq, и до несокращаемого состояния S₂ с помощью последователь­ности seq₂ так, что (то есть все процессы в состояниях S, и S₂ или заблокиро­ваны, или изолированы).

Если сделать такое предположение, то мы приходим к противоречию, которое устраняется только при условии, что S, = S₂. Действительно, предположим, что последовательность seq, состоит из упорядоченного списка процессов (Р„ Р₂, .... Р_к). Тогда последовательность seq, должна содержать процесс Р, который не содер­жится в последовательности seq₂. В противном случае S, = S₂, потому что редукция графа только удаляет дуги, уже существующие в состоянии S, а если последо­вательности seq, и seq₂ содержат одно и то же множество процессов (пусть и в раз-

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

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

- Имеет место соотношение , так как вершина S может быть редуцирована
процессом Р, а состояние S₂ должно, следовательно, также содержать процесс Р,.

- Пусть . Однако поскольку после редукции процессами P_i?

возможно еще сокращение графа процессом P_j+I, это же самое дол­жно быть справедливо и для последовательности seq₂ независимо от порядка следования процессов. То же самое множество ребер графа удаляется с помо­щью процесса Р;. Таким образом,

Следовательно, для i = 1, 2,..., к и Р не может существовать, а это противоре-

чит нашему предположению, что . Следовательно, Si = S₂.

Теорема о тупике: Состояние S есть состояние тупика тогда и только тогда, когда граф повторно используемых ресурсов в состоянии S не является полностью со­кращаемым.

- Для доказательства предположим, что состояние S есть состояние тупика, и
процесс Pi находится в тупике в S. Тогда для всех , таких что про­
цесс Pj заблокирован в состоянии Sj (по определению). Так как сокращения гра­
фа идентичны для серии операций процессов, то конечное несокращаемое
состояние в последовательности сокращений должно оставить процесс Pj бло­
кированным. Следовательно, граф не является полностью сокращаемым.

- Предположим теперь, что состояние S не является полностью сокращаемым. Тогда существует процесс Р,, который остается заблокированным при всех воз­можных последовательностях операций редукции в соответствии с леммой (см. выше). Так как любая последовательность операций редукции графа по­вторно используемых ресурсов, оканчивающаяся несокращаемым состоянием, гарантирует, что все ресурсы типа SR, которые могут когда-либо стать доступ­ными, в действительности освобождены, то процесс Р_; навсегда заблокирован и, следовательно, находится в тупике.

Первое следствие: процесс Р; не находится в тупике тогда и только тогда, когда серия сокращений приводит к состоянию, в котором Р_: не заблокирован.

Второе следствие: если S есть состояние тупика (по ресурсам типа SR), то по край­ней мере два процесса находятся в тупике в S.

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

Граф повторно используемых ресурсов может быть представлен матрицами или списками. В обоих случаях экономия памяти может быть достигнута за счет взве-

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

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

Рассмотрим вариант с матричным представлением. Поскольку граф двудольный, он представляется двумя матрицами размером n x m. Одна матрица — матрица распределения , в которой элемент отражает количество единиц R, ре-

сурса, выделенного процессу , то есть где — это дуга между

вершинами и .ведущая из в Pj. Вторая матрица — матрица запросов ,

где

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

Здесь — вершина, представляющая ресурс, — вес дуги, то есть Подобным образом и ресурсы, запрошенные процессом , связаны вместе.

Аналогичные списки создаются и для ресурсов (списки распределенных и запро­шенных ресурсов):

Здесь

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

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

является обратная последовательность, то есть , а также в случае,

когда процесс запрашивает все m ресурсов. Тогда число проверок процессов равно:

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

Более эффективный алгоритм может быть получен за счет хранения некоторой дополнительной информации о запросах. Для каждой вершины процесса опре­деляется так называемый счетчик ожиданий w, отображающий количество ресур­сов (не число единиц ресурса), которые в какое-то время вызывают блокировку процесса. Кроме того, можно сохранять для каждого ресурса запросы, упорядо­ченные по размеру (числу единиц ресурса). Тогда следующий алгоритм сокраще­ний, записанный на псевдокоде, имеет максимальное время выполнения, пропор­циональное m х n.

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

For all P !!!!!!!!!!1 L do

Begin for all R₃ з |(Rj.P)| > 0 do Begin r, := i-j + |(R,.P)|:

For all P, э 0 < "| CPi.Rj) | <= Tj do Begin w, := w, - 1;

If w, = 0 then L := L U {Pi}
End
End
End
Deadlock := Not (L = {PI. P2... Pn}):

Здесь L — это текущий список процессов, которые могут выполнять редукцию гра­фа. Можно сказать, что L = {P_f | w, = 0}. Программа выбирает процесс Р из списка L, процесс Р сокращает граф, увеличивая число доступных единиц rj всех ресурсов fy, распределенных процессу Р, обновляет счетчик ожидания w, каждого процесса Р₍, который сможет удовлетворить свой запрос на частный ресурс Rj, и добавляет Р₍ к L, если счетчик ожидания становится нулевым.

Методы обнаружения тупика по наличию замкнутой цепочки запросов

Структура графа обеспечивает простое необходимое (но не достаточное) условие для тупика. Для любого графа G = <Х, Е> и вершины х I X пусть Р(х) обозначает множество вершин, достижимых из вершины х, то есть

Можно сказать, что в ориентированном графе потомством вершины х, обозначен­ным как Р(х), называется множество всех вершин, в которые ведут пути из х.

Тогда если существует некоторая вершина то в графе G имеется

цикл.

Первая теорема; цикл в графе повторно используемых ресурсов является необхо­димым условием тупика.

Для доказательства этой теоремы (которое мы опустим¹) можно воспользоваться следующим свойством ориентированных графов: если ориентированный граф не содержит цикла, то существует линейное упорядочение вершин такое, что если существует путь от вершины i к вершине], то i появляется перед j в этом упорядо­чении.

Вторая теорема: если S не является состоянием тупика и где есть

состояние тупика, в том и только в том случае, когда операция процесса есть запрос и находится в тупике в

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

' При желании его можно найти в [54].

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

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

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

Пучок, или узел, в ориентированном графе G = <Х, Е> — это подмножество вер­шин Z I X, таких что х I Z, Р(х) = Z, то есть потомством каждой