- •Общие вопросы моделирования. Понятие модели. Классификация моделей. Модели физические, абстрактные, смешанные.
- •Виды моделей. Способ реализации моделирования и степень отражения в моделях времени и неопределенности.
- •Объект моделирования – вычислительная система. Основные задачи исследования объекта, их характеристика и методы решения.
- •Графовые модели алгоритмов и программ. Построение графовых моделей.
- •Эквивалентные преобразования графовых моделей алгоритмов и программ.
- •Марковские случайные процессы и их место при построении и исследовании вероятностных моделей объектов.
- •Дискретные марковские цепи. Основные задачи их исследования. Примеры объектов, для исследования которых могут быть использованы дмц.
- •Потоки событий. Основные понятия и определения. Простейший поток событий и потоки Эрланга.
- •Непрерывные марковские цепи. Основные задачи их исследования. Примеры объектов, для исследования которых могут быть использованы дмц.
- •Типовые графы состояний системы. Процесс “гибели и размножения”. Примеры объектных систем.
- •Типовые графы состояний системы. Циклический процесс. Примеры объектных систем.
- •Методы исследования немарковских случайных процессов, сводящихся к марковским.
- •Теория массового обслуживания и ее место при построении и исследовании вероятностных моделей объектов. Основные понятия и определения.
- •Системы массового обслуживания (смо). Обобщенная структура смо.
- •Основные параметры и характеристики смо.
- •Разомкнутые смо с очередью и нетерпеливыми заявками. Примеры объектных систем.
- •Разомкнутые смо с очередью и терпеливыми заявками. Примеры объектных систем.
- •Разомкнутые смо без потерь. Примеры объектных систем.
- •Замкнутые смо с простейшими потоками событий. Примеры объектных систем.
- •Смо с произвольными потоками событий. Случай бесприоритетной дисциплины обслуживания.
- •Смо с произвольными потоками событий. Случай дисциплины обслуживания с относительным приоритетом.
- •Смо с произвольными потоками событий. Случай дисциплины обслуживания с абсолютным приоритетом.
- •Сети массового обслуживания с простейшими потоками событий. Анализ разомкнутой сети. Примеры объектных систем.
- •Сети массового обслуживания с простейшими потоками событий. Анализ замкнутой сети. Примеры объектных систем.
- •Статистическое моделирование случайных процессов. Организация статистического моделирования. Моделирование базовых случайных величин (св).
- •Моделирование непрерывной случайной величины с произвольным распределением. Моделирование дискретной св. Моделирование случайных событий и потоков случайных событий.
-
Системы массового обслуживания (смо). Обобщенная структура смо.
На вход поступают заявки на обслуживание (однородные и неоднородные). Первопричина заявок – источник заявок. В зависимости от его характера СМО бывают разомкнутыми и замкнутыми. Для разомкнутых СМО источник заявок располагается вне системы, количество заявок считается неограниченным, а поведение источника заявок никак не связано с состоянием системы. Для замкнутых источник заявок – сама система, количество заявок ограничено и связано с состоянием самой системы.
Поступающие заявки обслуживаются каналами обслуживания, которые могут быть однотипными или разнотипными, универсальными или специализированными.
Каждый канал обслуживания может обслуживать в данный момент времени только одну заявку. Количество каналов: 1..m.
В зависимости от дисциплин ожидания и обслуживания (Д1 и Д2) различают СМО с бесприоритетными и приоритетными дисциплинами. В СМО с бесприоритетными дисциплинами все заявки считаются равноправными, а в СМО с приоритетными заявками некоторые типы заявок имеют более высокий приоритет. В таких СМО каналы могут прерывать обслуживание, если появляется требование обслуживания заявки с большим приоритетом.
Если хотя бы один канал свободен, то заявка немедленно поступает на обслуживание. Если все каналы заняты – может образовываться очередь заявок. Очередь может быть общая и раздельная. Длина очереди может быть ограниченной (практика) и неограниченной (в теории).
Заявки могут быть терпеливыми и нетерпеливыми. Терпеливая заявка, попав в СМО, непременно дождется конца обслуживания. Нетерпеливая заявки может организовать уход. Уходы могут случаться как в из очереди, так и из канала обслуживания.
Существуют СМО с отказами и без отказов. В СМО с отказами если очередь ограничена и заявки равноценны – то заявка может получить отказ.
Если у заявок разная степень важности, и приходит более важная заявка, то менее важная выталкивается.
СМО делятся на:
-
“чистые” СМО = без потерь.
-
Все заявки – терпеливые => нет уходов.
-
Неограниченная очередь => нет отказов.
-
Все заявки однородные => нет выталкивания.
-
СМО с потерями.
-
Основные параметры и характеристики смо.
Для описания СМО используется 5-элементный кодификатор – обозначение СМО:
A, B – тип распределения временных интервалов между соседними событиями соответственно во входящем потоке A и в потоке обслуживания одного канала B.
m – число каналов обслуживания в системе (ограничение – каналы должны быть однотипными и универсальными, иначе стандартным кодификатором их не описать).
n – число мест в очереди (ограничение – очередь обязательно должна быть общей).
N – количество источников заявок.
m = ∞ => бесконечное число каналов обслуживания, очереди в системе быть не может.
n = ∞ => очередь бесконечна, система без отказов.
N = ∞ => возможно, если система разомкнута.
Параметры (первичные свойства) СМО.
-
Параметры входящего потока.
-
A – тип распределения временных интервалов между соседними событиями входящего потока.
-
A = {M, Ek, D, G}
M – экспоненциальное (показательное) распределение – одно из наиболее популярных.
Ek – распределение Эрланга k-того порядка.
D – детерминированный (регулярный) поток.
G – поток произвольного типа.
Простейший поток задает “верхний предел” возможного поведения (неупорядоченности).
-
– суммарная интенсивность входящего потока. Q источников заявок, каждый генерирует заявки с интенсивностью.
-
Допустимое время пребывания заявки в системе. νож, νоб – интенсивность потока уходов нетерпеливых заявок (в состоянии ожидания и из каналов обслуживания).
-
Параметры системы обслуживания.
-
m – число каналов обслуживания.
-
B = {M, Ek, D, G} – тип распределения временных интервалов между соседними событиями в потоке обслуживания одного канала.
-
tоб – СВ, время обслуживания одной заявки одним каналом. Если тип распределения M, то интенсивность потока обслуживания заявки одним каналом .
-
n – число мест в очереди (~ объем памяти). Если очередь раздельная => n1… nk.
-
Д1 – дисциплина ожидания – выборка заявок из входящего потока и распределение их по очередям.
-
Д2 – дисциплина обслуживания – выборка заявок из очереди и назначение в каналы.
-
Дисциплины могут быть бесприоритетными и приоритетными.
В случае бесприоритетной дисциплины заявки размещаются в очереди в порядке поступления. Последняя поступившая заявка занимает последнее место. Если нет места в очереди – в любом случае получает отказ.
В случае приоритетной дисциплины может происходить выталкивание, то есть свежая заявка с более высоким приоритетом может вытолкнуть самую старую.
К бесприоритетным дисциплинам обслуживания относят очередь, стек, случайный выбор.
К приоритетным – обслуживание с относительным, абсолютным или смешанным приоритетом.
Характеристики (производные свойства от параметров).
Любая характеристика отображает лишь потенциальную возможность системы.
-
– суммарная интенсивность потока обслуженных заявок (абсолютная пропускная способность).
-
– суммарная интенсивность потока потерянных (необслуженных) заявок.
-
– вероятность обслуживания заявок (относительная пропускная способность).
-
– вероятность заявки быть потерянной
-
– среднее время ожидания обслуживания (время пребывания заявки в очереди):
– первоначальное ожидание (до попадания в канал обслуживания).
– ожидание в прерванном состоянии.
-
– среднее время пребывания заявки в системе от появления во входном потоке до появления в выходном потоке (обратная величина к производительности):
-
– средняя длина очереди (число мест в очереди). Если система разомкнута и без потерь, то:
-
– среднее число занятых каналов обслуживания. Ψ – коэффициент загрузки каналов,
-
– среднее число заявок в системе. Если система разомкнута и без потерь, то
Существует интегральный (комплексный) параметр (аддитивная свертка):
H – число значимых для исследования характеристик.
– частные показатели.
– весовой коэффициент.
Если частные параметры имеют одну размерность и одно начало отсчета – можно использовать аддитивную свертку, иначе – нет. В нашем случае эти условия выполняются не всегда, поэтому надо:
-
Нормировать
-
Поменять суть весовых коэффициентов – не обязательно . приобретает суть штрафа, определяется экспертами.
Если увеличению эффективности соответствует возрастание Е – показатель называется прямым, иначе – обратным.