Моделирование СМО с отказами по схеме событий

(Описание алгоритма)

подготовка:

ввод данных (m_t, t_обсл,, правило остановки)

установка начальных значений переменных, соответствующих нулевому шагу

основная часть:

шаг имитации (подробно раскрыт ниже)

выполнено условие остановки (напр., пройдено Nдоп шагов)

вычисление оценок искомых характеристик (Р_пот, Р₀, Р₁, Р₂, Р_зп

про указанным выше формулам)

завершение:

выдача результатов

запрос пользователю на выбор дальнейшего действия (выдача

меню) и переход в соответствующее место программы в

зависимости от ответа пользователя)

моделирования.

 

Далее раскрыт алгоритм шага имитации

 

 

увеличение номера шага (N:=N + 1)

запоминание значений некоторых переменных (Y_p:=Y; T_L:=T_T)

определение момента и типа очередного события:

t_T := min(T_з,Т₁,Т₂); J_T:=

имитация события:

поступила заявка (J_T=0)

есть свободный прибор (Y<2)

поиск номера свободного прибора (Jv), начиная

с первого прибора

занятие прибора Jv (Х _Jv:=1)

увеличение числа занятых приборов (Y:=Y+1)

(освободился прибор J_т)

перевод прибора в свободное состояние (X_JT:=0)

уменьшение числа занятых приборов (Y:=Y-1)

пополнение статистик:

поступила заявка (Jт = 0)

пополнение счетчика заявок (Кз:=Кз + 1)

заявка потерялась ( =2)

пополнение счетчика потер. заявок (К_пот:=К_пот+1)

пополнение суммарного времени пребывания в соответст-

вующем состоянии (DT:=Т_т-Т_p;

планирование событий (корректировка календаря):

поступила заявка (J_T=0)

планирование следующей заявки (Тз:= T_Т+t, t получа-

ется обращением к датчику случайных чисел)

заявка поступила в прибор J_V (Y_L<2)

планирование его освобождения (:=Т_Т+t_обсл)

(освободился прибор J_Т) :=¥

 

Отметим, что в алгоритме шага четко разделены этапы: имитация события, пополнение статистик, планирование событий. Если отказаться от такого разделения, можно избежать повторения некоторых пpoвeрок и введения переменной Т_p. Однако опыт программистов показал, что стройность и четкость важнее экономии. Поэтому приведенный вариант представляется более предпочтительным.

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

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

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

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

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

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

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

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

До начала шагов производятся ввод исходных данных и установка начальных значений переменных, а по окончании шагов - подсчет оценок искомых характеристик по накопленным статистикам и выдача результатов.

Описанные принципы моделирования пригодны как для простых, так и.для сложных случаев, но в сложных случаях потребуется трудная работа по составлений перечня возможных событий и разработке алгоритмов имитации этих событий. Трудность состоит в том, что многие события оказываются взаимообусловленными и должны рассматриваться как одно сложное событие, включающее ряд элементарны событий. Рассмотрим, например, моделирование СМО, в которой имеется буфер. Имитация поступления заявки включает несколько частей: выяснение, имеется ли свободный прибор; поиск свободного прибора и его занятие; в случае отсутствия свободного прибора - поиск и занятие свободной ячейки буфера. Если заявка имеет абсолютный приоритет, возможно вытеснение менее приоритетной заявки из прибора. Тогда надо будет еще учесть дальнейшую судьбу вытесненной заявки. Таким образом, в рамках одного события имитируются многие элементарные события, отражающие изменения состояний сразу нескольких объектов: поступившей заявки, прибора, ячейки 6yфеpa, вытесненной заявки.

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

Приведем схему шага моделирования, алгоритм которого построен по

принципу D t для СМО G/G/2, и схемы частных алгоритмов «Обработка заявки» «Обработка окончания обслуживания прибора» для схемы СМО М/М/1/ .

 

 

ШАГ ИМИТАЦИИ ПО ПРИНЦИПУ Dt

Рис. Блок схема шага имитации по принципу Dt

(СМО G/G/2)

 

Принцип особых моментов.

Блок-схемы частных алгоритмов моделирования СМО с очередью

 

 

Z=o

да

нет

:=

S1:=S1+

Z:=1

:= tT +

Tос:=tT+

Кс:= Кс+1

>

tT: =

S2:=S2+

да

Кс:= Nзад

нет

На вход шага имитации

да

Вычисление оценок и их точности

нет

Рис. Частный алгоритм «Обработка заявки» Исх. данные: S1=S2= = = 0

 

To

да

Тo:=

Z:=1

Вход Оператора 3

Рис. Блок-схема частного алгоритма «Обработка окончания обслуживания прибора»

Z:=0

= 0

нет

:= –1

Tо:=tT+

tT:=Tо

 

Вопросы и задания

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

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

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

4. Сформулируйте основной признак схемы событий.

5. Какие части в алгоритме шага можно поменять местами?

6. Проведите эксперименты, чтобы сравнить точность двух оценок вероятности потери заявки: оценки по заявкам и оценки по времени.

 

 

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: