Тема 28. Подходы к имитационному моделированию. Событийное моделирование и способы его организации в математической модели (потактовый и пособытийный).

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

Среди различных подходов к имитационному моделированию дискретных систем наиболее распространенными являются следующие три: транзактный, процессный, событийный.

При использовании транзактного подхода функционирование изучаемой системы с дискретными состояниями воспроизводится путем имитации последовательности процессов прохождения условных «заявок на обслуживание» (транзактов) через все фазы «обслуживания» этих заявок в системе, предусматриваемые ее структурой и параметрами.

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

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

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

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

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

Системное время есть то время, в котором происходит функционирование системы, и течение {продвижение) которого имитируется в ходе моделирования.

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

Продвижение системного времени может осуществляться двумя способами: а) с заданным шагом; б) от события к событию.

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

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

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

Операции, выполняемые в подпрограмме события, можно разделить на следующие три группы:

1) моделирование изменений в системе, связанных с рассматриваемым событием;

2) обновление календаря событий;

3) сбор и статистическая обработка результатов моделирования, полученных на интервале времени между предшествующим и текущим (исполняемым) событием в системе.

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

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

Изложенные принципы событийного подхода к моделированию дискретных систем могут быть воплощены в программе, составленной как на проблемно-ориентированном, так и на универсальном языке программирования. Рассмотрим пример составления алгоритма программы, ориентированного на его воплощение на каком-либо универсальном языке применительно к простейшей системе массового обслуживания. Для простоты предположим, что система содержит один прибор обслуживания и одно место в накопителе заявок. Заявки поступают в систему с интенсивностью λ₃ и обслуживаются прибором с интенсивностью λ_об. При занятом накопителе пришедшие заявки покидают систему необслуженными.

В данном случае состояние системы определяется состояниями накопителя и прибора, которые будем обозначать бинарными переменными К и С соответственно. Событиями, изменяющими состояние системы, являются: 1) приход заявки в систему; 2) освобождение канала обслуживания; 3) завершение времени моделирования системы.

В календаре событий должны храниться три величины: моменты t_ПЗ, t_ОП, ближайшие по отношению к текущему системному време­ни событий: «приход заявки» П_ПЗ, «освобождение прибора» П_ОП, а кс момент t_м события «окончание времени моделирования» П_М.

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

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

Блокуправления продвигает системное время по схеме от событийк событию с помощью оператора min(t_ПЗ, t_ОП, t_м ), управляет своевременным выполнением подпрограмм событий П_ПЗ, П_ОП и П_М.

При выполнении подпрограммы события «приход заявки» в систему П_ПЗ осуществляются следующие действия:

1) разыгрывается новый случайный интервал между заявками и рассчитывается момент прихода следующей заявки в систему, который заносится в календарь;

2) проверяются состояния прибора и накопителя. Если прибор в момент прихода заявки свободен, логической переменной С присваивается значение С = 1 (состояние «прибор занят»), разыгрывается случайная продолжительность обслуживания заявки и определяется момент освобождения прибора, который заносится в календарь. Если прибор в момент прихода заявки занят, а накопитель свободен (К = 0), то заявка поступает в накопитель и это событие фиксируется присвоением переменной К значения 1 («накопитель занят»). Если же в момент прихода заявки К = 1, то заявка покидает систему необслуженной.

В момент события П_ОП также проверяется состояние накопителя, и если он занят (К = 1), то заявка переводится на обслуживание в приборе по описанной выше схеме, а накопитель переводится в стояние «свободен» присвоением переменной К состояния К = 0.

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

В момент t_м события «окончание времени моделирования» проводится расчет показателей свойств системы по результатам, накопленным в данной реализации. Итоговые оценки показателей рассчитываются путем обработки данных расчета большого числа реализаций, если работа системы анализируется в переходном режиме, или одной длинной реализации, — если процесс функционирования системы является эргодичным и свойства системы анализируются в стационарном режиме.

Язык GPSS состоит из набора абстрактных понятий — объектов, в терминах которых осуществляется описание моделируемой системы. Объекты разделены на четыре класса: динамические, аппаратно-ориентированные, статические и операционные.

Динамические объекты или транзакты — суть абстракции, с помощью которых представляются элементы внешних потоков, «обслуживаемых» моделируемой системой. Транзакты «создаются» и «уничтожаются» в соответствии с логикой работы системы. С их мощью, например, имитируется поток заявок, поступающих в систему массового обслуживания, а также потоки отказов, которым подвержены элементы изучаемой системы.

Аппаратно-ориентированные объекты соответствуют оборудованию моделируемой системы. Они «обслуживают» транзакты. К таким объектам относятся устройства, накопители, логические переключатели.

Устройство может одновременно обслуживать только один транзакт, при этом обслуживание может быть прервано другим транзактом, а отстраненный от обслуживания транзакт или уничтожается,или ожидает повторного обслуживания, или пытается войти на обслуживание в какое-то другое устройство. Отстранением от обслуживания, например, имитируется отказ какого-либо элемента СТС. По каждому устройству, имеющемуся в исследуемой системе, автоматически накапливается статистика: отношение времени, в те­чение которого оно было занято, к общему моделируемому времени функционирования системы (коэффициент загрузки устройства), общее число поступивших в него транзактов, среднее время пребы­вания транзакта в устройстве и др.

Накопитель — устройство с ограниченной емкостью, которое может одновременно обслуживать несколько транзактов. Транзакт может «войти» в накопитель только при условии, что в нем в данный момент имеется «свободное» место. Статистика работы накопителя включает среднее число занятых мест в нем, коэффициент загрузки, общее число транзактов, поступивших в накопитель, среднее время пребывания транзакта в накопителе и др.

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

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

Операционные объекты называются также блоками. Они обеспечивают моделирование логики работы системы, давая транзактам указания о направлении и характере их последующего движения по системе. Блоки могут быть различных типов. Каждый из них имеет определенную логику работы. Например, блок типа SEIZE (захват) сначалапроверяет, свободно ли устройство, на которое претендует транзакт. Если устройство занято, то транзакт остается в этом блоке и повторяет попытку занять устройство в следующий момент времени.

Чтобы составить модель системы на языке GPSS, надо составить описание системы в терминах этого языка. Это описание представляет собой программу, которая при выполнении управляет работой симулятора GPSS. Симулятор генерирует транзакты и передвигает их от блока к блоку аналогично тому, как движутся в реальной системе единицы потоков, представляемые транзактами. Каждое движение транзакта является событием в системе. Симулятор регистрирует моменты наступления событий каждого типа в системе и осуществляет статистическую обработку интервалов между ними. Для воспроизведения системного времени в симуляторе моделируется таймер.

Программа моделирования системы на языке GPSS составляется в виде схемы моделирования, отображающей последовательность осуществления событий в системе. Каждый элемент этой схемы ответствует определенному событию, которое описывается определенным блоком. Блоки на схеме соединяют линиями, показывающими путь транзакта от одного блока к другому. В блок может входить несколько линий, если событие, характеризуемое данным блоком, может произойти после предшествующих событий нескольких других типов. Альтернативные ситуации, которые могут возникнуть в блоке, изображаются двумя или несколькими линиями, выходящими из него. Выбор пути при наличии нескольких альтернатив может быть случайным или логическим в соответствии с логикой работы реальной системы. Случайные величины моделируются в симуляторе с учетом их функций распределения, указанных исследователем в программе моделирования, с помощью генератора псевдослучайных чисел, равномерно распределенных на отрезке [0, 1].

При составлении программы моделирования системы исследователь должен хорошо знать функции, которые выполняют блоки языка GPSS. Руководство по использованию системы моделирования GPSS можно найти в [58, 73].

В качестве примера рассмотрим построение имитационной модели одноканальной системы массового обслуживания, состоящей из одного обслуживающего «прибора». Если в момент поступления заявки прибор оказывается занятым обслуживанием предшествующей заявки, то эта заявка поступает в накопитель, где ожидает своей очереди поступления в прибор на обслуживание. Пусть исследователя интересуют среднее время обслуживания заявки, среднее время ее пребывания в очереди и средняя длина очереди. Для решения задачи имитационную модель системы можно представить в видеследующего процесса прохождения транзакта через систему:

1) генерация транзакта в соответствии с заданной интенсивностью потока заявок с помощью блока GENERATE;

2) вход транзакта в очередь в прибор QUEUE. Этот блок не задерживает транзакт, а служит для фиксации момента поступления транзакта в очередь;

3) попытка занять прибор SEIZE. Если прибор занят, то транзакт остается в этом блоке, т.е. в очереди, вплоть до прохождения всех предшествующих транзактов из очереди через прибор;

4) выход транзакта из очереди DEPART. Этот блок не задерживает транзакт и нужен программе для регистрации момента покидания транзактом очереди;

5) обслуживание транзакта прибором ADVANCE. Этот блок имитирует случайное время обслуживания в соответствии с заданным законом его распределения вероятностей;

6) освобождение прибора RELEASE;

7)уничтожение транзакта TERNINATE.

Для организации заданного числа прогонов этой модели исследователь должен использовать управляющие операторы языка GPSS.

Не нашли, что искали? Воспользуйтесь поиском по сайту: