Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 67
Текст из файла (страница 67)
8.5.О,ЛЭ5ОР13Рис. 8.5. Сеть Петри для системы двух взаимодействующих процессовЭта сеть соответствует примеру тупиковой ситуации, которая возникает привзаимодействии процессов Пр1 и Пр2 во время передачи сообщений и потреблении ресурса R каждым из процессов (см. листинг 8.3). Начальная маркировка для сети, показанной на рис. 8.5, будет равна (1, 0, 0, 0, 0, 4, 0, 0, 1, 0, 0, 0, 0).Здесь позиция р2 означает, что процесс Пр1 получил три единицы ресурса RДуга, соединяющая позицию рй (число маркеров в ней соответствует количеству доступных единиц ресурса R), имеет вес 3, и при срабатывании перехода цпроцесс Пр1 получает затребованные три единицы ресурса.
Переход t2 представляет посылку процессом Пр1 сообщения для Пр2; переход t 5 — прием этогосообщения. Появление маркера в позиции р7 означает, что процесс Пр2 обработал сообщение и послал ответ процессу Пр1. Срабатывание перехода tA преД"ставляет возврат в систему трех единиц ресурса, которыми владел процесс ПрРассмотренная сеть не является живой, так как в ней всегда будут мертвы преходы t3, L, tr„ t7 и t&.Примеру тупиковой ситуации, возникающей при работе с ресурсами типа о(см. рис. 8.3), соответствует сеть Петри, показанная на рис.
8.6.реальные модели для изучения проблемы тупиковых ситуаций259Рис. 8.6. Сеть Петри для тупиковой ситуации на ресурсах типа SRВ этой сети номера переходов соответствуют отмеченным номерам операторов,которые выполняют процессы Пр1 и Пр2, а позиции р, и р 2 — семафорам S1 и S2,над которыми выполняются операции Р и V.
Сеть на рис. 8.6 также не являетсяживой, хотя для нее и существуют последовательности срабатывания переходов,не ведущие к тупиковой ситуации.Сети Петри могут быть использованы для анализа системы на возможность возникновения в ней тупиковых ситуаций. При таком анализе исследуется пространство возможных состояний сети Петри, под которым понимается множество возможных маркировок сети. Для анализа сетей посредством матричных методовхарактерно множество проблем, поэтому в основном используется подход, основанный на построении редуцированного до дерева1 графа возможных маркировок121]. В таком дереве вершины графа — это состояния (маркировки) сети, а ветвиДерева, помеченные соответствующими переходами сети, — это возможные изменения состояний сети, то есть срабатывания ее переходов.Модель пространства состояний системыПриведем еще одну формальную модель (она подробно рассмотрена в работе [54]).та модель очень проста, однако она позволяет сформулировать, что нам нужноать> чтобы не попасть в тупиковое состояние.Нал°Мпим, что деревом в теории графов называют граф, не имеющий циклов.260Глава 8.
Проблема тупиков и методы борьбы с нимиПусть состояние операционной системы сводится к состоянию различных ресурсов в системе (свободны они или выделены какому-нибудь процессу). Состояниесистемы изменяется процессами, когда они запрашивают, приобретают или освобождают ресурсы — это единственно возможные действия (точнее, мы принимаемво внимание только такие действия). Если процесс не блокирован в данном состоянии, он может изменить это состояние на новое.
Однако так как в общем случаеневозможно знать априори, какой путь может избрать произвольный процесс всвоей программе (это неразрешимая проблема!), то новое состояние может бытьлюбым из конечного числа возможных. Следовательно, процессы нами будут трактоваться как недетерминированные объекты. Введенные ограничения на известные понятия приводят нас к нескольким формальным определениям.О Система есть пара <о, п>, гдеа — множество состояний системы { S,, S2, S3,..., S„};я — множество процессов { Р ( , Р 2 , Р 3 , -, Рк }•Q Процесс Р, есть частичная функция, отображающая состояние системы в непустые подмножества ее же состояний.
Это обозначается так:Р,: G ^ { Q } .Если процесс Р: определен на состоянии S, то область значений Р: обозначаетсякак Pj(S). Если Sk e Pj(Sc), то мы говорим, что Pj может изменить состояние S(, всостояние Sk посредством операции, и используем обозначение Sc — - — > Sk.Наконец, запись Sc. —-—> S„, означает, что Se = Sw, или St, — - — > Sw для некоторого i, или Sc — - — > Sk для некоторых i и Sk, причем Sk —-—> S„..Другими словами, система может быть переведена посредством п > 0 операцийс помощью m > 0 различных процессов из состояния Sc в состояние Sw.Мы говорим, что процесс заблокирован в данном состоянии, если он не может изменить состояние, то есть в этом состоянии процесс не может ни требовать, ниполучать, ни освобождать ресурсы. Поэтому справедливо следующее.Процесс Р; заблокирован в состоянии St„ если не существует ни одного состоянияSk, такого что S c —2—> Sk, причем Pj(Sc) = 0.Далее, мы говорим, что процесс Pi находится в тупике в данном состоянии Sc, еслион заблокирован в состоянии SL.
и если вне зависимости от того, какие операции(изменения состояний) произойдут в будущем, процесс Pj остается заблокированным. Поэтому дадим еще одно определение.Процесс Р; находится в тупике в состоянии Sc, если для всех состояний Sk, такихчто Sc —-—> Sk, процесс Р, блокирован в состоянии Sk.Приведем пример. Определим систему <а, я>:a = {S 1 ,S 2 ,S 3 ,S 4 };тг = {Р 1 ,Р 2 };P 1 (S,) = {S 2 ,S 3 };P 2 (S,) = {S 3 };P I (S 2 ) = 0;P 2 (S 2 ) - { S,, S 4 };P,(S 3 ) - { S 4 );P,(S.) = { S 3 };P 2 (S 3 ) = 0;P 2 (S 4 ) = 0.формальные модели для изучения проблемы тупиковых ситуаций261Некоторые возможные последовательности изменений для этой системы таковы:S.--> S3; S2-> S4; S,•*s 4 .Последовательность S, —-—> S4 может быть реализована, например, следующимйобразом: S ( — ^ — * S2; S 2 — — * S 4 или же S, —3—> S3; S 3 —S—> S4.Заметим, что процесс Р2 находится в тупике как в состоянии S3, так и в состоянииS • для последнего случая S2 — s — > S4 или S2—> Su и процесс Р, не оказывается заблокированным ни в S4, ни в S,.Диаграмма переходов этой системы изображена на рис.
8.7.Рис. 8.7. Пример системы <<т, п> на четыре состоянияСостояние S называется тупиковым, если существует процесс Р;, находящийся в тупике в состоянии S.Теперь мы можем сказать, что, по определению, тупик предотвращается при введении такого ограничения на систему, чтобы каждое ее возможное состояние небыло тупиковым состоянием.Введем еще одно определение.Состояние Sj есть безопасное состояние, если для всех Sk, таких что S, —-—> Sk, Skне является тупиковым состоянием.Рассмотрим еще один пример системы <о, it>.
Граф ее состояний приведен наРис. 8.8. Здесь состояния S2 и S3 являются безопасными; из них система никогда несможет попасть в тупиковое состояние. Состояния S, и S4 могут привести как кбезопасным состояниям, так и к опасному состоянию S5. Состояния S6 и S7 является тупиковыми.Наконец, в качестве еще одной простейшей системы вида <а, п> приведем примертупика с ресурсами типа SR, уже рассмотренный нами ранее и проиллюстрированный рис.
8.3. Для этого определим состояния процессов Р( и Р 2 , которые используют ресурсы Rl и R2 (табл. 8.1).*Усть состояние системы Sy означает, что процесс Р! находится в состоянии S,,процесс Р2 — в состоянии Sj. Возможные изменения в пространстве состояний262Глава 8. Проблема тупиков и методы борьбы с\н\лмцэтой системы изображены на рис. 8.9. Вертикальными стрелками показаны возможные переходы из одного состояния в другое для процесса Р,, а горизонтальными — для процесса Р 2 .
В данной системе имеется три опасных состояния: S22, S 23 иS32. Попав в любое из них, мы неминуемо перейдем в тупиковое состояние S33.Рис. 8.8. Пример системы <а, п> с безопасными, опасными и тупиковым состояниямиРис. 8.9. Модель системы из двух процессов263Таблица 8 . 1 . Состояния процессов Р, и Р г при использовании ресурсов R, и R 2рОписаниеНе держит никаких ресурсов1Запросил ресурс R2, не держитникаких ресурсовР20Описание1Запросил ресурс R,, не держитникаких ресурсовНе держит никаких ресурсов2Держит ресурс R22Держит ресурс R,3Запросил ресурс R,, держит ресурс R23Запросил ресурс R2, держит ресурс R,4Держит ресурсы R, и R24Держит ресурсы R, и R25Держит ресурс R2 после освобожденияресурса R,5Держит ресурс R2 после освобожденияресурса R,Теперь, когда мы знаем понятия надежного, опасного и безопасного состояний,можно рассмотреть методы борьбы с тупиками.Методы борьбы с тупикамиПроблема тупиков является чрезвычайно серьезной и сложной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
