Основные соотношения.Для формального описания структуры и взаимодействия параллельных систем и процессов, а также анализа причинно-следственных связей в сложных системах используются сети Петри (англ. Petri Nets), называемые N-схемами.
Графы специального вида, получившие в дальнейшем название “Сети Петри” были впервые введены Карлом Петри в 60-х годах. В следующем десятилетии начался “бум” разработок в этом направлении. Популярность сетей Петри вызвана удачным представлением различных типов объектов, присутствующих во многих моделируемых системах и “событийным” подходом к моделированию.
Формально N-схема задается четверкой вида
N = <B, D, I, O>,
где В – конечное множество символов, называемых позициями, B ¹ O;
D – конечное множество символов, называемых переходами D ¹ O,
B Ç D = O;
I – входная функция (прямая функция инцидентности), I: B ´ D ® {0, 1};
О – выходная функция (обратная функция инцидентности),
О: B ´ D ® {0, 1}.
I - переход dj в множество входных позиций bj Î I(dj),
O - переход dj в множество выходных позиций bj Î О(dj).
Для каждого перехода dj Î D
I(dj) = { bi Î B | I(bi, dj) = 1 },
O(dj) = { bi Î B | O(dj, bi) = 1 },
i = ; j = ; n = | B |, m = | D |.
Для каждой позиции bi Î B
I(bi) = { djÎ D | I(dj, bi,) = 1 },
O(bi) = { djÎ D | O(bi, dj) = 1 }.
Таким образом входная функция I отображает переход dj в множество входных позиций bj Î I(dj), а выходная функция O отображает переход dj в множество выходных позиций bj Î О(dj). Для каждого перехода dj Î D можно определить множество входных позиций перехода I(dj) и выходных позиций перехода O(dj) как
Аналогично для каждой позиции bi Î B вводятся определения множеств входных переходов позиции I(bi) и выходных переходов позиции O(bi):
Графически N-схема изображается в виде двудольного ориентированного мультиграфа, представляющего собой совокупность позиций и переходов (рис. 1). Граф N-схемы имеет два типа узлов: позиции и переходы, изображаемые O и | соответственно. Ориентировочные дуги соединяют позиции и переходы, причем каждая дуга направлена от элемента одного множества (позиции или перехода) к элементу другого множества (переходу или позиции). Граф N-схемы является мультиграфом, так как он допускает существование кратных дуг от одной вершины к другой.
Рис. 1. Графическое изображение N-схемы
Пример.Представим формально N-схему, показанную в виде графа на рис. 1:
N = <B, D, I, O>,
B = <b1, b2, b3, b4, b5>,
D = <d1, d2, d3, d4>.
Входные позиции перехода Выходные позиции
перехода
I(d1)={b1}, O(d1)={b2, b3, b5},
I(d2)={b2, b3, b5}, O(d2)={b5},
I(d3)={b3}, O(d3)={b4},
I(d4)={b4}. O(d4)={b2, b3}.
Возможные приложения N-схем.Приведенное представление N-схемы может использоваться только как отражение статики моделируемой системы (взаимосвязи событий и условий), но не позволяет отразить в модели динамику функционирования моделируемой системы. Для представления динамических свойств объекта вводится функция маркировки (разметки) позиций М: В ® {0, 1, 2, …}. Маркировка М есть присвоение неких абстрактных объектов, называемых метками (фишками), позициям N-схемы, причем количество меток, соответствующее каждой позиции, может меняться. При графическом задании N-схемы разметка отображается помещением внутри вершин позиций соответствующего числа точек (когда количество точек велико, ставят цифры).
М: В ® {0, 1, 2, …}.
Маркированная (размеченная) N-схема может быть описана в виде
NМ = <B, D, I, O, M>.
М0: В ® {0, 1, 2, …}.
Функционирование N-схемы отражается путем перехода от разметки к разметке. Начальная разметка обозначается как Смена разметок происходит в результате срабатывания одного из переходов dj Î D сети.