Методы анализа сетей Петри

2.3. Методы анализа сетей Петри

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

            2.3.1. Задачи анализа

            Одним из важнейших свойств СП, моделирующей реальное устройство, является безопасность. Известно, что если позиция безопасна, то число меток в ней равно 0 или 1. Следовательно, позицию можно реализовать одним триггером. Безопасность - это частный случай более общего свойства ограниченности. Безопасность позволяет реализовать позицию триггером, но в более общем случае можно использовать счетчик. Однако любой аппаратно реализованный счетчик ограничен по максимальному числу, которое он может представить.

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

            Большинство задач, к которым мы до сих пор обращались, касается достижимости разметки. Задача достижимости формулируется следующим образом: для СП N с начальной разметкой m0 и разметкой m' определить m0 ® m' . Задача достижимости, пожалуй, является основной задачей анализа СП. Многие другие задачи анализа можно сформулировать в терминах задачи достижимости.

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

            2.3.2. Анализ сетей Петри на основе дерева достижимости

Рекомендуемые материалы

            Множество достижимых разметок R(N) в СП N можно представить в виде дерева достижимости. Данное дерево представляет собой ориентированный граф, множество вершин которого образовано множеством R(N), причем из вершины m в вершину m' ведет дуга, помеченная символом перехода t, если и только если

m  m' .

            В общем случае для любой СП с бесконечным множеством достижимых разметок соответствующее дерево также должно быть бесконечным. Даже СП с конечным множеством достижимых разметок может иметь бесконечное дерево. Дерево содержит все возможные последовательности запусков переходов. Всякий путь в дереве, начинающийся в корне, соответствует допустимой последовательности переходов. Для превращения дерева в полезный инструмент анализа необходимо найти средства ограничения его до конечного размера. Для этого необходимо найти средства, которые ограничивают введение новых разметок, называемых граничными. Будем использовать следующие приемы [46, 26]. Во-первых, могут оказать помощь разметки, в которых нет разрешенных переходов (тупиковые разметки). Тупиковые разметки будем называть терминальными вершинами. Во-вторых, выделим разметки, ранее встречавшиеся в дереве. Такие разметки будем называть дублирующими вершинами. Если встретилась дублирующая разметка, то никакие последующие маркировки рассматривать нет необходимости - все они будут порождены из места первого появления дублирующей разметки в дереве. В-третьих, выделим разметки, в которых существуют позиции, увеличивающие число меток в результате срабатывания последовательности переходов n. Следовательно, разметка данных позиций может быть неограниченно большой. Представим бесконечное число меток, формирующихся в позиции в результате циклов описанного типа, с помощью специального символа, который означает "бесконечность".

            Для любого постоянного a определим:

w + a = w; w - a = w; a << w.

            Сформулируем алгоритм построения дерева достижимости. Каждая вершина i дерева связывается с расширенной разметкой mi . В расширенной разметке число меток в позиции может быть либо неотрицательным целым, либо w . Каждая вершина классифицируется или как граничная, терминальная, дублирующая вершина, или как внутренняя. Граничными являются вершины, которые еще не обработаны алгоритмом. После обработки граничные вершины становятся либо терминальными, либо дублирующими, либо внутренними.

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

            Пусть x - граничная вершина, которую необходимо обработать и с которой связана разметка m(x):

            1. Если в дереве имеется другая вершина y, не являющаяся граничной, и с ней связана разметка m(y) = m(x) , то вершина x дублируется.

            2. Если для разметки m(x) один из переходов неразрешим, то есть m(x) - тупиковая разметка, то x - терминальная вершина.

            3. Для любого перехода ti из множества Т, разрешенного в разметке m(x), создать новую вершину z дерева достижимости. Разметка m(z) , связанная с этой вершиной, определяется для каждой позиции pi  следующим образом:

            а) если mi(x) =  w , то mi(z) =  w ;

            б) если на пути от корневой вершины к вершине x существует вершина y, такая, что m(y)  m(x) , m(y) < m(x) и mi(y) < mi(x) , то mi(z) = w ;

            в) в противном случае mi(z) = mi(x). Дуга, помеченная tj, направлена от вершины x к вершине z . Вершина x переопределяется как внутренняя, вершина z становится граничной.

            Когда все вершины дерева становятся терминальными, дублирующими или внутренними, алгоритм останавливается.

            2.3.3. Матричные методы анализа

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

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

C = O - I = HÔ - F ,

            где HÔ - транспонированная матрица Н.

            Пусть размерность С равна n ´ m , где m и n мощности множеств P и T . Рассмотрим матричные уравнения :

                                               C  *  x = 0 ;                                        (2.18)

                                                y  *  C = 0 ,                                       (2.19)

где x и y - векторы, размерность которых равна n и m соответственно. Вектор у, удовлетворяющий решению уравнения (2.19) и все элементы которого положительны, называется р-цепью; р-цепь, все элементы которой больше нуля, называется полной р-цепью. Анaлогично на основе уравнения (2.18) определяются понятия t-цепи и полной t-цепи. СП, для которой существует полная р-цепь, называется инвариантной. СП, для которой существует полная t-цепь, называется последовательной .

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

В лекции "Статически определимые фермы" также много полезной информации.

            В общем случае множество решений данных уравнений может быть бесконечным. Так как целью решения уравнений является определение существования полных р- и t-цепей, то для сокращения времени вычислений воспользуемся следующим приемом. Пусть элементы множества Z={z1, z2, ..., zk} являются решениями уравнения (2.18) (или (2.19)), причем элементы вектора zi могут принимать значения только из набора {0,1}. Тогда справедлива следующая     

Теорема 2.2. Вектор  = z1 + z2 +... + zk является t-цепью (р-цепью).

            Доказательство данной теоремы легко проводится на основе положений линейной алгебры [22].

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

            1) определение множества Z= {z1, z2, ..., zk} для уравнения (2.18) (или (2.19));

            2) получение вектора . Вид вектора  дает ответ на вопрос о существовании полных р- или t-цепей.