Моделирование СМО по событиям
Компьютерное моделирование СМО на основе Марковского процесса возможно, если потоки заявок и потоки обслуживания распределены по экспоненциальному закону. В общем случае для произвольных распределений этот метод не применим.
Для моделирования СМО с произвольными распределениями потоков заявок и потоков обслуживания применяется метод имитационного моделирования по событиям. Событиями в СМО называются моменты времени, когда очередная заявка приходит в систему и когда обслуженная заявка покидает систему. Другими словами, это моменты изменения состояния системы. Эти моменты образуют список событий, в котором можно выделить текущее событие и списки прошедших и будущих событий. Метод имитационного моделирования включает последовательное формирование списка событий и продвижение процесса моделирования от одного события к другому. Модельное время при имитационном моделировании является зависимой переменной и изменяется скачками, равными интервалам времени между последовательными событиями.
Схема алгоритма имитационного моделирования по событиям приведена на рисунке 6.
Принятые обозначения:
Входные параметры:
N — максимальное число входящих заявок (условие окончания моделирования).
NK — количество каналов.
LMAX — максимально допустимая длина очереди.
Накапливаемая статистика:
T — текущее модельное время, изменяющееся скачком между моментами возникновения событий в системе.
TA — момент прихода очередной заявки (время, прошедшее с начала моделирования).
K — счетчик пришедших заявок.
KS — счетчик обслуженных заявок.
L — текущая длина очереди.
LOS — счетчик отказов (заявок, поучивших отказ в обслуживании).
Массивы:
OCP[i] — признак занятости i-го канала (0 — канал свободен, 1 — канал занят).
TD[i] — ожидаемый момент выхода заявки из i-го канала (время, прошедшее с начала моделирования).
TOS[i] — счетчик суммарного времени занятости i-го канала — сколько единиц модельного времени в течение всего процесса моделирования канал был занят.
TL[M] — суммарное время пребывания системы в состоянии, когда в ней ровно M заявок.
Вспомогательные величины:
MIN — ближайший момент выхода обслуженной заявки из канала, считая от текущего модельного времени.
S — номер канала, который в текущем состоянии системы освободится первым (в момент времени MIN).
DTA — время между приходами заявок (генерируемая в процессе моделирования случайная величина).
DTS — время обслуживания заявки в канале (генерируемая в процессе моделирования случайная величина).
Для рассматриваемой СМО
,
где u1, u2 — равномерно распределенные на интервале [0, 1) случайные величины (рекомендуется использовать для их генерации два независимых датчика ррсч[0,1) ).
В процессе моделирования в любой момент времени известны моменты наступления событий для всех возможных источников (момент прихода очередной заявки и моменты освобождения каждого из каналов). Если канал свободен, то считается (с целью упрощения алгоритма), что ожидаемое время его освобождения бесконечно велико; в предлагаемой схеме алгоритма в качестве заведомо большого значения взято число 999999.
Установка начальных значений (блок 2) состоит в заполнении массива TD большими числами (999999), а всех переменных и других массивов — нулевыми значениями. Это соответствует ситуации, когда все каналы свободны и модельное время равно 0.
Блок 3 определяет момент прихода очередной заявки, при этом увеличивается счетчик пришедших заявок K, модельное время не изменяется.
Блок 4 — проверка условия окончания моделирования.
Блоки 7-11 реализуют определение номера канала, который освобождается первым, и момента его освобождения. При начальном запуске системы все каналы свободны, поэтому номер канала S не важен (вообще-то это будет последний канал), а в качестве момента его освобождения MIN будет обнаружено заведомо большое число.
Далее происходит проверка: какое из событий наступит раньше, приход заявки в момент времени TA или освобождение канала в момент времени MIN (блок 12)? При начальном запуске ближайшим событием окажется приход заявки (так как все каналы свободны) и произойдет переход на блок 19.
Блок 19 осуществляет накопление статистики по пребыванию системы в состоянии с M заявками. Очевидно, что M равно сумме количества занятых каналов (суммы всех элементов массива OCP[i]) и количества заявок в очереди L. Если текущее модельное время T, а переход в новое состояние произойдет в момент времени TA по приходу заявки, то в состоянии М система пробудет (TAT) единиц модельного времени.
Блок 20 изменяет модельное время. Теперь состояние системы можно сформулировать как "очередная заявка только что пришла в систему".
Блоки 21-24 организуют цикл поиска свободного канала. Если свободный канал найден, то происходит переход на блок 25 и досрочный выход из цикла поиска.
Блоки 25-26 реализуют действия алгоритма моделирования в случае, когда в системе есть свободный канал. В этом случае канал объявляется занятым (блок 25) и сразу же разыгрывается время обслуживания заявки в канале DTS и момент его освобождения TD[i], равный текущему модельному времени T плюс DTS. Сразу же в массиве TOS[i] учитывается и время, которое занимаемый канал потратит на обслуживание заявки.
Если в системе нет свободных каналов, то заявка помещается либо в очередь, либо, если очередь уже имеет максимально допустимую длину, получает отказ. Эта логика реализуется блоками 27-29.
После обработки прихода очередной заявки в блоках 19-29 происходит переход на блок 3, где происходит определение момента прихода очередной заявки.
Рис. 6. Схема алгоритма моделирования многоканальной СМО по событиям
Рассмотрим теперь вариант, когда текущее состояние системы таково, что приход очередной заявки случится позже, чем освобождение одного из каналов. При этом в результате выполнения поиска первого освобождающегося канала в блоках 7-11 будет определен номер S канала, освобождающегося первым, и момент его освобождения MIN. Переход из блока 12 произойдет на блок 13.
Блок 13 идентичен блоку 19 и осуществляет накопление статистики по пребыванию системы в состоянии с M заявками.
Блок 14 имитирует окончание обслуживания заявки в канале S. Счетчик обслуженных заявок увеличивается на единицу, а модельное время становится равным времени MIN выхода заявки из канала S.
В блоке 15 осуществляется проверка наличия заявок, ожидающих в очереди.
Если заявки в очереди есть, то ожидающая заявка сразу направляется в только что освободившийся канал S, генерируется время ее обслуживания DTS и определяется момент окончания обслуживания TD[S]. Сгенерированное время DTS учитывается также в статистике времени занятости канала TOS[S] (блоки 16-17).
Если очередь пуста, то канал S объявляется свободным и в качестве момента его освобождения TD[S] устанавливается заведомо большое число.
Для систем с бесконечной этот алгоритм обычно тоже применим, при этом в LMAX должно быть установлено достаточно большое число (например 100).
Вычисление характеристик СМО. По окончании моделирования основные характеристики СМО могут быть получены следующим образом:
1. Вероятности пребывания в состоянии, когда в системе ровно i заявок, определяется как доля времени, в течение которого в системе было i заявок, в общем времени моделирования:
2. Вероятность отказа — доля заявок, получивших отказ, в общем количестве заявок:
3. Пропускная способность — количество обслуживаемых в единицу времени заявок:
4. Среднее количество занятых каналов можно определить как отношения суммарного времени занятости всех каналов к общему времени моделирования:
5. Среднее время ожидания в очереди можно определить как суммарное время ожидания заявок в очереди, отнесенное к количеству входящих заявок. Если B — это время, проведенное всеми заявками в системе, и C — время, проведенное всеми заявками в каналах, то их разность — время, проведенное всеми заявками в очереди. Тогда
 |
, , ;
6. Средняя длина очереди может быть вычислена как математическое ожидание количества заявок в очереди в процессе моделирования:
 |
Полученные по этим формулам характеристики СМО необходимо сравнить с характеристиками, полученными в результате аналитического расчета.
3. ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНЫХ РАБОТ 3 И 4
При подготовке к лабораторной работе в соответствии с вариантом индивидуального задания необходимо :
· Составить список состояний СМО;
· Нарисовать граф состояний СМО;
· Составить и решить систему уравнений Колмогорова;
· Рассчитать основные характеристики СМО:
1. Вероятность отказа;
2. Коэффициент загрузки;
3. Пропускная способность;
4. Среднее число заявок, обслуживаемое в СМО
5. Среднее количество занятых каналов и т.д.
· Во время лабораторной работы провести численное моделирование этого же варианта СМО по методу, указанному в задании.
· Сравнить основные характеристики СМО, полученные в результате аналитического и численного расчета.
Отчет должен содержать:
1. Исходные данные для моделирования СМО в соответствии с вариантом задания;
2. Список состояний СМО;
3. Граф состояний СМО;
4. Уравнения Колмогорова;
5. Вероятности нахождения СМО в каждом состоянии;
6. Основные характеристики СМО, полученные аналитически,
7. Основные характеристики СМО, полученные численно,
8. Анализ полученных результатов.
ЗАДАНИЯ
к лабораторной работе №3 «Моделирование СМО»
Группа А4-
| № | Число каналов | Длина очереди | Интенсивность потока событий λ | Среднее время обслужи-вания 1/μ | Метод численного моделирования |
| ≤ 3 | По событиям | ||||
| ≤ 2 | 2.5 | По событиям | |||
| 1.2 | По событиям | ||||
| По событиям | |||||
| ∞ | 0.8 | По событиям | |||
| ∞ | 1.5 | 1.6 | По событиям | ||
| ≤ 3 | 1.5 | 1.5 | По событиям | ||
| ≤ 2 | 1.5 | По событиям | |||
| 1.5 | По событиям | ||||
| 4.5 | По событиям | ||||
| ∞ | 1.2 | 1.4 | По событиям | ||
| ∞ | 0.7 | По событиям | |||
| ≤ 3 | 2.5 | 1.5 | По событиям | ||
| ≤ 2 | 1.5 | По событиям | |||
| 2.3 | 1.5 | По событиям | |||
| 2.4 | По событиям | ||||
| ∞ | 2.5 | 0.6 | По событиям | ||
| ∞ | 1.8 | 1.3 | По событиям | ||
| ≤ 4 | 1.8 | 1.4 | По событиям | ||
| ≤ 3 | 2.5 | 1.25 | По событиям | ||
| 2.4 | 1.5 | По событиям | |||
| 1.8 | 2.4 | По событиям | |||
| ∞ | 1.25 | 1.2 | По событиям | ||
| ∞ | 2.25 | 1.1 | По событиям |
ЗАДАНИЯ
к лабораторной работе №4 «Моделирование СМО»
Группа А4-
| № | Число каналов | Длина очереди | Интенсивность потока событий λ | Среднее время обслужи-вания 1/μ | Метод численного моделирования |
| ≤ 3 | 1.2 | 1.2 | Цепь Маркова | ||
| ≤ 2 | 1.8 | Цепь Маркова | |||
| 1.2 | Цепь Маркова | ||||
| 2.2 | Цепь Маркова | ||||
| ∞ | 2.5 | 0.6 | Цепь Маркова | ||
| ∞ | 1.8 | 1.25 | Цепь Маркова | ||
| ≤ 3 | 1.75 | 1.45 | Цепь Маркова | ||
| ≤ 2 | 2.3 | 1.4 | Цепь Маркова | ||
| 2.25 | 1.4 | Цепь Маркова | |||
| 1.6 | 3.2 | Цепь Маркова | |||
| ∞ | 1.25 | 1.25 | Цепь Маркова | ||
| ∞ | 2.5 | Цепь Маркова | |||
| ≤ 3 | 2.6 | 1.2 | Цепь Маркова | ||
| ≤ 2 | 1.25 | 3.2 | Цепь Маркова | ||
| 2.8 | 1.3 | Цепь Маркова | |||
| 2.8 | 2.25 | Цепь Маркова | |||
| ∞ | 2.8 | 0.6 | Цепь Маркова | ||
| ∞ | 1.5 | 1.1 | Цепь Маркова | ||
| ≤ 4 | 1.85 | 1.5 | Цепь Маркова | ||
| ≤ 3 | 2.6 | 1.35 | Цепь Маркова | ||
| 2.5 | 1.5 | Цепь Маркова | |||
| 1.85 | 2.5 | Цепь Маркова | |||
| ∞ | 1.5 | 1.1 | Цепь Маркова | ||
| ∞ | 2.5 | Цепь Маркова |
ЗАДАНИЯ
к лабораторной работе №3 «Моделирование СМО»
Группа А12-
| № | Число каналов | Длина очереди | Интенсивность потока событий λ | Среднее время обслужи-вания 1/μ | Метод численного моделирования |
| ≤ 3 | 2.25 | По событиям | |||
| ≤ 2 | 1.5 | 2.5 | По событиям | ||
| 3.2 | 1.1 | По событиям | |||
| 2.5 | 1.6 | По событиям | |||
| ∞ | 2.2 | 0.7 | По событиям | ||
| ∞ | 2.4 | 1.1 | По событиям | ||
| ≤ 3 | 1.25 | 1.8 | По событиям | ||
| ≤ 2 | 2.3 | 1.4 | По событиям | ||
| 2.5 | 1.25 | По событиям | |||
| 1.4 | По событиям | ||||
| ∞ | 1.25 | 1.1 | По событиям | ||
| ∞ | 2.6 | 0.8 | По событиям | ||
| ≤ 3 | 2.85 | 1.4 | По событиям | ||
| ≤ 2 | 1.85 | 2.3 | По событиям | ||
| 2.35 | 1.4 | По событиям | |||
| 2.2 | 1.8 | По событиям | |||
| ∞ | 2.85 | 0.5 | По событиям | ||
| ∞ | 1.85 | 1.3 | По событиям | ||
| ≤ 4 | 1.85 | 1.4 | По событиям | ||
| ≤ 3 | 2.55 | 1.5 | По событиям | ||
| 2.5 | 1.6 | По событиям | |||
| 1.9 | 2.3 | По событиям | |||
| ∞ | 1.45 | 1.1 | По событиям | ||
| ∞ | 2.05 | 1.2 | По событиям |
ЗАДАНИЯ
к лабораторной работе №4 «Моделирование СМО»
Группа А12-
| № | Число каналов | Длина очереди | Интенсивность потока событий λ | Среднее время обслужи-вания 1/μ | Метод численного моделирования |
| ≤ 3 | 1.25 | 1.25 | Цепь Маркова | ||
| ≤ 2 | 1.85 | Цепь Маркова | |||
| 3.5 | 1.05 | Цепь Маркова | |||
| 2.25 | Цепь Маркова | ||||
| ∞ | 2.55 | 0.6 | Цепь Маркова | ||
| ∞ | 1.7 | 1.5 | Цепь Маркова | ||
| ≤ 3 | 1.5 | 1.8 | Цепь Маркова | ||
| ≤ 2 | 2.5 | 1.5 | Цепь Маркова | ||
| 2.5 | 1.3 | Цепь Маркова | |||
| 1.8 | Цепь Маркова | ||||
| ∞ | 1.55 | 1.15 | Цепь Маркова | ||
| ∞ | 2.55 | 1.05 | Цепь Маркова | ||
| ≤ 3 | 2.65 | 1.2 | Цепь Маркова | ||
| ≤ 2 | 1.2 | 3.2 | Цепь Маркова | ||
| 2.5 | 1.5 | Цепь Маркова | |||
| 2.5 | 2.5 | Цепь Маркова | |||
| ∞ | 2.7 | 0.6 | Цепь Маркова | ||
| ∞ | 1.5 | 1.7 | Цепь Маркова | ||
| ≤ 4 | 1.8 | 1.5 | Цепь Маркова | ||
| ≤ 3 | 2.7 | 1.35 | Цепь Маркова | ||
| 2.6 | 1.5 | Цепь Маркова | |||
| 1.9 | 2.5 | Цепь Маркова | |||
| ∞ | 1.6 | 1.1 | Цепь Маркова | ||
| ∞ | 2.4 | 1.1 | Цепь Маркова |