Моделирование дискретных асинхронных процессов и сети Петри

Сети Петри [13] предназначены для моделирования дискретных асинхронных процессов. Их основные отличия от автоматной модели – возможность отображать параллелизм, асинхронность и иерархичность моделируемых объектов.

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

N=(P,T,F,H,m₀ )

Где P – конечное непустое множество позиций (состояний);

Т - конечное непустое множество переходов (событий);

F:P^хT®{0,1,2..} – функция входных инциденций

H:T^хP®{0,1,2..} - функция выходных инциденций

m₀ :P®{0,1,2..} – начальная маркировка (разметка) сети.

Сети Петри удобно представлять графически в виде двудольного ориентированного графа с двумя типами вершин, соответствующими

0001 0011 0010

а) S₁ S₂ б) S₁ S₂

1001

0101 1010

0110

S₃ S₄ S_{3 1100} S₄

0100 1000

00 01 000 001

в) S₁ S₂ г) S₁ S₂

101

011

S₃ S₄ S_{3 110} S₄

10? 100 010

Рис.43

позициям pÎP и переходам tÎT (рис.44) Позиции изображаются кружками. Внутри кружка могут находиться маркеры (фишки), изображаемые точками. Переходы изображаются черточками (барьерами).

Функции входных и выходных инциденций могут быть представлены матрицами. Для сети на рис. 44 имеем:

t₁ t₂ t₃ t₄ p₁ p ₂ p₃ p₄ p₅

p₁ 1 0 0 0 t₁ 0 0 1 2 0

p₂ 1 0 0 0 t₂ 1 0 0 0 1

F= p₃ 0 1 0 0 H= t₃ 1 1 0 0 0

p₄ 0 0 1 0 t₄ 0 0 0 1 0

p₅ 0 0 0 1

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

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

" pÎP:m¹(p) – F(p,t)³0

В результате срабатывания перехода t маркировка М заменяется маркировкой М¹

V_PÎP:M¹(P)= M(P) – F(p,t)+H(t,p).

Это означает, что в результате срабатывания из всех входных позиций перехода t удаляются F(p,t) маркеров, а в каждую входную позицию добавляется H(t,p) маркеров. В рассматриваемом случае маркировка M¹ непосредственно достижима из маркировки М, что обозначается М→ M¹ функционирование сети Петри – это последовательная система маркировок в результате срабатывания возбужденных переходов. Состояние сети Петри – в каждый момент времени определяется ее текущей маркировкой.

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

Возможные варианты функционирования сети описываются графом достижимости. Вершинами графа достижимости являются маркировки, а

дуги представляют отношение непосредственной достижимости на множестве маркировок.

Маркировка М называется тупиковой, если при этой маркировке ни один переход не может сработать.

Маркировка М¹ достижима из маркировки М, если на графе достижимости существует такой путь ΐ=(t₁,t₂,…,t_k), что

t₁ t₂ t_k

m→m₁→…→m¹

Множество всех маркировок, достижимых из начальной маркировки m₀, называется множеством достижимости сети Петри и обозначается R(N). На рис.45 показано построение графа достижимости.

Виды сетей Петри

Множества входных и выходных позиций перехода t обозначают соответственно (⁰p), (p⁰)

Сеть Петри называется:

- автономной сетью, если для каждого t € T имеется не более одной входной позиции и не более одной выходной позиции, т.е. |⁰t|=|t⁰|=1;

- маркированым графом, если для каждого p€P имеется только один входной и один выходной переходы, т.е. |⁰P|=|P⁰|=1;

- сетью свободного выбора, если для каждого t_i€T и для каждого p_j€*t_i позиция P_j является либо единственной входной позицией перехода t_i, т.е. |P_j *|=1, либо этот переход имеет единственную входную позицию, т.е. |⁰t_j|=1;

- простой сетью, если любая пара переходов t_i,t_j€T имеет не более одной общей выходной позиции, т.е. |*t_int_j⁰|≤1;

- бесконфликтной сетью, если для каждой позиции p€P существует не более одной исходящей дуги |P⁰|≤1 либо для всех t€T выполняется условие t€⁰p.

Дата добавления: 2015-10-23