4.4. Имитационное моделирование. Сети Петри

Имитационное моделирование используется в задачах проектирования РЭС и ТП лишь в тех случаях, когда исследуемые процессы настольно сложны и многообразны, что обычная аналитическая модель становится слишком грубым приближением к действительности. В имитационной модели поведение элементов системы описывается набором моделирующих алгоритмов, которые позволяют оценить поведение системы в различных реальных ситуациях. При этом необходимы исходные данные о начальном состоянии системы в виде фактических значений ее параметров.

В задачах имитационного моделирования РЭС и ТП используются два подхода к представлению проектируемой системы и ее функционирования: событийный подход использует представление в виде последовательности событий, а сетевой – в виде специального аппарата сетей Петри. Имитационная модель в принципе не точна и невозможно оценить степень этой неточности. Поэтому получение хорошей имитационной модели – это достаточно сложная задача, включающая в себя не только получение программной имитационной модели, но и ее отладку и испытание, что связано с дополнительными затратами. На практике наиболее широкое применение нашли метод моделирования РЭС и ТП в виде систем массового обслуживания и метод сетей Петри (рис. 4.4).

Рис. 4.4. Сеть Петри для моделирования простой

вычислительной системы

Сети Петри являются средством математического описания процессов функционирования дискретных систем с параллельно и асинхронно действующими элементами. Сеть Петри определяется следующим образом: S=<P, Т, I, О>, где Р и Т - конечные множества позиций и переходов, I и О - входная функция. Сеть Петри можно представить в виде двудольного ориентированного мультиграфа, в котором позициям соответствуют вершины, изображаемые кружками, переходам - вершины, изображаемые утолщенными линиями, функция I изображается дугами, направленными от позиций p_i к переходам t_j, a функция О - дугами, направленными от t_j к р_j. Пример сети Петри, представляющей модель вычислительной системы, дан на рис. 4.4.

С помощью сетей Петри моделируются процессы, представляемые в виде последовательности событий. Принято считать, что события происходят мгновенно и разновременно. Каждому из возможных событий соответствует определенный переход. Событие происходит, если выполнены некоторые условия. Каждому из условий в сети Петри соответствует определенная позиция. Выполнение условий отображается с помощью маркеров, помещаемых в виде точек внутри соответствующих позиций. Число состояний сети Петри определяется числом возможных маркировок. Маркировкой называется распределение маркеров по позициям. Если упорядочить позиции p_i по возрастанию индекса i, то маркировку можно представить вектором (0, 0, 1,0), i-й элемент которого равен числу маркеров в позиции p_i.

Моделирование процессов с помощью сетей Петри выражается в перемещении маркеров между позициями. Получающаяся последовательность событий t_j - это последовательность срабатывания (возбуждения или запуска) переходов. Событие t_i происходит (переход t_j срабатывает), если имеются маркеры во всех входных позициях перехода t_j. Входными позициями для t_j называются те, из которых дуги направлены в переход t_j. Совершение события t_j выражается в изъятии маркеров из всех входных позиций и в помещении их во все выходные позиции перехода t_j. Выходными позициями перехода t_j называются те, в которые ведут дуги из перехода t_j. Следовательно, реализация события t_j (запуск перехода t_j) приводит к смене маркировок.

На рис. 4.4 приняты обозначения: t₁₂ – появление задачи на входе, t₁₀ – решение задачи, t₁₁ – окончание решения, t₁₃ – выход решенной задачи, p₁ – соответствует условию «во входной очереди есть задачи», р₂ – решение окончено, р₃ – «процессор свободен», р₄ – в выходной очереди есть задачи. Начальная маркировка – в виде маркера в позиции р₃. Приход задачи отображается запуском перехода t₁₂ и появлением маркера в р₁, а следовательно, срабатывает переход t₁₀, а затем изменяется маркировка

Для моделирования ВС наиболь­ший интерес представляют временные, стохастические и функци­ональные сети Петри.

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

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

Функциональная сеть Петри характеризуется тем, что отражает не только последовательность событий (поток yправления), но и процессы обработки некоторого потока данных. Для этого в описание каждого перехода добавляется алгоритм об­работки данных. С помощью функциональных сетей Петри можно моделировать разнообразные элементы ВС, производить статисти­ческую обработку результатов моделирования, отображать различ­ные алгоритмы функционирования.

Цветная сеть Петри используется тогда, когда требуется отличать друг от друга некоторые группы маркеров. Например, при моделировании гибких производственных систем маркеры мо­гут отображать детали разных типов, которые должны направлять­ся в определенные сборочные центры. Для разнотипных деталей вводятся разноцветные маркеры со своими правилами перемеще­ния между позициями. Например, для фрагмента сети можно принять следующее правило: маркер цвета А в позиции p_i вызывает запуск перехода t₁ а маркер цвета В - запуск перехода t₂.

Другие модификации сетей Петри: ингибиторные, приоритетные и автоматные.

Ингибиторная сеть Петри характеризуется тем, что в нее могут вводиться запрещающие (ингибиторные) ветви.

Приоритетная сеть Петри характеризуется вводом приоритетов для ветвей. Благодаря этому разрешаются конфлик­ты - срабатывает переход, в который от р₁ ведет ветвь с более высоким приоритетом. Популярны Е-сети, в которых предусмотрены задержки срабатываний, разре­шение конфликтов, наличие параметров у объектов сети.

Автоматная сеть Петри - это сеть, в которой каждый переход имеет только один вход и один выход. В автоматной сети число маркеров постоянно, эти сети по своим возможностям моде­лирования эквивалентны конечным автоматам.

Основное назначение сетей Петри в САПР - использование их в качестве имитационных моделей для изучения поведения проектируемых систем при заданных внешних воздействиях. Эти модели используются не только для имитации, но и для исследования некоторых общих свойств систем, не свя­занных с конкретными внешними воздействиями.

Общие свойства сетей Петри: К-ограниченность, безопасность, достижимость, сохраняемость, живость.

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

Безопасность - свойство сети, определяемое условием К= 1.

Достижимость - свойство сети Петри, заключающееся в возможности достижения заданных маркировок. Анализ достижи­мости позволяет определить множество маркировок, в которые воз­можны переходы в процессе функционирования сети.

Сохраняемость - свойство сети, характеризующее невоз­можность возникновения или уничтожения ресурсов в моделируе­мом объекте.

Живость – свойство сети, означающее, что из любого состояния, достижимого из начального, возможен переход в любое другое достижимое состояние.