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

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