Моделирование систем массового обслуживания (стр. 1 из 7)
Методика построения программной модели
Для разработки программной модели исходная система должна быть представлена как стохастическая СМО. Это объясняется следующим: информация от внешней среды поступает в случайные моменты времени, длительность обработки различных типов информации в общем случае также является различной. Таким образом, внешняя среда может быть отображена как генератор сообщений, а комплекс ВС – обслуживающими устройствами.
Обобщенная структурная схема ВС.
 |
ИИ – источники информации – выдают на вход буферной памяти независимые друг от друга сообщения. Закон появления сообщений - произвольный.
В БП (буферной памяти) сообщения записываются «в навал» и выбираются по одному в обслуживающий аппарат по принципу FIFO/LIFO. Длительность обработки одного сообщения в ОА (обслуживающий аппарат) в общем случае может быть случайной, но закон обработки всегда должен быть задан. Т.к. быстродействие ОА ограничено, то на входе системы в БП возможно сложение данных, ожидающих обработку.
ПБССт - программный блок сбора статистики.
Блок синхронизации необходим, чтобы система заработала.
Моделирование потока сообщений.
Поток сообщений обычно моделируется моментами появления очередного сообщения в потоке. Текущий момент времени появления очередного сообщения:
где Ti– интервал времени между появлением i-го и (i-1)-го сообщения.
Процедура.
обращение к процедуре выражения случайного числа Rnd
| Вид распределения | Выражение |
| равномерное на [a,b] |  |
| нормальное |  |
| экспоненциальное |  |
| Эрланга |  |
Моделирование работы Обслуживающего Аппарата.
Программа – имитатор работы ОА представляет собой комплекс, вырабатывающий случайные отрезки времени, соответствующие длительностям обслуживания требований. Например, если требования от источника обрабатываются в ОА по нормальному закону с параметрами Mx и sx, то длительность обработки i-ого требования:
Схема алгоритма имитатора.
Ri – случайное число с равномерным законом распределения
ТОБР – время обработки очередного сообщения
T – время освобождения ОА
XM – Мат ожидание для заданного закона обратки
DX – СКО для заданного закона обратоки
Моделирование работы абонента
Абонента можно рассматривать как ОА, поток информации на который поступает от процессора. Для моделирования работы абонентов необходимо вырабатывать длительности обслуживания требований. Кроме того, абонент сам может быть источником заявок, претендуя на те или иные ресурсы вычислительной системы. Эти заявки могут имитироваться с помощью генератора сообщений по наперед заданному закону. Таким образом, абонент либо имитируется как ОА, либо как генератор.
Моделирование работы буферной памяти
Блок буферной памяти должен производить запись и считывания числа, выдавать сигналы переполнения и отсутствия данных. В любой момент времени располагать сведениями о количестве требований в блоке. Сама запоминающая среда имитируется некоторым одномерным массивом, размер которого определяет размер БП. Каждый элемент этого массива может быть либо свободен, либо занят.
| P | массив сообщений | LM | объем буферной памяти |
| WYB | признак обращения к буф. памяти = 1 – режим выборки сообщений = 0 – режим записи | NPOS | номер последнего сообщения, поступившего в память |
| NP | число сообщений в памяти | NPER | номер первого сообщения в памяти |
| POLN | признак переполнения памяти = 1 – нет свободных ячеек | PUST | признак отсутствия сообщений = 1 – в памяти нет сообщений |
| NPOS | = NPOS + 1, если NPOS < LM = NPOS – LM + 1, иначе | NPER | = NPER – 1, если NPER < 1 = NPER – LM + 1, иначе |
| X | ячейка для сообщения |
Разработка программы сбора статистики
Задача блока статистики заключается в накоплении численных значений, необходимых для вычисления статистических оценок заданных параметров моделируемой системы.
При моделировании работы простейшей СМО обычно интерес представляет среднее время ожидания в очереди. Для каждого сообщения время ожидания в очереди равно разности между моментами времени, когда оно было выбрано на обработку ОА, и моментом времени, когда оно пришло в систему от источника информации.
Суммируя значения количества сообщений в БП через небольшие промежутки времени и разделив на число суммирований, получим среднее значение длины очереди в памяти.
Коэффициент загрузки ОА определяется как отношение времени работы ОА к общему времени моделирования.
Разработка управляющей программы имитационной модели
Если программа - имитатор работы источника обслуживающего аппарата или памяти моделирует работу отдельных устройств, то управляющая программа имитирует алгоритм взаимодействия элементов системы. Управляющая программа реализуется в основном по двум принципам:
1. принцип Dt
2. событийный принцип
Принцип Dt.
Принцип заключается в последовательном анализе состояний всех блоков в момент t+Dt по заданному состоянию блоков в момент t. При этом новое состояние блоков определяется в соответствии с их алгоритмическим описанием с учетом действия случайных факторов, задаваемых распределением вероятностей. В результате этого анализа принимается решение о том, какие общесистемные события должны имитироваться в программной модели на данный конкретный момент времени.
Основной недостаток в том, что происходят значительные затраты машинного времени на реализацию исследования системы. При недостаточно малом Dt появляется опасность пропуска отдельных событий в системе, что приводит к получению неправильных результатов.
Событийный принцип
Характерное свойство моделируемых систем – состояние отдельных устройств изменяется в дискретные моменты времени, которые совпадают с моментами поступления сообщений в систему, моментами окончания решения задач, моментами возникающих аварийных сигналов и т.д. Поэтому, моделирование и продвижение текущего времени в системе удобно проводить использую событийный принцип, при котором состояние всех блоков системы анализируется лишь в момент наступления какого-либо события. Момент наступления следующего события определяется минимальным значением из списка будущих событий, представляющих собой совокупность моментов ближайшего изменения состояний каждого из блоков системы.
t11, t12 – моменты появления сообщений на выходе генератора (источника информации)
b1 – интервал времени обслуживания первого сообщения
t3 n – момент сбора статистики
t41– момент окончания моделирования
Методика реализации событийной модели
1. Для всех активных блоков (блоков, порождающих события) заводя свой элемент в одномерном массиве – списке будущих событий.
2. В качестве подготовительной операции в список будущих событий SBS заносят время ближайшего события от любого активного блока. Активизируя программу-имитатор, ИИ вырабатывает псевдослучайную величину a0, определяющую момент появления первого сообщения t11. Эту величину заносят в список будущих событий.
Активизируя программу-имитатор, ОА вырабатывает псевдослучайную величину b0, определяющую момент времени t21, которую также заносят в SBS.
Момент времени t31 (1ый сбор статистики) определяется равным стандартному шагу сбора tСТАТ, и заносится в SBS
В SBS заносится t41 – время окончания моделирования.
Подготовительная часть на этом закончена и начинается протяжка модельного времени.
3. В SBS определяется минимально числовое значение и его номер.
4. Реализуется событие, порождаемое блоком с соответствующим номером, т.е. модельное время = t11. Далее реализуется событие с номером 1, связанное с появлением нового сообщения в ИИ. Реализация этого события заключается в том, что само сообщение записывается в память, а с помощью имитатора ИИ, вырабатывается момент появления следующего события t12. Это время помещается в соответствующую ячейку SBS место t11.
Затем вновь организуется поиск минимального элемента в SBS. Для данного примера реализуется событие 3, после чего выражение момента времени t32 – новое время сбора статистики. Так до тех пор, пока минимально время не станет равным t41.