Сети Петри, определения, основные элементы, правила срабатывания переходов. Примеры изменения вектора маркировок при последовательном срабатывании переходов

- Сети Петри являются средством математического описания процессов функционирования дискретных систем с параллельно и асинхронно действующими элементами.

- Сеть Петри представляется множеством векторов

S = f (P, T, I, O).

где Р - вектор позиций, Т - вектор переходов, I - вектор входных функций и O - вектор выходных функций.

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

- Модель представляет собой последовательность событий.

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

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

- Число состояний сети Петри (СП) определяется числом возможных маркировок. Если позиции пронумерованы (проиндексированы), то состояние системы определяется вектором состояний (или маркировкой), например, Р (0,1,0,0,1,…).

Пример: модель простой ВС.

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

- Событие ti происходит (переход срабатывает), если имеются маркеры во всех входных позициях для перехода ti.

- Свершение события ti заключается в изъятии маркеров из всех входных позиций и в помещении их во все выходные позиции для перехода ti.

- В модели данного примера переходы описывают следующие события: t 12 – (событие) появление задачи на входе ВС, t 10 – (событие) начало решения задачи, t 11 – (событие) окончание решения задачи, t 13 – (событие) выход решенной задачи из ВС. Позиция Р 1 соответствует условию, что во входной очереди имеется задача, Р 2 – (условие) решение окончено, Р 3 – (условие) процессор свободен, Р 4 – (условие) в выходной очереди имеется задача.

- Начальная маркировка в данном примере задана исходным вектором Р 0 = (Р 1, Р 2, Р 3, Р 4) = (0, 0, 1, 0). Приход задачи в ВС отображается запуском перехода t12 и появлением маркера в позиции Р 1, вектор состояния будет иметь вид - (1, 0, 1, 0). Теперь удовлетворяются условия для срабатывания перехода t 10, в результате чего удаляются маркеры из позиций Р 1 и Р 3, помещается маркер в позицию Р 2. Тогда маркировка будет иметь вид - (0, 1, 0, 0). Далее выполняются условия для срабатывания перехода t 11, появляется новая маркировка - (0, 0, 1, 1). Выполняются условия для срабатывания t1 3, и система приходит в исходное состояние - (0, 0, 1, 0).