Анализ систем массового обслуживания с Марковскими потоками требований.

1)Система М/M/1. Анализ.

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

На рис. 1. приведена простейшая схема такой системы. Она содержит буфер, который может хранить очередь бесконечной длины, состояние которой может быть отождествлено с числом заявок, содержащихся в очереди в каждый момент времени.

Рис. 1. СМО типа М/М/1.

Поскольку входной процесс ординарный, то в каждый момент времени к очереди может добавиться только одна заявка, поскольку сервер один, то в каждый момент времени может быть обслужена, то есть уйти из очереди только одна заявка. Таким образом, рассматриваемая СМО относится к процессу класса «гибели-размножения». Для анализа необходимо конкретизировать параметры системы. Распределение вероятностей входного потока и времени обслуживания позволяет полагать интенсивности вероятностей в модели постоянными.

Здесь  – среднее время обслуживания в сервере.

На рис 2 приведена диаграмма интенсивностей переходов для рассматриваемой системы.

Рис. 2 Диаграмма интенсивности переходов для СМО типа М/М/1.

Полученное ранее общее решение позволяет сразу записать вероятность того, что в стационарном состоянии в очереди будет находиться k заявок

Найдем начальное значение вероятности, учитывая сходимость соответствующего ряда

.

Окончательно получаем формулу для вероятности длины очереди

.

2) Система с несколькими серверами: M/M/m

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

Система M/M/2 может быть представлена как процесс размножения-гибели с параметрами:

Таким образом, в системе с двумя серверами время задержки сокращается. Нетрудно убедиться, что производительность системы M/M/2 также выше.

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

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

Рис. 1. Нормированные графики среднего времени задержки в системе с одним и с двумя серверами одной и той же производительности и с одним серверов, работающим с вдвое большей скоростью.

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

Рассмотрим теперь общий случай СМО с m серверами. Диаграмма интенсивностей

переходов для такой системы представлена на рис. 2.

Рисунок 2. Диаграмма интенсивностей переходов для СМО типа M/M/m.

Интенсивности переходов могут быть определены следующим образом:

3)Система обслуживания с m серверами явными потерями: M/M/m/Loss

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

Такая система оказывается также эргодичной и диаграмма интенсивностей переходов, приведенная на рис. 3

Рис. 3 Диаграмма интенсивностей переходов для СМО типа M/M/m:Loss.

Основной характеристикой QoS для этой системы является средняя доля времени, когда все серверы оказываются занятыми. В этом случае говорят о том, что в системе наступила блокировка.

4)Система типа M/M/m:m

Систему, имеющую одинаковое число входных линий и обслуживающих серверов, например выходных линий. Очевидно, что блокировка в такой системе невозможна. Диаграмма интенсивностей переходов состояний может быть представлена в виде совокупности несвязных m простейших подсистем с двумя состояниями – свободно/занято. ( Рис. 1.20)

Рис. 1.20 Диаграмма интенсивностей переходов состояний для СМО типа M/M/m:m.

Вероятности того, что k подсистем находятся в состоянии «занято», описывается формулой Энгсета:

.

Нетрудно видеть, что в этом случае в знаменателе записан бином Ньютона, и формула для вероятностей может быть существенно упрощена:

Полученное распределение вероятностей носит название биноминального или распределения Бернулли. Величина a определяет вероятность занятости сервера, а величина (1-a) – вероятность его простоя. Поскольку таких серверов m , то распределение вероятностей будет таким же, как для классической задачи о бросании m монет. Следует отметить также что