Дисциплина обслуживания
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ
ФЕДЕРАЦИИ
____________________________
МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
В.Н. Балашов, А.Г. Гольцов
МОДЕЛИРОВАНИЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ
Рекомендации к лабораторным занятиям
по курсу "Моделирование
для студентов, обучающихся по направлению
"Информатика и вычислительная техника"
ДЛЯ ГРУПП А4-11 и А12-11
Москва Издательство МЭИ 2013
УДК
621.398
П692
УДК:681.3
Утверждено учебным управлением МЭИ
Подготовлено на кафедре вычислительных машин, систем и сетей.
Балашов В.Н., Гольцов А.Г.
Моделирование генераторов случайных чисел
Рекомендации к лабораторным занятиям. Методическое пособие по курсу "Моделирование" / Под ред. ______________ – М.: Изд-во МЭИ, 2009, 40с.
Представлены описание лабораторной работы, выполняемой на ПЭВМ типа IBM PC , по имитационному моделированию систем массового обслуживания (СМО). Лабораторная работа включает теоретический материал, рекомендации и индивидуальные задания, в соответствии с которыми проводится аналитический расчет основных характеристик СМО, а затем проводится компьютерное имитационное моделирование тог же варианта СМО с последующим сравнением результатов.
Предназначен студентам специальности 22.01 "Вычислительные машины, комплексы, системы и сети", изучающим курс "Моделирование".
Работа выполняется по индивидуальным заданиям. Продолжительность лабораторного занятия – 4 часа.
___________________________
© Московский энергетический институт, 2009
АНАЛИТИЧЕСКИЕ МЕТОДЫ МОДЕЛИРОВАНИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ.
Структура СМО
Рассмотрим в качестве примера структуру многоканальной СМО с очередью:
Каналы обслуживания
X Очередь Y
…
Рис. 1. Структура многоканальной СМО с очередью
СМО содержит несколько каналов обслуживания, соединенных по входам параллельно. Между входом СМО X и каналами обслуживания помещен блок "очередь", в который помещаются заявки, если все каналы обслуживания заняты.
Поток заявок. Поток заявок X, поступающий на вход реальной СМО, определяется конкретной ситуацией и в принципе неуправляем. При построении математической модели СМО необходимо построить и модель потока заявок. В качестве модели потока заявок принимается случайный процесс (последовательность случайных величин с заданным распределением), определяющий случайные моменты времени поступления заявок.
Каналы обслуживания. Заявки поступают на входы свободных каналов обслуживания. Каждая заявка обслуживается в одном канале определенное время, называемое временем обслуживания. СМО может включать один канал обслуживания (одноканальная СМО) или несколько каналов (многоканальная СМО).
Поток обслуживания. Время обслуживания каждой заявки определяется потоком обслуживания, который с математической точки зрения аналогичен потоку заявок.
Очередь. В структуру СМО может входить блок "очередь". Очередь характеризуется числом мест ожидания для заявок. В модели СМО в очереди запоминаются моменты времени поступления заявки. Очередь может быть конечной, тогда в случае переполнения заявки теряются (СМО с потерями) или бесконечной. Существуют СМО без очереди.
Структура СМО обычно характеризуется последовательностью из четырех символов {А, В, n, m}, где А и В - соответственно поток заявок и поток обслуживания, n и m - соответственно число каналов и число мест в очереди.
Состояния. Математическая модель СМО отличается от схемы, представленной на рис. 3.1. Модель СМО имеет конечное число дискретных состояний S0, S1, …, Sn+m .
Состояние S0 означает, что в системе нет заявок. Состояние S1 означает, что в системе обслуживается одна заявка, очередь пуста. Состояние Sn - обслуживается n заявок, очередь пуста. Состояние S n+1, - обслуживается n заявок и в очереди одна заявка. Состояние Sn+m, - обслуживается n заявок и в очереди m заявок. Система полностью заполнена заявками, поэтому очередная заявка будет отброшена.
Состояния S0, S1, …, Sn+m являются дискретной случайной величиной. Каждому состоянию Si соответствует вероятность пребывания в этом состоянии Pi.
Замечание. Модели СМО соответствует математическая модель - Марковский процесс с непрерывным временем.
Дисциплина обслуживания
В СМО с очередью существуют различные дисциплины обслуживания (порядок обслуживания) заявок, поступивших на вход:
Обслуживание в порядке поступления заявок (FIFO, First In First Out),
Обслуживание в порядке, обратном порядку поступления заявок (LIFO, Last In First Out).
Обслуживание по приоритетам. Каждой заявке в очереди заранее присваивается приоритет (определенное число). Первой обслуживается заявка из очереди, имеющая максимальный приоритет. Приоритет бывает абсолютным или относительным. Если в очередь СМО с абсолютным приоритетом поступает заявка с приоритетом, превышающим приоритет обслуживаемой заявки, то обслуживание прекращается и начинается обслуживание поступившей заявки. Если в очередь СМО с относительным приоритетом поступает заявка с приоритетом, превышающим приоритет обслуживаемой заявки, то обслуживание поступившей заявки начинается после окончания обслуживания текущей заявки.
Случайный порядок обслуживания. Выбирается случайным образом одна из заявок в очереди.
Обслуживание в первую очередь заявок с минимальным временем обслуживания. Это очень эффективная дисциплина обслуживания, позволяющая минимизировать среднее время пребывания заявок в системе. Однако в большинстве практических случаев время обслуживания заранее не известно.
Характеристики СМО
В процессе моделирования необходимо определить количественные характеристики СМО, позволяющие оценить их работу. Поток заявок и поток обслуживания в модели СМО - последовательности случайных величин. Поэтому для определения характеристик СМО применяют методы теории вероятностей и математической статистики.
Обычно представляют интерес следующие характеристики СМО:
Pотк - вероятность потери заявки из-за занятости очереди (вероятность отказа),
А - пропускная способность - среднее количество обслуженных заявок в единицу времени,
kср - среднее количество занятых каналов обслуживания,
rср - средняя длина очереди
tож - среднее время ожидания заявкой обслуживания в очереди.