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

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

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

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

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

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

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

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

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

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

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

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

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

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

; ,

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

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

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

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

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

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