Анализ сетей Петри Докладчик: Манузина А. Н. Преподаватели: проф. Губарев В. В., д.т.н., доц. Казанская О. В., к.т.н. Тема магистерской диссертации: Автоматизация документооборота электронного обучения Руководитель: проф. Бобко И. М., д.т.н

Список литературы 1.Котов В. Е. Сети Петри. - М.: Наука, Питерсон Дж. Теория сетей Петри и моделирование систем. - М.: Мир, Майника Э. Алгоритмы оптимизации на сетях и графах /Под ред. Е.К.Масловского - М.: Мир, c.

Цель работы Ознакомиться с сетями Петри; привести основные понятия, структуру и свойства сетей Петри Рассмотреть основные принципы анализа сетей Петри Рассмотреть применение сетей Петри для проверки корректности абстрактного сценария бизнес-систем

Основные понятия Сеть Петри – это помеченный ориентированный двудольный граф. Все вершины графа относятся к одному из двух классов - позициям и переходам. Позиции изображаются окружностями, переходы - отрезками прямой. Дуги в сетях Петри - направленные. Причем каждая дуга связывает вершины только разных классов.

Основные понятия входная позиция некоторого конкретного перехода – позиция, из которой исходят дуги, входящие в данный переход. выходная позиция некоторого конкретного перехода - позиция, в которую входят дуги, исходящие из данного перехода. Срабатывание перехода состоит в изъятии фишек из каждой входной позиции и помещении их в каждую выходную позицию. Причем, количество фишек, изымаемых из конкретной позиции, или помещаемых в конкретную позицию равно количеству дуг, соединяющих срабатывающий переход с данной конкретной позицией.

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

Структура сети Петри

Свойства сетей Петри Предметом теоретического исследования сетей Петри является процесс их функционирования, т.е. возможные последовательности срабатывания переходов и свойства получаемых при этом разметок сети. Свойства сетей Петри Ограниченность Сохранение Активность Достижимость и покрываемость Эквивалентность и включение

Ограниченность Под ограниченностью понимают свойство сети не допускать превышения количества фишек в конкретной или произвольной позиции некоторого фиксированного числа. Позиция сети Петри ограничена (k-ограничена), если существует такое целое число k, что число объектов в этой позиции никогда не превышает k. Число k называют емкостью позиции. Сеть Петри ограничена, если ограничены все ее позиции. Если известны емкости всех позиций, и наибольшая из них kmax, то сеть называют kmax-ограниченной. Сеть, все позиции которой 1-ограничены, называют безопасной.

Ограниченность Ограниченная сеть Не ограниченная сеть

Сохранение Сеть Петри называют сохраняющей, если число циркулирующих в ней объектов постоянно.

Активность Переход сети Петри называют тупиковым, если в процессе функционирования сеть может оказаться в состоянии, в котором этот переход заблокирован. Нетупиковый переход называют активным. активность уровня 0, если он никогда не может быть активирован (пассивный переход); активность уровня 1, если существует состояние (достижимое из начального), в котором он активирован; активность уровня 2, если для всякого целого n существует последовательность срабатывания переходов, в которой данный переход присутствует по крайней мере n раз; активность уровня 3, если существует бесконечная последовательность срабатывания переходов, в которой данный переход присутствует неограниченно часто; активность уровня 4, если для любого достижимого состояния существует последовательность срабатываний, приводящая в такое состояние, в котором этот переход активирован (активный переход).

Активность Пример сети всегда приходящей к тупиковой разметке. Сеть никогда не "попадает в тупик" Сеть, которая может остановиться, а может и нет

Достижимость и покрываемость Состояние S достижимо в сети Петри, если существует цепочка срабатываний переходов, ведущая из начального состояния в S. Состояние S'=(P1'...Pn') покрывает состояние S"=(P1"...Pn"), если для каждого i=1,...,n имеет место Pi' Pi", т.е. имеет место S' S". Задача достижимости (покрываемое) состоит в том, чтобы для данной сети и состояния S определить достижимо ли S (достижимо состояние, покрывающее S). Задачи достижимости и покрываемости можно рассматривать применительно к набору не всех, а лишь некоторых позиций, т.е. к подсостояниям сети Петри.

Эквивалентность и включение Сети Петри эквивалентны, если они имеют одинаковое поведение, определяемое множеством достижимых состояний или множеством реализуемых последовательностей переходов. Сеть СП1, включается в сеть СП2, если поведение СП1 является подмножеством поведения СП2.

Анализ сети Петри Анализ сети Петри выполняется на основе ее дерева достижимости Алгоритм построения дерева достижимости: Пусть S=(P1,..,Pn) граничная вершина дерева (состояние сети Петри), не являющаяся тупиковой или дублирующей. Тогда для каждого перехода tj, активированного в S, создается новая вершина S' =(Pi',..,Pn'), в которой состояние позиций Рi', i=1,...,n, определяется следующим образом: ЕСЛИ Pi=So, ТО Р,' = ω ЕСЛИ на пути от корневой вершины к S существует вершина S"=(Р1",..,Рn"), такая что S'>S" (Рi'>Рi"), ТО Рi'= ω В противном случае значение Рi' определяется на основе срабатывания перехода tj из состояния S Вершина S переопределяется как внутренняя, вершина S' становится граничной. Алгоритм заканчивает работу, когда все вершины дерева тупиковые, дублирующие или внутренние.

Дерево достижимости

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

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

Применение сетей Петри для проверки корректности абстрактного сценария Проверка корректности сценария бизнес-системы может быть организовано 2 способами: глобальная процедура локальная процедура Сценарий бизнес-системы будем считать корректным, если: корректны все образующие его сценарные модули модули корректно согласованы

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

Заключение Рассмотрены сети Петри, даны основные понятия сетей и их свойства Рассмотрены принципы анализа сетей Петри Рассмотрен способ применения анализа сетей Петри для корректировки абстрактных сценариев бизнес- систем