7. Функционирование сетей Петри

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

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

Сеть Петри начинает функционировать при начальной разметке М₀ (Что такое начальная разметка и как ее выполнить?). Изменение разметок М₁, … происходит при срабатывании одного из переходов (Что такое переход как электронное устройство и как его запустить?). Переход может произойти при соблюдении такого условия: переход V_i может сработать при разметке М, если для каждого места P_i, принадлежащего множеству мест P, т.е. P_i  P, имеется неотрицательное значение разности М(Р) – F(P_i, V_j) ≥ 0, которое означает, что все входные места перехода V_j содержат хотя бы по одной фишке, т.е. в этом случае все места P_i такие, что F(P_i, V_j) = 1.

В результате срабатывания перехода V_j при разметке М последняя сменяется разметкой М′ по правилу: P_i  P, М′(Р_i) = М(Р_i) – F(P_i, V_j) + H(P_i, V_j).

Это правило соответствует данному ранее описанию процесса функционирования сети Петри: переход V_i изымает по одной фишке из каждого своего входного места и добавляет по одной фишке в каждое свое выходное место, т.е. в каждое место Рi , такое, что Н(V_i, P_i) = I.

Запись M  М′ означает, что разметка М предшествует разметке М′, а разметка М′ следует за разметкой М. Если в некоторой цепочке разметок последней оказалась разметка М_i+1, при которой не может сработать ни один переход, то сеть Петри останавливается, а такая разметка М_i+1 называется тупиковой.

Рассмотрим несколько шагов функционирования сети, заставляя "случайным образом" срабатывать переходы сети. Напомним, что разметка М сети Петри – это присвоение фишек местам. Формально разметка представляет собой функцию, которая отображает множество мест Р в множестве неотрицательных целых чисел K, т.е. M: P → К. Разметка также определяется как n-мерный вектор М = (М₁, ..., М_n), где n = | P | и каждое М_i K, i = 1, 2, ..., n. Вектор М определяет для каждого места Р_i сети Петри количество фишек в этом месте.

Процесс функционирования сети Петри, представленной на рисунке 2, сведен в таблицу, в которой приведены смены разметок сети, начиная с М₀ (первая строка таблицы – первый n-мерный вектор разметки). При начальной разметке М₀ только один переход V₁ может сработать. Происходит смена разметок М_о  M₁ (вторая строка). Переход V_i изымает по одной фишке из каждого своего входного места и добавляет по одной фишке в каждое свое выходное место, т.е. в каждое место Рi, такое, что Н(V_i, P_i) = I. Поэтому вторая строка таблицы разметки M₁ имеет следующие значения Р = (1, 1, 1, 1).

Разметка		Места
М	V	Р1	Р2	Р3	Р4
M0	Vi	2	0	1	0
M1	V2	1	1	1?	1
М2	V3	0	1	2	0
М3	V1	1	0	1	0
М4	V1	0	1	1	1
М5	V3	1	0	0	1
М6	V1 V2	0	1	0	2
М7		0	0	1	0

При разметке M₁ к срабатыванию готовы все три перехода V₁, V₂ и V₃ (Каково условие готовности к срабатыванию?). Однако может сработать только один переход. Предположим, что "случайным образом" сработает переход V₂. Образовалась разметка М₂, при которой может сработать только переход V₃. Образовалась разметка М₃, при которой может сработать только переход V₁. Образовалась разметка М₄, при которой может сработать только переход V₁. Образовалась разметка М₅, при которой могут сработать два перехода: V₁ и V₂. Пусть сработает переход V₁, приходим к разметке М₆ , которая оказалась тупиковой. Процесс функционирования сети остановился. Если бы при разметке М₅ сработал переход V₂, а не V₁, то образовалась бы разметка М₇ , которая тоже оказалась тупиковой. Ни один из переходов сработать не может.

Если при переходе к разметке М₁ "случайно" сработает переход V₁ или переход V₃, а не переход V2, то пошаговая смена разметок по цепочке срабатывания переходов примет следующий вид:

М0  V1  М1  V2  М2 V3  М3  V1  М4  V3  М5 	 V1  М6
	 V2  М7

В этом случае оказались достижимыми разметки М₆ и М₇, являющиеся заключительными (тупиковыми). Если вернуться к разметке М₁ (1, 1, 1, 1), при которой готовы к срабатыванию и разрешены переходы V₁, V₂, V₃, то можно показать образование следующих цепочек (последовательностей) срабатываний, приводящих в каждом случае к достижению тупиковых разметок:

V₁  V₃  V₁ (0, 2, 0, 3),

V₁  V₃  V₂  V₃  V₂ (0, 0, 1, 0),

V₁  V₃  V₂  V₃  V₁ (0, 1, 0, 2),

V₃  V₁ (0, 1, 0, 2), V₂  V₃  V₁ (0, 0, 1, 0).

8. Дерево достижимости сети Петри