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

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

Безопасность.Позиция 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.

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