Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 68
Текст из файла (страница 68)
Разработано несколько подходов к разрешению этой проблемы, однако ни один из них нельзясчитать панацеей. В некоторых случаях цена, которую приходится платить за то,чтобы освободить систему от тупиков, слишком высока. Кстати, именно по этойпричине нам не так уж редко приходится сталкиваться с тупиковыми ситуациями.В других случаях, например в системах управления процессами реального времени, просто нет иного выбора, как идти на значительные затраты, поскольку возникновение тупика может привести к катастрофическим последствиям.Проблема борьбы с тупиками становится все более актуальной и сложной по мереразвития и внедрения параллельных вычислительных систем. При проектировании таких систем разработчики стараются проанализировать возможные тупиковые ситуации, используя специальные модели и методы.
Борьба с тупиковымиситуациями основывается на одной из трех стратегий:• предотвращение тупика;• обход тупика;Q распознавание тупика с последующим восстановлением.Предотвращение тупиковПредотвращение тупика основывается на предположении о чрезвычайно высокой° стоимости, поэтому лучше потратить дополнительные ресурсы системы, чтооыисключить вероятность его возникновения при любых обстоятельствах. Этотподход используется в наиболее ответственных системах, обычно в системах реального времени.егРедотвращение можно рассматривать как запрет существования опасных состоИи.
Поэтому подсистема распределения ресурсов, предотвращающая тупик,окна гарантировать, что ни одного из четырех условий, необходимых для еговступления, не возникнет.н264Глава 8. Проблема тупиков и методы борьбы с нимцQУсловие взаимного исключения можно подавить путем разрешения неограниченного разделения ресурсов. Это удобно для повторно входимых программ и рядадрайверов, но совершенно неприемлемо для совместно используемых переменных в критических секциях.•Условие ожидания можно подавить, предварительно выделяя ресурсы.
При этомпроцесс может начать исполнение, только получив все необходимые ресурсызаранее. Следовательно, общее число затребованных параллельными процессами ресурсов должно быть не больше возможностей системы. Поэтому предварительное выделение может привести к снижению эффективности работывычислительной системы в целом. Необходимо также отметить, что предварительное выделение ресурсов зачастую невозможно, так как реально необходимые ресурсы становятся известны процессу только в ходе исполнения.•Условие отсутствия перераспределения можно исключить, позволяя операционной системе отнимать у процесса ресурсы. Для этого в операционной системе должен быть предусмотрен механизм запоминания состояния процесса сцелью последующего восстановления хода вычислений.
Перераспределениепроцессора реализуется достаточно легко, в то время как перераспределениеустройств ввода-вывода крайне нежелательно.QУсловие кругового ожидания можно исключить, предотвращая образование цепизапросов. Это можно обеспечить с помощью принципа иерархического выделения ресурсов. Все ресурсы образуют некоторую иерархию. Процесс, затребовавший ресурс на одном уровне, может затем потребовать ресурсы только на болеевысоком уровне. Он может освободить ресурсы на данном уровне, только после освобождения всех ресурсов на всех более высоких уровнях. После того какпроцесс получил, а потом освободил ресурсы данного уровня, он может запросить ресурсы на три же самом уровне.
Пусть имеются процессы Пр1 и Пр2,которые могут иметь доступ к ресурсам R1 и R2, причем R2 находится на болеевысоком уровне иерархии. Если процесс Пр1 захватил ресурс R1, то процессПр2 не может захватить ресурс R2, так как доступ к нему проходит через доступ к ресурсу R1, который уже захвачен процессом Пр1. Таким образом, создание замкнутой цепи исключается. Иерархическое выделение ресурсов часто недает никакого выигрыша, если порядок использования ресурсов, определенныйв описании процессов, отличается от порядка уровней иерархии.
В этом случаересурсы будут расходоваться крайне неэффективно.В целом стратегия предотвращения тупиков — это очень дорогое решение проблемы тупиков, и эта стратегия используется нечасто.Обход тупиковОбход тупика можно интерпретировать как запрет входа в опасное состояние. Еслини одно из упомянутых четырех условий не исключено, то вход в опасное состояние можно предотвратить при наличии у системы информации о последовательности запросов, связанных с каждым параллельным процессом. Доказано [54J, чесли вычисления находятся в любом неопасном состоянии, то существует, по кра ней мере, одна последовательность состояний, которая обходит опасное состоpM l°gblб°Рь б ы с265тупикамиие.
Следовательно, достаточно проверить, не приведет ли выделение затребовано ресурса сразу же к опасному состоянию. Если да, то запрос отклоняется, еслиего можно выполнить. Определение того, является состояние опасным илиеТнет', требует анализа последующих запросов от процессов.Рассмотрим следующий пример. Пусть имеется система из трех вычислительныхпроцессов, потребляющих некоторый ресурс R типа SR; который выделяется дискретными взаимозаменяемыми единицами, причем существует всего десять единиц этого ресурса.
В табл. 8.2 приведены сведения о текущем распределении процессами этого ресурса R, об их текущих запросах на этот ресурс и о максимальныхпотребностях процессов в ресурсе R.оГТаблица 8 . 2 . Пример распределения ресурсовИмя процессаВыделеноЗапросМаксимальнаяпотребностьОстатокпотребностей23613272235ОПоследний столбец в таблице показывает нам, сколько еще единиц ресурса можетзатребовать каждый из процессов, если бы он получил ресурс на свой текущийзапрос.Если запрос процесса А будет удовлетворен первым, то он в принципе может запросить еще одну единицу ресурса R, и уже в этом случае мы получим тупиковуюситуацию, поскольку ни один из наших процессов не сможет продолжить своивычисления. Следовательно, при выполнении запроса процесса А мы попадаем вненадежное1 состояние.Если первым будет выполнен запрос процесса В, то у нас останется свободной ещеодна единица ресурса R.
Однако если процесс В запросит еще две, а не одну единицу ресурса R, а он может это сделать, то мы опять получим тупиковую ситуацию.Если же мы сначала выполним запрос процесса С и выделим ему не две (как процессу В), а все три единицы ресурса R, то у нас не останется никакого резерва, нопроцесс С сможет благополучно завершиться и вернуть системе все свои ресурсы,поскольку на этом его потребности в ресурсах заканчиваются. Это приведет к тому,что свободное количество ресурса R станет равно пяти.
После этого уже можнобудет удовлетворить запрос либо процесса В, либо процесса А, но не обоих сразу.Часто бывает так, что последовательность запросов, связанных с каждым процессом, заранее не известна. Но если заранее известен общий запрос на ресурсы кажД°! о типа, то выделение ресурсов можно контролировать. В этом случае необходи0Для каждого требования, в предположении, что оно удовлетворено, определить,УЩествует ли среди общих запросов от всех процессов некоторая последовательРмин «ненадежное состояние» не предполагает, что в данный момент существует пли в какое-тоРемя обязательно возникнет тупиковая ситуация.
Он просто говорит о том, что в случае некоторойлагоприятпой последовательности событий система может зайти в тупик.266Глава 8. Проблема тупиков и методы борьбыс н и ц иность требований, которая может привести к опасному состоянию. Данный под.ход является примером контролируемого выделения ресурса.Классическое решение этой задачи предложено Дейкстрой и известно как алгоритм банкира [53].
Алгоритм банкира напоминает процедуру принятия решенияо том, может ли банк безопасно для себя дать взаймы денег. Принятие решенияосновывается на информации о потребностях клиента (нынешних и максимальновозможных в принципе) и учете текущего баланса банка. Хотя этот алгоритм практически нигде не используется, рассмотрим его, так как он интересен с методической и академической точек зрения.Пусть существует N процессов, для каждого из которых известно максимальноеколичество потребностей в некотором ресурсе R (обозначим эти потребности через Max(i)).
Ресурсы выделяются не сразу все, а в соответствии с текущим запросом. Считается, что все ресурсы i-ro процесса будут освобождены по его завершении.Количество полученных ресурсов для i-ro процесса обозначим Получ^'). Остатокв потребностях i-ro процесса на ресурс R обозначим через Остаток^'). Признак того,что процесс может не завершиться, — это значение false для переменной Заверши).Наконец, переменная Своб_рес будет означать количество свободных единиц ресурса R, а максимальное количество ресурсов в системе определено значением Всего_рес.
Текст программы алгоритма банкира приведен в листинге 8.4.Листинг 8.4. Алгоритм банкира ДейкстрыBeginСвоб_рес := Всего_рес;For i := 1 to N doBeginСвоб_рес := Своб_рес - ПолучШ;ОстатокП) := Max(i) - ПолучО);ЗавершО) := false; { процесс может не завершиться }End:flag := true:{ признак продолжения анализа }while flag dobeginflag := false;for i := 1 to N dobeginif ( not ( ЗавершП) )) and ( ОстатокО) <= Своб_рес )then beginЗаверш(i) := true;Своб_рес := СвоО_рес + ПолучП);Flag := trueEndEndEnd;If СвоО_рес = Bcero_pecthenСостояние системы безопасное.и можно выдать ресурсelseСостояние небезопасное.и выдавать ресурс нельзяend.Каждый раз, когда что-то может быть выделено из числа остающихся незанять ^ресурсов, предполагается, что соответствующий процесс работает, пока не о1\/1ЙТОДЫ борьбы с тупиками267чптся, а затем его ресурсы освобождаются.
Если в конце концов все ресурсы освобождаются, значит, все процессы могут завершиться и система находится в безопасном состоянии. Другими словами, согласно алгоритму банкира система удовлетворяет только те запросы, при которых ее состояние остается надежным. Новоесостояние безопасно тогда и только тогда, когда каждый процесс может окончиться Именно это условие и проверяется в алгоритме банкира.
Запросы процессов,приводящие к переходу системы в ненадежное состояние, не выполняются и откладываются до момента, когда их можно будет выполнить.Алгоритм банкира позволяет продолжать выполнение таких процессов, которымв случае системы с предотвращением тупиков пришлось бы ждать. Хотя алгоритмбанкира относительно прост, его реализация может обойтись довольно дорого.Основным накладным расходом стратегии обхода тупика с помощью контролируемого выделения ресурса является время выполнения алгоритма, так как он выполняется при каждом запросе. Причем, алгоритм работает наиболее медленно,когда система близка к тупику.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
