Событийный метод моделирования

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

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

Рассмотрим возможную схему реализации событийного метода имитационного моделирования.

Моделирование начинается с просмотра операторов генерирования заявок, т.е. с обращения к моделям источников входных потоков.

Для каждого независимого источника такое обращение поволяет рассчитать момент генерации первой заявки. Этот момент вместе с именем-ссылкой на заявку – заносится в список будущих событий (СБС), а сведения о генерируемой заявке – в список заявок (СЗ). Запись в СЗ включает в себя имя заявки, значения ее параметров (атрибутов), место, занимаемое в данный момент в СИМ. В СБС события упорядочиваются по увеличению моментов наступления.

Затем из СБС выбирают совокупность сведений о событиях, относящихся к наиболее раннему моменту времени. Эта совокупность переносится в список текущих событий (СТС), из которого извлекаются ссылки на события. Обращение по ссылке к СЗ позволяет установить место в СИМ заявки А, с которой связано моделируемое событие. Пусть этим местом является устройство Х. Далее программа моделирования выполняет следующие действия (рис. 15.7):

1) изменяет параметры состояния устройства Х; например, если

заявка А освобождает Х, а очередь к Х не была пуста, то в соответствии

с заданной дисциплиной обслуживания из очереди к Х выбирается заявка В и поступает на обслуживание в Х;

2) прогнозируется время наступления следующего события, связанного с заявкой В, путем обращения к модели устройства Х, в которой рассчитывается продолжительность обслуживания заявки В; сведения об этом будущем событии заносятся в СБС и СЗ;

3) происходит имитация движения заявки А в СИМ по маршруту,

определяемому заданной программой моделирования, до тех пор, пока

заявка не придет на вход некоторого ОА; здесь либо заявка задерживается в очереди, либо путем обращения к модели этого ОА прогнозируется наступление некоторого будущего события, связанного с дальнейшей судьбой заявки А; сведения об этом будущем событии также заносятся в СБС и СЗ;

4) в файл статистики добавляются необходимые данные.

После отработки всех событий, относящихся к моменту времени

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

Рис.15.7. Иллюстрация событийного моделирования

Сети Петри

Сети Петри – аппарат для моделирования динамических дискретных систем (преимущественно асинхронных параллельных процессов).

Сеть Петри определяется как четверка <P,T,I,O>, где Р и Т – конечные

множества позиций и переходов, I и О – множества входных и выходных функций. Другими словами, сеть Петри представляет собой двудольный ориентированный граф, в котором позициям соответствуют вершины, изображаемые кружками, а переходам – вершины, изображаемые утолщенными черточками; функциям I соответствуют дуги, направленные от позиций к переходам, а функциям О – от переходов к позициям.

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

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

Рис.15.8. Сеть Петри

Правила срабатывания переходов (рис. 15.8), конкретизируют следующим образом: переход срабатывает, если для каждой из его входных позиций выполняется условие Nii Ki, где Ni – число маркеров в i–й входной позиции, Ki – число дуг, идущих от i–й позиции к переходу; при срабатывании перехода число маркеров в i–й входной позиции уменьшается на Ki, а в j–й выходной позиции увеличивается на Mj, где Mj – число дуг, связывающих переход с j–й позицией.

На рисунке 15.8 показан пример распределения маркеров по позициям перед срабатыванием, эту маркировку записывают в виде (2,2,3,1).

После срабатывания перехода маркировка становится иной: (1,0,1,4).

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

Так, прежде всего полезно ввести модельное время, чтобы моделировать не только последовательность событий, но и их привязку ко времени. Это осуществляется приданием переходам веса – продолжительности (задержки) срабатывания, которую можно определять, используя задаваемый при этом алгоритм. Полученную модель называют временной сетью Петри.

Если задержки являются случайными величинами, то сеть называют стохастической. В стохастических сетях возможно введение вероятностей срабатывания возбужденных переходов. Так, на рис. 15.9представлен фрагмент сети Петри, иллюстрирующий конфликтную ситуацию – маркер в позиции p может запустить либо переход t1, либо переход t2. В стохастической сети предусматривается вероятностный выбор срабатывающего перехода в таких ситуациях.

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

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

Рис.15.9. Конфликтная ситуация

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

Поясним на следующих примерах.

1. Требуется описать с помощью сети Петри работу группы пользователей на единственной рабочей станции WS при заданных характеристиках потока запросов на пользование WS и характеристиках поступающих задач. Сеть Петри представлена на рис. 15.10.

Рис.15.10. Сеть Петри для примера 1

Здесь переходы связаны со следующими событиями: t1 – поступление запроса на использование WS, t2 – занятие станции, t3 – освобождение станции, t4 – выход обслуженной заявки; позиция р4 используется для отображения состояния WS: если в р4 имеется метка, то WS свободна и пришедшая заявка вызывает срабатывание перехода t2; пока эта заявка не будет обслужена, метки в р4 не будет, следовательно, пришедшие в позицию «1» запросы вынуждены ожидать срабатывания перехода t3.

2. Требуется описать с помощью сети Петри процессы возникновения и устранения неисправностей в некоторой технической системе, состоящей из L однотипных блоков; в запасе имеется один исправный блок; известны статистические данные об интенсивностях возникновения отказов и длительностях таких операций, как поиск неисправностей, замена и ремонт отказавшего блока. На рис.15.11представлена соответствующая сеть Петри. Отметим, что при числе меток в позиции, равном M, можно в ней не ставить M точек, а записать в позиции значение M.

Рис.15.11. Сеть Петри для примера 2

В нашем примере значение M в позиции «2» соответствует числу имеющихся в системе блоков. Переходы отображают следующие события: t1 – отказ блока, t2 – поиск неисправного блока, t3 – его замена, t4 –окончание ремонта.

Очевидно, что при непустой позиции р2 переход t1 срабатывает, но с задержкой, равной вычисленному случайному значению моделируемого отрезка времени между отказами. После выхода маркера из t1 он попадает через р1 в t2, если имеется метка в позиции р6, это означает, что обслуживающая систему бригада специалистов свободна и может приступить к поиску возникшей неисправности. В переходе t2 метка задерживается на время, равное случайному значению длительности поиска неисправности. Далее маркер оказывается в р3 и, если имеется запасной блок (маркер в р4), то запускается переход t3, из которого маркеры выйдут в р2, р5 и в р6 через отрезок времени, требуемый для замены блока. После этого в t4 имитируется восстановление неисправного блока.

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

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

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

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

Безопасность– частный случай ограниченности, а именно это

1–ограниченность. Если для некоторой позиции установлено, что она

безопасна, то ее можно представлять одним триггером.

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

т.е.

ΣAiNi = const,

где Ni – число маркеров в i–й позиции, Ai – весовой коэффициент.

ДостижимостьMk→Mj характеризуется возможностью достижения маркировки Mj из состояния сети, характеризуемого маркировкой

Mk.

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

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

Один из методов анализа достижимости любой маркировки из состояния Мо – построение графа достижимости. Начальная вершина графа отображает Мо, а остальные вершины соответствуют маркировкам. Дуга из Мi в Мj означает событие Mi→Mj и соответствует срабатыванию перехода t. В сложных сетях граф может содержать чрезмерно большое число вершин и дуг. Однако при построении графа можно не отображать все вершины, так как многие из них являются дублями (действительно, от маркировки Mk всегда порождается один и тот же подграф вне зависимости от того из какого состояния система пришла в Мk). Тупики обнаруживаются по отсутствию разрешенных переходов из какой–либо вершины, т.е. по наличию листьев – терминальных вершин. Неограниченный рост числа маркеров в какой–либо позиции свидетельствует о нарушениях ограниченности.

Рис.15.12. Сеть Петри и граф ее достижимости для примера 1

Рис.15.13. Сеть Петри и граф ее достижимости для примера 2