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

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

Метками раскрашенной сети приписывают атрибуты, которые называют цветами. Правила возбуждения переходов дополняются условиями, предполагающими выбор меток определённых цветов из позиций 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

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

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

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

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