Основные характеристики систем массового обслуживания.

СМО – любая система, в которой существуют заявки и элементы обслуживания этих заявок. Такие элементы называются каналами обслуживания. Например, телефонные станции, билетные кассы, магазины.

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

 

СМО широко распространены в технике и быту. Любая система обслуживания, где может накапливаться очередь, относится к СМО. Примерами СМО могут служить телефонные станции, ремонтные мастерские, парикмахерские, поликлиники, магазины, справочные бюро, билетные кассы. Основные компоненты СМО и их параметры изображены на нижнем рисунке.

 

Заявки.

Характеризуются моментом поступления, именем, временем обслуживания, приоритетом.

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

 

 

 

Красные заявки отбрасываются (могут откладываться в буфер) т.к. канал занят.

Закон распределения интервалов между заявками: j(t), где T – интервал между заявками.

j(T)

 

T

 

Интенсивность – кол-во заявок поступающих в единицу времени

Стационарность – постоянство характеристик закона распределения интервалов между заявками.

Последействие – его отсутствие означает, что предыдущие заявки не влияют на последующие.

Ординарность потока заявок – заявки появляются не группами, а по одной.

Поток заявок называется простейшим, если он обладает 3мя свойствами:

1) Стационарен

2) Ординарен

3) Не имеет последействия

 

Очереди.

Случайный характер моментов поступления заявок и времен их обслуживания приводит к неравномерной загрузке СМО – СМО то простаивает, то перегружена. Если она перегружена, то заявки образуют очередь. Основными характеристиками очереди являются:

- имя очереди;

- длина очереди - количество содержащихся в ней заявок (текущая; максимально допустимая и др.);

- приоритет очереди;

- статистика очереди.

1. Имя, длина и приоритет очереди. Понятия имени и длины очереди очевидны. В СМО может существовать несколько очередей к одному и тому же каналу. Например, разные очереди могут порождаться заявками, идущими от разных источников. В этом случае очередям может присваиваться разный приоритет, определяющий очерёдность обслуживания очередей. В то же время внутри одной и той же очереди могут существовать заявки, имеющие разный приоритет.

2. Статистика очереди. Под статистикой очереди понимаются её статистические характеристики, накапливающиеся во время работы СМО. Например, статистика может включать среднюю длину очереди, максимальную и минимальную длину очереди, средний разброс длины очереди, гистограмму длины очереди, под которой понимается эмпирически построенная зависимость количества очередей N заданной длины Li от значения Li.

Заметим, что следует отличать организацию очереди в СМО от возможности её наблюдения, если она возникает. Для организации очереди необходимо, как минимум, задать имя очереди и её приоритет. Для наблюдения достаточно воспользоваться стандартными средствами языка моделирования СМО, определяющими место возможного появления очереди и те её характеристики, которые хотелось бы наблюдать в процессе работы СМО.

 

Каналы обслуживания заявок.

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

1. Пропускная способность – это максимальное количество заявок, которое может обслужить канал за единицу времени. Пропускная способность зависит, с одной стороны, от времени, затребованным заявкой на своё обслуживание, например, временем, заказанным одним абонентом для телефонного разговора. С другой стороны, пропускная способность зависит от быстродействия самого канала. Например, пусть покупатель сделал в магазине N покупок, подошёл к кассе и стал предъявлять покупки кассиру, затрачивая на предъявление каждой покупки время Тп. Пусть кассир тратит на обслуживание одной покупки время Тк (время просмотра стоимости покупки и пробивки чека). Будем считать обслуживание кассиром каждого покупателя обслуживанием одной заявки. Тогда время обслуживания заявки равно Тз = N(Тп +Тк), а пропускная способность канала (кассира) Пк, то есть наибольшее число покупателей, которое может обслужить кассир за единицу времени, равна Пк = 1/Nмакс(Тп+Тк) и зависит как от характера заявки (числа покупок), так и от быстродействия канала (скорости работы кассира). Если пропускная способность канала меньше интенсивности потока заявок, то образуется очередь. Например, если канал может обслужить самое большее 10 заявок в минуту, а интенсивность потока заявок составляет 11 заявок в минуту, то неизбежно появление очереди.

 

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

 

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

 

Время задержки – среднее время обслуживания одной заявки.

 

Общие характеристики СМО.

К общим характеристикам СМО относятся принцип обслуживания заявок, дисциплины обслуживания заявок, число каналов и порядок их занятия.

1. Принцип обслуживания заявок. В общем случае, СМО – совокупность независимых m каналов, одновременно обслуживающих n заявок. Если все каналы заняты, то заявка ожидает обслуживания. В зависимости от времени ожидания обслуживания заявок t_{ожидания}, СМО подразделяют на три класса:

1. Системы с отказами.

t_{ожидание} = 0.

В такой системе, если все каналы заняты обслуживанием заявок, то поступившая новая заявка получает отказ в обслуживании и пропадает. Вероятность отказа или среднее число отказов за определенное время является показателем качества работы СМО.

2. Системы с ожиданием.

t_{ожидания}®¥, отказов нет.

Показателями качества работы СМО являются:

- среднее время ожидания обслуживания заявки;

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

3. Смешанные системы.

t_{ожидания} = const ¹ 0.

Заявка ждет обслуживания определенное время; если время вышло, то заявка получает отказ в обслуживании и пропадает. Основными показателями качества работы такой системы являются вероятность отказа и среднее время ожидания обслуживания заявки.

Представляют интерес так же такие характеристики СМО, как время занятости канала (время обслуживания одной заявки в одном канале) и время ожидания обслуживания заявки.

2. Дисциплины обслуживания заявок. Дисциплиной обслуживания заявок называется способ их обслуживания. Если все заявки имеют одинаковый приоритет, то дисциплина называется бесприоритетной.

Наиболее часто используется бесприоритетная дисциплина типа «первым пришел – первым обслужили» (FIFO). В этом случае, если заявки образуют очередь, то обслуживание заявок начинается с начала очереди. Второй распространенный тип – «последним пришел – первым обслужили» (LIFO). В этом случае, если заявки образуют очередь, то обслуживание заявок начинается с конца очереди.

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

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

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

3. Число каналов и порядок их занятия. Вопрос о числе каналов, необходимых для безотказного обслуживания заявок, является одним из главных при проектировании СМО. При малом числе каналов велика вероятность отказов, а при большом велики расходы на создание и функционирование СМО.

Каналы СМО при поступлении заявок можно занимать по разным правилам. Например, это может быть занятие в порядке возрастания номеров каналов, занятие в порядке заданной очереди (каналов), занятие в случайном порядке согласно заданным вероятностям; занятие по мере освобождения каналов.

 

Примеры практических СМО

 

Рассмотрим некоторые практические примеры СМО.

2.1. Одноканальная СМО.

 

 

Аn

А2

 

 

 

Здесь А1…Аn – пользовательские терминалы. От каждого терминала могут поступать задачи для решения на процессоре. Для решения каждой задачи выделяется квант времени Dt (время на обслуживания заявки от терминала). Время предоставляется поочередно каждой заявке. Если в течение времени Dt задача оказалась решенной, то по каналу 1 сведения о решении поступают на терминал. Если задача не решена за время Dt, то по каналу 2 она возвращается на вход процессора и становится в конец очереди.

Чтобы смоделировать такую систему, нужно построить ее имитационную модель. В имитационной модели могут появляться элементы, которых нет физически в реальном объекте. В данном случае таким элементом будет очередь заявок. Модель СМО примет следующий вид:

 

 

Процессор

Регистрация решений

Генератор потока заявок

 

Рассмотрим графическую иллюстрацию работы такой модели.

Т1 Т2 Т3 Т4

время

 

время

 

 

время

 

 

На первой диаграмме показаны заявки со случайными интервалами времени между ними, на третьей – интервалы времени, необходимые для обслуживания каждой заявки,

на второй – обслуженные и не обслуженнные заявки. Обозначение означает, что заявка не обслуживается. Как видим, не все заявки обслуживаются. Пока обрабатывается одна, другие, поступившие за это время, пропадают. В данном примере поступило 13 заявок, будет обработано только 5 из них. Получаем следующие вероятности Р отказа и безотказной работы:

Рбезотк.раб. = 5/13 Ротказа = 8/13.

Если бы не было отказов, то была бы очередь. В случае неограниченной очереди все заявки будут обслужены.