Теория вычислительных процессов
Лекция 15
назад | содержание | вперед

Лекция 15

4. СЕТИ ПЕТРИ

4.1. Введение в сети Петри

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

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

В одном из подходов к проектированию и анализу систем сети Петри используются как вспомогательный инструмент анализа. Здесь для построения системы используются общепринятые методы проектирования. Затем построенная система моделируется сетью Петри, и модель анализируется. Если в ходе анализа в проекте найдены изъяны, то с целью их устранения проект модифицируется. Модифицированный проект снова моделируется и анализируется. Цикл повторяется до тех пор, пока проводимый анализ не приведет к успеху.

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

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


4.2. Основные определения

4.2.1. Теоретико-множественное определение сетей Петри

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

Сеть Петри N является четверкой N=(p, T,I,О), где

р = {р1, р2,…,рn} - конечное множество позиций, n >=0;

т = {t1, t2,…, tm} - конечное множество переходов, m >=0;

I: Т -> P* - входная функция, сопоставляющая переходу мультимножество его входных позиций;

O: Т -> Р* - выходная функция, сопоставляющая переходу мультимножество его выходных позиций.

Позиция p P (р принадлежит Р) называется входом для перехода t T, если p I(t). Позиция p P называется выходом для перехода t T, если p O(t). Структура сети Петри определяется ее позициями, переходами, входной и выходной функциями.

Пример 4.1. Сеть Петри N =(Р,T,I,O),

Р={p1, p2, p3},

Т={ t1, t2},

I(t1)={ p1, p1, p2}, О(t1)={p3},

I(t2)={ p1, p2, p2}, О(t2)={p3}. .

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


4.2.2. Графы сетей Петри

Наиболее наглядным представлением сети Петри является её графическое представление, которое представляет собой двудольный, ориентированный мультиграф.

Граф сети Петри обладает двумя типами узлов: кружок О, представляющий позицию сети Петри; и планка -----, представляющая переход сети Петри. Ориентированные дуги этого графа (стрелки) соединяют переход с его входными и выходными позициями. При этом дуги направлены от входных позиций к переходу и от перехода к выходным позициям. Кратным входным и выходным позициям перехода соответствуют кратные входные и выходные дуги. Граф сети Петри примера 4.1.

Рис.4.1.

В графе сети Петри не возможны дуги между двумя позициями и между двумя переходами.


4.2.3. Маркировка сетей Петри

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

Маркировка m сети Петри N=(P,T,I,O) есть функция, отображающая множество позиций P во множество Nat неотрицательных целых чисел. Маркировка m, может быть также определена как n-вектор m=<m(p1), m(p2), , m(pn)>, где n - число позиций в сети Петри и для каждого 1 <i < n m(pi) Nat – количество фишек в позиции pi.

Маркированная сеть Петри N=(P,T,I,O,m) определяется совокупностью структуры сети Петри (P,T,I,O) и маркировки m. На рисунке 4.2 представлена маркированная сеть Петри m = <1,0,1>.

Рис. 4.2

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


4.2.4. Правила выполнения сетей Петри

Сеть Петри выполняется посредством запусков переходов. Запуск перехода управляется фишками в его входных позициях и сопровождается удалением фишек из этих позиций и добавлением новых фишек в его выходные позиции.

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

Пусть функция ^#: РxТ -> Nat для произвольных позиции р Р и перехода t T задает значение ^#(р,t), которое совпадает с кратностью дуги, ведущей из р в t, если такая дуга существует, и с нулем, в противном случае.

Пусть функция #^: ТхР ->Nat для npоизвольных и перехода t T позицни p Р задает значение #^(t,р), которое совпадает с кратностью дуги, ведущей из t в р, если такая дуга существует, и с нулем, в противном случае.

Переход teT в маркированной сети Петри N=(P,T,l,O,m) разрешен, если для всех p I(t) справедливо m(p)>= ^#(р,t).

Запуск разрешённого перехода t T из своей входной позиции p I(t) удаляет ^#(p,t) фишек, а в свою выходную позицию р' O(t) добавляет #^(t,р') фишек.

Сеть Петри до запуска перехода t1 (рис. 4.3, а). Сеть Петри после запуска перехода t1 (рис. 4.3, б).

Рис 4.3.

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

m’(p)=m(p)- ^#(p,t)+#^ (t,p).

Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный переход. Когда не останется ни одного разрешенного перехода, выполнение прекращается.

Если запуск произвольного перехода t преобразует маркировку m сети Петри в новую маркировку m', то будем говорить, что m' достижима из m посредством запуска перехода t и обозначать этот факт, как m->tm'. Это понятие очевидным образом обобщается для случая последовательности запусков разрешённых переходов. Через R(N,m) обозначим множество всех достижимых маркировок из начальной маркировки m в сети Петри N.

Преобразование маркировки сети Петри изображено на рисунке 4.3. Переход t1, преобразует маркировку m =<5,1> в маркировку m'=<2,3>.


назад | содержание | вперед