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

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

Прочитайте:
  1. I. Противоположные философские системы
  2. II. Клетки иммунной системы
  3. III. Лечение некоторых экстренных состояний
  4. IV. Анатомия органов сердечно-сосудистой системы
  5. IV. Реакция эндокринной системы на гипогликемию
  6. V. Органы лимфатической системы, иммунной системы
  7. VI. Анатомия центральной нервной системы
  8. VII. Анатомия периферической нервной системы
  9. А) при повышении тонуса симпатической нервной системы
  10. А. Идентификация эпидурального пространства.

Приведем еще одну формальную модель (она подробно рассмотрена в работе [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 |



При использовании материала ссылка на сайт medlec.org обязательна! (0.008 сек.)