Анализ абстрактного сценария на основе сетей Петри

Краткие сведения о сетях Петри

Сеть Петри (СП) – это хорошо известная дискретная динамическая модель с наглядным графическим представлением. Классические определения СП – формальные. Однако в аспекте сценарно-логического моделирования СРЭ уместно напомнить и достаточно очевидные содержательные понятия, связанные со структурой, поведением и свойствами СП. Структура СП определена как ориентированный граф с двумя типами вершин – позициями и переходами, изображаемыми соответственно кружками и планками (черточками). Дуги в графе соединяют только вершины разного типа (двудольный граф). В позиции помещаются маркеры, изображаемые жирными точками. Число маркеров в позиции определяет её состояние, а набор состояний всех позиций – состояние (маркировку) СП. Маркировка позиции и сети в целом является переменной величиной – функцией дискретного времени. Начальная маркировка СП указывается на её рисунке. Пример структуры СП, заимствованный из [Питерсон, 1984], дан на рис. 1.2.

Рис. 1.2. Пример сети Петри

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

1)  ограниченность (число маркеров в позиции не превышает величины ее емкости k, если k=1, то сеть называют безопасной);

2)  сохранение (число циркулирующих в сети маркеров постоянно);

3)  активность (переход называют активным, если в сети отсутствует маркировка, в которой он никогда не может активироваться, т.е. является тупиковым; различают 5 разных уровней активности переходов);

4)  достижимость и покрываемость (маркировка достижима в СП, если существует цепочка срабатываний переходов, ведущая из начальной в данную маркировку; маркировка М₁ покрывает маркировку М₂, если все маркировки позиций в М₁ не меньше соответствующих маркировок в М₂, но по меньшей мере одна строго больше);

5) реализуемость последовательности переходов (определить «пройдёт» ли в сети заданная последовательность переходов);

6)  эквивалентность и включение (сети эквивалентны, если они имеют одинаковое поведение, определяемое множеством достижимых маркировок или множеством реализуемых последовательностей переходов).

Рис. 1.3. Дерево достижимости для сети Петри на рис.1.2

Для проверки корректности А-сценария СРЭ (потоковой диаграммы) анализируются важнейшие свойства СП: ограниченность, отсутствие «тупиковых маркировок», отсутствие «ловушек» - циклов, не имеющих выхода. Анализ СП выполняется на основе дерева достижимости сети Петри, алгоритм построения которого описан в [Питерсон, 1984]. Неограниченность при описании маркировок позиций СП отображается специальным символом «w», обозначающим бесконечность. Для любого постоянного «с» определены операции над w: w + c = w;  w – c = w, если w≤w. Пример дерева достижимости с использованием символа w для сети Петри на рис.1.2 дан на рис. 1.3.

А-сценарий будем считать корректным если, во-первых, корректны все образующие его сценарные модули, и, во-вторых, модули корректно согласованы. Условия согласованности обсуждались выше. Что касается проверки корректности модулей, то для этого могут эффективно применяться сети Петри. Преобразование сценарного модуля в адекватную сеть Петри производится следующим образом:

1)     для каждой операции удаляется входная (выходная) стрелка, и вместо неё внутрь рамки операции помещается входная (выходная) позиция, помеченная также, как и удаленная стрелка;

2) каждой паре скобок в логической формуле преобразования потоков данной операции сопоставляется переход, также размещаемый внутри рамки операции;

3) введенный переход соединяется с входными и выходными позициями согласно логической формуле;

4) одинаково помеченные позиции, принадлежащие разным операциям, отождествляются.

Применение рассмотренного алгоритма к сценарному модулю А₀, изображенному на рис 1.1, порождает модуль в виде адекватной сети Петри, приведённый на рис. 1.4. Проведя анализ этой сети, получаем откорректированный модуль верхнего уровня абстрактного сценария, данный на рис. 1.5

Рис. 1.4. Сеть Петри, адекватная сценарному модулю А₀ (рис. 1.1)

Рис. 1.5. Откорректированный сценарный модуль верхнего уровня