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

Лекция 11

Вычислительные схемы

Вычислительная схема – это представление в графической форме асинхронной системы, состоящей из набора операторов (процессов), которые воздействуют на множество «регистов» (данных). Каждая вычислительная схема определяется с помощью двух графов: графа потока данных и графа управления.

Граф потока данных (информационный граф) определяет входные и выходные данные для каждого оператора. Дуга (R_iS_k) от регистра R_i к оператору S_k означает, что данные R_i являются элементом входных данных этого оператора; дуга (S_kR_j) определяет данные R_j как выходные. Очевидно, что некоторые данные R могут являться выходными для оператора S_i и входными для оператора S_j. Пример графа потока данных для некоторой вычислительной схемы представлен на рис. 7.7, а; операторы и регистры данных представлены соответственно кружками и прямоугольниками.

Рис. 7.7.Пример вычислительной схемы: а – граф потока данных;

б – граф управления

Граф управления определяет последовательность выполнения операторов. Каждый оператор (представлен кружком) связан с некоторым количеством управляющих счётчиков (представлены прямоугольниками). Каждый из управляющих счётчиков содержит неотрицательное целое число. Текущие значения счётчиков совместно со значениями данных на графе потока данных определяют состояние вычислительной схемы. Пример графа управления представлен на рис. 7.7, б. Если все счётчики, указывающие на оператор S (то есть входные счётчики), имеют ненулевые значения, то говорят, что оператор S определен. В этом случае он может выполниться, изменив свои выходные регистры в соответствии с графом потока данных и изменив счётчики графа управления по следующему правилу:

значения всех выходных счётчиков оператора S уменьшаются на единицу, а значение выходных – увеличивается, причём для каждого выходного счётчика оператора S приращение может быть своё, персональное, и определяется оно с помощью специальной функции от значений регистров.

Обратите внимание на сходство между графом управления и сетью Петри. Если под операторами и счётчиками понимать переходы и позиции, то единственным существенным различием между этими моделями будет зависимость приращения счётчика от входных данных оператора S.

Такая последовательность операторов S₁,S₂,..., S_n,..., что каждый оператор S, определён (то есть его входные счётчики не равны нулю) при тех значениях счётчиков, которые получаются в результате выполнения предшествующих операторов, называется последовательностью исполнения схемы. Поскольку с операторами не связано никакого особого отсчёта времени (подобно сетям Петри), то порядок, в котором операторы будут выполняться, не всегда может быть предсказан. Любая допустимая последовательность исполнения является возможной последовательностью событий. Как мы уже знаем, для системы взаимодействующих параллельных процессов результаты вычислений зависят от последовательности исполнения, если не обеспечить взаимное исключение для критических интервалов. В случае, когда вычислительная схема вырабатывает одинаковые результаты для всех допустимых последовательностей исполнения, говорят, что она детерминирована. Схема на рис. 7.7 является детерминированной.

Рассмотрим вычислительную схему на рис. 7.8. Операторы S₁ и S₂,как это видно из графа управления, выполняются параллельно и асинхронно. Очевидно, что значение регистра R₃ будет различным в зависимости от того, выполняется ли оператор S₁ раньше или позже оператора S₂. Поскольку граф управления здесь допускает последовательности исполнения, которые приводят к различным результатам, то эта схема не детерминирована.

Говорят, что два оператора соперничают в регистре R, если один из них изменяет R, а другой либо изменяет R, либо обращается к нему. Если два оператора, которые соперничают в некотором регистре, могут быть выполнены в одно и то же время, то говорят, что в схеме существует условие соперничества и такая схема является недетерминированной. Одна из возможных форм недетерминированного исполнения заключается в том, что схема может «зависнуть» (попасть в тупиковую ситуацию).

Рис. 7.8. Пример недетерминированной вычислительной схемы

К сожалению, вычислительные схемы, как и сети Петри, не являются конструктивной моделью (с точки зрения борьбы с тупиковыми ситуациями, возникающими в операционных системах), несмотря на свою интуитивную привлекательность и возможность сделать вывод о возможности существования тупиков в той или иной системе. Мы знаем, что возможность существования тупиковой ситуации в большинстве ОС существует. Но ведь это же не означает, что эти ОС нельзя использовать. Важнее уметь обнаружить существование тупиковой ситуации в конкретный момент времени и поправить ситуацию (насколько это возможно). Поэтому гораздо более продуктивной с этой точки зрения является модель Холта.

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

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

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

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

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

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

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

P_i}s{®s:

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

Наконец, запись SeS_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.

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

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

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. Пример системы <p,s> на 4 состояния

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

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

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

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

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

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

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

состояниями

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

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

Состояния для процесса Р1	Состояния для процесса Р2
	Не содержит никаких ресурсов		Не содержит никаких ресурсов
	Запросил ресурс R2, не держит никаких ресурсов		Запросил ресурс R1, не держит никаких ресурсов
	Держит ресурс R2		Держит ресурс R1
	Запросил ресурс R1, держит ресурс R2		Запросил ресурс R2, держит ресурс R1
	Держит ресурсы R1 и R2		Держит ресурсы R1 и R2
	Держит ресурс R2 после освобождения ресурса R1		Держит ресурс R2 после освобождения ресурса R1

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

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

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