Анализ сетей Петри на основе матричных уравнений

 

Матричный подход основывается на представлении сети двумя матрицами Д^- и Д⁺, представляющими входную и выходную функции сети. Каждая матрица имеет m строк (по одной на переход) и n столбцов (по одному на позицию). Определим матрицы Д^-(j,i)=K(P_i,I(t_j)) и Д⁺(j,i)=K(P_i,O(t_j)). Д^- описывает входы в переходы, Д⁺ - выходы из переходов, K – кратность позиции по входам и выходам.

Введём m - вектор e(j), содержащий нули везде, за исключением j-й компоненты. Переход t_j представляется m - вектором e(j).

Тогда переход t_j в маркировке М разрешён, если М≥e(j)Д^-, а результат запуска перехода t_j в маркировке М обозначим функцией δ(M,t_j) определяющей новую маркировку М’:

 

δ(M,t_j)=M - e(j) Д^- + e(j) Д⁺ = M+ e(j)(- Д^- + Д⁺) = M + e(j)Д,

 

где Д = Д⁺ - Д^- - составная матрица изменений состояний сети.

Тогда для последовательности запусков переходов G={t_j1,t_j2,…,t_jk}имеем:

 

δ(M,G) =δ(M, t_j1, t_j2,…, t_jk) =

= M + e(j₁)Д + e(j₂)Д + … + e(j_k)Д =

= M +[ e(j₁) + e(j₂) + … + e(j_k)]Д = M + f(G)Д.

 

Вектор f(G) = e(j₁)+e(j₂) …..+e(j_k) называется вектором запуска последовательности t_j1,t_j2,…,t_jk. i-й элемент вектора f(G), f(G)_i - это число запусков перехода t_j в последовательности t_j1,t_j2,…,t_jk. Вектор запусков, следовательно, является вектором с неотрицательными целыми компонентами.

Рассмотрим задачу сохранения при известном векторе взвешивания меток W. Если M₀ - начальная маркировка, а M’ - произвольная достижимая маркировка, необходимо, чтобы M₀W = M’W. Тогда существует последовательность запусков переходов G, которая переводит сеть из M₀ в M’. Поэтому,

 

M’ = δ(M₀,G) = M₀ + f(G)Д.

 

Следовательно, M₀W = M’W = (M₀ + f(G) Д) W = M₀W + f(G) ДW. Исходя из условия сохранения, имеем: f(G)ДW = 0.

Поскольку это должно быть верно для всех f(G), имеем ДW = 0.

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

Матричная теория является инструментом для решения проблемы достижимости. Пусть маркировка M’ достижима из M₀, тогда существует последовательность (возможно пустая) запусков переходов G, которая приводит из M₀ к M’. Это означает, что f(G) является неотрицательным целым решением следующего матричного уравнения для X:

 

M’ = M₀ + X Д. (*)

 

Следовательно, если M’ достижима из M₀, тогда уравнение (*) имеет решение в неотрицательных целых. Если уравнение не имеет решения, тогда M’ недостижима из M₀.

Покажем возможности применения уравнения (*) для анализа сети, приведённой на рис. 5.16.

 

Д^- =

 

 

 

Д⁺=

 

 

	-1	-1
	+2	+1	-1
		-1	+1

 

Д = Д⁺ - Д^- =

 

Рис. 5.16. Пример сети и построения матрицы Д

 

В начальной маркировке M₀=(1,0,1,0) переход t₃ разрешён и приводит к маркировке M’, где:

	-1	-1
	+2	+1	-1
		-1	+1

 

M’=(1,0,1,0)+(0,0,1) =(1,0,1,0)+(0,0, 1,1)=(1,0,0,1)

 

Последовательность G={t_­­3, t_­­2, t_­­3, t_­­2, t_­­1}представляется вектором запусков f(G)=(1,2,2) и получает маркировку M’:

 

	-1	-1
	+2	+1	-1
		-1	+1

 

M’ = (1,0,1,0) + (1,2,2) =(1,0,1,0)+(0,3,-1,0)=(1,3,0,0)

 

 

Для определения того, является ли маркировка (1, 8, 0, 1) достижимой из маркировки (1, 0, 1, 0), имеем уравнение:

 

	-1	-1
	+2	+1	-1
		-1	+1

 

(1, 8, 0, 1) = (1, 0, 1, 0) + X или

 

	-1	-1
	+2	+1	-1
		-1	+1

 

(0,8,-1,1)=X,

 

 

которое имеет решение X=(0, 4, 5). Это соответствует последовательности G= {t₃, t₂, t₃, t₂, t_3, t₂, t₃, t₂, t₃}.

Можно показать, что маркировка (1, 7, 0, 1) недостижима из маркировки (1, 0, 1, 0) поскольку матричное уравнение:

	-1	-1
	+2	+1	-1
		-1	+1

 

(1,7,0,1)=(1,0,1,0) + X или

 

 

	-1	-1
	+2	+1	-1
		-1	+1

 

(0,7,-1,1)= X,

 

 

не имеет решения.

 

 

Недостатки матричных методов.

 

1. Матрица Д теряет информацию о ситуациях, когда переходы имеют входы и выходы из одной позиции (петли).

2. Отсутствие информации о последовательности в векторе запуска. Хотя и известно число переходов, порядок их запуска неизвестен.

3. Решение уравнения (*) является необходимым для достижимости, но недостаточным.

 

 

Модификации сетей Петри

 

 

Временная сеть Петри

 

Такая сеть позволяет более реалистично отражать процессы в ВС. Во временных сетях каждому переходу t_j сопоставляется время τ_j. Если переход возбуждается, то метки, вызвавшие запуск перехода, покидают входные позиции Pre(t_j). Порождение меток в выходных позициях Post(t_j) происходит через время τ_j.

Формальное определение временной сети:

TN = {N, τ},

где N - сеть Петри; τ: T → R₀ -функция времён срабатывания, сопоставляющая каждому переходу постоянное время срабатывания; R₀ - множество неотрицательных рациональных чисел.

 

Сеть с приоритетами переходов

 

Формальное определение:

PRN = {N, PR},

где N - сеть Петри; PR - отношение приоритетности (порядка), задаваемое на множестве переходов Т и определяющее порядок потребления меток возбуждёнными переходами в условиях конфликта за метку.

 

Временная сеть с приоритетами переходов

 

Такая сеть объединяет элементы, описанные в рассмотренных выше классах сетей.

Формальное определение:

PRTN = {N, τ, PR}.

 

Пример взаимодействия двух узлов сети ЭВМ

Рассмотрим пример модели взаимодействия между узлами сети ЭВМ, описывающей протокол связи с исправлением ошибки, рис. 5.17. Протокол предусматривает подтверждение приёма посланного сообщения, повторение передачи при потере сообщения и соответствует упрощенной версии реального протокола.

Содержательный смысл, соответствующий состояниям и переходам сети Петри, имеет определённые значения.

Переходам t_j сопоставлены времена τ_j, отражающие длительность выполнения соответствующих действий в системе обработки и обмена, генераторах помех и тайм-аута. отношения приоритетности введены для двух пар переходов – (t­₂,t₈) и (t₇,t₁₁), поскольку только по отношению к ним может возникнуть конфликт за метку. Они имеют вид:

 

PR(t₈) > PR(t₂) и PR(t₇) > PR(t₁₁).

 

 

 

ПрИ – процессор-источник;

ПрП – процессор-приёмник;

ГТ – генератор тайм-аута;

ИП – источник помех;

t₁ - передача сообщений в буфер обмена;

t₂ - приём сообщения;

t₃ - посылка подтверждения о приёме данных;

t₄ - приём подтверждения;

t₅ - обработка данных в ПрИ;

t₆ - обработка в ПрП;

t₇ - повторение передачи;

t₈, t₉ - переходы модели источника помех;

t₁₀, t₁₁ - элементы ГТ;

P₁ - конец обработки в ПрИ и запрос действия t₁;

P₂ - буфер сообщения;

P₃ - ПрП готов принять сообщение и запрашивает t₂;

P₄ - ПрИ ожидает подтверждения;

P₅ - завершение действия t₂ и запуск t₃;

P₆ - запрос t₆;

P₇ - буфер подтверждения;

P₈ - запрос t₅;

P₉, P₁₀ - позиции ГТ;

P₁₁, P₁₂ - позиции ИП;

 

Рис. 5.17. Пример временной сети Петри с приоритетами.

Передача сообщения процессором-источником порождает буферирование копии сообщения и запуск генератора тайм-аута, посылку сообщения в канал, а также формирование условия подтверждения о приёме, что отражается появлением меток в P₂, P₄, P₉. Если сообщение в канале P₂ исчезнет благодаря действию ИП (что отражается возбуждением t₈), то не приходит подтверждение приёма (метка в P₇ не появится), и через время тайм-аута (связанное с t₁₀) произойдёт повторная выдача сообщения в канал (что отражается срабатыванием t₇). С t₉ связан интервал времени между потерей в канале очередного сообщения и возникновением условия для потери следующего сообщения. С t₁₀ связано время тайм-аута, через которое организуется повторная посылка потерянного сообщения. Если через τ₁₀ в P₄ нет метки, то не создадутся условия возбуждения t₇ и метка из P₁₀ покинет ГТ.

 

Рис. 5.18. Граф допустимых маркирований

 

На рисунке изображён граф допустимых маркирований элементов модели ПрП и ПрИ. В вершинах графа состояний перечислены наборы позиций, в которых одновременно находятся метки-сообщения, полученные для начального маркирования M₀. Ориентированные дуги указывают переходы между состояниями системы, а пометки у дуг указывают на переходы t, срабатывание которых вызывает данное изменение состояния.

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

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

 

 

Раскрашенные сети

 

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

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

 

 

t₁, t₂ - загрузка процессоров;

t₃, t₄ – обработка;

t₅, t₆ - освобождение процессоров

P₀ - позиция супервизора;

P₁, P₂ - заявки на обработку;

P₃, P₄ - Заявки приняты;

P₅, P₆ - конец обработки;

P₇, P₈ - обработанные заявки;

P₉, P₁₀ - двоичные семафоры,

исключающие запуск

занятых процессоров.

 

 

Рис. 5.19. Пример раскрашенной сети для двухпроцессорной системы.

 

На Рис.5.19 приведена модель процессов в двухпроцессорной системе, управляемой супервизором. Множество атрибутов-цветов, связываемых с метками и дугами сети, принято равным С = {λ, C₁, C₂, C₃, C₄}. В сети раскрашена метка, имитирующая работу супервизора и дуги, имитирующие последовательность запуска процессоров. Прочие дуги, а также метки-заявки и метки управления не нарушены.

Начальный цвет метки в P₀ равен C₁ и дуга (P₀,t­₁) окрашена в C₁. Поэтому условие возбуждения выполнимо для перехода t₁. После срабатывания t₁ в P₀ метка возвращается, уже имея цвет C₂, поскольку дуга (t₁,P₀) раскрашена в цвет C₂.

Раскрашивание дуг обеспечивает возбуждение только одного из переходов, следующих за P₀, при любом состоянии системы. При данной раскраске алгоритм работы супервизора представлен последовательностью срабатывания переходов t₁, t₂ (t₃, t₄) t₅, t₆, т. е. происходит запуск первого процессора, затем второго, после чего следует их освобождение и цикл повторяется.

Рис. 5.20. Пример раскрашенной сети: а) – граф алгоритма; б) – биграф алгоритма;

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

 

В примере 2 раскрашенная сеть используется для представления мультипрограммного выполнения алгоритма с ветвями и точкой синхронизации в ВС с процессором и УВВ.

На Пр и УВВ параллельно могут выполняться операторы 2 и 3, завершение которых является условием выполнения оператора 0, что видно из рис.5.20а. Переходы t₀ – t₃ биграфа (рис. 5.20б) соответствуют вершинам графа на рис. 5.20а. Для отображения точки входа в алгоритм на его биграфе введена маркированная позиция P₁, поэтому нулевой вершине графа (рис. 5.20а) поставлены в соответствие переходы t₀ и t₄ биграфа. При построении сети (рис. 5.20в) учтено, что время выполнения операций t₁ и t₄ мало по сравнению с остальными. Учитывая также, что действия t₀ и t₂ выполняются на процессоре, позиции P₁ и P₅, а также P₂ и P₆ биграфа совмещены на рис.5.20в и обозначены как P₁ и P₂. Процессы выполнения алгоритмов представлены движением меток. Раскраска меток двухэлементная, определяющая номер процесса a = {1, 2, 3} и номер этапа обработки C = {C₀, C₁, C₂, C₃}.

Из рис. 5.20в видно, что некоторые из дуг раскрашены одним цветом (C_i), другие парой цветов (a C_i), третьи не раскрашены вовсе, что учитывается при управлении возбуждением переходов и изменении цвета меток. Заметим, что при раскрашивании парой цветов все эти признаки анализируются или изменяются в комплексе. Например, входные дуги перехода t₄ помечены парами a C₂ и a C₃, что определяет выбор для синхронизации на t₄ процессов с одним и тем же номером a и завершенными этапами обработки C₂ и C₃ соответственно.

Следующий пример (рис. 5.21) показывает изобразительные возможности раскрашенных сетей по разделению путей данных и управления в УВВ. Данные от двух источников U₁ и U₂ помечены квадратами в P₁ и P₃, а сигналы запроса на обработку – кружками в P₂ и P₄. Запросы принимаются (переходы t₁, t₂), накапливаются в регистре (позиция P₅), выбираются из неё (переход t₃) и запускают пересылку данных от источников (P₁ или P₃) в буфер P₇. Метка-треугольник в позиции P₈ отражает управляющий процесс, разрешающий выполнение только одной из двух операций считывания t₄ или t₅. Читателю предлагается самостоятельно разобраться, почему необходимо использовать раскрашенную метку в позиции P₈ и на дугах и .

 

 

 

Рис. 5.21. Пример сети с разделением передачи данных

 

Таким образом, процедура раскраски сети Петри – это модельный способ трактовки различных по характеру реальных элементов:

- в алгоритмах – номера оператора или этапа обработки;

- в мультипрограммных системах – номера задачи, её приоритета и других атрибутов;

- для ресурсов – их типа, способы использования и т. п.