Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Глава_7.doc
Скачиваний:
2
Добавлен:
01.07.2025
Размер:
2 Мб
Скачать
☆

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

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

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

ограничения на известные понятия приводят нас к следующим формальным оп­ределениям:

Q Система есть пара <о, п>, где

а — множество состояний системы (S^ $2! S3,..., Sn}; я — множество процессов {Pj, Р2, рз, ..., P|J-

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

Р,: а -> {а}

Если pj определен на состоянии S, то область значений pj обозначается как Pj(S). Если Sij е Pj(Se), то мы говорим, что Р* может изменить состояние Se в со­стояние Sk посредством операции, и используем обозначение Se —^—» s^.

Наконец, запись Se —-—» Sw обозначает, что

Se = Sw или . Se —^—> Sw для некоторого i или

Se —^—> Зь для некоторого i и Sk, и Sk —-—> Sw.

Другими словами, система может быть переведена посредством п > 0 операций с помощью т > 0 различных процессов из состояния Se в состояние Sw.

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

Q Процесс pj заблокирован в состоянии Se, если не существует ни одного со­стояния Sk, такого что Se —%—»Sk (Pj(Se) = 0).

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

Q Процесс pj находится в тупике в состоянии Se если для всех состояний Sk, та­ких что Se —-—>Sk) процесс pj блокирован в Sk.

Приведем пример. Определим систему <сг, п>:

о - {S,( S2, S3> S4}; я - {Plt Р2};

P,(S,) - {S2l S3}; P2(S,) = {S3};

P,(S2)-0; P2(S2) = 4S,, S4};

Pt(S3) - {S4}; P2(S3) - 0 ;

Pi(S4) = {S3}; P2(S4) = 0. Некоторые возможные последовательности изменений для этой системы таковы:

Si —3—> S3; S2 —я—» S4; S( > S4.

Последовательность Sf —'—•» S4 может быть реализована, например, следующим образом: S( —3—> S2; S2 —£__>. S4 или же S, —u—> S3; S3 ^ > S4. Заметим, что процесс Р2 находится в тупике как в состоянии S3, так и в состоя­нии S4; для последнего случая S2 —и—> S4 или S2 —U—> S, и процесс Р, не ста­новится заблокированным ни в S4, ни в S(.

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

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

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

Введем еще одно определение.

Q Состояние Sj есть безопасное состояние, если для всех Sk, таких что S( —-—> Sk, Sk не является тупиковым состоянием.


Наконец, в качестве еще одной простейшей системы вила <<з, я> приведем при­мер тупика с SR-ресурсами, уже рассмотренный нами в этой главе ранее. Опре-


Рассмотрим еще один пример системы <а, л>. Граф ее состояний приведен на рис. 7.10. Здесь состояния S2 и S3 являются безопасными; из них система нико­гда не сможет попасть в тупиковое состояние. Состояния S( и S4 могут привести как к безопасным состояниям, так и к опасному состоянию S5. Состояние S6 и S7 является тупиковым.

делим следующим образом состояния процессов pj и Р2, которые используют ре­сурсы r! и R2.

Пусть состояние системы Sy означает, что процесс Pt находится в состоянии Sj, а процесс Р2 — в состоянии Sj. Возможные изменения в пространстве состояний этой системы изображены на рис. 7.11. «Вертикальными» стрелками показаны возможные переходы из одного состояния в другое для процесса PlF а «горизон­тальными» — для процесса Р2. В данной системе имеются три опасных состоя­ния. Попав в любое из них, мы неминуемо перейдем в тупиковое состояние.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]