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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



 

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

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

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

 

δ(M,tj)=M - e(j) Д- + e(j) Д+ = M+ e(j)(- Д- + Д+) = M + e(j)Д,

 

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

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

 

δ(M,G) =δ(M, tj1, tj2,…, tjk) =

= M + e(j1)Д + e(j2)Д + … + e(jk)Д =

= M +[ e(j1) + e(j2) + … + e(jk)]Д = M + f(G)Д.

 

Вектор f(G) = e(j1)+e(j2) …..+e(jk) называется вектором запуска последовательности tj1,tj2,…,tjk. i-й элемент вектора f(G), f(G)i - это число запусков перехода tj в последовательности tj1,tj2,…,tjk. Вектор запусков, следовательно, является вектором с неотрицательными целыми компонентами.

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

 

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

 

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

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

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

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

 

M’ = M0 + X Д. (*)

 

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

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

 
 


       
       
       

 

Д- =

 

 

       
       
       

 

Д+=

 

 

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

 

Д = Д+ - Д- =

 

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

 

В начальной маркировке M0=(1,0,1,0) переход t3 разрешён и приводит к маркировке 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= {t3, t2, t3, t2, t3, t2, t3, t2, t3}.

Можно показать, что маркировка (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. Решение уравнения (*) является необходимым для достижимости, но недостаточным.

 

 

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

 

 

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

 

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

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

TN = {N, τ},

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

 

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

 

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

PRN = {N, PR},

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

 

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

 

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

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

PRTN = {N, τ, PR}.

 

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

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

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

Переходам tj сопоставлены времена τj, отражающие длительность выполнения соответствующих действий в системе обработки и обмена, генераторах помех и тайм-аута. отношения приоритетности введены для двух пар переходов – (t­2,t8) и (t7,t11), поскольку только по отношению к ним может возникнуть конфликт за метку. Они имеют вид:

 

PR(t8) > PR(t2) и PR(t7) > PR(t11).

 

 

       
   
 
 

 


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

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

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

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

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

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

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

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

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

t6 - обработка в ПрП;

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

t8, t9 - переходы модели источника помех;

t10, t11 - элементы ГТ;

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

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

P3 - ПрП готов принять сообщение и запрашивает t2;

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

P5 - завершение действия t2 и запуск t3;

P6 - запрос t6;

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

P8 - запрос t5;

P9, P10 - позиции ГТ;

P11, P12 - позиции ИП;

 

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

Передача сообщения процессором-источником порождает буферирование копии сообщения и запуск генератора тайм-аута, посылку сообщения в канал, а также формирование условия подтверждения о приёме, что отражается появлением меток в P2, P4, P9. Если сообщение в канале P2 исчезнет благодаря действию ИП (что отражается возбуждением t8), то не приходит подтверждение приёма (метка в P7 не появится), и через время тайм-аута (связанное с t10) произойдёт повторная выдача сообщения в канал (что отражается срабатыванием t7). С t9 связан интервал времени между потерей в канале очередного сообщения и возникновением условия для потери следующего сообщения. С t10 связано время тайм-аута, через которое организуется повторная посылка потерянного сообщения. Если через τ10 в P4 нет метки, то не создадутся условия возбуждения t7 и метка из P10 покинет ГТ.

 

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

 

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

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

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

 

 

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

 

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

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

 

 
 

 


t1, t2 - загрузка процессоров;

t3, t4 – обработка;

t5, t6 - освобождение процессоров

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

P1, P2 - заявки на обработку;

P3, P4 - Заявки приняты;

P5, P6 - конец обработки;

P7, P8 - обработанные заявки;

P9, P10 - двоичные семафоры,

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

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

 

 

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

 

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

Начальный цвет метки в P0 равен C1 и дуга (P0,t­1) окрашена в C1. Поэтому условие возбуждения выполнимо для перехода t1. После срабатывания t1 в P0 метка возвращается, уже имея цвет C2, поскольку дуга (t1,P0) раскрашена в цвет C2.

Раскрашивание дуг обеспечивает возбуждение только одного из переходов, следующих за P0, при любом состоянии системы. При данной раскраске алгоритм работы супервизора представлен последовательностью срабатывания переходов t1, t2 (t3, t4) t5, t6, т. е. происходит запуск первого процессора, затем второго, после чего следует их освобождение и цикл повторяется.

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

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

 

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

На Пр и УВВ параллельно могут выполняться операторы 2 и 3, завершение которых является условием выполнения оператора 0, что видно из рис.5.20а. Переходы t0 – t3 биграфа (рис. 5.20б) соответствуют вершинам графа на рис. 5.20а. Для отображения точки входа в алгоритм на его биграфе введена маркированная позиция P1, поэтому нулевой вершине графа (рис. 5.20а) поставлены в соответствие переходы t0 и t4 биграфа. При построении сети (рис. 5.20в) учтено, что время выполнения операций t1 и t4 мало по сравнению с остальными. Учитывая также, что действия t0 и t2 выполняются на процессоре, позиции P1 и P5, а также P2 и P6 биграфа совмещены на рис.5.20в и обозначены как P1 и P2. Процессы выполнения алгоритмов представлены движением меток. Раскраска меток двухэлементная, определяющая номер процесса a = {1, 2, 3} и номер этапа обработки C = {C0, C1, C2, C3}.

Из рис. 5.20в видно, что некоторые из дуг раскрашены одним цветом (Ci), другие парой цветов (a Ci), третьи не раскрашены вовсе, что учитывается при управлении возбуждением переходов и изменении цвета меток. Заметим, что при раскрашивании парой цветов все эти признаки анализируются или изменяются в комплексе. Например, входные дуги перехода t4 помечены парами a C2 и a C3, что определяет выбор для синхронизации на t4 процессов с одним и тем же номером a и завершенными этапами обработки C2 и C3 соответственно.

Следующий пример (рис. 5.21) показывает изобразительные возможности раскрашенных сетей по разделению путей данных и управления в УВВ. Данные от двух источников U1 и U2 помечены квадратами в P1 и P3, а сигналы запроса на обработку – кружками в P2 и P4. Запросы принимаются (переходы t1, t2), накапливаются в регистре (позиция P5), выбираются из неё (переход t3) и запускают пересылку данных от источников (P1 или P3) в буфер P7. Метка-треугольник в позиции P8 отражает управляющий процесс, разрешающий выполнение только одной из двух операций считывания t4 или t5. Читателю предлагается самостоятельно разобраться, почему необходимо использовать раскрашенную метку в позиции P8 и на дугах и .

 

 

 

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

 

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

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

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

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

 

 



Поделиться:


Последнее изменение этой страницы: 2016-08-16; просмотров: 318; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.229.62.45 (0.075 с.)