АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

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

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

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

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

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

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

Р,: а -> {а}

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

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

S_e ⁼ S_w или. S_e —^—> S_w для некоторого i или

S_e —^—> Зь для некоторого i и S_k, и S_k —-— > S_w.

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

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

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

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

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

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

о - {S,₍ S₂, S_3> S₄}; я - {P_lt Р₂};

P,(S,) - {S_2l S₃}; P₂(S,) = {S₃};

P,(S₂)-0; P₂(S₂) = 4S,, S₄};

P_t(S₃) - {S₄}; P₂(S₃) - 0;

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

Si —3— > S₃; S₂ —я—» S₄; S(------- > S₄.

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2015-01-18 | Просмотры: 618 | Нарушение авторских прав