Модель пространства состояний системы
Приведем еще одну формальную модель (она подробно рассмотрена в работе [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. В данной системе имеются три опасных состояния. Попав в любое из них, мы неминуемо перейдем в тупиковое состояние.
Теперь, когда мы знаем понятия надежного, опасного и безопасного состояний, можно рассмотреть и методы борьбы с тупиками.
Дата добавления: 2015-01-18 | Просмотры: 661 | Нарушение авторских прав
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|