Сети Петри

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

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

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

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

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

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

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

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

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

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

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

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

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

Введенные понятия поясним на следующих примерах.

Пример 1

Требуется описать с помощью сети Петри работу группы пользователей на единственной рабочей станции WS при заданных характеристиках потока запросов на пользование WS и характеристиках поступающих задач. Сеть Петри представлена на рис. 3.

Здесь переходы связаны со следующими событиями: — поступление запроса на использование WS, — занятие станции, — освобождение станции, — выход обслуженной заявки; позиция используется для отображения состояния WS: если в имеется метка, то WS свободна и пришедшая заявка вызывает срабатывание перехода ; пока эта заявка не будет обслужена, метки в не будет, следовательно, пришедшие в позицию запросы вынуждены ожидать срабатывания перехода .

Рис. 3. Сеть Петри для примера 1

Пример 2

На рис. 4 представлена сеть Петри, соответствующая организации параллельных вычислений на основе асинхронного message passing interface (MPI) [1].

Рис. 4. Сеть Петри для примера 2

Пример 3

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

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

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

Рис. 5. Сеть Петри для примера 3

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