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

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

Пусть состояние системы будет сводиться к состоянию различных ресурсов в системе (свободны они или распределены). Состояние системы изменяется процессами, когда они запрашивают, приобретают или освобождают ресурсы; это будут единственно возможные действия, которые принимаются во внимание. Если процесс не блокирован в данном состоянии, он может изменить это состояние на новое. Но, так как в общем случае невозможно знать заранее, какой путь может избрать произвольный процесс в своей программе (это неразрешимая проблема!), то новое состояние может быть любым из конечного числа возможных. Следовательно, процессы нами будем трактовать как недетерминированные объекты. Введенные ограничения на известные понятия приводят к следующим формальным определениям.
Определение 5.5. Система есть пара <σ, π >, где:
1) σ - множество состояний системы {S1, S2, ..., Sn};
2) π - множество процессов {P1, Р2, …, Pk}.
Определение 5.6. Процесс Pj есть частичная функция, отображающая состояние системы в непустые подмножества ее же состояний. Это обозначается так: Pj: σ → {σ}.
Если Pj определен на состоянии S, то область значений Pj обозначается как Pj(S). Если , то говорят, что Pj может изменить состояние Sl в состояние Sk посредством операции, и используют обозначение: .
Запись соответствует выполнению одного из трех условий:
1) Sl = Sw;
2) для некоторого j;
3) для некоторого j и Sk, и .
Т.е. система может быть переведена посредством n≥0 операций с помощью m≥0 различных процессов из состояния Slв состояние Sw.
Процесс заблокирован в данном состоянии, если он не может изменить состояние системы. Формально это можно определить следующим образом.
Определение 5.7. Процесс Pj заблокирован в состоянии Sl, если не существует ни одного состояния Sk, такого что ().
Процесс находится в тупике в данном состоянии Sl, если он заблокирован в состоянии Sl и вне зависимости от того, какие операции произойдут в будущем, процесс остается заблокированным. Формально это можно определить следующим образом.
Определение 5.8. Процесс Pj находится в тупике в состоянии Sl, если для всех состояний Sk, таких что , процесс Pj блокирован в Sk.
Пример 5.2. Определим систему <σ, π > следующим образом:
1) σ = {S1, S2, S3, S4, S5};
2) π = {P1, P2}, где P1(S1) = {S2, S3, S4}; P2(S1) = {S2}; P1(S2)= {S5}; P2(S3) = {S5}; P1(S4) = {S5}; P2(S4) = {S1}; P1(S5) = {S2}.
Примерами возможных последовательностей изменений для этой системы являются . Последовательность может быть реализована, например, следующим образом: или же . Процесс Р2 находится в тупике в состояниях S2 и S5; для случая процесс Р1 не становится заблокированным в S5.
Диаграмма переходов этой системы изображена на рисунке 5.3.

Рисунок 5.3 - Пример системы <σ, π> на 4 состояния

Определение 5.9. Состояние S называется тупиковым, если существует процесс Pj, находящийся в тупике в состоянии S.
Определение 5.10. Состояние Si безопасное, если для всех состояний Sk, таких что , Sk не является тупиковым состоянием.
Пример 5.3. Граф состояний системы <σ, π> приведен на рисунке 5.4. Здесь состояния S2, S3 и S4 являются безопасными, т.к. из них система никогда не сможет попасть в тупиковое состояние. Состояние S1 может привести как к безопасным состояниям, так и к опасному состоянию S5. Состояния S6 и S7 являются тупиковыми.

Рисунок 5.4 - Система с безопасными, опасными и тупиковым
состояниями

Пример 5.4. Пусть в системе <σ, π> состояния процессов P1 и Р2, которые используют ресурсы R1 и R2, описаны в таблице 5.1.

Таблица 5.1 - Состояния процессов Р1 и Р2

Ресурс/Процесс	Процесс Р1		Процесс Р2
Ресурс/Процесс	R1	R2	R1	R2
Захватывается в состоянии	S3	S5	S5	S4
Освобождается в состоянии	S5	S6	S6	S6

Пусть состояние системы Sij означает, что процесс P1 находится в состоянии Sj, а процесс Р2 - в состоянии Si. Возможные изменения в пространстве состояний этой системы изображены на рисунке 5.5. Вертикальными стрелками показаны возможные переходы из одного состояния в другое для процесса Р2, а горизонтальными - для процесса Р1. Фигурными скобками выделены интервалы удерживания ресурсов процессами. Участки взаимного исключения процессов показаны штриховкой. В данной системе имеется одно опасное состояние S43, попав в него, система неминуемо перейдем в тупиковое состояние S44.