Анализ систем массового обслуживания

Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Анализ систем массового обслуживания

Классификация систем

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

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

В дальнейшем будем подробно исследовать однолинейную систему обслуживания, представленную на рис.2.1.

Рис. 2.1. Однолинейная система обслуживания.

В контексте сетей передачи данных обслуживающая линия – это средство передачи, которое передаёт данные с предписанной скоростью С. Например, канал обрабатывающий поступающие заявки - пакеты длинной 1000 бит и передающий их со скоростью 2400 бит/с., образует обслуживающую линию с интенсивностью обслуживания μ=2,4 пакет/с. При этом - средняя скорость (интенсивность) поступлений с размерностью пакет/с. Если речь идет о сети с коммутацией каналов, то имеет размерность вызов/с, а величина имеет смысл средней продолжительности занятия.

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

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

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

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

- времени обработки в узле,

- длины пакета,

- пропускной способности канала передачи (число пакетов в секунду),

- интенсивности поступления пакетов в рассматриваемый узел,

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

Важный параметр – состояние очереди, то есть число пакетов в очереди. Это величина случайная, характеризуется определенной вероятностью и влияет на многие количественные характеристики системы. Для расчёта вероятности состояния очереди надо знать:

1) характеристики процесса поступления заявок на обслуживание,

2) распределение времени обслуживания (распределение длины пакетов),

3) дисциплину обслуживания.

При рассмотрении систем массового обслуживания будем придерживаться классификации, данной Кендаллом. Общий вид обозначения системы - А/В/С. Здесь первая позиция (А) описывает распределение промежутков времени между событиями во входном потоке, позиция В - распределение времени обслуживания и С – число обслуживающих линий.

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

В системе М/G/1 распределение интервалов времени во входном потоке экспоненциальное, а распределение времени обслуживания (G) может быть произвольным (G - general). М/D/1 – D – постоянное (детерминированное) время обслуживания. Самой сложной является система G/G/1, в которой оба распределения могут быть произвольными. Такие системы редко встречаются на практике и требуют специальных математических методов при анализе.

Система обслуживания М/М/1.

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

Пусть есть система М/М/1, изображенная на рис. 2.2а.

а)

б)

Рис.2.2. Система обслуживания М/М/1 и диаграмма ее состояний.

Интенсивность пуассоновского потока на входе - l, а процесс обслуживания (длина пакета или продолжительность соединения) описывается экспоненциальным распределением с параметром μ, которое имеет вид

. (2.1)

Найдём - вероятность того, что в момент в системе будет находиться n клиентов. В силу ординарности входного потока есть сумма вероятностей состояний (взаимно исключающих) n-1, n или n+1, в которых система могла быть в момент t (см. диаграмму на рис.2.2б), умноженных на независимые вероятности попадания в состояние n за время Δt.

(2.2)

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

Преобразуя (отбрасывая члены, пропорциональные ), получим:

. (2.3)

Уравнение (2.3) позволяет исследовать переходный режим системы. Разложим в ряд Тейлора и удержим в ряде два члена

. (2.4)

Подставляя (2.4) в (2.3), получим

. (2.5)

Стационарное значение можно найти из условия . При этом из (2.5) имеем:

. (2.6)

Это уравнение равновесия. Левая часть описывает уходы из состояния n, правая – приходы в состояние n. Графически последовательность состояний и возможные переходы из состояния в состояние отражены на рис.2.3. Состояния отображаются пронумерованными точками, а переходы – стрелками.

Рис.2.3. Диаграмма состояний системы М/М/1.

Пунктиром на рисунке отмечены две области: овальная область (область 1), охватывающая состояние равновесия n , и прямоугольная область (область 2), охватывающая все состояния от 0 до n . Если для области 1 в состоянии равновесия приравнять исходящий поток (интенсивность уходов из состояния n) входящему потоку (интенсивность прихода в состояние n), то получим уравнение (2.6). Значит, эта диаграмма позволяет не только составить уравнение (2.6), но и решить его. Для этого рассмотрим область 2. Поток, поступающий в эту область: , поток, покидающий его: . Поэтому:

. (2.7)

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

В результате получаем , где , а P₀ можно найти из условия нормировки .

Для бесконечной очереди: .

. Здесь использована формула суммы членов геометрической прогрессии, конечный результат в которой достигается при . Поэтому

, (2.8)

и . (2.9)

Итак, равновесие в системе возможно при . Распределение (2.9), характеризующее систему M/M/1, называется геометрическим распределением. Оно представлено на рис.2.4.

Рис.2.4. Геометрическое распределение.

В силу того, что (т.е. вероятность того, что система пуста, n=0), вероятность того, что система не пуста т.е. равна коэффициенту нагрузки.

Для конечной очереди N уравнение равновесия (2.6) справедливо для всех n, кроме двух граничных точек: n=0 и n = N. Уравнение (2.7) справедливо всегда. Из условия нормировки: , которое после вычисления суммы запишется как , получаем Р₀

. (2.10)

Поэтому для конечной очереди из N пакетов в системе M/M/1:

. (2.11)

Вероятность того, что очередь заполнена: . Эта вероятность, по – другому, есть вероятность блокировки, т. е. вероятность того, что пакеты не могут быть приняты системой, т.к. накопитель заполнен. Проиллюстрируем это понятие.

Вероятность блокировки.

Пусть есть произвольная система обслуживания (не обязательно M/M/1), изображенная на рис.2.5.

Рис.2.5. К понятию вероятности блокировки.

При наличии блокировки с вероятностью P_B чистая интенсивность поступлений может быть интерпретирована как . Но это должно быть не чем иным, как пропускной способностью (производительностью) или числом клиентов, обслуживаемых в секунду в консервативной системе. Таким образом . Пропускную способность можно определить и другим способом.

Пусть - средняя скорость обслуживания, когда система не пуста. Система пуста с вероятность P₀. Поэтому фактическая скорость обслуживания . Итак, в системе с конечной очередью:

. (2.12)

Подставим сюда из (2.10)

, где .

Преобразуя, получим: , что совпадает с для системы M/M/1 с конечной очередью.

Если и , то, и , что совпадает с выражением (2.9) для системы M/M/1 с бесконечной очередью, то есть это есть вероятность того, что система находится в состоянии n = N. Таким образом, при усечение бесконечной очереди в точке n = N не повлияет на статистику очереди.

Пример: . В системе M/M/1 требуется реализовать . Из выражения находим N=9. Если , то N=19.

Исследуем выражение (2.11). Для существования стационарных вероятностей здесь не требуется . Эти вероятности существуют из-за конечности очереди для любого . При увеличении , из-за увеличения очередь переполняется всё более часто и при очередь находится в состоянии n = N с вероятностью 1. Характер зависимости представлен на рис.2.6.

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

Рис.2.6. Характеристики системы M/M/1 при конечной очереди.

Из (2.12) можно получить . Данное выражение представляет собой нормированную производительность системы M/M/1 с конечной очередью. Зависимость от r также представлена на рис.2.6. При получаем , и при .

Сравнение поведения системы M/M/1 при конечной и бесконечной очереди позволяет сделать вывод, что в области целесообразно исследовать только бесконечный накопитель. Как было указано выше, на основе известного распределения вероятностей состояний можно рассчитывать различные характеристики системы.

Найдем среднее число клиентов в системе E(n).

С учетом , получаем

. (2.13)

Результат (2.13) можно получить непосредственно, используя формулу [ 8 ]

, где для нашего случая a=0 и r=1.

График зависимости среднего числа клиентов от r приведен на рис.2.7.

Из (2.13) следует, что при малой нагрузке число клиентов в очереди мало, с увеличением нагрузки ( ) число клиентов в очереди тоже увеличивается (за счёт в знаменателе). Сравнивая два последних рисунка можно сказать, что при росте нагрузки системы растёт и её производительность, однако, всё большее количество клиентов блокируется и растёт среднее число клиентов в очереди.

Рис.2.7. Зависимость E(n) от r для системы M/M/1.

2.3. Формула Литтла.

В предыдущем параграфе было рассчитано среднее число клиентов в системе М/М/1. С величиной Е(n) тесно связана временная характеристика системы, которая называется время задержки Т, и которая включает в себя время ожидания в очереди W и время обслуживания (см.рис.2.8). В силу того, что m в однолинейной системе представляет собой среднюю интенсивность обслуживания можно не вводить специального обозначения для среднего времени обслуживания, а просто писать .

Рис. 2.8. Время задержки в однолинейной системе.

Поэтому . (2.14)

Очевидно, должна существовать связь среднего времени задержки клиента в системе Е(Т) со средним числом клиентов E(n) в установившемся режиме. Установим эту связь.

Обозначим через m(t) число поступлений в систему к мо-менту времени t на интервале (0, t). Число уходов из накопителя на обслуживание на этом же интервале – l(t). Никаких предположений относительно процессов поступлений и уходов не делается, т.е. полученный результат будет справедлив для любых типов однолинейных систем. В соответствие с введенными обозначениями для числа s(t) ожидающих клиентов в системе к моменту времени t можно записать

На рис.2.9 m(t) изображена сплошной линией, а l(t) – пунктиром. Там же отмечены моменты поступления клиентов в систему и моменты ухода на обслуживание , . Пусть дисциплина обслуживания – в порядке поступления, тогда Соответственно - время ожидания j-го клиента.

Рис.2.9. К выводу формулы Литтла.

Рассмотрим интервал . Число поступлений на этом интервале , а средняя интенсивность поступлений

. (2.15)

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

. (2.16)

Пусть - среднее время ожидания в промежутке . Тогда

. (2.17)

Среднее число клиентов в системе

. (2.18)

Из (2.16), (2.17) и (2.18) имеем

или .

Это и есть формула Литтла. При , , и для установившегося режима можно записать окончательно

. (2.19)

Формула Литтла справедлива при любой дисциплине обслуживания. Это можно показать из соотношения

которое следует интерпретировать так, что сумма слева зависит только от суммы времен ухода, а не от разности .

Вернемся к системе M / M /1.

Формулу Литтла перепишем в привычных обозначениях: . Теперь

. (2.20)

При - здесь задержка определяется только обслуживанием. Последний результат представлен графически на рис.2.10, где по оси ординат отложена нормированная задержка , т.е. нормировка осуществляется делением на среднее время обслуживания.

Рис.2.10. Нормированная средняя задержка.

Со средним временем задержки E(T) можно связать ещё понятия (см.рис.2.8)

E(W) – среднее время ожидания в очереди,

E(q) – среднее число клиентов, ожидающих в очереди.

Кроме очевидного равенства (2.14), на основе формулы Литтла, которая применима не только ко всей системе, но и к ее части, можно записать

(2.21)

В (2.21) понимается как среднее число клиентов на обслуживании. Оно меньше 1, т. к. на обслуживание либо есть клиент, либо нет. Этот результат подтверждается уже известным для системы М/М/1 фактом: - это вероятность того, что ни один клиент не обслуживается, - это вероятность того, что на обслуживание находится один клиент.

Эти рассуждения справедливы для любой однолинейной системы.

Системы M / G /1

Строгий вывод формулы для E(n) через производящую функцию, как видно, довольно сложен. Проще E(n) можно получить из (2.42).

Возведём (2.42) в квадрат, возьмём математическое ожидание от обеих частей и положим :

. (*)

При из (2.42) следует .

Кроме того: и - оба равенства следуют из определения U(n).

Будем считать, что и независимы, тогда

С учетом сделанных замечаний формулу (*) перепишем в виде:

Учтем также, что т. к. случайные величины n и n независимы. Теперь

откуда .

Т.к. , то для E(n) окончательно запишем

что совпадает с (2.66)

Здесь - дисперсия числа клиентов, поступающих в течение времени обслуживания.

Найдём . По определению дисперсии

. (2.67)

Поток заявок на обслуживание пуассоновский, поэтому для используем выражение (2.62), а , поэтому

. (2.68)

Изменим порядок интегрирования и суммирования с учётом следующих соотношений:

В последних трех формулах использованы свойства распределения Пуассона. Теперь (2.68) преобразуется к виду

Если в последней формуле учесть, что

то для можно окончательно записать

, (2.69)

где - дисперсия распределения времени обслуживания.

Подставим теперь (2.69) в (2.66):

т. е. . (2.70)

Формула (2.70) называется формулой Поллячека-Хинчина. Из формулы Литтла

. (2.71)

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

В системе M / M /1 время обслуживания распределено экспоненциально. Дисперсия этого распределения . Подставляя в (2.70), получаем: , что совпадает с полученным ранее.

Для системы M / D /1 все клиенты требуют одного времени обслуживания , при этом . Тогда:

, (2.72)

Можно считать, что система M/D/1 - это частный случай M/M/1 с наименьшей длиной очереди и задержкой.

В заключение найдем среднее время ожидания E(W) для M/G/1:

Подставим сюда E(T) из (2.71):

, (2.73)

где - второй момент распределения времени обслуживания.