Сучкова Л.И. Абстрактный и структурный синтез автоматов

Подождите немного. Документ загружается.

состояние стояние

4 СЕТИ ПЕТРИ

4.1 Структура и функционирование сетей Петри

Параллельно функционирующие и асинхронно взаимо-

действующие системы не описываются адекватно в терминах

классической теории автоматов. Рассмотрим классический

метод описания и анализа дискретных параллельных систем.

Сети Петри предложены Карлом Петри для моделирова-

ния асинхронных информационных потоков в системах пре-

образования данных. Сети Петри

обеспечивают описание как

алгоритмов и программ, так и собственно вычислительных

систем и их устройств, а также порождаемых вычислитель-

ных процессов. Компоненты таких систем и их функциони-

рование представляются абстрактными событиями. Событие

может произойти (реализоваться) один раз, повториться мно-

гократно, порождая конкретные действия (реализация собы-

тия), или не произойти ни разу. Совокупность

действий, воз-

никающих как реализация событий при функционировании

дискретной системы, образует процесс, порождаемый этой

системой. В общем случае одна и та же система может функ-

ционировать в одних и тех же условиях по-разному, порож-

дая некоторое множество процессов, т. е. функционировать

недетерминированно.

Реальная система функционирует во времени, событие

происходит

в некоторые моменты времени и длится некото-

рое время. В синхронных моделях дискретных систем собы-

тия явно привязаны к определенным моментам или интерва-

лам времени, в которые происходит одновременное измене-

ние состояния всех компонентов системы, то есть изменение

общего состояния системы. Смена состояний происходит

последовательно.

В сетях Петри обычно отказываются от

введения в мо-

дели дискретных систем времени и тактированных последо-

вательностей изменений состояний, заменяя их причинно-

следственными связями между событиями (асинхронные мо-

дели). Если возникает необходимость осуществить привязку

ко времени, то моменты или интервалы времени представля-

ют как события. Таким образом синхронные системы могут

описываться в терминах асинхронных моделей. Отказ от

времени приводит к тому, что события в асинхронной моде-

ли рассматриваются как элементарные (неделимые, мгновен-

ные) или как составные, имеющие некоторую внутреннюю

структуру, образованную из подсобытий.

Взаимодействие событий в сложных асинхронных сис-

темах имеет, как правило, сложную динамическую структу-

ру. Эти взаимодействия будут описываться более просто, ес-

ли указывать не непосредственные связи между событиями, а

те ситуации, при которых данное событие может реализо-

ваться. При этом глобальные ситуации в системе формиру-

ются

с помощью локальных операций, называемых условия-

ми реализации событий.

Условие имеет емкость: условие не выполнено (емкость

= 0), выполнено (емкость = 1), условие выполнено с n-

кратным запасом (емкость = n, где n – целое положительное

число). Определенные сочетания условий разрешают реали-

зоваться некоторому событию (предусловия события), а реа-

лизация события изменяет некоторые условия (постусловия

события), т. е. события

взаимодействуют с условиями, а ус-

ловия – с событиями.

Таким образом, предполагается, что для решения ука-

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

как структуры, образованные из элементов двух типов: собы-

тий и условий. В сетях Петри события и условия представле-

ны абстрактными символами из двух непересекающихся ал-

фавитов, называемых соответственно множеством переходов

и множеством позиций. В графическом представлении сетей

переходы изображаются «барьерами» или планками (t), а по-

зиции – кружками (Р) (рисунок 4.1). Условия и события-

переходы связаны отношением непосредственной зависимо-

сти, которое изображается с помощью направленных дуг,

ведущих из позиции в переходы и из переходов в позиции.

Позиции, из которых ведут дуги на данный переход, называ-

ются его выходными позициями. Позиции, на которые ведут

дуги из данного перехода, называются его входными пози-

циями. Если переход и позиция связаны несколькими дугами

в одном и том же направлении, то говорят о кратности дуги.

Рис. 4.1. Графическое изображение сети Петри

Выполнение

условий изображается разметкой соответ-

ствующей позиции, а именно: помещением числа n фишек

(маркеров) в соответствующее место, где n > 0 – емкость ус-

ловия.

Неформально работу сети можно представить как сово-

купность локальных действий, которые называются срабаты-

ваниями переходов. Они соответствуют реализациям собы-

тий и приводят к изменению разметки позиций, т. е. к ло-

кальному

изменению условий в системе.

Формально сеть Петри состоит из 4-х элементов: мно-

жество позиций Р, множество переходов Т, входная функция

I и выходная функция О. Входная и выходная функции свя-

заны с переходами и позициями. Входная функция I отобра-

жает переход t

в множество позиций I(tj), называемых вход-

ными позициями перехода. Выходная функция О отображает

переход t

в множество позиций О(tj), называемых выходны-

ми позициями перехода.

Маркировка сети Петри заключается в присвоении фи-

шек (маркеров) позициям сети Петри. При работе сети Петри

фишки, находящиеся в кружках, перемещаются из одних по-

зиций в другие и управляют выполнением переходов сети.

При переходе удаляются фишки из входных позиций и по-

мещаются в выходные позиции перехода. Переход может

происходить только в

том случае, когда он разрешен. Пере-

ход называется разрешенным, если каждая из его входных

позиций имеет число фишек по крайней мере равное числу

дуг из позиции в переход.

Фишки во входной позиции, которые разрешают пере-

ход, называются его разрешающими фишками. Например,

если позиции р1 и р2 служат входами для перехода t3,

тогда

t3 разрешен, если р1 и р2 имеют хотя бы по одной фишке.

Для перехода t3 с входными позициями {p1, p1, p1, p1} пози-

ция р1 должна обладать по крайней мере четырьмя фишками,

для того чтобы t3 был разрешен. Переход запускается удале-

нием всех разрешающих фишек из его входных позиций и

последующим помещением в каждую из его

выходных пози-

ций по одной фишке для каждой дуги. Кратные фишки соз-

даются для кратных выходных дуг. Например, переход t3 с

I(t3) = {p2} и О(t3) = {p7, р8} разрешен всякий раз, когда в р2

будет хотя бы одна фишка. Переход t3 запускается удалени-

ем одной фишки из позиции р2 и помещением одной фишки

в позицию р7

и в р8 (его выходы). Дополнительные фишки в

позиции р2 не влияют на запуск t3 (хотя они могут разрешать

дополнительные запуски t3). Переход t2, в котором I(t2) =

{p1, р3} и О(t2) = {p4, р5, р5} запускается удалением одной

фишки из р1 и одной фишки из р3, при этом одна фишка по-

мещается в р4 и две в

р5 (т. к. р5 имеет кратность, равную

двум). Запуск перехода в целом заменяет маркировку сети

Петри на новую маркировку. Так как можно запустить толь-

ко разрешенный переход, то при запуске перехода количест-

во фишек в каждой позиции всегда остается неотрицатель-

ным. Запуск перехода никогда не удалит фишку, отсутст-

вующую во входной

позиции. Если какая-либо входная пози-

ция перехода не обладает достаточным количеством фишек,

то переход не разрешен и не может быть запущен.

Тупик в сети Петри – это переход (или множество пере-

ходов), которые не могут быть запущены.

4.2 Моделирование систем и событий с помощью сетей

Петри

С помощью сетей Петри можно моделировать широкий

класс систем. Рассмотрим примеры

Пример 1. Рабочая станция.

Требуется описать с помощью сети Петри работу груп-

пы пользователей на единственной рабочей станции при за-

данных характеристиках потока запросов на ее пользование

и характеристиках поступающих задач. Сеть Петри пред-

ставлена на рисунке 4.2.

Рисунок 4.2

Здесь переходы связаны со следующими событиями: t1 -

поступление запроса на использование станции, t2 - занятие

станции

, t3 - освобождение станции, t4 - выход обслуженной

заявки; позиция p4 используется для отображения состояния

станции: если в p4 имеется метка, то станция свободна и

пришедшая заявка вызывает срабатывание перехода t2; пока

эта заявка не будет обслужена, метки в p4 не будет, следова-

тельно, пришедшие в позицию p1 запросы вынуждены ожи-

дать срабатывания перехода t3.

Пример 2. Техническая система.

Требуется описать с помощью сети Петри процессы

возникновения и устранения неисправностей в некоторой

технической системе, состоящей из множества однотипных

блоков; в запасе имеется один исправный блок; известны ста-

тистические данные об интенсивностях возникновения отка-

зов и длительностях таких

операций, как поиск неисправно-

стей, замена и ремонт отказавшего блока. Поиск и замену

отказавшего блока производит одна бригада, а ремонт заме-

ненного блока - другая бригада. Сеть Петри показана на ри-

сунке 4.3.

Рисунок 4.3

Значение М в позиции p2 соответствует числу имею-

щихся в системе блоков. Переходы отображают следующие

события: t1 - отказ блока, t2 -

поиск неисправного блока, t3 -

его замена, t4 - окончание ремонта. Очевидно, что при непус-

той позиции p2 переход t1 срабатывает, но с задержкой, рав-

ной вычисленному случайному значению моделируемого

отрезка времени между отказами. После выхода маркера из t1

он попадает через отрезок p1 в t2, если имеется метка в пози-

ции p6, это означает, что обслуживающая систему бригада

специалистов свободна и может приступить к поиску воз-

никшей неисправности. В переходе t2 метка задерживается

на время, равное случайному значению длительности поиска

неисправности. Далее маркер оказывается в p3 и, если имеет-

ся запасной блок (маркер в p4), то запускается переход t3, из

которого маркеры выйдут в p2, p5 и в p6 через отрезок вре-

мени, требуемый для замены блока. После этого в t4 имити-

руется восстановление неисправного блока.

Рассмотрим моделирование событий, имеющих некото-

рую длительность. Запуск перехода (и соответственно

собы-

тия) рассматривается как мгновенное событие, занимающее

нулевое время, и возникновение двух событий одновременно

невозможно. Моделируемое таким образом событие называ-

ется примитивным; примитивные события мгновенны и не-

одновременны. Непримитивными называются такие события,

длительность которых отлична от нуля. Они не являются не-

одновременными и, следовательно, могут пересекаться во

времени. Так как выполнение

большинства событий все же

реально и длится некоторое время, то они являются непри-

митивными событиями и поэтому не могут должным образом

моделироваться переходами в сети Петри. Однако неприми-

тивное событие может быть представлено в виде двух при-

митивных событий: «Начало непримитивного события»,

«Конец непримитивного события» и условия «Непримитив-

ное событие

происходит» (рисунок 4.4).

Рисунок 4.4 - Моделирование непримитивного события

При моделировании сложных вычислительных систем

на нескольких иерархических уровнях сети Петри представ-

ляются в отдельные элементы сети целыми подсетями. От-

дельными элементами в этом случае являются прямоуголь-

ники, представляющие непримитивные события, а планки

представляют примитивные события. Такое моделирование

вычислительной системы представлено на рисунке 4.5.

Рисунок 4.5 - Моделирование вычислительной системы с ис-

пользованием непримитивного перехода

4.3 Расширенные сети Петри

Применение классических подходов и добавление до-

полнительных атрибутов позволили разработать сети различ-

ной целевой направленности, получившие название расши-

ренные. Рассмотрим подробнее некоторые типы сетей Петри.

Ингибиторная сеть представляет собой сеть Петри, до-

полненную специальными ингибиторными (запрещающими)

дугами

. Переход t в ингибиторных сетях может сработать,

если каждая его входная позиция, соединенная с переходом

обычной дугой с кратностью w (p, t) содержит не менее w(p,

t) фишек, а каждая входная позиция, соединенная с перехо-