Ординарные сети Петри

Формально ординарная сеть Петри задается в виде тройки , где- непустое конечное множество позиций сети;- непустое конечное множество переходов;- отношение инцидентности позиций и переходов (множество дуг сети).

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

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

В качестве примера рассмотрим задачу моделирования простого автомата-продавца. Автомат-продавец находится в состоянии ожи­дания до тех пор, пока не появится заказ, который он выполняет и посылает на доставку. Условиямидля такой системы являются:p₁- автомат-продавец ждет;p₂- заказ прибыл и ждет;p₃- автомат-продавец выполняет заказ;p₄- заказ выполнен. Событиями будут:t₁- заказ поступил;t₂- автомат-продавец начи­нает выполнение заказа;t₃- автомат-продавец заканчивает выпол­нение заказа;t₄- заказ посылается на доставку.

Предусловия события t₂(автомат-продавец начинает выполнение заказа) очевидны:p₁- автомат-продавец ждет;p₂- заказ прибыл и ждет. Постусловие для событияt₂:p₃- автомат-продавец выполняет заказ. Аналогично можно определить предусловия и постусло­вия для других событий и составить таблицу событий и их пред- и постусловий (табл.5.8).

Таблица 5.8.Описание процесса функционирования автомата-продавца

Такое представление системы легко моделировать сетью Петри. В сети Петри входы перехода являются предусловиями соот­ветствующего события; выходы — постусловиями. Сеть Петри на рис.5.4 иллюстрирует модель приведенного выше автомата-продавца. C каждым переходом и позицией связано соответствующее событие и условие.

Начальное состояние сети Петри задается с помощью маркировки её позиций. Маркировка сети заключается в присвоении позициям числовых значений (меток, емкостей): Маркировку сети удобно представлять в виде вектора

,

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

Начальное состояние рассматриваемой сети описывается следующим образом: заказ поступил и находится в состоянии ожидания ( условие p₂ выполнено); автомат-продавец занят выполнением заказа ( выполнено условиеp₃).

Отсутствие маркеров во всех остальных позициях сети означает, что связанные с этими позициями условия в начальном состоянии не выполняются. Записывая начальную разметку в виде вектора, для рассмотренного примера получим M₀=(0110).

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

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

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

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

• выполнение перехода - неделимый акт, изменение разметки входных и выходных позиций перехода при его выполнении осуществляется мгновенно.

Например, в сети на рис. 5.4, имеющей начальную маркировку M₀=(0110), будет возбужден переход. Новая маркировка M₁=(1101) получается по правилу:

Маркировке будет соответствовать новое состояние сети, в котором возбужденными оказываются переходыt₂ иt₄. При срабатывании, например,t₄метка изp₄будет выведена из системы, в результате чего установится новая разметка сети M₂=(1100). Вследствие этого состояние сети снова изменится. Теперь уже возбужденным оказывается только переходt₂и т. д.

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

Действие такого механизма проявляется в свойстве недетерминированности сетей Петри. Ни два, ни более возбужденных в некотором состоянии сети переходов одновременно не выполняются. Всякий возбужденный переход готов для выполнения, но момент его фактического срабатывания не определен с той абсолютной точностью, которая соответствует размещению событий на временной шкале. Иначе говоря, в сетях Петри не моделируется ход времени. События упорядочиваются по отношению «произошло после». Такой способ упорядочивания обеспечивает логически правильную, хотя и вневременную, взаимосвязь событий, которая естественным и эффективным образом закрепляется в структуре и механизме выполнения сетей Петри.

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

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

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

Ограниченность. Позициясетиявляется s-ограниченной, если

.

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

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

.

Если , то сеть является строго сохраняющей, и в ней выполняется условие

.

Тупики. Множество переходов сети Петри ( или один какой-то переход), которые в некотором состоянии сети оказываются заблокированными (не могут более выполняться), называются тупиками.

Активность.Нетупиковые переходы называются активными. Тупик имеет активность нулевого уровня. Переходt_jТсети Петрибудет активным, если существует такая разметка сети, при которой переход оказывается возбужденным. Активный переход называется переходом первого уровня активности. Переходt_j обладает активностью уровняn, если в сети может существовать последовательность срабатываний переходов, в которой данный переход будет выполняться не менееnраз.

Достижимость. Достижимой в сети Петриназывается разметка , т.е. существует последовательность срабатывания переходов, переводящая сеть из состоянияM_o в состояниеM_k.

Живость.Сеть- живая, если все ее переходы живые. Переходназывается живым, если для любой разметкив сети достижима разметка , при которой переходt_j может сработать.

Наибольшие затруднения при изучении свойств сетей Петри связаны с задачами достижимости. Для неограниченных сетей эти задачи могут быть решены лишь в некоторых частных постановках. Исследование достижимости на ограниченных сетях удается проводить только для сетей относительно небольших размеров.

Наряду с рассмотренным нами графическим представлением сетей Петри довольно часто используют матричные способы их описания: или, где- матрица инциденций размерности;

- вектор начальной разметки сети.

Если - некоторая текущая разметка сети Петри, то неравенство выражает условие возбуждения перехода, а уравнениеформально задает правило нахождения новой маркировки сети, возникающей в ней сразу после срабатывания перехода. Здесь- вектор-строка длины, имеющая единственный ненулевой элемент, равный 1, в позицииj.

Проиллюстрируем применение матричной формы описания сети Петри. Для этого воспользуемся данными примера.

Матрицы инциденций сети, приведенной на рис.5.4, имеют вид

;;.

Начальная разметка M₀=(0110).

, т.е. при разметкеМ₀срабатывает переходt₃, в результате чего сеть переходит в новое состояние и получает разметку

.

Обозначим через  конечную сумму векторов вида (j).Каждый образующий эту сумму вектор(j)устанавливает факт срабатывания переходапри выполнении некоторой рассматриваемой последовательности переходов. Количество слагаемых суммы равно числу переходов, составляющих последовательность. Отдельные переходы в последовательности могут повторяться. Множество вхождений каждого перехода в последовательность указывает, сколько раз этот переход сработал при реализации данной последовательности. Отсюда следует, что в состав суммы некоторые векторы(j)входят столько раз, сколько раз повторяются переходыt_jв рассматриваемой последовательности.

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

При известной матрице инциденций Rи заданной начальной разметкеМ₀ (или конечной разметкеМ_k) это уравнение можно использовать при анализе достижимости, цикличности, ограниченности, безопасности, живости, тупиков и других свойств сетей Петри. Разработка эффективных машинно-ориентированных методов решения однородных и неоднородных систем линейных целочисленных уравнений относится к области вычислительных задач линейной алгебры и целочисленного программирования.