Анализ заключается в изучении основных свойств сетей Петри: безопасности, ограниченности, сохранении, активности, достижимости и покрываемости. Напомним определение каждого из этих свойств.
Безопасность.Позиция piÎP сети C=(P, T, I, O, M0) является безопасной, если m(pi)£I для любой MÎR(C, M0). Сеть Петри безопасна, если безопасна каждая ее позиция.
Безопасность – важное свойство для аппаратной реализации. Безопасная позиция имеет число меток 0 или 1 и может быть реализована одним триггером.
Сети, в которых позиции рассматриваются (интерпретируются) как предусловия событий, маркировка каждой позиции должна быть безопасной.
Ограниченность.Безопасность – это частный случай более общего свойства ограниченности. Безопасность позволяет реализовать позицию триггером, а в более общем случае можно использовать счетчик. Любой счетчик ограничен по максимальному числу К. Соответствующая позиция также является К-безопасной или К-ограниченной, если количество меток в ней не может превысить целое число К.
Позиция piÎP сети C=(P, T, I, O, M0) является К-безопасной, если m(pi)£К для всех MÎR(C, M0).
Позиция называется ограниченной, если она К-безопасна для некоторого К.
Сеть Петри ограничена, если все ее позиции ограничены.
Сохранение.В сетях Петри, моделирующих запросы, распределения и освобождения ресурсов, некоторые позиции могут представлять состояние ресурсов. Например, если три метки в позиции представляют три устройства (однотипных) в вычислительной системе, то интерес представляет свойство сохранения меток. То есть метки, представляющие ресурсы, никогда не создаются и не уничтожаются.
Сеть Петри называется строго сохраняющей, если для всех MÎR(C, M0)
выполняется условие:
å m(pi) = å m0(pi).
piÎP piÎP
Сеть Петри должна сохранять ресурсы, которые она моделирует. Однако не всегда имеется однозначное соответствие между меткой и количеством или числом ресурсов. В этом случае метка используется для создания кратных меток (по одной на ресурс), путем запуска перехода с большим числом выходов, чем входов. Поэтому вводятся взвешенные метки, а условие сохранения определяется через взвешенную сумму меток.
Активность.Другой задачей, возникающей при распределении ресурсов, является задача выявления тупиков. Рассмотрим на рис. 5.14 систему, включающую два различных ресурса q и r и два процесса а) и в), нуждающиеся в обоих ресурсах. Каждый процесс запрашивает ресурс, а затем освобождает его. Процесс а) сначала запрашивает ресурс q, затем ресурс r, и освобождает их. Процесс в) работает аналогично, но запрашивает сначала ресурс r, а затем q.
а) в)
Рис. 5.14. Иллюстрация наличия тупика
Начальная маркировка помечает ресурсы свободными и готовность процессов к работе. Выполнение сети в последовательности t1, t2, t3, t4, t5, t6 или t4, t5, t6, t1, t2, t3 не приводит к тупику. Если начать с переходов t1, t4 то выполнение заблокировано, процесс а) обладает ресурсом q и хочет получить r, процесс в) обладает r и хочет получить q.
Тупик в сети Петри – это переход (или множество переходов), которые не могут быть запущены. Переходы t2 и t5 являются тупиковыми. Переход называется активным, если он не заблокирован, то есть потенциально запустимым.
Достижимость и покрываемость.Задача достижимости заключается в определении для маркировки M0 маркировки MÎR(C, M0). К этой задаче могут сводиться многие перечисленные выше задачи. Например, тупик в сети на рисунке может возникнуть, если достижимым является состояние (0, 1, 0, 0, 0, 0, 1, 0).
Задача покрываемости. Для сети С с начальной маркировкой M0 и маркировки M определить, существует ли такая достижимая маркировка M’ÎR(C, M0), что M’³M.
Задачи достижимости и покрываемости могут рассматриваться относительно некоторых интересующих нас подмножеств позиций.