Параметры и показатели систем массового обслуживания

Для описания СМО используются три группы параметров:

• 1) структурные;
• 2) нагрузочные;
• 3) функциональные (параметры управления).

К структурным параметрам относятся:

• • количество обслуживающих приборов п, равное единице для одноканальной СМО и п > 1 для многоканальной СМО;
• • количество т накопителей и емкости накопителей Epj = 1, m;
• • способ взаимосвязи накопителей с приборами (в случае многоканальных СМО), например в виде матрицы связей.

Нагрузочные параметры СМО включают в себя:

• • количество поступающих в систему классов заявок Н, которое равно единице для СМО с однородным потоком заявок и Н > 1 для СМО с неоднородным потоком;
• • закон распределения интервалов времени между поступающими в систему заявками класса i = 1, Н или по крайней мере первые два момента распределения, задаваемые, например, в виде интенсивности поступления заявок и коэффициента вариации v₍ интервалов;
• • закон распределения длительности обслуживания заявок класса i = 1,..., Н или как минимум первые два момента распределения, в качестве которых обычно используются средняя длительность Г,_обсл или интенсивность щ = 1 Д_{( обсл} обслуживания и коэффициент вариации v,. В компьютерных системах ИМ возможны любые варианты.

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

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

Для компактного описания систем массового обслуживания часто используются обозначения, предложенные Д. Кендаллом, в виде

где А и В задают законы распределений интервалов времени между моментами поступления входящего потока заявок в систему и длительности обслуживания заявок в приборе соответственно; С — число приборов обслуживания в системе: 1, 2, ..., °°; Q — число мест в накопителе: 0,1, 2,..., о°; К — число источников заявок в системе: 0, 1, 2,...,

Для задания законов распределений А и В используются следующие обозначения:

G (General) — поток общего вида (генеральное распределение), О < v <

М (Markovian) — экспоненциальное (показательное) распределение — простейший поток, v = 1;

D (Deterministik) — детерминированное распределение — регулярный поток, v = 0;

U (Uniform) — равномерное распределение;

Ек {Erlangian) — распределение Эрланга к-то порядка — поток Эрланга к-го порядка, v = 1 / Vfc;

hfc {hip о exponential) — гипоэкспоненциальное распределение к-го порядка (с к последовательными разными экспоненциальными фазами);

Hr {Hiperexponential) — гиперэкпоненциальное распределение порядка г (с г параллельными экспоненциальными фазами);

Р {Pareto) — распределение Парето и т.д.

Примеры:

• • М/М/1 /°о/1 — одноканальная СМО с накопителем неограниченной емкости, на вход которой поступает однородный (от одного источника) простейший поток заявок с экспоненциальной длительностью обслуживания заявок.
• • D/D/2/4/1 — двухканальная СМО с накопителем ограниченной емкости, равной четырем, на вход которой поступает однородный (от одного источника) детерминированный поток заявок, и регулярным обслуживанием заявок в приборе.
• • M/G/3/10/3 — трехканальная СМО с накопителем ограниченной емкости, равной 10, на вход которой от трех источников поступает однородный простейший поток, и длительностью обслуживания заявок, распределенной по закону общего вида. Обозначение G не означает, что данный параметр невозможно описать, а говорит о том, что данный поток может быть любым из известных законов либо он может определяться какой-нибудь другой функцией разработчика.
• • D/E2/7/0/1 — семиканальная СМО без накопителя (емкость накопителя равна нулю), в которую поступает однородный поток заявок с детерминированными интервалами времени между последовательными заявками (детерминированный поток), и длительностью обслуживания заявок в приборе, распределенной по закону Эрланга 2-го порядка.

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

СМО может работать в следующих режимах:

• • установившемся, или стационарном;
• • неустановившемся.

Часто в системах самого различного назначения протекают процессы, которые можно представить в виде марковской модели «гибели и размножения». Граф состояний такого процесса показан на рис. 2.9.

Рис. 2.9. Схема модели «гибели и размножения»

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

Своим названием модель «гибели и размножения» обязана биологической задаче об изменении численности популяции и распространении эпидемий: состояние популяции S_k означает наличие в популяции к единиц особей, переход вправо связан с размножением особей, а влево — с их гибелью.

Очевидно, стационарное состояние в этом процессе существует.

Но при исследовании сложных объектов интересуют следующие вопросы: возможен ли в исследуемой системе установившийся (стационарный) режим (т.е., как ведет себя система при t —> °°)? Существуют ли предельные значения вероятностей p(t) нахождения системы в ее состояниях?

Ответ на данные вопросы дает теорема А. А. Маркова (старшего): если для однородного дискретного марковского процесса с конечным или счетным числом состояний все вероятности p(t) > 0, то предельные значения существуют и их значения не зависят от выбранного начального состояния системы.

Применительно к непрерывным марковским процессам теорема Маркова трактуется так: если процесс однородный и из каждого состояния возможен переход за конечное время в любое другое состояние и число состояний счетное или конечное, то предельные значения p(t) существуют и их значения не зависят от выбранного начального состояния.

Например (рис. 2.10), в системе А стационарный режим есть, а в системе В стационарного режима нет: если система окажется в состоянии S₄, то она не перейдет ни в какое другое состояние.

Итак, режимы работы СМО — это установившийся, или стационарный, когда вероятности состояний системы не изменяются со временем, и неустановившийся, когда параметры системы изменяются со временем, что может быть обусловлено:

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

Рис. 2.10. Примеры графов состояний систем с различными режимами

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

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

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

Показатели СМО с однородным потоком заявок. Показатели систем со стохастическим характером функционирования являются случайными величинами и полностью описываются соответствующими законами распределений. На практике при моделировании часто ограничиваются определением только средних значений (математических ожиданий), реже — определением двух первых моментов этих показателей.

В зависимости от типа системы показателями эффективности системы массового обслуживания являются следующие.

Для СМО с отказами:

• • абсолютная пропускная способность — среднее число заявок, обслуженных системой за время моделирования Т;
• • относительная пропускная способность — средняя доля поступивших заявок, обслуживаемых системой (отношение среднего числа обслуженных заявок к среднему числу поступивших заявок за время Т);
• • средняя длина очереди заявок;
• • средняя время ожидания в очереди;
• • среднее число занятых каналов;
• • коэффициент занятости (использования) каналов;
• • коэффициент простоя каналов;
• • вероятность потерь заявок;
• • вероятность обслуживания заявки, т.е. вероятность того, что поступившая в систему заявка будет обслужена;
• • интенсивность потока потерянных (необслуженных) заявок из-за ограниченной емкости накопителя.

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

• • среднее время ожидания заявок в очереди;
• • среднее время пребывания заявок в системе, складывающееся из времени ожидания и времени обслуживания;
• • средняя длина очереди заявок;
• • среднее число свободных и занятых каналов;
• • коэффициенты простоя и использования каналов;
• • среднее число заявок в системе (в очереди и на обслуживании в приборе).

Показатели СМО с неоднородным потоком заявок. Для СМО

с неоднородным потоком заявок, в которую поступают Я классов заявок с интенсивностями X_l5 ..., Х_н и средними длительностями обслуживания С _обсл, t_2oбсл, ..., t_H обсл, определяются две группы показателей обслуживания заявок:

• 1) показатели по каждому классу (потоку) заявок;
• 2) показатели объединенного (суммарного) потока заявок.

Показатели по каждому классу заявок г = 1, ..., Я идентичны показателям СМО с однородным потоком.

Показатели объединенного (суммарного) потока заявок позволяют определить усредненные по всем классам заявок показатели эффективности функционирования СМО.

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

Показатели СеМО. Показатели СеМО делятся:

• • на узловые, характеризующие эффективность функционирования отдельных узлов СеМО;
• • сетевые, характеризующие функционирование СеМО в целом.

Состав узловых показателей СеМО такой же, как и приведенный

выше для СМО, поскольку отдельный узел — это СМО.

На основе узловых показателей рассчитываются сетевые показатели СеМО:

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

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

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

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

Пример 2.2

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

Описание состояний СМО:

S₀, S_v ..., S₄— состояния исправной СМО;

Sq, Sj',..., S₄ — состояния неисправной СМО.

Обозначения:

А. — интенсивность поступления заявок;

р — интенсивность обработки заявки каналом;

v — интенсивность поломок канала;

г) — интенсивность ремонта неисправного канала.

Граф состояний СМО с конечной надежностью каналов обслуживания приведен на рис. 2.11.

Рис. 2.11. Граф состояний СМО с конечной надежностью

Если в состоянии S₀ (канал свободен, в очереди заявок нет) система выйти из строя не может, то состояния Sq нет. Так как при отказе заявка, находившаяся на обслуживании, теряется, то после восстановления переход осуществляется к предыдущему состоянию, например из состояния S3 в состояние S₂. Если принять условие, что заявка не теряется, то осуществляется переход из S3 в S₃.

Приведенная в примере модель не является моделью «гибели и размножения». Поэтому соответствующие показатели находятся составлением и решением системы линейных алгебраических уравнений, полученных из уравнений Колмогорова¹ для стационарного режима.

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

Другие показатели также определяются встроенными средствами, например длина очереди (средняя, минимальная, максимальная), время обслуживания (минимальное, среднее, максимальное), гистограмма распределения вероятностей какого-либо показателя, функция и плотность распределения. Система моделирования GPSS World имеет свыше 50 такого рода системных числовых атрибутов. Системы GPSS World и AnyLogic имеют также около 30 встроенных генераторов случайных чисел. Их наличие вместе с другими инструментальными средствами существенно повышает эффективность разработки и эксплуатации компьютерных имитационных моделей.