Тема: Описание информационных систем с помощью сетей Петри

↑

▷ Содержание

⇐ ПредыдущаяСтр 21 из 21

Учебные вопросы:

1. Основные понятия сетей Петри.

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

3. Приложения сетей Петри.

Основные понятия сетей Петри

Информационная система, как один из видов сложных систем, характеризуется:

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

2. Недетерминированностью: подсистемы взаимодействуют в процессе функционирования системы в произвольные моменты времени, что делает поведение системы случайным (стохастическим), т.е. система при одних и тех же начальных условиях может функционировать по-разному, порождая не единственный процесс, а некоторое множество процессов.

3. Параллелизмом: несколько подсистем могут функционировать в системе одновременно, не влияя друг на друга (т.е. в системе могут протекать одновременно ряд параллельных процессов);

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

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

Событие (event)  - некоторый факт в системе, трактуемый как потенциальное действие одной из ее подсистем, которое может реализоваться один раз, повториться многократно или не произойти ни разу.

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

Условие (condition)  - предикат, являющийся логическим описанием ситуации, при которой некоторое событие может произойти (реализоваться). Т.е. если предикат, соответствующий условию  имеет значение “истина (“1”)”, то событие  может произойти; если предикат, соответствующий условию  имеет значение “ложно (“0”)”, то событие  реализоваться не может. Через  обозначается множество условий, которые связаны с событиями, принадлежащими множеству .

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

Предусловие (pre-condition) – логическое отношение “ ” нескольких условий, при истинном значении, которого некоторое событие  может реализоваться.

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

Постусловие (post-condition) – определенное сочетание нескольких условий , на которые оказывает влияние реализация события , делая их значения “истинными”.

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

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

Причинно-следственная связь (pre/consequence condition) – непосредственная зависимость между событием  и условиями , принадлежащими его предусловию и постусловию .

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

Состояние системы (state of system)  - совокупность значений истинности для каждого из условий , в некоторый момент времени .

Пусть  множество всех допустимых состояний системы .

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

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

1. Отказ от временных зависимостей приводит к тому, что события  являются элементарными, т.е. являются неделимыми и происходят “мгновенно”, а изменения значений условий  в предусловиях  и постусловиях  происходят одновременно, т.е. выполнение события  считается незримым актом.

2. Реализация события  приводит к тому, что все условия  становятся “ложными”, а  - “истинными”.

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

4. Каждое событие  при определенных условиях может реализоваться хотя бы один раз.

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

Если событие имеет длительность отличную от нуля, например,  - ” задание в процессоре обрабатывается  минут ”, и это существенно для функционирования системы, то событие  представляется в виде двух событий  и , которые происходят мгновенно:

 - “ начало обработки задания в процессоре”;

 - “ конец обработки задания в процессоре”;

и вновь вводимого условия  - “ обработка задания в процессоре в течение  минут”, которое удовлетворяет следующим отношениям принадлежности:  и .

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

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

Условно/событийная система (condition/event system) – четверка , где  - конечное непустое множество событий;  - конечное непустое множество условий;  - множество достижимых состояний;  - отображение, описывающее совокупность правил перехода.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 и

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

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

                                     3                        

                                                                   . 

						-1	-1	2
						1	-1
							3	-1

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

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

                                                                                                        петля

						1		1
							1
							1

							-1		-1
		1					1	-1
			1	1				0	1

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

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

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

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

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

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

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

            Чистая СП      Простая СП    Ординарная СП         

Рис. 7.1. Классы Сетей Петри

Сеть Петри со свободным выбором (ССВ) – простая сеть Петри такая, что:

Если ”

ССВ:

			{ }
			{ }

не ССВ:

			{ , }
			{ }

Сеть Петри со свободным выбором (свободна сеть Петри ССВ)) (free choice Petri net; FC – net) – простая сеть Петри, в которой для каждого перехода  выполняется одно из следующих условий для любой его входной позиции  (рис. 7.2):

– либо  - единственная входная позиция перехода  (т.е. позиция  больше не связана с другими переходами);

– либо, если  является входной позицией нескольких переходов

то она является единственной для этих переходов

(т.е. эти переходы больше не связаны ни с какими другими позициями).