Мережі Петрі

Приклад мережі Петрі.

Мережа Петрі — математична абстакція для представлення дискретних розподілених систем. Графічно представляється у вигляді дводольного орієнтованого мультиграфу з маркерами («фішками») (маркований орієнтований граф), який має дві групи вершин: позиції та переходи. Позиції можуть бути пустими або маркованими та визначають <стан> мережі. Переходи визначають дії. Орієнтовані ребра графу задають зв'язки між позиціями та переходами. Процес функціонування мережі Петрі полягає в послідовному «виконанні» переходів, та відповідному перерахункові кількості «фішок» у позиціях. Дуги можуть бути кратними, коли два вузли з'єднані більше ніж однією дугою однакового напрямку. Альтернативно, для відображення кратності дуг може використовуватися функція «ваги» дуг.

Визначення

Мережа Петрі задається у вигляді маркованого дводольного орієнтованого графу. Розрізняють два види вершин:

• Позиції. P — множина позицій,
• Переходи. T — множина переходів.

Ребра називають дугами. Петлі в графі мереж Петрі неможливі, оскільки дуги можуть з'єднувати лише вершини різних типів (позиції та переходи). Позиції що з'єднані дугами з переходом називають вхідними та вихідними для цього переходу, відповідно до напрямку цих дуг.

Кожній позиції приписують деяке ціле додатнє число

$\mu _{p}\in \mathbb {N} \cup \{0\}$

що називається маркуванням. Сукупність маркувань всіх позицій можна записувати у вигляді вектора.

Таким чином, для того щоб задати мережу Петрі, необхідно задати пару

$\left\langle \mathbf {N} ,\mu _{0}\right\rangle$

де $\mu _{0}=\left\{\mu (p_{1}),\mu (p_{2}),...\mu (p_{n})\right\}$ — вектор маркування позицій, $\mathbf {N}$ — структура мережі Петрі:

$\mathbf {N} =\left\langle \mathbf {P} ,\mathbf {T} ,\mathbf {I} ,\mathbf {O} \right\rangle$.

де $\mathbf {P}$ — множина позицій, $\mathbf {T}$ — множина переходів, $\mathbf {I}$ — вхідна функція, $\mathbf {O}$ — вихідна функція.
Вхідна та вихідна функції задаються у вигляді множин комлектів позицій, які є вхідними та вихідними для заданого переходу:

$\mathbf {I} =\left\{\mathbf {I} (t_{j})\right\}$, $\mathbf {\mathbf {I} } (t_{j})=\left\{p_{k}\right\}$.

$\mathbf {O} =\left\{\mathbf {O} (t_{j})\right\}$, $\mathbf {\mathbf {O} } (t_{j})=\left\{p_{k}\right\}$.

Комплект — узагальнення множини, в якому допускається багаторазове включення однакових елементів. Для комплектів визначається операція кратності. Для запису функції кратності використовується символ #. Кратність вхідної (вихідної) позиції $p_{i}$ для переходу $t_{j}$ це кількість появ позиції $p_{i}$ у вхідному (вихідному) комплекті переходу $t_{j}$:

$\#(p_{i},\mathbf {I} (t_{j}))$.

Альтернативною формою представлення вхідної та вихідної функції є задання множини дуг та окремого вектору кратності (ваги) дуг.
Виконання переходу можливе лише за наявності достатньої кількості «фішок» у його вхідних позиціях. Умова можливості виконання переходу $t_{j}$:

$\mu (p_{i})\geq \;\#\left(p_{i},\mathbf {I} (t_{j})\right)\forall p_{i}\in \mathbf {P}$.

Результатом виконання переходу є зміна кількості «фішок» у вхідних та вихідних позиціях цього переходу, тобто зміна маркування (стану) мережі Петрі. Нове маркування $\mu ^{i+1}$ визначається таким співвідношенням:

$\mu ^{i+1}(p_{i})=\mu ^{i}(p_{i})-\#(p_{i},\mathbf {I} (t_{j}))+\#(p_{i},\mathbf {O} (t_{j}))$,

де $t_{j}$ — перехід що виконується $\mu ^{i+1}(p_{i})$ — попереднє маркування.
Цей вираз дозволяє записати векторну функцію наступного стану, яка виражає наступне маркування мережі Петрі через попереднє маркування та перехід що виконується:

$\mu ^{i+1}=\delta \left(\mu ^{i},t_{j}\right)$.

Для заданої послідовності виконання переходів $\sigma =\left\langle t_{j1},t_{j2},...,t_{jl}\right\rangle$ використовується розширена функція наступного стану:

$\mu ^{i+l}=\delta \left(\mu ^{i},\sigma \right)=\delta \left(...\delta \left(\delta \left(\mu ^{i},t_{j1}\right),t_{j2}\right),...,t_{jl}\right)$.

Виконання переходів є атомарним, тобто перехід змінює стан всіх вхідних та вихідних позицій однією дією, яка не може бути перервана виконанням іншого переходу. Виконання мереж Петрі в цілому є недетермінованим:

1. відразу декілька переходів можуть бути дозволеними, і кожен з них може бути виконаний
2. дозволені переходи не обов'язково виконуються. Дозволений перехід може бути виконаний.

Взагалі, мережі Петрі не розглядають поняття «часу» виконання переходу, а лише послідовність виконань. За допомогою мереж Петрі можна моделювати такі якості як:

• асинхронність,
• конфліктнісь,
• паралелізм.

Дослідження мережі Петрі

Основні методи дослідження мереж Петрі:

1. Дерево досягальності,
2. Графічний,
3. Аналітичний,
4. За допомогою еквівалентних перетвореннь.

Взагалі, мережі Петрі досліджують на такі властивосі:

1. Безпечність — досліджує виконання умови що кількість «фішок» в позиції не перевищує 1;
2. Обмеженість — досліджує виконання умови що кількість «фішок» в позиції не перевищує заданого числа,
3. Зберігальність — досліджує виконання умови що кількість «фішок» в мережі не змінюється,
4. Оберненість — для довільного досяжного стану досліджується існування послідовності виконань переходів яка повертає мережу в початковий стан),
5. Активність переходів — досліджує можливість виконання певних переходів та наявність тупиків — станів у яких переходи не дозволені та для яких неможливо досягти стану в якому ці переходи дозволені,
6. Досяжність маркування — досліджує існування послідовності виконань переходів при якій можна досягнути задане маркування,
7. Покриття — досліджує існування послідовності виконань переходів при якій можна досягнути маркування що покриває (є більшим) за задане маркування.

Умова зберігальності може бути послаблена, для чого вводять поняття функції ваги:

$\mathbf {W} :\qquad (\mathbf {T} \times \mathbf {P} )\cup (\mathbf {P} \times \mathbf {T} )\to \mathbb {N} \cup \{0\}$

яка залишається постійною під час роботи.

Більшість досліджень мереж Петрі можна звести до побудови дерева досяжності.

Дивіться також

• Теорія графів,
• Розподілена система.

Література

• Reisig, Wolfgang; Rozenberg, Grzegorz (1998). Lectures on Petri Nets I--basic models: advances in Petri Nets. Berlin: Springer. ISBN 3-540-65306-6.
• Reisig, Wolfgang; Rozenberg, Grzegorz (1998). Lectures on Petri nets II--applications: advances in Petri nets. Berlin: Springer. ISBN 3-540-65307-4.