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

Приведём еще одну формальную модель (она подробно рассмотрена в работе [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. Состояния процессов Р₁ и Р₂

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

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

 

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

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

Методы борьбы с тупиками

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

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

¨ предотвращение тупика;

¨ обход тупика;

¨ распознавание тупика с последующим восстановлением.

Предотвращение тупиков

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

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

Условие взаимного исключения можно подавить путем разрешения неограничен­ного разделения ресурсов. Это удобно для повторно входимых программ и ряда драйверов, но совершенно неприемлемо к совместно используемым переменным в критических интервалах.

Условие ожидания можно подавить, предварительно выделяя ресурсы. При этом процесс может начать исполнение, только получив все необходимые ресурсы заранее. Следовательно, общее число затребованных параллельными процессами ресурсов должно быть не больше возможностей системы. Поэтому предварительное выделение может привести к снижению эффективности работы вычислительной системы в целом. Необходимо также отметить, что предварительное выделение зачастую невозможно, так как необходимые ресурсы становятся из­вестны процессу только после начала исполнения.

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

Условие кругового ожидания можно исключить, предотвращая образование цепи запросов. Это можно обеспечить с помощью принципа иерархического выделения ресурсов. Все ресурсы образуют некоторую иерархию. Процесс, затребовавший ресурс на одном уровне, может затем потребовать ресурсы только на более высо­ком уровне. Он может освободить ресурсы на данном уровне только после осво­бождения всех ресурсов на всех более высоких уровнях. После того как процесс получил, а потом освободил ресурсы данного уровня, он может запросить ресур­сы на том же самом уровне. Пусть имеются процессы ПР1 и ПР2, которые могут иметь доступ к ресурсам R1 и R2, причем R2 находится на более высоком уровне иерархии. Если ПР1 захватил R1, то ПР2 не может захватить R2, так как доступ к нему проходит через доступ к R1, который уже захвачен ПР1. Таким образом, создание замкнутой цепи исключается. Иерархическое выделение ресурсов час­то не дает никакого выигрыша, если порядок использования ресурсов, опреде­ленный в описании процессов, отличается от порядка уровней иерархии. В этом случае ресурсы будут использоваться крайне неэффективно.

В целом стратегия предотвращения тупиков – это очень дорогое решение проблемы, и она используется нечасто.

Обход тупиков

Обход тупика можно интерпретировать как запрет входа в опасное состояние. Если ни одно из упомянутых четырех условий не исключено, то вход в опасное состояние можно предотвратить при наличии у системы информации о последовательности запросов, связанных с каждым параллельным процессом. Доказано [92], что если вычисления находятся в любом неопасном состоянии, то сущест­вует по крайней мере одна последовательность состояний, которая обходит опас­ное. Следовательно, достаточно проверить, не приведет ли выделение затребо­ванного ресурса сразу же к опасному состоянию. Если да, то запрос отклоняется. Если нет, его можно выполнить. Определение того, является ли состояние опас­ным или нет, требует анализа последующих запросов процессов.

Рассмотрим следующий пример. Пусть имеется система из трех вычислительных процессов, которые потребляют некоторый ресурс R типа SR, который выделя­ется дискретными взаимозаменяемыми единицами, причем существует всего десять единиц этого ресурса. В табл. 7.2 приведены сведения о текущем распределении процессами этого ресурса R, об их текущих запросах на этот ресурс и о максимальных потребностях процессов в ресурсе R.

Последний столбец в табл. 7.2 показывает, сколько ещё единиц ресурса может затребовать каждый из процессов, если получит ресурс на свой текущий запрос.

Если запрос процесса А будет удовлетворен первым, то он в принципе может за­просить еще одну единицу ресурса R, и уже в этом случае мы тогда получим тупиковую ситуацию, поскольку ни один из процессов не сможет продолжить свои вычисления. Следовательно, при выполнении запроса процесса А мы попадаем в ненадежное1 состояние.

Таблица 7.2. Пример распределения ресурсов

Имя процесса	Выделено	Запрос	Максимальная потребность	«Остаток» потребностей
А
В
С

 

Если первым будет выполнен запрос процесса В, то у нас останется свободной еще одна единица ресурса R. Однако если процесс В запросит еще две, а не одну единицу ресурса R, а он может это сделать, то мы опять получим тупиковую си­туацию.

Если же мы сначала выполним запрос процесса С и выделим ему не две (как у процесса В), а все три единицы ресурса R и у нас при этом даже не останется никакого резерва, то, поскольку на этом его потребности в ресурсах заканчива­ются, процесс С сможет благополучно завершиться и вернуть системе все свои ресурсы. Это приведет к тому, что свободное количество ресурса R станет равно пяти. Теперь уже можно будет выполнить запрос либо процесса В, либо процес­са А, но не обоих сразу.

Часто бывает так, что последовательность запросов, связанных с каждым процессом, неизвестна заранее. Но если заранее известен общий запрос на ресур­сы каждого типа, то выделение ресурсов можно контролировать. В этом случае необходимо для каждого требования, предполагая, что оно удовлетворено, опре­делить, существует ли среди общих запросов от всех процессов некоторая последовательность требований, которая может привести к опасному состоянию. Дан­ный подход является примером контролируемого выделения ресурса.

Классическое решение этой задачи известно как алгоритм банкира Дейкстры [89]. Алгоритм банкира напоминает процедуру принятия решения, может ли банк без­опасно для себя дать взаймы денег. Принятие решения основывается на информации о потребностях клиента (текущих и максимально возможных) и учёте те­кущего баланса банка. Несмотря на то, что этот алгоритм нигде практически не используется, рассмотрим его, так как он интересен с методической и академиче­ской точек зрения. Текст программы алгоритма банкира приведен в листинге 7.4.

Пусть существует N процессов, для каждого из которых известно максимальное количество потребностей в некотором ресурсе R (обозначим эти потребности через Max(i)). Ресурсы выделяются не сразу все, а в соответствии с текущим запросом. Считается, что все ресурсы i-го процесса будут освобождены по его завершении. Количество полученных ресурсов для i-го процесса обозначим Получ(i). Остаток в потребностях i-го процесса на ресурс R обозначим через Остаток(i). Признак того, что процесс может не завершиться – это значение false для пере­менной Заверш(i). Наконец, переменная Своб_рес будет означать количество сво­бодных единиц ресурса R, а максимальное количество ресурсов в системе опре­делено значением Всего_рес.

Листинг 7.4. Алгоритм банкира Дейкстры

Begin

Своб_рес: = Всего_рес;

For i: = 1 to N do

Begin

Своб_рес: = Своб_рес – Получ(i);

Остаток(i): = Мах(i) – Получ(i);

Заверш(i): = false: { процесс может не завершиться }

end

flag: = true; ( признак продолжения анализа }

while flag do

begin

flag: = false;

for i: = 1 to N do

begin

if ( not ( За верш(i) )) and ( Остаток(i) < = Своб_рес )

then begin

Заверш(i): = true;

Своб_рес: = Своб_рес + Получ(i);

Flag: = true

end

end

end;

If Своб_рес = Bcero_pec

then Состояние системы безопасное

и можно выдать ресурс

else Состояние не безопасное

и выдавать ресурс нельзя

end.

Каждый раз, когда какой-то остаток может быть выделен из числа остающихся незанятыми ресурсов, предполагается, что соответствующий процесс работает, пока не окончится, а затем его ресурсы освобождаются. Если, в конце концов, все ресурсы освобождаются, значит, все процессы могут завершиться и система находится в безопасном состоянии. Другими словами, согласно алгоритму банкира система удовлетворяет только те запросы, при которых её состояние остается надёжным. Новое состояние безопасно тогда и только тогда, когда каждый процесс все же может окончиться. Именно это условие и проверяется в алгоритме банкиpa. Запросы процессов, приводящие к переходу системы в ненадёжное состоя­ние, не выполняются и откладываются до момента, когда его всё же можно будет выполнить.

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

Рассмотренный алгоритм примитивен, в нём учитывается только один вид ресурса, тогда как в реальных системах количество различных типов ресурсов бывает очень большим. Были опубликованы варианты этого алгоритма для большого числа различных типов системных ресурсов. Однако все равно алгоритм не получил распространения. Причин тому несколько:

¨ Алгоритм исходит из того, что количество распределяемых ресурсов в систе­ме фиксировано, постоянно. Иногда это не так, например, вследствие неисправности отдельных устройств.

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

¨ Алгоритм требует, чтобы число работающих процессов оставалось постоянным. Это возможно только для очень редких случаев. Очевидно, что выпол­нение этого требования в общем случае не реально, особенно в мультитерминальных системах либо если пользователь может запускать по несколько процессов параллельно.

Обнаружение тупика

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

Очевидно, что незаблокированный процесс (он только что получил ресурс и по­этому не заблокирован) через некоторое время освобождает все свои ресурсы и затем благополучно завершается. Освобождение ранее занятых ресурсов может «разбудить» некоторые ранее заблокированные процессы, которые, в свою очередь, развиваясь, смогут освободить другие ранее занятые ресурсы. Это может продолжаться до тех пор, пока либо не останется незаблокированных процессов, либо какое-то количество процессов всё же останется заблокированными. В последнем случае (если существуют заблокированные процессы при завершении указанной последовательности действий) начальное состояние S является состоя­нием тупика, а оставшиеся процессы находятся в тупике в состоянии S. В про­тивном случае S не есть состояние тупика.

⇐ Предыдущая34353637383940414243Следующая ⇒

Поделиться:

Популярное:

1. B. Функции языка как театральной коммуникативной системы
2. II этап. Обоснование системы показателей для комплексной оценки, их классификация.
3. II. НЕПОСРЕДСТВЕННОЕ ОБСЛЕДОВАНИЕ ДЫХАТЕЛЬНОЙ СИСТЕМЫ У ДЕТЕЙ
4. XVI. Основные правовые системы современности.
5. АВТОМАТИЗИРОВАННЫЕ ИНФОРМАЦИОННО – УПРАВЛЯЮЩИЕ СИСТЕМЫ
6. Автоматизированные системы управления
7. Алгоритм перевода чисел из одной системы счисления в другую
8. АНАЛИЗ СИЛЬНЫХ И СЛАБЫХ СТОРОН, ВОЗМОЖНОСТЕЙ И УГРОЗ организации (предприятия) системы потребительской кооперации
9. Анализ структуры и выполняемые функции информационной подсистемы «Кадры» ОГУ
10. Анализ эффективности работы видеосистемы
11. АНАТОМИЯ И ФИЗИОЛОГИЯ ДЕТОРОДНОЙ СИСТЕМЫ
12. АНАТОМИЯ МОЧЕПОЛОВОЙ СИСТЕМЫ.