В. Столлингс - Операционные системы (1114679), страница 62
Текст из файла (страница 62)
Устранение взаимоблокировок до гчие трех необходимых условий возникновения взаимоблокировок, но ~ем меры к тому, чтобы ситуация взаимного блокирования процессов, ать достигнута. Соответственно, устранение взаимоблокировок обеспе ую параллельность вычислений, чем предотвращение. Решение о том, с Герман "устранение= несколько запутывает ситуациго. В некотором 'атриваемые в данном разделе стратегии можно считать примерами пре аимоблокировок. так как их использование деасгпвительно предотвраг4ае следи их. Ф Не запускать процесс, если его запросы могут привести к взаимоблокировке. ° Не удовлетворять запросы процесса, если их выполнение способно привести к взаимоблокировке. дапре1цение запуска процесса Рассмотрим систему из п процессов и т различных типов ресурсов. Определим гледукпцие векторы и матрицы: Общее количество каждого ресурса в системе Общее количество каждого ресурса, не выделенного процессам Ресурс = доступность = С.
Сгг - С„„ С„С," С„, Запросы каждого процесса на каждый из ресурсов 'А„А„. А„„') А„А„- А,,„~~ А„, А„, .- А„„, ~ Текущее распределение ресурсов Распределение = Матрица требований, в которой каждая строка описывает один из процессов, Указывает максимальные требования каждого процесса к разным ресурсам, т.е. С;,— зто требования процессом г ресурса г. Для работоспособности метода устранения взанмоблокировок эта информация должна быть объявлена процессом заранее. Аналогично„А„— текущее количество ресурса г, выделенное процессу к Должны выполняться следующие соотношения.
г,, =-- ь;. + ~ Аи для всех ~': все ресурсы либо свободны, либо выделены. 1. 2. . й, для всех й и г: ни один процесс не может потребовать ресурс, превышающий его общее количество в системе. 3. А <С ь — С,, для всех й и г: ни один процесс не может получить больше ресурсов, чем было затребовано им. д все указанные величины определены, мы в состоянии создать стратеКог а Ранения взаимоблокировок„которая запрещает запуск нового процесса, ~ Уст а лн требования ресурсов могут привести к взаимоблокировке. Новый просс р .
° ~ запускается только если В, ~ С,„.„, +,) Си для всех г. кущий запрос ресурса в случае его удовлетворения привести к возникновению гзмоблокировки, принимается в этом случае динамически (и, следовательно, при , пользовании данной технологии необходимо знать о том, какие ресурсы потребу,тся процессу в дальнейшем). Б этом разделе мы познакомимся с двумя подходами к устранению взаимоб„„кнровок. Часть 2 . б. Взаимоблокировка и голодание Р1 Р2 РЗ Р4 Вектор ресурсов й1 Р2 йЗ Матрица требований Вектор доступности йт Р2 йЗ Р1 Р2 РЗ Р4 Вектор доступности Матрица требований Матрица распределения б) Р2 выполнен до завершения й1 й2 йЗ Р1 Р2 Р4 Вектор доступности Матрицатребаваний Матрицараспределения в1 Р1 выполнен до завершения Р1 Р2 РЗ Р4 Р1 Р2 РЗ Р4 Вектор доступности Матрица требований Матрица распределения 'Часть 2 Зто означает, что запуск нового процесса произойдет только в том', 1и могут быть удовлетворены максимальные требования всех текутцизт.", , плюс требования запускаемого процесса.
Зта стратегия ни в коей ме тся оптимальной, поскольку предполагает худшее: что все процессы".' " г максимальные требования одновременно. з. 1прет вьщеления ресурса ',.у Стратегия запрета выделения ресурса, известная также как алгор ра,а впервые была предложена в работе 101)К65]. Мы начнем рассмо. "' нцепций состояния (в1аФе) и безопасного состояния (ваХе в(а1.е). Ост системе с фиксированным количеством процессов и фиксированным,,:-' " юм ресурсов. В каждый момент времени процесс может иметь нескод'"' пенных ему ресурсов (или не иметь нн одного). Состояние системы ет собой проста текущее распределение ресурсов по процессам. СледовЩ :тояние можно представить как два ранее определенных вектора— ступности — и две матрицы — требований и распределения.
Безопа' ' зяиие — это такое состояние, в котором имеется по крайней мере о вательность, которая не приводит к взаимоблокировке (т.е. все проц г быть выполнены до завершения). Состояние, не являющееся безопасвв' вается, соответственно, опасным состоянием. Описанную концепцию иллюстрирует приведенный далее пример. Н»:" казана состояние системы, образованной четырьмя процессами и тремя щее количество ресурсов В1, В2 и ВЗ составляет соответственно 9, 3 и $;, результате сделанного к этому моменту распределения ресурсов по проц„ пными остались по одной единице ресурсов В2 и ВЗ.
Безопасно ли :е? Для ответа на этот вопрос зададимся другим вопросом, а именно— кой-нибудь из четырех процессов быть выполнен при данных доступных завершения? Или, говоря иначе, могут ли при данном распределении"." пъ удовлетворены максимальные требования какого-то из процессов за-,"' вшихся ресурсов? Ясно, что для процесса Р1 это невозможно, так как у ся только одна единица ресурса В1, и для полного удовлетворения ему' ~е по две единицы ресурсов В1, В2 и ВЗ.
Однако если выделить процесс)т,; иницу ресурса ВЗ, то будут удовлетворены максимальные требования сса и он сможет быть завершен. ч гтейкстра воепальзовалея таким названием, сравнивая эту задачу е тью баитса„где клиент, который хочет осуществить заем денег, отождес оиессан, а деньги — с ресурсам. Банк имеет ограниченное количество денез"ч в, и список клиентов, у каждого из которых имеется свая предельная вел та.
Клиент может неоднократно осущестпвлять заем в пределах этой вели,. м иет никакаи гарантии, что ои погасит хотя бы часть задолженности дат 'нта, пока не заимет всю возможную сумму. Таким образом, если несколько, аупт частичные займы, та гарантиравапть возврат этпих денег банку мож который резервныи фанд. В худтисм случае, тсогда все клиенты пагаигаят тлька по достижении ими предельной суммы кредита.
этот Фонд должен змажность выдать им эти максимальные суммы. Следовотпельио, при исч жных запасов да размеров резервного т2танда банк будет выиулсдеи отказа ~ клиенту в предоставлении займа, иначе деньги в банк мазут никогда не в т1 РЗ выполнен до завершения Рис. 6.6. Определение безопаснага состояния П е Р дположим, что именно так и произошло — процесс Р2 оказался заверптен, „ Распределенные ему ресурсы вернулись в пул доступных. Зто состояние систем т оказано на рис. б.б,б. Вернувшись к вопросу о том, какой из процес- в м„..
' т быть завершен в данной ситуации, мы находим, что могут быть удовы максимальные требования как процесса Р1, так и процесса РЗ. Пред~творены что мы выбрали процесс Р1. По его завершении и возвращении захваоло~ „ * "ых им м Ресурсов в пул доступных ситуация будет выглядеть так как :,.оказ „„„ Ф о на рпс.
6.6,в. И, наконец, по завершении процесса РЗ мы придем к соявию,,з , изображенному на рис. 6.6,г. К этому моменту все процессы завершеаэ еде ° 'ледовательно, исходное состояние (рис. 6.6,а) является безопасным. а б. Взаимоблокировка и голодание Ббт";об БЬ" Ье ".~ь геяопгсе )тп); 1пб аьа11аЬ1е~>а)т )т«. «Б1а1п~)п«) ттп); а11ос~п) ~>а); 9,.:,3 ! Р1 Р2 РЗ Р4 Матрица требований Матрица распределения 1 ««,в а) Начальное состояние 0 ' 1'4"., Р "1 Р2 РЗ Р4 Матрица требований Матрицараспределения 333 Часть 2.
П 32 Описанная концепция автоматически приводит к стратегии ус аимоблокировок, которая гарантирует, что система процессов и рес а находится в безопасном состоянии. Когда процесс делает запрос к ие'. ,т множеству ресурсов, предполагается, что запрос удовлетворен, после ' ' ,деляется, является ли обновленное состояние системы безопасным. к, то запрос удовлетворяется; в противном случае процесс блокируетса.". >р, пока удовлетворение его запроса не станет безопасным. Рассмотрим состояние, определяемое матрипей на рис.
6.7,а. Бреди о процесс Р2 делает запрос на одну дополнительную единицу ресурса В:," л — ресурса ВЗ. Если запрос будет выполнен, то в результате состояние':: ы станет таким, как показано на рис. 6.6,а, Мы уже видели, что зто >ляется безопасным. Таким образом, запрос можно удовлетворить. Тецв'. .моя к состоянию, представленному на рис.
6,7,а, и предположим, чт~:; Е ЗаПрОС На ОдНу дОПОЛНИтЕЛЬНуЮ ЕдИНИцу рЕСурСа В1 И ОдНу — рЕСуревет,.'-;- >ет процесс Р1. Если этот запрос будет удовлетворен, состояние системи';.;' >ким, как показано на рис. 6.7,б. Является ли это состояние безопа е тнном случае ответ — нет, поскольку каждому из процессов требуется ' >полнительной единице ресурса В1, а в наличии свободных единиц этого:;" > уже нет. Следовательно, запрос процесса Р1 должен быть отклонейв.-.' зоцесс блокирован.
б) Процесс Рт запрашивает по одной единице ресурсов В1 и ЙЗ Рве. 6.7. Определение опасного состояния Важно отметить, что состояние, представленное на рис. 6.7,б, не >аимоблокировкой. Оно всего лишь может привести к ней. Например.,; >те процесс Р1 может освободить по одной единице ресурсов В1 и ВЗ, и ювь вернется в безопасное состояние. Следовательно, стратегия ус япмоблокировок не занимается точным предсказанием взаимоблокировок; она „ттттть предвидит их возможность и устраняет ее.
В листинге 6.1 приведена логика работы алгоритма устранения взаимоблакир .ирт>вок. Основной алгоритм показан в части б. Состояние системы описывается руктурой Ббабе, а вектор геаиевт ) *) определяет ресурсы, затребованные процессом 1. Сначала выполняется проверка того, что запрос не превышает ис, дные требования процесса. Если запрос корректен, то следующий шаг алгоитмя состоит в определении возможности удовлетворения запроса тт.е. выясне„ни, достаточно ли для этого свободных ресурсов).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
