Формальные модели для изучения проблемы тупиковых ситуаций

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

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

Сети Петри

Среди многих существующих методов описания и анализа параллельных систем уже более 35 лет значительное место занимают сетевые модели, восходящие к сетям спе­циального вида, предложенным в 1962 году Карлом Петри для моделирования асин­хронных информационных потоков в системах преобразования данных [36].

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

Формальные модели для изучения проблемы тупиковых ситуаций_______________ 255

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

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

- теоретико-множественное представление;

- графово-бихроматический (двудольный ориентированный) граф и, соответ­
ственно, графическое представление;

- матричное представление.

При использовании теоретико-множественного подхода к описанию сети Петри (поскольку эта модель представляет и структуру, и функционирование системы) она формально может быть определена как двойка вида N = <S, Мо>. Здесь 5 — это структура сети, которая представляется двудольным ориентированным мульти-графом S ={ V, U), где V — вершины этого графа, U — его дуги. Мо — это начальное состояние сети Петри, которое также называется начальной маркировкой. Сеть Петри может функционировать и соответственно изменять свое состояние.

В силу того что граф S является двудольным, можно перейти к формальному опи­санию структуры сети Петри в виде тройки:

S=<Р, Т, Y>.

Здесь Р — конечное множество позиций, Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru ; Т — конечное множество

переходов, Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru , то есть Тк Р — это два типа вер-

шин биграфа S; Y — конечное множество дуг, заданное отношениями между вер­шинами графа 5:

Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru

Поскольку двудольный мультиграф S является ориентированным, то любой пере­ход Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru , соединяется с позициями р: !!!!! Р через входные и выходные дуги, которые задаются через функцию предшествования В :{Р*!!!! Т) —> {0,1, 2,...} и функ­цию следования Е : (Т • Р) —> {0,1, 2,...}, являющиеся отображениями из множества переходов в комплекты позиций [36] (синонимом термина «комплект» является понятие мультимножества). Эти функции определяют комплекты позиций Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru , связанных с переходом Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru через множество дуг, Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru где Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru , и комплекты позиций Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru , связанных с перехо­дом Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru через множество дуг Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru . Здесь W — мультичисло графа Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru — пространство комплектов, заданное на множестве Р функциями Е и В; Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru — v-я дуга, выходящая из позиции р, и входящая в пере-

256_______________________ Глава 8. Проблема тупиков и методы борьбы с ними

ход Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru — v-я дуга, выходящая из перехода Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru и входящая в позицию рк. Таким

образом, теперь структура S сети Петри N может быть представлена как четверка:

S = <Р, Т, В, Е>.

Представим далее множество позиций Р как объединение двух пересекающихся множеств: Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru . Здесь мы через I и О обозначили следующие мно-

жества:

Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru

Здесь

Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru

где Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru — дуга с весом w < W, выходящая из вершины Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru и входящая в вершину Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru ;

Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru — дуга с весом w<W, выходящая из вершины Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru и входящая в вершину Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru , то есть Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru и Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru — комплекты входных и выходных позиций перехода Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru соот-

ветственно .

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

Начальная маркировка Мо (как и текущая маркировка М, которая соответствует некоторому состоянию сети в текущий момент модельного времени) определяет­ся одномерной матрицей (вектором), число компонентов которой равно числу по­зиций сети п, п - \Р\, а значение i-го компонента (1 < i < п ) есть натуральное чис­ло m(pi)} которое определяет количество маркеров (меток) в позиции р;.

Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru

Здесь Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru — множество неотрицательных целых чисел. Ее же (мар-

кировку М) можно также представлять как множество или комплект с той разни­цей, что отсутствие некоторого элемента в множестве будем обозначать специаль­ным элементом — нулем. В этом случае запись вида Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru означает разность множеств и такое изменение маркировки, при котором на соответствую­щих местах вектора Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru будут уменьшенные значения.

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

Формальные модели для изучения проблемы тупиковых ситуаций_______________ 257

Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru

Переход, для которого выполняется это условие, называется возбужденным. Здесь запись вида Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru означает число появлений позиций pt во входном комп-

лекте перехода Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru оно, естественно, равно весу w соответствующей дуги, если вме­сто мультиграфа рассматривать взвешенный граф. При срабатывании перехода Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru маркировка Мо изменяется на маркировку М, следующим образом:

Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru

Иначе говоря:

Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru

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

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

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

Говорят, что некоторый переход tj для разметки М является живым, если для всех разметок М', достижимых из разметки М, существует последовательность сраба­тывания переходов, приводящая к маркировке М, при которой переход tj может сработать. Сеть Петри называется живой, если живы все ее переходы; живучая раз­метка — это разметка, при которой каждый из ее переходов сможет запускаться бесконечное число раз. Когда достигнута такая разметка, при которой ни один из переходов не может быть запущен, говорят, что сеть Петри завершилась (достиг­нута желаемая конечная маркировка) или же зависла (то есть имеет место тупико­вая ситуация).

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

258_______________________ Глава 8. Проблема тупиков и методы борьбы с ними

Два перехода, готовые к срабатыванию, находятся в конфликте, если они связаны с общей входной позицией.

В качестве примера рассмотрим рис. 8.5.

Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru

Рис. 8.5. Сеть Петри для системы двух взаимодействующих процессов

Эта сеть соответствует примеру тупиковой ситуации, которая возникает при взаимодействии процессов Пр1 и Пр2 во время передачи сообщений и потреб­лении ресурса R каждым из процессов (см. листинг 8.3). Начальная маркиров­ка для сети, показанной на рис. 8.5, будет равна (1, 0, 0, 0, 0, 4, 0, 0, 1, 0, 0, 0, 0). Здесь позиция р2 означает, что процесс Пр1 получил три единицы ресурса R. Дуга, соединяющая позицию р6 (число маркеров в ней соответствует количе­ству доступных единиц ресурса R), имеет вес 3, и при срабатывании перехода tt процесс Пр1 получает затребованные три единицы ресурса. Переход t2 пред­ставляет посылку процессом Пр1 сообщения для Пр2; переход t5 — прием этого сообщения. Появление маркера в позиции р7 означает, что процесс Пр2 обра­ботал сообщение и послал ответ процессу Пр1. Срабатывание перехода tA пред­ставляет возврат в систему трех единиц ресурса, которыми владел процесс Пр1. Рассмотренная сеть не является живой, так как в ней всегда будут мертвы пе­реходы t3, tA, ta, t7 и ts.

Примеру тупиковой ситуации, возникающей при работе с ресурсами типа SR (см. рис. 8.3), соответствует сеть Петри, показанная на рис. 8.6.

Формальные модели для изучения проблемы тупиковых ситуаций_______________ 259

Формальные модели для изучения проблемы тупиковых ситуаций - student2.ru

Рис. 8.6. Сеть Петри для тупиковой ситуации на ресурсах типа SR

В этой сети номера переходов соответствуют отмеченным номерам операторов, которые выполняют процессы Пр1 и Пр2, а позиции р, и р2 — семафорам S1 и S2, над которыми выполняются операции Р и V. Сеть на рис, 8.6 также не является живой, хотя для нее и существуют последовательности срабатывания переходов, не ведущие к тупиковой ситуации.

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

Наши рекомендации