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

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

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

¨ Система есть пара <s, p>, где

s – множество состояний системы {S₁, S₂, S₃, ... , S_n};

p – множество процессов {P₁, Р₂, Р₃, ... , Р_k}.

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

P_i: s®{s}

Если P_i определён на состоянии S, то область значений Р_i , обозначается как P_i(S). Если S_k Î P_i(S_e), то мы говорим, что P_i может изменить состояние S_e в состояние S_k посредством операции, и используем обозначение S_e S_k .

Наконец, запись S_e S_w обозначает, что

S_e = Sw или

S_e S_w для некоторого i или

S_e S_k для некоторого i и S_k, и S_k S_w.

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

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

¨ Процесс P_i заблокирован в состоянии S_e, если не существует ни одного состояния S_k, такого что S_e S_k (P_i(S_e) = Æ).

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

¨ Процесс P_i находится в тупике в состоянии S_e, если для всех состояний S_k, та­ких что S_e S_k, процесс P_i блокирован в S_k.

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

s = {S₁, S₂, S₃, S₄}; p = {P₁, Р₂};

P₁(S₁) = {S₂, S₃}; P₂(S_l) = {S₃};

P_l(S₂) = Æ ; P₂(S₂) = {S₁, S₄};

P_l(S₃) = {S₄}; P₂(S₃) = Æ;

P₁(S₄) = {S₃}; P₂(S₄) = Æ.

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

S₁ S₃; S₂ S₄; S₁ S₄.

Последовательность S₁ S₄ может быть реализована, например, следующим образом: S₁ S₂; S₂ S₄ или же S₁ S₃; S₃ S₄.

Заметим, что процесс Р₂ находится в тупике как в состоянии S₃, так и в состоя­нии S₄; для последнего случая S₂ S₄ или S₂ S₁ и процесс P₁ не ста­новится заблокированным ни в S₄, ни в S₁.

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

Рис. 7.9. Пример системы <s, p> на 4 состояния

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

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

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

¨ Состояние S_i есть безопасное состояние, если для всех S_k, таких что

S_i S_k, S_k не является тупиковым состоянием.

Рассмотрим ещё один пример системы <s, p>. Граф её состояний приведен на рис. 7.10. Здесь состояния S₂ и S₃ являются безопасными; из них система нико­гда не сможет попасть в тупиковое состояние. Состояния S₁ и S₄ могут привести как к безопасным состояниям, так и к опасному состоянию S₅. Состояние S₆ и S₇ является тупиковым.

Рис. 7.10. Пример системы <s, p> с безопасными, опасными и тупиковым

состояниями

Наконец, в качестве ещё одной простейшей системы вида <s, p> приведём при­мер тупика с SR-ресурсами, уже рассмотренный нами в этой главе ранее. Определим следующим образом состояния процессов P₁ и Р₂, которые используют ре­сурсы R₁ и R₂.

Таблица 7.1. Состояния процессов Р₁ и Р₂

Пусть состояние системы S_ij означает, что процесс P₁ находится в состоянии S_i, а процесс Р₂ – в состоянии Sj. Возможные изменения в пространстве состояний этой системы изображены на рис.7.11. «Вертикальными» стрелками показаны возможные переходы из одного состояния в другое для процесса P₁, а «горизонтальными» – для процесса Р₂. В данной системе имеются три опасных состоя­ния. Попав в любое из них, мы неминуемо перейдем в тупиковое состояние.

Рис. 7.11. Пример системы

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