Модели систем массового обслуживания. Классификация систем массового обслуживания (стр. 2 из 2)
Раскрывая скобки и проводя деление на Δt, получим:
В пределе получается система дифференциально-разностных уравнений, решение которой будут играть важную роль для практических задач.
В соответствие этой системе уравнений можно поставить наглядную диаграмму интенсивностей переходов, которая аналогична диаграмме переходов для дискретных цепей Маркова (Рис. 2)
Рис. 2 Диаграмма интенсивностей переходов для процесса размножения и гибели.
Овалам здесь соответствуют дискретные состояния, а стрелки определяют интенсивности потоков вероятности (а не вероятности!) переходов от одного состояния к другому.
Имеет место своеобразный «закон сохранения»:
Разность между суммой интенсивностей, с которой система попадает в состояние k и суммой интенсивностей, с которой система покидает это состояние должна равняться интенсивности изменения потока в это состояние (производной по времени).
Применение закона сохранения позволяет получать уравнения для любой подсистемы Марковской цепи типа процесса «гибели-размножения». Особенно эффективным оказывается построение решений в стационарном, установившемся режиме, когда можно полагать что вероятности в произвольный, достаточно отдаленный момент времени, остаются постоянными.
Приравнивая производную по времени нулю, получаем систему разностных уравнений
Полагая, что интенсивности λ-1 =λ-2 = λ-3 =…0; μ0 = μ-1 = μ-2 = μ-3 =…=0, второе уравнение выписывать отдельно далее не потребуется. Итак, стационарный режим в цепи Маркова будет описываться системой разностных уравнений и условием нормировки для вероятностей
Нетрудно видеть, что эти уравнения легко выводятся из закона сохранения интенсивностей вероятностей. В стационарном режиме разность потоков равна нулю и полученные выше уравнения приобретают смысл уравнений равновесия или баланса, как их и называют.
.Интенсивность потока вероятностей в состояние k равна интенсивности потока из этого состояния.
Решать уравнение баланса можно, сначала определив при k =0 значение
.Затем, построив систему уравнений для k =1, можно получить
.Далее получаем
Из условия нормировки:
.Система, описываемая полученными выше выражениями, будет иметь стационарные вероятности состояний, когда она эргодическая. Это условие может быть выражено через соотношение интенсивностей. Необходимо и достаточно, чтобы существовало некоторое значение k , начиная с которого выполнялось неравенство
.Для большинства реальных систем массового обслуживания это неравенство выполняется.
Классификация систем массового обслуживания.
Используется трех -, четырех -, шести – компонентное символическое обозначение системы массового обслуживания, предложенное Кендаллом (Candall) и развитое в работах Г.П.Барашина.
a/b/c :d/e/f
a – распределение поступающего потока запросов.
b – закон распределения времени обслуживания.
Типовые условные обозначения:
М – экспоненциальное (Марковское) распределение,
D – детерминированное распределение,
Ek – эрланговское распределение k-го порядка,
HMk – гиперэкспоненциальное,
HEk – гиперэрланговское распределение порядка k,
GI – произвольное распределение независимых промежутков между заявками,
G – произвольное распределение длительностей обслуживания.
c – структура системы обслуживания (обычно число серверов).
d – дисциплина обслуживания (параметры после двоеточия иногда опускают).
Обычно используется сокращенное символическое обозначение, например FF вместо FIFO, LF, PR и т.п.
e – максимальное число запросов, воспринимаемое системой, может употребляться символ ¥.
f – максимальное число запросов к системе обслуживания.
В некоторых публикациях последними символами отражают качественные характеристики системы обслуживания. Некоторые общие результаты и основы математического аппарата, необходимого для анализа можно получить, рассматривая системы G/G/m.
Формула Литтла (Little).
Рассмотрим временную диаграмму работы системы массового обслуживания (рис. 3), отразив на ней последовательность поступления требований, помещение требований в очередь и обработки серверами системы.
Временная диаграмма работы системы массового обслуживания.
В общем случае ясно, что с увеличением числа требований растет время ожидания. Установим соотношение между средним числом требований в системе, интенсивностью потока и среднего времени пребывания в системе. Обозначим число поступающих в промежутке времени (0 , t) требований как функцию времени α(t).
Число исходящих из системы заявок (обслуженных) на этом интервале обозначим δ(t). На рисунке 4 показаны примеры функциональных зависимостей этих двух случайных процессов от времени.
Рис. 4 Зависимость между средним числом требований в системе, интенсивностью потока и средним времени пребывания в системе.
Число требований, находящихся в системе в момент t будет равно:
.Площадь между двумя рассматриваемыми кривыми от 0 до t - дает общее время, проведенное всеми заявками в системе за время t.
Обозначим эту накопленную величину γ(t) . Если интенсивность входного потока равна λ, а средняя интенсивность за время t:
,то время, проведенное одной заявкой в системе, усредненное по всем заявкам будет равно: 
.Наконец, определим среднее число требований в системе в промежутке (0,t):
.Из последних трех уравнений следует, что:
, (где 
).Если в СМО существует стационарный режим, то при t→ ∞ , будут иметь место соотношения:
Последнее соотношение означает, что среднее число заявок в системе равно произведению интенсивности поступления требований в систему на среднее время пребывания в системе. При этом не накладывается никаких ограничений на распределения входного потока и времени обслуживания. Впервые доказательство этого факта дал Дж.Литтл и это соотношение носит название формула Литтла.
Интересно, что в качестве СМО можно рассмотреть только очередь из заявок в буфере. Тогда формула Литтла приобретает иной смысл - средняя длина очереди равна произведению интенсивности входного потока заявок на среднее время ожидания в очереди:
.Если наоборот рассматривать СМО только как серверы, то формула Литтла дает:
,где
– среднее число заявок в серверах, а 
– среднее время обработки в сервере.В любом случае:
.Одним из основных параметров, которые используются при описании СМО, является коэффициент использования (utilizationfactor). Это фундаментальный параметр, так как он определяется как отношение интенсивности входного потока к пропускной способности системы. Поскольку пропускная способность СМО содержащей m серверов может быть определена как:
, то коэффициент использования может быть определен как: 
.Нетрудно видеть, что коэффициент использования равен в точности интенсивности нагрузки, если СМО с одним сервером и в m раз меньше для систем с m серверами. Величина коэффициента использования равна среднему значению от доли занятых серверов и
.Если в СМО типа G/G/1 существует стационарный режим и можно определить вероятность того, что в некоторый случайный момент сервер будет свободный, то
.ЛИТЕРАТУРА
1. Л.Н. Волков, М.С. Немировский, Ю.С. Шинаков. Системы цифровой радиосвязи: базовые методы и характеристики. Учебное пособие.-М.: Эко-трендз, 2005.
2. М.В. Гаранин, В.И. Журавлев, С.В. Кунегин. Системы и сети передачи информации. - М.: Радио и связь, 2001.
3. Передача дискретных сообщений./Под ред. В.П. Шувалова. – М.: Радио и связь, 1990.
4. Основы передачи дискретных сообщений./Под ред. В.М. Пушкина. – М.: Радио и связь, 1992.
5. Н.В. Захарченко, П.Я. Нудельман, В.Г. Кононович. Основы передачи дискретных сообщений. –М.: Радио и связь, 1990.