3.7. Имитация случайных потоков

Как правило, потоки событий имитируются с исполь­зованием распределений случайного времени между двумя соседними событиями. Если рассматриваемый поток является стационарным и известна плотность или функция распределения времени между событиями, то методами имитации случай­ных величин вычисляются значения Δt₁, Δt₂, случайного времени между событиями. Тогда момент наступления i -го события вычисляется по формуле

При этом t₀ должно быть задано. Если поток является нестационарным, то для формирования каждого Δt_i использу­ется свой закон распределения.

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

следует упорядочить события потока по времени наступления.

Е сли многомерный поток является стационарным и ординарным с многомерной интенсивностью ,то его можно имитировать следующим об­разом. Моделируется одномерный поток событий с интенсивностью а принадлежность события i - й составляющей потока определяется по жребию с вероятностью

При этом λ_i есть величина, обратная среднему време­ни между заявками.

3.8. Имитация процессов функционирования

СМО

Имитацию процессов функционирования СМО будем рассматривать на примере простейшей одноканальной СМО.

Пусть в одноканальную СМО входит одномерный по­ток, закон распределения которого известен. Длительность об­служивания τ есть случайная величина с заданным законом распределения. Заявки в системе обслуживаются, в порядке очереди, т.е. в том порядке, в котором они поступают в систе­му. Если поступившая заявка застанет канал занятым, то она встает в очередь и ожидает освобождения канала. Как только

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

Процесс функционирования СМО будем рассматри­вать в интервале времени [0, Т], где Т - заданное время моде­лирования. Это означает, что заявки, пришедшие в момент времени t >Т, в систему не попадают и не обслуживаются. Если же время поступления заявки t < Т, но время окончания обслуживания (время освобождения канала) t^oce > Т, то такая заявка считается получившей отказ.

В качестве исходных данных для решения задачи должны быть заданы значения времени моделирования Т, за­коны распределения потока заявок и времени обслуживания, а также количество реализаций N^* , обеспечивающие заданную точность.

Перед началом моделирования задаются начальные условия:

- время поступления "нулевой" заявки t = 0;

• время освобождения канала t^oce = 0;

• число обслуженных заявок m = 0;

• число заявок, получивших отказ, = 0;

- длина очереди к = 0;

- суммарное время пребывания заявок в системе t^np =0;

• суммарное время ожидания заявок в системе t^ож = 0;

• выполненное число имитаций N =0;

Блок-схема имитации данной СМО приведена нарис.31.

Остановимся кратко на работе алгоритма и его основ­ных операторов. Оператор 1 вводит исходную информацию и устанавливает начальные условия. Оператор 2 формирует по­ступления очередной заявки t. Оператор 3 проверяет выпол­нение условия t <T . Если это условие выполняется, то заявка попадает в систему, в противном случае она в системе не рас­сматривается. В блоке 4 проверяется, свободен ли канал. Если канал занят (ω= 1), то в блоке 5 проверяется, есть ли место в очереди. Если есть (ω=0) , то в блоке 6 длина очереди уве­личивается, а на последнее место в буфере записывается вре­мя поступления заявки (блок 7). Если места в очереди нет (ω= 0 блоке 5), заявка получает отказ и в блоке 8 число отка­зов увеличивается на единицу.

Если ω = 0 в блоке 4, т.е. канал свободен, в блоке 9 проверяется, есть ли в системе очередь. Если ω= 0 в блоке 9, это означает, что очереди в системе нет, а поскольку канал свободен, то с блока 10 начинается обслуживание вновь посту­пившей заявки. При этом в блоке 10 за начало обслуживания t^H принимается t - время поступления данной заявки. В блоке 11 формируется случайная длительность обслуживания τ. Оператор 12 определяет время освобождения канала от обслу­живания данной заявки. В блоке 13 проверяется условие t Т, Если это условие выполнено (ω= 0), то заявка считается обслуженной. Оператор 14 увеличивает число об­служенных заявок m на единицу. В блоке 15 накапливается время пребывания всех заявок в системе, а в 16 - время ожидания в очереди.

Если ω = 0 в блоке 13, то обслуживание заявки не укладывается во время моделирования Т и заявка получает отказ (блок 17). Поскольку в этом случае заявка покидает сис­тему не в момент t^осв, а в момент времени Т, то для подсчета t^np и t^ож в блоках 15,16 необходимо сделать присвоения t^осв = T (блок 18).

Если ω = 1 в блоке 9, то в системе свободен канал, и есть очередь. Вновь пришедшую заявку, время которой еще не наступило, так как t > t^осв, нужно запомнить в специально отведенной ячейке памяти. Это запоминание имитирует опера­тор 22, а в 23 вырабатывается признак а — 1 (сформировано время поступления заявки, которое пока не использовано). В блоке 24 имитируется выбор из очереди первой заявки; в бло­ках 25-29 происходит сдвиг значения в буфере с занулением последнего элемента. В блоке 30 очередь уменьшается, а в 31 за начало обслуживания выбранной заявки принимается мо­мент освобождения канала. Затем имитируется обслуживание заявки в блоках 11-16. После завершения обслуживания в бло­ке 19 проверяется, есть ли в памяти уже сформированное, но не использованное время поступления заявки. Если нет (ω= 0), то управление передается блоку 2 для формирования времени поступления очередной заявки. Если ω= 1 в блоке 19, то из памяти забирается записанное там t и управление передается блоку 4.

Если ω = 0 в блоке 3, то момент поступления заявки вышел за время моделирования Т. В этом случае за время от t^oce по T можно обслужить заявку из очереди, если она есть. Поэтому оператор 32 проверяет, есть ли очередь. Если есть ω=0 в (32) , управление передается оператору 24, в котором имитируется выбор заявки из очереди. Если ω= 0 в (32), и это означает конец реализации. В блоке 33 число реализаций имитации увеличивается на единицу, а в блоке 34 оно сравни­вается с максимальным. В зависимости от результатов сравне­ния следует передача управления либо на блок 35, где установка начальных условий для новой реализации t = 0 , t^oce = 0, к = 0, либо на блок 36 для обработки и выдачи результатов.

Рис.31

Обработка результатов заключается здесь в определении вероятности отказа

среднего времени ожидания заявки в очереди

среднего времени пребывания заявки в системе

Замечание. Аналогично можно разработать блок-схему имитации процессов функционирования других систем массо­вого обслуживания. Широкое применение, благодаря простоте освоения в самых различных областях науки и промышленно­сти, получил язык моделирования CPSS.

ЛИТЕРАТУРА

1. Анисимов В.В.., Закусило O.K., Донченко B.C. Эле­менты теории массового обслуживания и асимптотического анализа систем. Киев; Вица школа,1987.

2. Бронштейн О.И., Духовный И.М. Приоритетное об­служивание в информационных системах. М: Наука, 1976.

3. Бусленко Н.П. Моделирование сложных систем. М: Наука, 1978.

4. Вентцель Е.С. Исследование операций. М: Совет­ское радио, 1972.

5. Гиеденко Б.В., Коваленко И.Н. Введение в теорию

массового обслуживания. М: Наука, 1987.

6. Ермаков СМ., Михайлов Г.А. Курс статистического моделирования. М: Наука, 1976.

7. Лившиц А.Л., Мальц Э.А. Статистическое модели­рование систем массового обслуживания. М: Советское радио,

1978.

8. Мова В.В., Пономаренко Л.А., Калиновский A.M. Организация приоритетного обслуживания в АСУ. Киев: Техника, 1977.

9. Овчаров Л.А. Прикладные задачи теории массового обслуживания. М: Машиностроение, 1969.

10. Советов Б.Я., Яковлев С.А. Моделирование систем. М: Высшая школа, 1985.

СОДЕРЖАНИЕ

1. Моделирование операций по схеме марковских случайных процессов...........................................................3

1.1. Марковский случайный процесс с дискретны­ми состояниями................................................................3

1.2. Марковский процесс с дискретными состоя­ниями и непрерывным временем. Уравнения Колмогорова для вероятностей состояний................................................................................................6

3. Поток событий. Простейший поток и его свой­ства.................................................................................16

4. Пуассоновские потоки событий и непрерыв­ные марковские цепи........................................................22

5. Предельные вероятности состояний..........................................................................................................26

6. Процесс "гибели и размножения"..............................................................................................................31

7. Циклический процесс..................................................................................................................................37

2. Теория массового обслуживания.......................................................................................................................41

1. Задачи теории массового обслуживания....................................................................................................41

1. Классификация систем массового обслужива­ния и их основные характеристики................................43

2. Одноканальная СМО с отказами................................................................................................................46

3. Многоканальная СМО с отказами..............................................................................................................51

2. Одноканальная СМО с ожиданием (число мест в очереди ограничено).................................................56

2.6. Одноканальная СМО с ожиданием (число мест в очереди не ограничено)...........................................64

7. Многоканальная СМО с ожиданием (число мест в очереди ограничено).............................................69

8. Многоканальная СМО с ожиданием (число мест в очереди не ограничено) .........................................74

9. СМО с ограниченным временем ожидания..............................................................................................77

10. Замкнутые системы массового обслужива­ния.........................................................................................81

11. Системы массового обслуживания с непуассоновскими потоками событий.......................................87

3. Имитационное моделирование систем массового обслуживания..................................................................88

1. Метод имитационного моделирования....................................................................................................88

2. Фиксация и обработка результатов имитаци­онного эксперимента.......................................................89

3. Оценка количества испытаний, необходимо­го для обеспечения заданной точности ..........................91

4. Генерирование равномерно распределенной в интервале (0,1) случайной величины.........................94

5. Имитация случайных событий.............................................................................................................97

6. Имитация случайных величин...........................................................................................................100

7. Имитация случайных потоков............................................................................................................105

8. Имитация процессов функционирования СМО.......................................................................................107

Набор и верстка Ф. С Хасанова

ЛРN 020342 от 7.02.97 г. Подписано в печать 27.12.99 г.

Формат 60x84/16 Бумага газетная Печать офсетная Уч.-изд.л. 7,2 Усл.-печ.л. 7,2 Тираж 300 экз. Заказ 1170/595 Издательство Камского политехнического института

Участок оперативной полиграфии КамПИ, 423810, г. Набережные Челны, Новый город, проспект Мира, 13