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

⇐ ПредыдущаяСтр 17 из 18Следующая ⇒

Поведение условно/событийной системы (behavior od system) – последовательный переход системы из начального состояния в любое достижимое состояние в результате реализации некоторой совокупности событий согласно правилам перехода .

Переход (transition) - вершина двудольного графа, изображаемая черточкой “ ”.

Обозначим конечное число переходов:

(имеется хотя бы один переход);

, m – число рассматриваемых в системе событий (подсистем или их действий).

Позиция (place) - вершина двудольного графа, изображаемая кружком “ “, которая соответствует условию .

Обозначим через - конечное множество позиций:

(имеется хотя бы одна позиция);

число рассматриваемых в системе условий;

- конечное множество;

- элемент множества не может быть одновременно элементом множества .

Причинно-следственные связи между событиями и условиями будем изображать в двудольном графе стрелочками “ Þ “:

– дуга, идущая от позиции к переходу : Þ , обозначает причинную связь между условием предусловия и событием ;

– дуга, идущая от перехода к позиции : Þ , обозначает следственную связь между событием и условием , принадлежащим постусловию ;

– соединения между вершинами одного типа не допускаются, т.е. позиции соединяются только с переходами, а переходы – только с позициями;

– каждый элемент должен иметь как минимум одно соединение, т.е. в двудольном графе не может быть изолированных вершин.

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

Пучок дуг (bund of arches) – специальная дуга, которая изображается двойной стрелкой “ ” и помечается числом , равным кратности дуги.

Входная функция (функция предшествования; прямая функция инцинденций) – отображение которое каждому переходу ставит в соответствие комплект входных позиций:

Выходная функция (функция следования; обратная функция инцинденций) – отображение которое каждому переходу ставит в соответствие комплект выходных позиций:

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

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

Таким образом, сеть Петри является графическим представлением структуры (статической топологии) моделируемой условно/событийной системы в виде двудольного графа с двумя видами вершин: вершин (изображаемых кружками) и вершин (изображаемых черточками). Эта абстрактная модель была предложена в 1962 г. немецким исследователем Карлом Адамом Петри для описания параллельных потоков информации в асинхронных системах.

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

Связная сеть Петри – сеть Петри , двудольный ориентированный мультиграф которой позволяет пройти из любой вершины в любую другую вершину по пути вдоль и против дуг.

Сильно-связная сеть Петри – сеть Петри , двудольный ориентированный мультиграф которой позволяет из любой вершины пройти в другую только вдоль дуг.

Емкость й позиции – целое неотрицательное число , которое характеризует степень выполнения го условия:

– 0, е условие не выполнено, ”ложно”;

– 1, е условие выполнено, ”истинно”;

– е условие выполнено с -кратным запасом;

– ( - целое положительное число).

Маркер (taken) – символ в виде точки “ ”, который используется в соответствующих кружках (позициях) для обозначения емкости каждого из условий, то есть маркер является примитивным понятием сети Петри, подобным понятиям “переход” и “позиция”. Наличие маркера внутри кружка (позиция ), говорит о выполнении условия (это событие “истинно”), а отсутствие маркера говорит о невыполнении условия (оно - ”ложно”).

Маркировка (разметка) сети Петри (marking) – отображение (множество натуральных чисел), с помощью которого всем позициям сети Петри приписываются определенные емкости .

Маркировка сети Петри может быть задана с помощью мерного вектора маркирования:

который полностью описывает текущее состояние условно/событийной системы в некоторый момент времени .

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

Маркированная сеть Петри сеть Петри с заданной начальной маркировкой .

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

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

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

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

Типы сетей Петри

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

Рассмотрим классификацию сетей Петри по ограничениям, которые могут быть наложены на дуги графа сети Петри

Общая сеть Петри – сеть Петри, на дуги ориентированного графа которой не наложено никаких ограничений.

Петля (loop) – пара, состоящая из позиции и перехода , для которого позиция одновременно является входной и выходной позицией.

Чистая сеть Петри (self-loop-free Petri net) – общая сеть Петри , свободная от петель.

Чистая сеть Петри; не ординарная сеть Петри:


-1	-1
	-1
		-1

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

Сеть Петри с петлей (не чистая сеть Петри); ординарная сеть Петри:

петля


-1		-1
	-1

Для описания не чистых сетей Петри требуются обе матрицы инциденций .

Ординарная сеть Петри (ordinary Petri net) – общая сеть Петри , кратность всех имеющихся дуг которой равна единице.

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

Следовательно, в ординарных сетях Петри комплекты сводятся к множествам.

Простая сеть Петри (simple Petri net) – ординарная сеть без петель.

Включения введенных классов СП с помощью диаграмм Вини имеют вид (рис. 7.1):

Общая сеть Петри

⇐ Предыдущая 9 10 11 12 13 14 15 161718 Следующая ⇒