Анализ сетей Петри
Анализ сложных систем на базе сетей Петри можно выполнять посредством имитационного моделирования СМО, представленных моделями сетей Петри. При этом задают входные потоки заявок и определяют соответствующую реакцию системы. Выходные параметры СМО рассчитывают путем обработки накопленного при моделировании статистического материала.
Возможен и другой подход к использованию сетей Петри для анализа объектов, исследуемых на системном уровне. Он не связан с имитацией процессов и основан на исследовании таких свойств сетей Петри, как ограниченность, безопасность, сохраняемость, достижимость, живость.
Ограниченность(или К-ограниченность) имеет место, если число меток в любой позиции сети не может превысить значения К. При проектировании автоматизированных систем определение К позволяет обоснованно выбирать емкости накопителей. Возможность неограниченного роста числа меток свидетельствует об опасности неограниченного роста длин очередей.
Безопасность— частный случай ограниченности. Конкретно безопасность соответствует 1-ограниченности. Если для некоторой позиции установлено, что она безопасна, то ее можно представлять одним триггером.
Сохраняемостьхарактеризуется постоянством загрузки ресурсов, т.е.
где Ni – число маркеров в i-й позиции; Ai – весовой коэффициент.
ДостижимостьМk → Мj характеризуется возможностью достижения маркировки Мj из состояния сети, характеризуемого маркировкой Мk.
Живостьсети Петри определяется возможностью срабатывания любого перехода при функционировании моделируемого объекта. Отсутствие живости означает либо избыточность аппаратуры в проектируемой системе, либо свидетельствует о возможности возникновения зацикливаний, тупиков, блокировок.
В основе исследования перечисленных свойств сетей Петри лежит анализ достижимости.
Один из методов анализа достижимости любой маркировки из состояния М0 – построение графа достижимости. Начальная вершина графа отображает М0, а остальные вершины соответствуют маркировкам. Дуга из Мi, в Мj означает событие Мi → Мj и соответствует срабатыванию перехода t. В сложных сетях граф может содержать чрезмерно большое число вершин и дуг. Однако при построении графа можно не отображать все вершины, так как многие из них являются дублями (действительно, от маркировки Мk всегда порождается один и тот же подграф вне зависимости от того, из какого состояния система пришла в Мk).
На рис. 5.18 показана сеть Петри к примеру с одной рабочей станцией и N пользователями. Граф достижимости для данной сети показана на рис. 5.19.
Рис. 5.18. Сеть Петри к примеру 1
На рисунке 5.19 вершины графа изображены в виде маркировок, дуги помечены срабатывающими переходами. Данная сеть явно обладает свойством живости, так как срабатывают все переходы, а тупики отсутствуют.
Рис. 5.19. Граф достижимости сети Петри к примеру 1
Пример 3. Сеть Петри для двухпроцессорной вычислительной системы с общей памятью и ее граф достижимости представлены на рис. 5.20. Сеть является живой: все разметки достижимы.
Рис. 5.20. Сеть Петри и ее граф достижимости к примеру 2
Вопросы к разделу 5.2
- Что такое N-схемы?
- Для чего используют сети Петри?
- Что такое маркировка сети Петри?
- Какая из разновидностей сетей Петри приводит практически к тем же результатам моделирования, что и теория массового обслуживания?
- Чем вызваны возможные конфликтные ситуации в N-схемах?
- В чем заключается анализ достижимости сетей Петри?
- Как строится граф достижимости сети Петри?
Дата добавления: 2015-09-18; просмотров: 3078;