АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

Обход тупика можно интерпретировать как запрет входа в опасное состояние. Если ни одно из упомянутых четырех условий не исключено, то вход в опасное состояние можно предотвратить при наличии у системы информации о последо­вательности запросов, связанных с каждым параллельным процессом. Доказано [92], что если вычисления находятся в любом неопасном состоянии, то сущест­вует по крайней мере одна последовательность состояний, которая обходит опас­ное. Следовательно, достаточно проверить, не приведет ли выделение затребо­ванного ресурса сразу же к опасному состоянию. Если да, то запрос отклоняется. Если нет, его можно выполнить. Определение того, является ли состояние опас­ным или нет, требует анализа последующих запросов процессов. Рассмотрим следующий пример. Пусть имеется система из трех вычислительных процессов, которые потребляют некоторый ресурс R типа SR, который выделя­ется дискретными взаимозаменяемыми единицами, причем существует всего де­сять единиц этого ресурса. В табл. 7.2 приведены сведения о текущем распреде­лении процессами этого ресурса R, об их текущих запросах на этот ресурс и о максимальных потребностях процессов в ресурсе R.

Последний столбец в табл. 7.2 показывает, сколько еще единиц ресурса может затребовать каждый из процессов, если получит ресурс на свой текущий запрос. Если запрос процесса А будет удовлетворен первым, то он в принципе может за­просить еще одну единицу ресурса R, и уже в этом случае мы тогда получим ту-

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

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

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

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

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

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

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

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

Begin

Своб_рес:- Всего_рес: For i:= 1 to N do Begin

Своб_рес:= Своб_рес - ПолучП) ОстатокО):= Max(i) - ПолучО);

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

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

flag:- false: for i:- 1 to N do begin

if (not (ЗавершО))) and (Остаток(1) <- Своб_рес) then begin

ЗавершП):= true; Своб_рес:- Своб_рес + ПолучШ: Flag:= true End End End: If Cso6_pec - Bcero_pec

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

и можно выдать ресурс else Состояние не безопасное и выдавать ресурс нельзя end.

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

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

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

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

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

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

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

Дата добавления: 2015-01-18 | Просмотры: 722 | Нарушение авторских прав