Анализ сетей Петри

 

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

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

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

Безопасность - частный случай ограниченности, а именно это l -ограниченность. Если для некоторой позиции установлено, что она безопасна, то ее можно представлять одним триггером.

Сохраняемость характеризуется постоянством загрузки ресурсов, т.е.

A_i N_i = const,

где N_i - число маркеров в i-й позиции; A_i - весовой коэффициент.

Достижимость M_k-> M_j характеризуется возможностью достижения маркировки M_j из состояния сети, характеризуемого маркировкой M_k.

Живость сети Петри определяется возможностью срабатывания любого перехода при функционировании моделируемого объекта. Отсутствие живости либо означает избыточность аппаратуры в проектируемой системе, либо свидетельствует о возможности возникновения зацикливаний, тупиков, блокировок [7].

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

Один из методов анализа достижимости любой маркировки из состояния М₀ - построение графа достижимости. Начальная вершина графа отображает М₀, а остальные вершины соответствуют другим маркировкам. Дуга из M_i в М_j означает событие М_i -> М_j и соответствует срабатыванию перехода t. В сложных сетях граф может содержать чрезмерно большое число вершин и дуг. Однако при построении графа можно не отображать все вершины, так как многие из них являются дублями (действительно, от маркировки M_k всегда порождается один и тот же подграф независимо от того, из какого состояния система пришла в M_k). Тупики обнаруживаются по отсутствию разрешенных переходов из какой-либо вершины, т.е. по наличию листьев — терминальных вершин. Неограниченный рост числа маркеров в какой-либо позиции свидетельствует о нарушениях ограниченности.

Приведем пример анализа достижимости,

На рис. 14, а показана сеть Петри, а на рис. 14, б - соответствующий ей граф достижимых разметок.

Вершины графа на рис. 14, б соответствуют маркировкам (состояниям сети Петри), представленным в виде последовательности цифр, цифры означают количества меток в позициях, перечисляемых в порядке р₁, р₂, p₃ р₄, р₅. Дуги помечены обозначениями срабатывающих переходов. Живость сети очевидна, так как срабатывают все переходы, тупики отсутствуют.

 

 

а

 

 

 

б

 

 

Рис 14. Сеть Петри (а) и граф достижимости (6) [7].