Модель пространства состояний системы

Приведем еще одну формальную модель (она подробно рассмотрена в работе [54]). Эта модель очень проста, однако она позволяет сформулировать, что нам нужно делать, чтобы не попасть в тупиковое состояние.

' Напомним, что деревом в теории графов называют граф, не имеющий циклов.

260_______________________ Глава 8. Проблема тупиков и методы борьбы с ними

Пусть состояние операционной системы сводится к состоянию различных ресур­сов в системе (свободны они или выделены какому-нибудь процессу). Состояние системы изменяется процессами, когда они запрашивают, приобретают или осво­бождают ресурсы — это единственно возможные действия (точнее, мы принимаем во внимание только такие действия). Если процесс не блокирован в данном состо­янии, он может изменить это состояние на новое. Однако так как в общем случае невозможно знать априори, какой путь может избрать произвольный процесс в своей программе (это неразрешимая проблема!), то новое состояние может быть любым из конечного числа возможных. Следовательно, процессы нами будут трак­товаться как недетерминированные объекты. Введенные ограничения на извест­ные понятия приводят нас к нескольким формальным определениям.

□ Система есть пара , где

— множество состояний системы

— множество процессов

□ Процесс Р_; есть частичная функция, отображающая состояние системы в непу­
стые подмножества ее же состояний. Это обозначается так:

Если процесс Р; определен на состоянии S, то область значений обозначается как . Если , то мы говорим, что может изменить состояние S,. в

состояние S_k посредством операции, и используем обозначение Наконец, запись означает, что для некоторо-

го i, или для некоторых i и S_k, причем

Другими словами, система может быть переведена посредством n > О операций с помощью m > 0 различных процессов из состояния S_t. в состояние S_w. Мы говорим, что процесс заблокирован в данном состоянии, если он не может из­менить состояние, то есть в этом состоянии процесс не может ни требовать, ни получать, ни освобождать ресурсы. Поэтому справедливо следующее. Процесс Р_: заблокирован в состоянии S,,, если не существует ни одного состояния

,такого что , причем

Далее, мы говорим, что процесс находится в тупике в данном состоянии , если он заблокирован в состоянии и если вне зависимости от того, какие операции (изменения состояний) произойдут в будущем, процесс остается заблокирован­ным. Поэтому дадим еще одно определение.

Процесс находится в тупике в состоянии , если для всех состояний , таких что , процесс Р, блокирован в состоянии

Приведем пример. Определим систему :

формальные модели для изучения проблемы тупиковых ситуаций_______________ 261

Некоторые возможные последовательности изменений для этой системы таковы:

Последовательность может быть реализована, например, следующим

образом: или же

Заметим, что процесс находится в тупике как в состоянии , так и в состоянии ; для последнего случая или и процесс не оказыва-

ется заблокированным ни в , ни в

Диаграмма переходов этой системы изображена на рис. 8.7.

Рис. 8.7. Пример системы <!!!!!!!!!!!!!!!!!!!!о, я> на четыре состояния

Состояние S называется тупиковым, если существует процесс , находящийся в ту­пике в состоянии S.

Теперь мы можем сказать, что, по определению, тупик предотвращается при вве­дении такого ограничения на систему, чтобы каждое ее возможное состояние не было тупиковым состоянием. Введем еще одно определение.

Состояние есть безопасное состояние, если для всех , таких что не является тупиковым состоянием.

Рассмотрим еще один пример системы . Граф ее состояний приведен на

рис. 8.8. Здесь состояния S₂ и S₃ являются безопасными; из них система никогда не сможет попасть в тупиковое состояние. Состояния S, и S₄ могут привести как к безопасным состояниям, так и к опасному состоянию S₅. Состояния S₆ и S₇ явля­ются тупиковыми.

Наконец, в качестве еще одной простейшей системы вида <!!!!!!!!!!!а, п> приведем пример тупика с ресурсами типа SR, уже рассмотренный нами ранее и проиллюстриро­ванный рис. 8.3. Для этого определим состояния процессов Pj и Р₂, которые ис­пользуют ресурсы R, и R₂ (табл. 8.1).

Пусть состояние системы означает, что процесс находится в состоянии , а процесс Р₂ — в состоянии . Возможные изменения в пространстве состояний

262_______________________ Глава 8, Проблема тупиков и методы борьбы с ними

этой системы изображены на рис. 8.9. Вертикальными стрелками показаны воз­можные переходы из одного состояния в другое для процесса Р,, а горизонтальны­ми — для процесса Р₂. В данной системе имеется три опасных состояния: S₂₂, S₂₃ и S₃₂. Попав в любое из них, мы неминуемо перейдем в тупиковое состояние S₃₃.

Рис. 8.8. Пример системы <а, !!!!!!!!!!п> с безопасными, опасными и тупиковым состояниями

Рис. 8.9. Модель системы из двух процессов

Методы борьбы с тупиками____________________________________________ 263

Таблица 8.1. Состояния процессов Р, и Р₂ при использовании ресурсов R, и R₂

Р, Описание Р₂ Описание

0 Не держит никаких ресурсов 0 Не держит никаких ресурсов

1 Запросил ресурс R_2l не держит 1 Запросил ресурс R,, не держит
никаких ресурсов никаких ресурсов

2 Держит ресурс R₂ 2 Держит ресурс R,

3 Запросил ресурс R,, держит ресурс R₂ 3 Запросил ресурс R₂, держит ресурс R,

4 Держит ресурсы R, и R₂ 4 Держит ресурсы R, и R₂

5 Держит ресурс R₂ после освобождения 5 Держит ресурс R₂ после освобождения
ресурса R, ресурса R,

Теперь, когда мы знаем понятия надежного, опасного и безопасного состояний, можно рассмотреть методы борьбы с тупиками.