Сеть Петри - это математическая модель дискретных динамических систем (параллельных программ,операционных систем, ЭВМ и их устройств, сетей ЭВМ), ориентированная на качественный анализ и синтез таких систем (обнаружение блокировок, тупиковых ситуаций и узких мест, автоматический синтез параллельных программ и компонентов ЭВМ и др.). .
Формально в терминах теории систем [11] сеть Петри (Petri Net - PN) - это набор элементов (кортеж)
PN = {O,P,T,F,M0}.(2.1)
В этом определении:
O= {0 = 0,1,2,...} - множество дискретных моментов времени;
Р = {р1,р2,...,рп,) - непустое множество элементов сети, называемых позициями (местами);
T ={t!,t2,…,tm) - непустое.множество элементов сети, называемых переходами.
Множества позиций и переходов не пересекаются:
P ÇT = Æ.
F– функция инцидентности,
F :(P x T) È (T x P) ® {0,1,2,…,k,…}, (2.2)
где k - кратность дуги. М 0- начальная маркировка позиций: М 0 : Р® {0,1,2,...}.
Функция инцидентности может быть представлена в виде F = FpÈ F' и фактически задает два отображения:
1) F p(p,t)=P x T®{0,1,2,..), т.е. для каждой позиции указываются связанные с ней переходы (с учетом их кратности);
2) F t(t,p)-T x P® [0,1,2,..], т.е. для каждого перехода указываются связанные с ним позиции (также с учетом кратности).
Эти функции, в общем случае зависящие от времени, могут быть представлены матрицами инцидентности
(2.3)
(2.4)
Из вершины - позиции рÎ Рведет дуга в вершину переход tj Î Tтогда и только тогда, когда
fijp> 0. В этом случае говорят, чтоt j - выходной переход позиции p i .
Множество всех позиций рk, для которых tj- выходной переход, будем обозначать Pj. Иными словами, Pj = {pk : f pkj > 0}.
Аналогично из каждой вершины перехода tjεT дуга ведет в вершину - позицию рi εР, тогда и только тогда, когда fjit> 0 . При этом говорят, что pi - выходная позиция перевода tj. Иными словами, переход i изымает из каждой своей
Множество всех переходов tl, для которых рi - выходная позиция, будем обозначать Ti. Таким образом, Ti= {tl : f tli > 0}. При fijp > 0 и f tji > 0 эти величины называются кратностью соответствующих дуг.
Каждая позиция pi εР может содержав некоторый целочисленный ресурс μ(р)≥0, часто отображаемый соответствующим числом точек (фишек) внутри позиции (см. рис. 2.1).
Вектор М = [μ1,...μn] называют маркировкой(разметкой) сети Петри.Каждая маркировка – это отображение
М : Р® {0,1,2,...}. (2.5)
Начальная маркировка Моопределяет стартовое состояние сети Петри. один и тот же язык.
Динамика поведения моделируемой системы описывается в отличие от конечных автоматов, в терминах которых в терминах функционирования сетей Петри. Как было сказано, вписываются глобальные состояния систем, сети Петри сеть функционирует в дискретном времени q=0,1,2,... в концентрируют внимание на локальных событиях (переходах), асинхронном режиме, переходя от одной маркировки к другой, локальных условиях (позициях) и локальных связях между
Смена маркировок(начиная с Мо) происходит в результате срабатывания переходов сети. Переход tj εT может сработать при маркировке М, если для всех piεРjвыполняется условие
μi(θ)-fijp(θ)≥0,
т.е. если каждая входная позиция для данного перехода pi εPjсодержит как минимум столько фишек, какова кратность ведущей к tj дуги.
В результате срабатывания перехода tjв момент времени θ маркировка М(θ) сменяется маркировкой М(θ+1) по правилу:
μ(θ+1)= μi(θ)-fijp(θ)+f tji(θ),
i=1,…,n, j=1,…,m, i ε Pj, j ε Ti
Иными словами, переход t изымает из каждой своей входной позиции число фишек, равное кратности входных дуг, и посылает в каждую свою выходную позицию число фишек, равное кратности выходных дуг.
Если может сработать несколько переходов, то срабатывает один, любой из них. Функционирование сети останавливается, если при некоторой маркировке (тупиковая маркировка) ни один из ее переходов не может сработать. При одной и той же начальной маркировке сеть Петри может порождать, в силу недетерминированности ее функционирования, различные последовательности срабатывания ее переходов. Эти последовательности образуют слова в алфавите Т.
Множество всевозможных слов, порождаемых сетью Петри, называют языком сети Петри. Две сети Петри эквивалентны, если порождают один и тот же язык.
В отличие от конечных автоматов, в терминах которых описываются глобальные состояния систем, сети Петри концентрируют внимание на локальных событиях (переходах), покальных условиях (позициях) и локальных связях между событиями и условиями. Поэтому в терминах сетей Петри более адекватно, чем с помощью автоматов, моделируется поведение распределенных асинхронных систем.
PN = {O,P,T,F,M0}.(2.1)
