Методы анализа характеристик сетей.

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

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

Маркирование называют достижимым из маркирования , если существует последовательность срабатывающих переходов , переводящая сеть из состояния в . Отношение следования маркирований, возбуждаемых действием последовательности имеет вид: .

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

Переход называют живым, если он достижим в из любого , где - множество достижимых маркирований сети.

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

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

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

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

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

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

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

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

; ,

где - состояние, которое следует после состояния в результате -го воздействия ; - начальное маркирование; - матрица, полученная транспонированием матрицы инцидентности позиций и переходов, причем ее элементы равны , , или 0, когда соответственно переход имеет исходящих дуг к позиции , входящих дуг в позицию или не имеет связи с позицией ; – управляющий вектор, компоненты которого . Если , то в -й момент асинхронного времени происходит срабатывание перехода , если же , то срабатывание не происходит.

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

 

Е-сети. В настоящее время теория сетей Петри получила существенное развитие. Так, для описания различных и многообразных свойств систем предлагается язык нагруженных сетей, который легко адаптируется для представления различных частных классов сетевых моделей, и при необходимости объединяет эти частные свойства в едином описании. Расширением языка сетей Петри является язык вычислительных сетей, которые получили название -сети. Так же, как и сеть Петри, -сеть является графом, содержащим вершины двух типов – позиции и переходы и ребра, соединяющие вершины разных типов.

Рис. 5.13. Переходы -сети

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

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

 

 

Задачи анализа сетей Петри

 

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

 

 

Безопасность. Позиция p_iÎP сети C=(P, T, I, O, M₀) является безопасной, если m(p_i)£I для любой MÎR(C, M₀). Сеть Петри безопасна, если безопасна каждая ее позиция.

Безопасность – важное свойство для аппаратной реализации. Безопасная позиция имеет число меток 0 или 1 и может быть реализована одним триггером.

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

 

Ограниченность. Безопасность – это частный случай более общего свойства ограниченности. Безопасность позволяет реализовать позицию триггером, а в более общем случае можно использовать счетчик. Любой счетчик ограничен по максимальному числу К. Соответствующая позиция также является К-безопасной или К-ограниченной, если количество меток в ней не может превысить целое число К.

Позиция p_iÎP сети C=(P, T, I, O, M₀) является К-безопасной, если m(p_i)£К для всех MÎR(C, M₀).

Позиция называется ограниченной, если она К-безопасна для некоторого К.

Сеть Петри ограничена, если все ее позиции ограничены.

 

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

Сеть Петри называется строго сохраняющей, если для всех MÎR(C, M₀)

выполняется условие:

å m(p_i) = å m₀(p_i).

p_iÎP p_iÎP

 

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

 

Активность. Другой задачей, возникающей при распределении ресурсов, является задача выявления тупиков. Рассмотрим на рис. 5.14 систему, включающую два различных ресурса q и r и два процесса а) и в), нуждающиеся в обоих ресурсах. Каждый процесс запрашивает ресурс, а затем освобождает его. Процесс а) сначала запрашивает ресурс q, затем ресурс r, и освобождает их. Процесс в) работает аналогично, но запрашивает сначала ресурс r, а затем q.

а) в)

 

Рис. 5.14. Иллюстрация наличия тупика

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

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

 

Достижимость и покрываемость. Задача достижимости заключается в определении для маркировки M₀ маркировки MÎR(C, M₀). К этой задаче могут сводиться многие перечисленные выше задачи. Например, тупик в сети на рисунке может возникнуть, если достижимым является состояние (0, 1, 0, 0, 0, 0, 1, 0).

Задача покрываемости. Для сети С с начальной маркировкой M₀ и маркировки M определить, существует ли такая достижимая маркировка M’ÎR(C, M₀), что M’³M.

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