Дисциплина обслуживания.

Наиболее простой и хорошо известной является дисциплина обслуживания “ первый пришел – первый обслужен ”, при которой заявки обслуживаются полностью без прерываний в порядке их поступления, причем заявка, поступившая в момент простоя обслуживающего устройства, сразу же начинает обслуживаться. Легко представить себе ситуацию, когда эта дисциплина нежелательна. Например, часто бывает, что одни заявки важнее других и заслуживают предпочтительного обслуживания. Разделение заявок на группы по степени их важности осуществляется с помощью приоритетных дисциплин обслуживания, и соответствующая система массового обслуживания называется системой с приоритетами. Правило назначения приоритетов определяет порядок, в котором будут обслуживаться ожидающие заявки. Приоритетные дисциплины обслуживания бывают двух типов: с абсолютными приоритетами и с относительными приоритетами. Если обслуживание текущей заявки прерывается при появлении заявки с более высоким приоритетом и последняя немедленно начинает обслуживаться, то говорят, что имеет место дисциплина обслуживания с абсолютными приоритетами. Если прерывание обслуживания не допускается, то имеет место дисциплина с относительными приоритетами.

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

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

Экспоненциальное распределение. Это распределение является самым простым с точки зрения получения аналитических результатов. Его функция распределения с параметром

и плотность

Среднее и дисперсия экспоненциального распределения равны соответственно и . Отсюда квадратичный коэффициент вариации экспоненциального распределения

.

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

Гамма-распределение и распределение Эрланга. В приложениях часто наблюдаются унимодальные распределения (т.е. распределения с одним максимумом) с квадратичным коэффициентом вариации, существенно отличным от единицы. В таких обстоятельствах наблюдаемое распределение можно попытаться аппроксимировать гамма-распределением с плотностью

(2)

где и – положительные постоянные, а – гамма-функция:

.

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

(3)

и

(4)

При гамма-распределение превращается в экспоненциальное распределение с параметром . При положительном и целом гамма-функция . Если положить среднее , то и в этом случае плотность (2) превратится в

.

Соответствующая этой плотности функция распределения имеет вид

.

Полученное распределение называется нормированным распределение Эрланга k -го порядка. Преобразование Лапласа от распределения Эрланга k -го порядка

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

Иногда распределение Эрланга называют гипоэкспоненциальным, в отличие от гиперэкспоненциального распределения, к определению которого мы переходим.

Обобщенный закон Эрланга n -го порядка имеет плотность распределения вероятностей

.

Гиперэкспоненциальное распределение. Пусть имеется k типов заявок, заявка i -го типа появляется с вероятностью и длительность обслуживания заявки i -го типа имеет экспоненциальное распределение со средним . Тогда общее распределение длительности обслуживания представляет собой смесь экспоненциальных распределений:

,

с плотностью .

Полученное распределение называют гиперэкспоненциальным распределением k- го порядка. Его среднее и дисперсия равны соответственно

и

.

Отсюда квадратичный коэффициент вариации

,

где равенство имеет место тогда и только тогда, когда для всех i.

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

Преобразование Лапласа от гиперэкспоненциального распределения

.

Краткие обозначения. Для определения типа системы массового обслуживания часто используются обозначения вида , где символы A и B обозначают входящий поток и распределение длительности обслуживания соответственно, а l – число параллельных устройств обслуживания в СМО. Чтобы отличить СМО, в которой нет ограничений на допустимое число заявок, от СМО, в которой не может находиться более m заявок, для последней используются обозначения вида . Приведем некоторые из общепринятых обозначений для часто используемых распределений:

– экспоненциальное распределение, которое приводит к “марковскому” свойству СМО;

– обозначает вырожденное распределение (deterministic), при котором интервалы между моментами поступления или моментами начала и завершения обслуживания заявок являются постоянными;

– распределение Эрланга (Erlang) k -го порядка;

– гиперэкспоненциальное (hyperexponetial) распределение k -го порядка;

– произвольное (general) распределение;

– рекуррентный входящий поток (general independent).

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

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

.

Если величины, стоящие в числителе и знаменателе этого отношения, равны соответственно и , то .

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

С нагрузкой тесно связан другой показатель качества – коэффициент использования, или коэффициент загрузки обслуживающего устройства. Этот показатель качества, обозначаемый через , определяется как доля времени, в течение которого обслуживающее устройство занято. Рассмотрим достаточно длительный интервал времени T. В СМО с l обслуживающими устройствами на каждое из них в среднем за время T придется по заявок в предположении, что поток заявок равномерно распределяется по l устройствам. Поскольку каждая заявка требует в среднем длительности обслуживания , то общее среднее время занятости обслуживающего устройства составит (сюда включены и простои обслуживающего устройства). Поделив эту величину на T, получим . Поскольку обслуживающее устройство не может быть занято более 100 % времени, то коэффициент использования не может превосходить единицу. Таким образом, получаем следующее выражение для коэффициента использования СМО с l обслуживающими устройствами:

.

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

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

.

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

С точки зрения заявки самым важным показателем качества, по-видимому, является время, которое она проводит в ожидании обслуживания. Определим время ожидания заявки j,равным отрезку времени от начала поступления заявки j в систему до начала ее обслуживания, а время ответа – равным отрезку времени от момента поступления заявки j в систему до момента завершения ее обслуживания. Таким образом, имеем следующее простое соотношение (индекс j опущен):

Время ответа (T) = время ожидания (W) + длительность обслуживания (S).

Для оценки качества СМО обычно применяются средние значения случайных величин и в установившемся (стационарном) режиме, когда . Эти средние уже не зависят от j, и мы будем обозначать их символами и соответственно.

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

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

.

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

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

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

,

где – нагрузка, или коэффициент использования обслуживающего устройства. Как следует из (5), в установившемся режиме .

Процесс передачи заявок в системе с одним обслуживающим устройством проиллюстрирован на рисунке.

Дата добавления: 2015-07-26