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

 

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

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

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

 

 

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

 

 

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

 

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

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

TN = {N, τ}

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

 

 

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

 

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

PRN = {N, PR}

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

 

 

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

 

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

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

PRTN = {N, τ, PR}

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

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

Переходам 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₁₂ - позиции ИП

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

 

 

На рисунке изображён граф допустимых маркирований элементов модели ПрП и ПрИ. В вершинах графа состояний перечислены наборы позиций, в которых одновременно находятся метки-сообщения (при начальном маркировании 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₁₀ - двоичные семафоры, исключающие попытки запустить занятые процессоры.

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

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

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

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

 

 

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

а) – граф алгоритма

б) – биграф алгоритма

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

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

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

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

 

ПРИМЕР 3

 

 

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

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

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

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