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

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

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

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

Безопасность— частный случай ограниченности. Конкретно безопасность соответствует 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

 

  1. Что такое N-схемы?
  2. Для чего используют сети Петри?
  3. Что такое маркировка сети Петри?
  4. Какая из разновидностей сетей Петри приводит практически к тем же результатам моделирования, что и теория массового обслуживания?
  5. Чем вызваны возможные конфликтные ситуации в N-схемах?
  6. В чем заключается анализ достижимости сетей Петри?
  7. Как строится граф достижимости сети Петри?








Дата добавления: 2015-09-18; просмотров: 3069;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.