Анализ сложных систем на базе сетей Петри можно выполнять посредством имитационного моделирования СМО, представленных моделями сетей Петри. При этом задают входные потоки заявок и определяют соответствующую реакцию системы. Выходные параметры СМО рассчитывают путем обработки накопленного при моделировании статистического материала.
Возможен и другой подход к использованию сетей Петри для анализа объектов, исследуемых на системном уровне. Он не связан с имитацией процессов и основан на исследовании таких свойств сетей Петри, как ограниченность, безопасность, сохраняемость, достижимость, живость.
Ограниченность (или К-ограниченностъ) имеет место, если число меток в любой позиции сети не может превысить значения К. При проектировании автоматизированных систем определение К позволяет обоснованно выбирать емкости накопителей. Возможность неограниченного роста числа меток свидетельствует об опасности неограниченного роста длин очередей.
Безопасность – частный случай ограниченности, а именно это
1-ограниченность. Если для некоторой позиции установлено, что она безопасна, то ее можно представлять одним триггером.
|
|
Сохраняемость характеризуется постоянством загрузки ресурсов, т.е. , где – число маркеров в j-и позиции, – весовой коэффициент.
Достижимость характеризуется возможностью достижения маркировки М из состояния сети, характеризуемого маркировкой Мy.
Живость сети Петри определяется возможностью срабатывания любого перехода при функционировании моделируемого объекта. Отсутствие живости либо означает избыточность аппаратуры в проектируемой системе, либо свидетельствует о возможности возникновения зацикливаний, тупиков, блокировок.
В основе исследования перечисленных свойств сетей Петри лежит анализ достижимости.
Один из методов анализа достижимости любой маркировки из состояния М0 – построение графа достижимости. Начальная вершина графа отображает М0, а остальные вершины соответствуют маркировкам. Дуга из My в М означает событие и соответствует срабатыванию перехода t. В сложных сетях граф может содержать чрезмерно большое число вершин и дуг. Однако при построении графа можно не отображать все вершины, так как многие из них являются дублями (действительно, от маркировки m£ всегда порождается один и тот же подграф вне зависимости от того, из какого состояния система пришла в МА). Тупики обнаруживаются по отсутствию разрешенных переходов из какой-либо вершины, т. е. по наличию листьев – терминальных вершин. Неограниченный рост числа маркеров в какой-либо позиции свидетельствует о нарушениях ограниченности.
|
|
Приведем примеры анализа достижимости.
Пример 3. Сеть Петри и граф достижимых разметок представлены на рис. 10.
На рисунке вершины графа изображены в виде маркировок, дуги помечены срабатывающими переходами. Живость сети очевидна, так как срабатывают все переходы, тупики отсутствуют.
Рис. 10. Сеть Петри и ее граф достижимости к примеру 3
Пример 4. Сеть Петри и граф достижимых разметок представлены на рис. 11. Сеть, моделирующая двухпроцессорную вычислительную систему с общей памятью, является живой, все разметки достижимы.
Рис. 11. Сеть Петри и ее граф достижимости к примеру 4