Сети Петри

Сети Петри — аппарат для моделирования динамических дискретных систем (преимущественно асинхронных параллельных процессов).

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

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

В сетях Петри вводятся объекты двух типов:

Ø динамические — изображаются маркерами внутри узлов;

Ø статические — им соответствуют узлы сети Петри.

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

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

Правила срабатывания переходов (рис. 1), конкретизируют следующим образом:

а) переход срабатывает, если для каждого из его входных узлов выполняется условие , где — число маркеров в -м входном узле, — число дуг, идущих от -го узла к переходу;

б) при срабатывании перехода число маркеров в -м входном узле уменьшается на , а в -м выходном узле увеличивается на , где — число дуг, связывающих переход с -м узлом.

На рис. 1 показан пример распределения маркеров по узлам перед срабатыванием, эту маркировку записывают в виде (2,2,3,1). После срабатывания перехода маркировка становится иной: (1,0,1,4).

Рис. 1. Фрагмент сети Петри

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

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

Рис. 2. Конфликтная ситуация

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

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

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