14. Сети Петри

Одно из основных достоинств аппарата сетей Петри заключается в том, что они могут быть представлены как в графической форме (что обеспечивает наглядность), так и в аналитической (что позволяет автоматизировать процесс их анализа).

При графической интерпретации сеть Петри представляет собой граф особого вида, состоящий из вершин двух типов — позиций и переходов, соединенных ориентированными дугами, причем каждая дуга может связывать лишь разнотипные вершины (позицию с переходом или переход с позицией). Вершины-позиции обозначаются кружками, вершины-переходы - черточками. С содержательной точки зрения переходы соответствуют событиям, присущим исследуемой системе, а позиции — условиям их возникновения. Таким образом, совокупность переходов, позиций и дуг позволяет описать причинно-следственные связи, присущие системе, но в статике. Чтобы сеть Петри «ожила», вводят еще один вид объектов сети — так называемые фишки, или метки позиций. Переход считается активным (событие может произойти), если в каждой его входной позиции есть хотя бы одна фишка [3].

Расположение фишек в позициях сети называется разметкой сети (пример перемещения фишек по сети приведен на рисунке 14.1.).

Рис. 14.1. Пример изменения разметки сети Петри при срабатывании переходов

В аналитической форме сеть Петри может быть представлена следующим образом:

P=(B,D,I,0,M),

где В = {b_i} — конечное непустое множество позиций;

D = {d_i } — конечное непустое множество переходов;

I: BxD → 0,1 — входная функция (прямая функция инцидентности), которая для каждого перехода задает множество его входных позиций;

О: DxB → 0,1 — выходная функция (обратная функция инцидентности), которая для каждого перехода задает множество его входных позиций;

М - функция разметки сети, т.е. М: В → 0, 1, 2,... - ставит каждой позиции сети в соответствие неотрицательное целое число.

Срабатывание перехода d_j изменяет разметку сети М(В) на разметку M'(B) по следующему правилу:

М'(В) = М(В) – I(d_j) + O(d_j),

т о есть переход d_j изымает по одной метке из каждой своей входной позиции и добавляет по одной метке в каждую из выходных позиций. Смену разметки обозначают так:

Основные направления анализа сети Петри следующие:

1. Проблема достижимости: в сети Петри с начальной разметкой М₀. Требуется определить, достижима ли принципиально некоторая разметка М' из М₀

С точки зрения исследования моделируемой системы, эта проблема интерпретируется как проблема достижимости (реализуемости) некоторого состояния системы.

2. Свойство живости. Под живостью перехода понимают возможность его срабатывания в данной сети при начальной разметке M₀.

Анализ модели на свойство живости позволяет выявить невозможные состояния в моделируемой системе (например, неисполняемые ветви в программе).

3. Безопасность сети. Безопасной является такая сеть Петри, в которой ни при каких условиях не может появиться более одной метки в каждой из позиций.

Для исследуемой системы это означает возможность функционирования ее в стационарном режиме. На основе анализа данного свойства могут быть определены требования к буферным накопителям в системе.

Итак, достоинства сетей Петри заключаются в том, что они:

1. позволяют моделировать ПП всех возможных типов с учетом вероятных конфликтов между ними;

2. обладают наглядностью и обеспечивают возможность автоматизированного анализа;

3. позволяют переходить от одного уровня детализации описания системы к другому (за счет раскрытия/закрытия переходов).

Контрольные вопросы

1. Дайте формальное определение сети Петри?

2. Что такое разметка сети?

3. Укажите основные направления анализа сетей Петри.

4. Перечислите достоинства и недостатки сетей Петри.

5. Где можно применять сети Петри?