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

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

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

Сети Петри

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

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

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

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

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

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

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

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

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

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

S=<Р, Т, Y>.

Здесь Р — конечное множество позиций, ; Т — конечное множество

переходов, , то есть Тк Р — это два типа вер-

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

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

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

ход — v-я дуга, выходящая из перехода и входящая в позицию р_к. Таким

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

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

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

жества:

Здесь

где — дуга с весом w < W, выходящая из вершины и входящая в вершину ;

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

ветственно .

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

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

Здесь — множество неотрицательных целых чисел. Ее же (мар-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эта сеть соответствует примеру тупиковой ситуации, которая возникает при взаимодействии процессов Пр1 и Пр2 во время передачи сообщений и потреб­лении ресурса R каждым из процессов (см. листинг 8.3). Начальная маркиров­ка для сети, показанной на рис. 8.5, будет равна (1, 0, 0, 0, 0, 4, 0, 0, 1, 0, 0, 0, 0). Здесь позиция р₂ означает, что процесс Пр1 получил три единицы ресурса R. Дуга, соединяющая позицию р₆ (число маркеров в ней соответствует количе­ству доступных единиц ресурса R), имеет вес 3, и при срабатывании перехода t_t процесс Пр1 получает затребованные три единицы ресурса. Переход t₂ пред­ставляет посылку процессом Пр1 сообщения для Пр2; переход t₅ — прием этого сообщения. Появление маркера в позиции р₇ означает, что процесс Пр2 обра­ботал сообщение и послал ответ процессу Пр1. Срабатывание перехода t_A пред­ставляет возврат в систему трех единиц ресурса, которыми владел процесс Пр1. Рассмотренная сеть не является живой, так как в ней всегда будут мертвы пе­реходы t₃, t_A, t_a, t₇ и t_s.

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

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

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

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

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