Книжка по сетям Петри (547616), страница 38
Текст из файла (страница 38)
Блок ввода представляет собой однопроходный транслятор с языка формул во внутреннее представление развернутых сетей. Синтаксическая структура этого языка аналогична структуре простых арифметических выражений. Простой синтаксис входного языка позволил найти простое программное решение блока. Грамматика языка расширена до автоматной, реализован стековый метод трансляции. Блок операций представляет собой набор процедур и функций, реализующих операции над сетями и некоторые вспомогательные действия.
Для внутреннего представления сетей, которые могут иметь произвольный объем и структуру, использовалась имеющаяся в языке Паскаль возможность динамического построения конечных графов с помощью списочных структур и процедур динамического размещения данных. Иерархическая сеть разбивается на уровни, имеющие одинаковую структуру. К высшему уровню относятся переходы, которые не являются внутренними для других ле(юходов сети. Их вложенность считаетсл равной единице, так как вся сеть рассматриваетсл как составной переход. Для каждого перехода его вложенность на единицу больша вложенности охваты. аающего перехода. Петри-машину можно представить как универсальную процедуру гене.
рации независимых копий процедуры управления функционированием составного перехода. Каждая такая копия генерируется для данного со. ставного перехода, когда он становится активным. Она организует локальное управление работой этого перехода в течение всего времени его актив. ности и исчезает после его завершения. В иерархической сети два и более составных перехода могут одновременно находиться в активном состоянии, и, следовательно, несколько копий управления работают параллельно.
Если некоторые составные переходы сети, имеют общее стороннее место, то при ее Функционировании может возникнуть конфликтнал ситуация, когда локальные управления переходов обращаются к этому месту. Локальное управление любого из этих составных переходов не может самостоятельно разрешить конфликт, оно может решать только вопросы, связанные с функционированием внутренней сети своего составного модуля.
Для разрешения конфликтов, связанных с общими сторонними местами, нужна специальная процедура, называемая арбитром. Ее копии порождаются при активацци составных модулей вместе с копиями основного управления. При работе арбитра используется сеть, построенная из заданной иерархической сети специальным образом (развернутая сеть(. В ней наряду с переходами заданной сети имеются так называемые теневые переходы, которые являются представителями конфликтующих переходов на тех уровнях сети, на которых разрешаются конфликты между данными переходзми.
Рассмотрим произвольную иерархическую сеть д(с множеством переходов ТТ и множеством мест Р и введем следующие обозначения: l(г! = (г етт(г' — внутреннийпереходг), 0(г) =(г етТ (г — объемлющий переход для с(, Т(рг = р О р, т.е. множество переходов, инцидентных месту р. В Р выделяется множество конфликтных мест сети Кн = с.! К (с), где нет т К[с! = (р Б Р ( Т(р) Г1.I(с) Ф Ф ЛТ(о) !,/(с) Ф )) ). Таким образом, конфликтные места для составного перехода с инцидентны как внутренним переходам перехода с, так и внешним по отношению к нему переходам. Пусть Р, — множество внутренних мест перехода с (напомним, что место р является внутренним для с, если Т(р! С,l(с) ), а Р [с) = с Нс.
БУДЕМ ГОВОРИТЬ, ЧтО С вЂ” ПЕРЕХОД тИПа О, ЕСЛИ Р [С) Г! Кн = й, И тИПа 1 в противном случае. Для конфликтного места р Б Кн определим охватывающий переход д (р) такой,что (а) р~' с[а) ' Б Р, следует, что д (р Границей конфликтов для перехода с назовем переход д [с! Б 0И) такой, что (а) Р (с) Срз[,), и (б) тг С' ть д [С) из Р (с ! Б Р, следует, что д [с) Б.l (с') . Другими словами, граница конфликтов для перехода с — зто "минимальный" объемлющий с переход, содержащий все входные и выходные места с в качестве внутренних.
Граница конфликтов существует для любого перехода, так как мы условились, что заданная иерархическая сеть представляет собой составной переход. для каждого перехода с типа 1 сети И в каждом переходе с' я 0(с! г! г! ./(д(с)) вводим дополнительный теневой переход типа 1, соответствующий с. В переходе д (с) вводим в качестве внутреннего теневой переход а (с) типа О. Значения функций инцидентности Е меняем так, что для любого с типа ! и для любого р Б Кн Г! Р (С) Е (р,а(с!) =Е[р,с),Е (з(С),р) =Е(с,р),Е (р,с) =О,Е (с,р) = О. Для остальных теневых переходов значения функций Е равны О. г Между переходами типа 1 и соответствующими теневыми переходами устанавливается двусторонняя связь для передачи информации о наличии Рио 8.1В !47 фишек в конфликтных местах.
Переход г связывается со своим теневыы переходом в охватывающем переходе, тот — с теневым переходом в еле. дующем объемлющем переходе и т.д. до () (т) . В результате таких преобразований исходной иерархической сети полу. чае(ся реэеернугал сеть. На рнс. В.15, э показана иерархическая сеть, а на рис. 8.15, 6 — соответствующая развернутая сеть. Теневые переходы изо. бражены светлыми барьерами, связи между ними и переходами типа 1— пунктирными стрелками. В процессе имитации сети дэя каждого составного переходе с генерирует.
ся копия основного управления С, и копия арбитрадл Управление Ст проверяет локальнью условия активации переходов, охватываемых переходом г, и переводит их из состояния в состояние. Арбитр Аг ведает конфликтными местами ртакими, чтод (р) = г.
При определении функционирования сетей с ожиданием вводилось два состояния переходов — активный и пассивный, а изменения состояний рассматривались как мгновенные события. При моделировании сетями реальных систем такие события имеют длительность. Аналогично при про. граммном моделировании сетей проверки условий активации, условий завершения и т.п.
также имеют длительность. Поэтому в Петри-машине с каждым переходом связано насколько состояний: он может быть пассивным, проверяемым, готовым, активным, ждущим, остановившимся. Проверка условий активации различна для переходов типа О и типа 1. Если для перехода типа О выполнено локальное условие активации, то он переводится в состояние "готов". Для перехода с типа 1 основное управле. ние охватывающего перехода проверяет локальные условия активации и, если сею выполнено, проверяемый переход переводится в состояние "ждущий".
Соответствующему теневому переходу "наверх" посылается запрос на фишки из мест Р (г) й Ку. Обработку этого запроса и возможную передачу запроса на верхние уровни осуществляет арбитр уровня перехода г, он же передает ответ назад о результате проверки. Если ответ положителен, то переход г переводится в состояние "готов", в противном случае — в состояние "пассивный". Арбитр некоторого уровня формирует запросы от некоторого перехода к верхним уровням только в том случае, если он удовлетворил запросы этого перехода на своем уровне. Переход, находящийся в состоянии "готов", может быть приведен основ.
ным управлением в активное или пассивное состояние. )чогда составной переход активирован, генерируется его локальное основное управление и локальный арбитр. Все внутренние переходы считаются пассивными. Составной переход завершается, если ни один из охватываемых им переходов не является активным или ждущим и локальное условие активации всех этих переходов не выполнено.
В процессе завершения происходит смена разметки сети. Основное управление, завершая переход типа О, передает фишки в его выходные места и переводит переход в пассивное состоя. ние. Если же переход имеет тип 1, то управление дополнительно сообщает соответствующему теневому переходу о завершении перехода. Арбитр, приняв этот сигнал„посылает фишки в выходные места теневого перехода.
Если теневой переход имеет тип О, то на этом передача сообщения "вверх" обрывается, а в противном случае сообщение идет на верхние уровни. Настоящая книге не охватывает всей проблематики теории сетей Петри н ее приложений к задачам моделирования дискретных систем. За рамками книги остались прежде всего различныа обобщения и модификации сетей Петри, вводимые как проблемно-ориентированные средства высокого уровня для моделирования систем специалыюго вида: радиоэлектронных устройств, сетевых протоколов, экономических систем и т.п.
Кроем того, не освещены систематически результаты применения сетей Петри к задачам обнаружения типовых ситуаций в дискретных системах, таких, как, например, взаимные блокировки. Это связано в первую очередь с тем, что описанные в литература результаты не образуют критическую массу, достаточную для их монографического обобщения.
Чтр касаатся общей теории сетей, то она, во.первых, мце находится в стадии становления и, во.вторых, образует внутренний, "технологический" уровень сетевой проблематики. Поэтому она требует более специального изложения и погружения в контекст современных математических основ обработки информации. Из су. ществующих по этому вопросу публикаций можно рекомендовать обзор !371 и книгу ~79). Приводимый ниже список литературы ни в коей мере не является библиографией по сетям Петри. Он содержит только непосредственно упоминаемые в тексте книги публикации и некоторые работы, тасно связанные с излагаемым материалом. Последнее замечание связано с терминологией. Базовая англоязычная (и немецкая) терминология сейчас устоялась, хотя и употребляются разные варианты именования одинаковых или близких понятий.
Попытка провести ее дальнейшую унификацию сделана в работе [391. Общепринятая советская терминология в области сетей Петри практически не существует, и не предпринимались попытки ее соадать. Поэтому автор взял на себя смелость использовать в книге те русские термины, которые в течение многих лет применялись в работе коллектива, ведущего исследования по сетям Петри и их приложениям в Вычислительном центре СО АН СССР. Двуязычный предметный указатель в конце книги поможет сопоставить их с английскими эквивалентами.
ЛИТЕРАТУРА 1. Алексеев Г.Н., Мьюьегков СЛ. Программная реализация Петри.машины. 8 кнх Многопроцессорные вычислительные системы и их математическое обеспечение. Новосибирск: Изд во ЗЦ СО АН СССР, 1982, с, 94 — 1 03. 2. Аниигев Л.А., Ачесоее С.М., Бвкдмая О.Л. и др. Методы параллельного микро. программирования. — Новосибирск: Науке, 1981, 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
