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

2. Анализ систем массового обслуживания 2.1. Классификация систем Все дальнейшее изложение материала будет ориентировано, в основном, на проблемы систем связи. Основой любой системы связи является сеть. Сеть – это соединение пользователей между собой. Если пользователей миллионы, то соединить каждого с каждым не представляется возможным, поэтому применяются сетевые коммутационные средства, или узлы, которые осуществляют концентрацию и распределение нагрузки между пользователями. Для этого коммутационные узлы соединяются между собой линиями передачи (кабельные, радио, спутниковые, оптические). Коммутационные узлы строятся по принципу коммутации пакетов и коммутации каналов. Технология коммутации пакетов используется в основном для передачи данных, коммутация каналов – для телефонных сетей. Современная цифровая обработка не только звуковой, но и видеоинформации позволяет использовать при их транспортировке технику передачи данных (например, технология АТМ), приводя к конвергенции технологий коммутации. Как бы то ни было, теория массового обслуживания является основой для построения любых сетей связи. В дальнейшем будем подробно исследовать однолинейную систему обслуживания, представленную на рис.2.1. Поступающие заявки Накопитель Обслуживающая Отправленные линия заявки Рис. 2.1. Однолинейная система обслуживания. В контексте сетей передачи данных обслуживающая линия – это средство передачи, которое передаёт данные с предписанной скоростью С. Например, канал обрабатывающий поступающие заявки - пакеты длинной 1000 бит и передающий 37 их со скоростью 2400 бит/с., образует обслуживающую линию с интенсивностью обслуживания μ=2,4 пакет/с. При этом  средняя скорость (интенсивность) поступлений с размерностью пакет/с. Если речь идет о сети с коммутацией каналов, то  1 имеет размерность вызов/с, а величина имеет смысл сред ней продолжительности занятия. Накопитель как элемент системы обслуживания в большей степени характерен для сетей с коммутацией пакетов. Важным параметром рассматриваемой системы является  коэффициент   , называемый коэффициентом использова ния канала или коэффициентом нагрузки. Ясно, что этот коэффициент соотносит возможности рассматриваемой системы с интенсивностью поступления заявок на обслуживание. При   1 в системе возможны перегрузки и, как следствие, блокировка системы. В системе может быть несколько обслуживающих линий, тогда одновременно могут обслуживаться несколько заявок. Время, затраченное на ожидание обработки в накопителе, является важной мерой, характеризующей работу системы массового обслуживания. Это время зависит от: - времени обработки в узле, - длины пакета, - пропускной способности канала передачи (число пакетов в секунду), - интенсивности поступления пакетов в рассматриваемый узел, - дисциплины обслуживания (обслуживание в порядке поступления, обслуживание в обратном порядке, в случайном порядке, обслуживание с приоритетом). Важный параметр – состояние очереди, то есть число пакетов в очереди. Это величина случайная, характеризуется определенной вероятностью и влияет на многие количественные характеристики системы. Для расчёта вероятности состояния очереди надо знать: 38 1) характеристики процесса поступления заявок на обслуживание, 2) распределение времени обслуживания (распределение длины пакетов), 3) дисциплину обслуживания. При рассмотрении систем массового обслуживания будем придерживаться классификации, данной Кендаллом. Общий вид обозначения системы - А/В/С. Здесь первая позиция (А) описывает распределение промежутков времени между событиями во входном потоке, позиция В - распределение времени обслуживания и С – число обслуживающих линий. Например, М/М/1 – система с одной обслуживающей линией, пуассоновским входящим потоком, экспоненциальным распределением времени обслуживания и дисциплиной обслуживания FIFO. Первая буква М в обозначении системы говорит о том, что интервалы времени между заявками на входе системы распределены по экспоненциальному закону, что в свою очередь указывает на пуассоновский поток событий, который можно считать разновидностью марковского случайного процесса. Вторая буква М в обозначении опять говорит о марковости процесса на выходе обслуживающей линии, что определяется экспоненциальным характером распределения времени обслуживания, порождающим пуассоновский поток обработанных заявок на выходе. В системе М/G/1 распределение интервалов времени во входном потоке экспоненциальное, а распределение времени обслуживания (G) может быть произвольным (G - general). М/D/1 – D – постоянное (детерминированное) время обслуживания. Самой сложной является система G/G/1, в которой оба распределения могут быть произвольными. Такие системы редко встречаются на практике и требуют специальных математических методов при анализе. 2.2. Система обслуживания М/М/1. Центральным понятием при анализе любой системы является ее состояние, причем под состоянием понимается коли39 чество клиентов (пакетов) в системе n, включая клиента, находящегося на обслуживании. Очевидно, n является случайной величиной и задача заключается в определении вероятности любого состояния системы в произвольный момент времени Pn (t ) . Если вероятности состояний найдены, то статистические свойства системы (например, среднее время занятия, вероятность блокировки для конечной очереди, средняя пропускная способность и др.) могут быть определены сравнительно просто. Пусть есть система М/М/1, изображенная на рис. 2.2а. Пуассоновский поток Экспоненциальное время обслуживания μ λ n Накопитель а) Состояние n+1 n n-1 . . . . Время t t+∆t б) Рис.2.2. Система обслуживания М/М/1 и диаграмма ее состояний. Интенсивность пуассоновского потока на входе - , а процесс обслуживания (длина пакета или продолжительность 40 соединения) описывается экспоненциальным распределением с параметром μ, которое имеет вид (2.1) w()  e  . Найдём Pn (t  t ) - вероятность того, что в момент (t  t ) в системе будет находиться n клиентов. В силу ординарности входного потока Pn (t  t ) есть сумма вероятностей состояний (взаимно исключающих) n-1, n или n+1, в которых система могла быть в момент t (см. диаграмму на рис.2.2б), умноженных на независимые вероятности попадания в состояние n за время Δt. Pn (t  t )  Pn (t )(1  λt )(1  μt )  μt  λt  O(t )   Pn 1 (t )λt  (1  μt )  O(t )  (2.2)  Pn 1 (t )μt  (1  λt )  O(t )  При записи (2.2) учтено, что если время обслуживания имеет экспоненциальное распределение, то поток моментов времени завершения обслуживания является пуассоновским потоком. Поэтому вероятность завершения обслуживания за время Δt есть μt  O(t ) , и, соответственно, вероятность не завершения обслуживания за время Δt равна 1  μt  O(t ) . Первая строка (2.2), к примеру, характеризует переход n  n , который может произойти либо при одном поступлении и одном уходе – вероятность чего записывается как (t  t ) , либо, если не будет ни поступления, ни ухода с вероятностью (1  t )(1  t ) . Преобразуя (отбрасывая члены, пропорциональные t 2 ), получим: Pn (t  t )  1  (  )t Pn (t )  tPn1 (t )  tPn1 (t ) . (2.3) Уравнение (2.3) позволяет исследовать переходный режим системы. Разложим Pn (t  t ) в ряд Тейлора и удержим в ряде два члена Pn (t  t )  Pn (t )  dPn (t )  t . dt Подставляя (2.4) в (2.3), получим 41 (2.4) dPn (t ) (2.5)  (  ) Pn (t )  Pn1 (t )  Pn1 (t ) . dt Стационарное значение Pn можно найти из условия dPn (t )  0 . При этом из (2.5) имеем: dt (  ) Pn  Pn1  Pn1 n  1. (2.6) Это уравнение равновесия. Левая часть описывает уходы из состояния n, правая – приходы в состояние n. Графически последовательность состояний и возможные переходы из состояния в состояние отражены на рис.2.3. Состояния отображаются пронумерованными точками, а переходы – стрелками. . λ . λ 1 μ . λ 2 μ ... 3 . . . n-1. . μ λ . n μ λ . λ n+1 μ . μ состояние Рис.2.3. Диаграмма состояний системы М/М/1. Пунктиром на рисунке отмечены две области: овальная область (область 1), охватывающая состояние равновесия n, и прямоугольная область (область 2), охватывающая все состояния от 0 до n . Если для области 1 в состоянии равновесия приравнять исходящий поток (интенсивность уходов из состояния n) входящему потоку (интенсивность прихода в состояние n), то получим уравнение (2.6). Значит, эта диаграмма позволяет не только составить уравнение (2.6), но и решить его. Для этого рассмотрим область 2. Поток, поступающий в эту область: Pn1 , поток, покидающий его: Pn . Поэтому: Pn  Pn1 . (2.7) Уравнение (2.7) выполняется для любого n и удовлетворяет уравнению (2.6), следовательно, может рассматриваться 42 как его решение. Перебирая n, можно записать решение в явном виде: P0  P1 , P1  P0 откуда  ,  далее P1  P2 , 2   P2  P1  P0   и т.д.   В результате получаем Pn  P0  n , где   условия нормировки  Pn  1.  , а P0 можно найти из  n Для бесконечной очереди:   Pn  1 . n 0 1  n 1  P0 . Здесь использована формула  P0   P0 nlim  1   1  n 0  n суммы членов геометрической прогрессии, конечный результат в которой достигается при   1 . Поэтому (2.8) P0  1   , и Pn  (1  ) n . Итак, равновесие в системе возможно при   (2.9)   1.  Распределение (2.9), характеризующее систему M/M/1, называется геометрическим распределением. Оно представлено на рис.2.4. Рис.2.4. Геометрическое распределение. 43 В силу того, что P0  1   (т.е. вероятность того, что система пуста, n=0), вероятность того, что система не пуста 1  P0  1  1     т.е. равна коэффициенту нагрузки. Для конечной очереди N уравнение равновесия (2.6) справедливо для всех n, кроме двух граничных точек: n=0 и n=N. Уравнение (2.7) справедливо всегда. Из условия нормировки: N  P0  n  1 , которое после вычисления суммы запишется n 0 как P0 1   N 1  1 , получаем Р0 1  1  . (2.10) 1   N 1 Поэтому для конечной очереди из N пакетов в системе M/M/1: P0  (1  ) n Pn  . 1   N 1 (2.11) (1  ) N Вероятность того, что очередь заполнена: PN  . 1   N 1 Эта вероятность, по – другому, есть вероятность блокировки, т. е. вероятность того, что пакеты не могут быть приняты системой, т.к. накопитель заполнен. Проиллюстрируем это понятие. Вероятность блокировки. Пусть есть произвольная система обслуживания (не обязательно M/M/1), изображенная на рис.2.5. Нагрузка PB λ Система обслуживания Производительность γ   (1  PB ) PB - вероятность блокировки Рис.2.5. К понятию вероятности блокировки. 44 При наличии блокировки с вероятностью PB чистая интенсивность поступлений может быть интерпретирована как (1  PB ) . Но это должно быть не чем иным, как пропускной способностью (производительностью)  или числом клиентов, обслуживаемых в секунду в консервативной системе. Таким образом   (1  PB ) . Пропускную способность можно определить и другим способом. Пусть  - средняя скорость обслуживания, когда система не пуста. Система пуста с вероятность P0. Поэтому фактическая скорость обслуживания   (1  P0 ) . Итак, в системе с конечной очередью:   (1  PB )  (1  P0 ) . (2.12) Подставим сюда P0 из (2.10)  1   (1  PB )  1  , где  . N 1   1   N (1  ) Преобразуя, получим: PB  , что совпадает с PN 1   N 1 для системы M/M/1 с конечной очередью. Если   1 и N  1, то,  N 1  1 и PB  (1  ) N , что совпадает с выражением (2.9) для системы M/M/1 с бесконечной очередью, то есть это есть вероятность того, что система находится в состоянии n=N. Таким образом, при  N  1 усечение бесконечной очереди в точке n=N не повлияет на статистику очереди. Пример:   0,5 . В системе M/M/1 требуется реализовать PB  10 3 . Из выражения PB  (1  ) N находим N=9. Если PB  10 6 , то N=19. Исследуем выражение (2.11). Для существования стационарных вероятностей здесь не требуется   1 . Эти вероятности существуют из-за конечности очереди для любого  . При 45 увеличении  , из-за увеличения  очередь переполняется всё более часто и при    очередь находится в состоянии n=N с вероятностью 1. Характер зависимости PB () представлен на рис.2.6. При    Pn  0 для всех n  N , а PN  1 , т. е. PB  PN  1. Область   1 называется областью скученности, здесь наиболее вероятны состояния очереди с наивысшими номерами. При   1 (с использованием правила Лопиталя) можно получить PB  1 . N 1 PB 1 1 N 1 ρ 1   1 N N 1 ρ 1 Рис.2.6. Характеристики системы M/M/1 при конечной очереди.  (1   N )  (1  P0 )  Из (2.12) можно получить . Данное  1   N 1 выражение представляет собой нормированную производительность системы M/M/1 с конечной очередью. Зависимость 46  от  также представлена на рис.2.6. При   1 получаем   N  , и при      1.  N 1  Сравнение поведения системы M/M/1 при конечной и бесконечной очереди позволяет сделать вывод, что в области   1 целесообразно исследовать только бесконечный накопитель. Как было указано выше, на основе известного распределения вероятностей состояний Pn можно рассчитывать различные характеристики системы. Найдем среднее число клиентов в системе E(n).    n 0 n 0 n 0 E (n)   nPn   n(1  ) n  (1  ) n n С учетом   n n 0 n    n n 1 n 0   n  1         , получаем  n0  1   (1  ) 2  E (n)  . (2.13) 1  Результат (2.13) можно получить непосредственно, используя формулу [ 8 ]   (a  kr)q k k 0  a rq  , где для нашего случая a=0 и r=1. 1  q (1  q) 2 График зависимости среднего числа клиентов от  приведен на рис.2.7. Из (2.13) следует, что при малой нагрузке число клиентов в очереди мало, с увеличением нагрузки (   1 ) число клиентов в очереди тоже увеличивается (за счёт 1   в знаменателе). Сравнивая два последних рисунка можно сказать, что при росте нагрузки системы растёт и её производительность, однако, всё большее количество клиентов блокируется и растёт среднее число клиентов в очереди. 47 E(n) ρ 1 Рис.2.7. Зависимость E(n) от  для системы M/M/1. 2.3. Формула Литтла. В предыдущем параграфе было рассчитано среднее число клиентов в системе М/М/1. С величиной Е(n) тесно связана временная характеристика системы, которая называется время задержки Т, и которая включает в себя время ожидания в очереди W и время обслуживания (см.рис.2.8). В силу того, что  в однолинейной системе представляет собой среднюю интенсивность обслуживания можно не вводить специального обозначения для среднего времени обслуживания, а просто писать  1 . E (q)  E (W ) μ m(t ) λ l (t ) E (n) = E (T ) Рис. 2.8. Время задержки в однолинейной системе. 48 E (T )  E (W )   1 . Поэтому (2.14) Очевидно, должна существовать связь среднего времени задержки клиента в системе Е(Т) со средним числом клиентов E(n) в установившемся режиме. Установим эту связь. Обозначим через m(t) число поступлений в систему к моменту времени t на интервале (0, t). Число уходов из накопителя на обслуживание на этом же интервале – l(t). Никаких предположений относительно процессов поступлений и уходов не делается, т.е. полученный результат будет справедлив для любых типов однолинейных систем. В соответствие с введенными обозначениями для числа s(t) ожидающих клиентов в системе к моменту времени t можно записать s(t )  m(t )  l (t ) . На рис.2.9 m(t) изображена сплошной линией, а l(t) – пунктиром. Там же отмечены моменты t j j  1,2,поступления клиентов в систему и моменты ухода на обслуживание t /j j  1,2,, t /j  t j . Пусть дисциплина обслуживания – в порядке поступления, тогда t1/  t 2/  t 3/   Соответственно W j - время ожидания j-го клиента. 6 W6 m(t ) 5 W5 4 3 W4 W2 l (t ) 2 W3 1 t t1 t3 t2 t5 t4 t6 t t1/ t 2/ t 3/ t 4/ t 5/ Рис.2.9. К выводу формулы Литтла. 49 t 6/ Рассмотрим интервал (0, ) . Число поступлений на этом интервале n()  m()  m(0) , а средняя интенсивность поступлений ()  n() .  (2.15)  Найдем  s(t )dt . Этот интеграл определяется как площадь под разностью s(t )  m(t )  l (t ) . Из рисунка следует, что эта площадь состоит из прямоугольников единичной высоты и длины W j .  n ( ) j 1  s(t )dt  W j . (2.16) Пусть W () - среднее время ожидания в промежутке (0, ) . Тогда W ()  1 n ( ) W j . n() j 1 (2.17) Среднее число клиентов в системе s () 1 s()   s(t )dt . 0 (2.18) Из (2.16), (2.17) и (2.18) имеем 1  s() W ()  s(t )dt     () 0 () или s()  ()W () . Это и есть формула Литтла. При    W ()  W , ()   , s()  s и для установившегося режима можно записать окончательно s   W . (2.19) Формула Литтла справедлива при любой дисциплине обслуживания. Это можно показать из соотношения n ( ) n ( ) n ( ) j 1 j 1 j 1 W j   (t /j  t j )   t /j   t j , 50 которое следует интерпретировать так, что сумма слева зависит только от суммы времен ухода, а не от разности t /j  t j . Вернемся к системе M/M/1. Формулу Литтла перепишем в привычных обозначениях: E (T )  E (n) . Теперь E ( n)  1   . (2.20)  (1  ) (1  ) 1 При   1 E (T )  - здесь задержка определяется толь E (T )  ко обслуживанием. Последний результат представлен графически на рис.2.10, где по оси ординат отложена нормированная E (T ) задержка  E (T ) , т.е. нормировка осуществляется делени 1 ем на среднее время обслуживания. μE (T ) 1 1 ρ 1 1 ρ Рис.2.10. Нормированная средняя задержка. Со средним временем задержки E(T) можно связать ещё понятия (см.рис.2.8) E(W) – среднее время ожидания в очереди, E(q) – среднее число клиентов, ожидающих в очереди. Кроме очевидного равенства (2.14), на основе формулы Литтла, которая применима не только ко всей системе, но и к ее части, можно записать 51 E (q)  E (W ),  1     E (T )    E (T )  ,     E (n)  . (2.21) В (2.21)  понимается как среднее число клиентов на обслуживании. Оно меньше 1, т. к. на обслуживание либо есть клиент, либо нет. Этот результат подтверждается уже известным для системы М/М/1 фактом: P0 1   - это вероятность того, что ни один клиент не обслуживается, 1  P0   - это вероятность того, что на обслуживание находится один клиент. Эти рассуждения справедливы для любой однолинейной системы. 2.4. Системы обслуживания, зависящие от состояний. Пусть есть система с очередью, в которой интенсивности поступлений и обработки зависят от состояния системы. Напомним, что под состоянием системы понимается количество клиентов n, находящихся в системе, включая клиента, на обслуживании. Предположение о зависимости процессов поступления и ухода от состояния приводит к понятию процессов размножения и гибели. Рассмотрим систему, представленную на рис. 2.11. λn Система обслуживания : n клиентов , Pn μn Рис. 2.11. Система, зависящая от состояний. Пусть поступления в систему – пуассоновские с интенсивностью  n , а распределение времени обслуживания – экспоненциальное с параметром  n . Определим для системы, находящейся в состоянии n, вероятность одного поступления за 52 интервал времени (t , t  t ) в виде λ n t  O(t ) . Вероятность отсутствия поступлений, соответственно, запишется как (1  λ n t )  O(t ) . Будем также предполагать, что последействие отсутствует, т.е. вероятность того, что происходит в интервале t , не зависит от того, что происходит на других интервалах. Процесс ухода клиентов определяется аналогичными вероятностями на интервале и μ n t  O(t ) (t , t  t ) : (1  μ n t )  O(t ) . Рассмотренная выше система, когда  n   и  n   , является частным случаем рассматриваемой. Объединяя два процесса и устремляя t  0 , для состояния статистического равновесия, повторяя вышеприведенные рассуждения, можно записать ( n   n ) Pn   n1 Pn1   n1 Pn1 . (2.22) Уравнение равновесия (2.22) может быть получено путем приравнивания интенсивностей уходов из состояния n к интенсивности приходов в состояние n (см. пунктирную область около состояния n на рис.2.12). λ0 . . λ1 1 μ1 . λ2 2 μ2 3 . .. .. n-1.. . λ n 1 μ3 . n μn λ n 1 λn . n+1 . μ n 1 состояние Рис.2.12. Состояние равновесия по уравнению (2.22). Решение уравнения (2.22) можно, как и выше, искать в виде  n Pn   n1 Pn1 , что приводит к 53 (2.23) n 1 Pn  P0  i i 0 n  i . (2.24) i 1 Вероятность P0 определяется из условия нормировки N  Pn  1 . n 0 Если N (число клиентов в очереди) конечно, то система всегда стабильна. При бесконечной очереди ( N   ) стабильность гарантируется при P0 >0. Приведем теперь примеры использования обсужденной модели системы массового обслуживания. Система М/М/2. Рассмотрим систему, изображенную на рис.2.13. На входе системы действует пуассоновский поток пакетов данных с интенсивностью . Длина пакетов предполагается случайной величиной с экспоненциальным распределением со средним значением  1 секунд. μ n λ μ Рис.2.13. Система М/М/2. Вероятность завершения обслуживания за интервал (t , t  t ) в любом канале равна t , а вероятность одного завершения обслуживания в системе - 2t . Таким образом, система М/М/2 может рассматриваться как система, зависящая от состояния, потому, что 54  n  ,  n  , при n  1,  n  2, при n  2. Из (2.24)     Pn  P0      2  где   n 1  2 P0  n , (2.25)  . 2 Вероятность Р0 найдем для случая бесконечного накопителя из условия   Pn  1 . n 0  Подставим (2.25) в условие нормировки: P0  2 P0   n  1. n 0 Теперь    n  Nlim  n 1    1  N  . И, наконец: 1   P0  1  . 1  (2.26) Формула (2.25) запишется как Pn  2(1  ) n  , 1  n  1. (2.27) Найдем среднюю занятость системы 2(1  )  E (n)   nPn  n n .  1   n 0 n 0  При выводе формулы (2.13) было получено    n n  (1  ) 2 . С n 0 учетом этого результата E ( n)  2 . 1  2 55 (2.28) Сравним занятость систем М/М/1 и М/М/2. Напомним, что E (n) M/M/1    , где   . С учетом соотношения для  1   можно утверждать, что средняя занятость системы М/М/2 всегда меньше. Среднее время задержки определим по формуле Литтла: E (T )  E ( n) 2 1  , где   .   2 2 2  (1   ) (1   ) Для сравнения: E (T ) M/M/1  (2.29) 1  , где   . Теперь вид (1  ) но, что всегда E (T ) M/M/2  E (T ) M/M/1 . На рис.2.14 приведены зависимости нормированной задержки от коэффициента нагрузки для трех систем: M/M/1 , М/М/2 и системы M/M/12 с удвоенной интенсивностью обслуживания. Из сравнения зависимостей следует, что добавление обслуживающей линии уменьшает время задержки и, естественно, увеличивает производительность системы. Но система M/M/12 будет лучше, чем М/М/2, т.е. удвоение пропускной способности лучше, чем добавление второй линии (если это оправдано стоимостью и надежностью оборудования). μE (T ) 3 M/M/2 M/M/1 2 1 M/M/12 μ 0,5 1 ρ λ 2μ Рис.2.14. Сравнение нормированной задержки трех систем. 56 Для системы М/М/2 максимально возможная производительность составляет величину 2 , но она никогда не может быть достигнута, т.к. с вероятностью Р0 система пустая и с вероятностью Р1 используется только одна линия. Поэтому средняя производительность определяется как (2.30)   P1  2(1  P0  P1 )   . В справедливости последнего знака равенства легко убедиться, подставив в (2.30) Р0 и Р1 из (2.26) и (2.27). С учетом  (2.30) величину   можно рассматривать как отношение 2 средней производительности к максимальной. Система M/M/  . Здесь обслуживающая линия доступна любому клиенту, поступающему в систему. Поэтому очередей и блокировок не возникает, и для данной системы   const, .  n  n n    n     P  , где    . Из (2.25) Pn  P0  n! n!   n  Из условия нормировки P0 1     1 . С учетом того,  n1 n!    n  что 1     e  , для Р0 получаем P0  e  . Если данное значе n1 n!  ние вернуть в формулу для Рn , то получится Pn  e  формула Пуассона. 57 n - это n!  Среднее количество клиентов в системе: E (n)   nPn   n 0 (результат был получен выше при исследовании распределения Пуассона). Итак (2.31) E (n) M/M/   . Сравнение E (n) M/M/1  с  1  показывает, что E (n) M/M/ < E (n) M/M/1 . Это сравнение говорит о целесообразности увеличения числа обслуживающих линий, либо о необходимости управления интенсивностью входящего потока. Производительность системы , определенная «по входу» равна , т.к. для всех n выполняется  n   . Средняя задержка E (T )  E ( n) 1  .   (2.32) Это очевидно, т.к. очереди нет, и время задержки равно 1 среднему времени обслуживания . Производительность сис темы можно рассчитать и «по выходу» через интенсивность обслуживания с учетом  n  n   n 0 n 0     n Pn    nPn  E (n)   , (2.33) что совпадает с производительностью, определенной «по входу». Система с «нетерпеливыми» клиентами. Это - система с управлением входным потоком. Здесь  n   и  n   . Доступна одна обслуживающая n 1 линия, и, когда очередь становится большой – клиенты уходят. Для передачи пакетов это означает, что контроллер системы либо отводит новые поступления, либо блокирует систему, что приводит к уменьшению интенсивности поступлений. 58 Нетрудно убедиться, что из общей формулы (2.24) легко для данной системы получить Pn  P0 Pn  e  n  , где   . Значит в этой системе P0  e  , и  n! n . Следовательно n!  E (n)   nPn   . n 0 Производительность системы, определенная «по входу», запишется как  n 1    n1  e     1  1 .   n0 (n  1)! n 0 ( n  1)!        n Pn  e   n 0 2 3    последнее С учетом того, что e  1    1 2 1 2  3  выражение примет вид     e (e  1)  (1  e  ) .  (2.34) Этот результат можно получить и по-другому, если учесть, что для однолинейной системы с интенсивностью обслуживания  производительность равна (1  P0 ) . Но здесь P0  e  , что и дает результат (2.34). Зная E (n) и  можно найти нормированное среднее время задержки E (T ) E (T )   При   1 E (T )  E ( n)    ,  .    1 e (2.35) E ( n)   1    , (с уче  (1  e ) (1  1  )  2   ), т.е. задержка приближенно равна вретом e  1    2 мени обслуживания и   (1  e  )   .  59 Система остается стабильной и при больших , т.к. существует управление потоком. При этом растет средняя занятость системы E (n) и наиболее вероятны состояния с большими значениями n. Система M/M/N/0. Это частный случай системы M/M/ с конечным числом обслуживающих линий и без мест для ожидания (без накопителя) – см. рис.2.15. μ μ 1 λ 2 . . . μ N Рис. 2.15. Система M/M/N/0. Здесь  n  n, 1  n  N и  n   . При n=N все поступления блокируются. Мест для ожидания нет и поэтому – это система с потерями. Данная система является базовой моделью для анализа телефонных станций. Для системы M/M/ было получено Pn  P0 Здесь условие нормировки имеет вид n  , где   . n!    Pn  1 . Подставляя сю- n 0 да Pn получаем 1  N n  P0     , и возвращая теперь P0 в Pn имеем  n0 n!  60 n Pn  N n! n .   n! n 0 Блокировка наступает при n=N. Поэтому N PB  NN ! n .   n! n 0 (2.36) (2.37) Формула (2.37) – это распределение Эрланга 1-го рода или В-распределение. Найдем среднюю занятость системы. N E (n)   nPn  n 1  1 N n  n 0 n! n  (n  1)!  n 1 N  N n  n 0 n!  n1  (n  1)!  n 1 N  N n  n 0 n! , k   ( 1  P )  B k  0 k! N 1 т.е. E (n)  (1  PB ) . (2.38) При увеличении  вероятность блокировки стремится к единице PB  1 и E (n)  N . Производительность , определенная «по входу», равна   (1  PB ) , N N n 0 n 0 (2.39) или – «по выходу :     n Pn    nPn  E (n)  (1  PB ) . При увеличении  производительность стремится к своему максимальному значению   N . Это происходит тогда, когда     N , большинство вызовов блокируется и PB  1 .  61 Средняя задержка вызовов, которые приняты системой равна  1 , т.е.среднему времени обслуживания (продолжительности занятия). Это подтверждает формула Литтла E (T )  E (n) (1  PB ) 1   .  (1  PB )  (2.40) 2.5. Система обслуживания M/G/1. Здесь процесс поступлений – пуассоновский, система – однолинейная, ёмкость накопителя бесконечная, распределение времени обслуживания – произвольное, т. е. пакеты имеют случайную произвольно распределенную длительность. Так как предполагается общий характер статистики времени обслуживания и, соответственно, невыполнение условия отсутствия последействия уходов обслуженных клиентов, здесь нельзя использовать уравнения равновесия. Будем использовать подход, основанный на рассмотрении занятости накопителя: Пусть n j – число клиентов, остающихся в системе, если j –ый клиент покинул систему.  j - число клиентов, поступающих за время обслуживания j – го клиента.  n j  (n j  1)   j n j 1  1 Тогда , (2.41)  n j 1  0 n j   j или n j  n j 1  U (n j 1 )   j , где U(x) – единичная функция. (2.42)  U ( x)  1 x  1 .  U ( x)  0 x  0 Выражение (2.42) может быть записано и в других обозначениях, которые упростят запись некоторых используемых ниже формул. Вводя 62   a  a при a  0 ,    a  при a   завершение обслуживания ( j  1) клиента   n j 1 n j 1 nj j j 1  время обслуживан ия j  го клиента j 1 t Рис. 2.16. Анализ состояния накопителя. (2.42) перепишем в виде n j  (n j 1  1)    j . (2.43) Здесь в (2.42) и в (2.43) n j и  j независимые случайные величины. Распределение вероятностей nj – это распределение суммы случайных величин, найти которое довольно сложно, потому что при непосредственных вычислениях оно находиться как свёртка распределений. Чтобы упростить вычисление используется аппарат производящих функций. В первой главе уже было использовано это понятие, однако, здесь напомним, что для дискретной случайной величины n производящая функция имеет вид:  Gn ( z )  E ( z n )   P ( n  k ) z k , (2.44) k 0 где z – произвольное комплексное число, но такое, которое, дает сходимость в (2.44). Обозначая P(n  k )  Pk , получим  Gn ( z )   Pk z k . k 0 63 (2.45) Отметим, что свёртке распределений соответствует произведение производящих функций. Если w=x+y, то w x y x y Gw ( z )  E ( z )  E ( z )  E ( z ) E ( z ) . Напомним, что из (2.45) следует: Pn  1 d n Gn ( z )  n! dz n , (2.46) z 0 т. е. Pn, являющиеся вероятностями состояния системы, могут быть найдены из разложения Gn(z) в ряд по степеням z. Зная Pn, можно определить и другие характеристики системы. Из (2.43) следует Gn j ( z )  Ga  ( z )  G j ( z ) , (2.47) где под величиной а+ подразумевается (n j 1  1)  . Функцию распределения величины  j будем считать известной, поэтому G j (z ) всегда можно определить. Будем также предполагать, что в системе возможен стационарный режим и при этом индекс j можно опустить. Найдём Ga  (z ) согласно (2.45)       Ga  ( z )  P (n  1)   0  P (n  1)   1 z  P (n  1)   2 z 2  ... . (2.48) Из определения величины а+ следует, что (n  1)   0 (n  1)   1 при n  0 или n  1 и при n  2,3,... Поэтому: Ga ( z )  P0  P1  P2  z  P3  z 2  ... Из сравнения с Gn ( z )  P0  P1  z  P2  z 2  ... следует Ga  ( z )  P0  Gn ( z )  P0 . z Подставляя (2.49) в (2.47) получим: 64 (2.49) Gn ( z )  P0 ( z  1)G ( z ) . z  G ( z ) (2.50) В (2.50) величина P0 пока неизвестна. Ее можно определить из условия, аналогичного условию нормировки, Gn ( z ) z 1  1 . , т. к. G (1)  1 , по определению. Раскрыть неопределённость можно, разложив G (z ) в ряд Тейлора в окрестности точки z=1. При z  1 в (2.50) возникает неопределенность типа dG ( z ) G ( z )  G (1)  dz d 2 G ( z )  ( z  1)  dz 2 z 1 ( z  1) 2   ... (2.51) z! z 1 Вычислим производные, входящие в (2.51) dG ( z ) dz d 2 G ( z ) dz 2  z 1  z 1  d E z  1 dz  d Ez z 1  E z  1 dz    E (  1) z  2 z 1   z 1 z 1  E ( ) , (2.52)  E ( 2 )  E () .(2.53) Последовательное дифференцирование позволяет получить различные моменты случайной величины  . Именно поэтому G (z ) называют производящей функцией моментов. Теперь:  G ( z )  1  E ()( z  1)  E ( 2 )  E () ( z z!1) 2  ... (2.54) С учетом полученного выражения знаменатель выражения (2.50) примет вид   ( z  1) 2 z  G ( z )  ( z  1)1  E ()  E ( )  E ()  ... z! 2 (2.55) Подставляя (2.55) в (2.50) и положив z=1, с учётом Gn ( z ) z 1  1 получим P0  1  E () . 65 (2.56) (Сравним: для системы M/M/1 P0  1   ) Теперь для Gn (z ) можно окончательно получить: Gn ( z )  1  E ()( z  1)G ( z) . (2.57) z  G ( z ) Воспользуемся выражением (2.57) для анализа системы M/D/1. Как следует из обозначения, на входе системы действует пуассоновский поток пакетов и, все пакеты имеют одинаковую длину  0 . При пуассоновских поступлениях с интенсивностью  вероятность того, что за время обработки одного пакета в систему поступит k пакетов определится в виде Pk  P(  k )  e  0 ( 0 ) k , k! E ()   0 . где (2.58) (2.59) Предполагается, что  0  1 , т. к. это ограничивает скорость поступлений. Это условие эквивалентно условию   1 для 1 системы M/M/1. А величину  0  можно интерпретировать  как среднюю длину сообщения при экспоненциальном времени обслуживания в системе M/M/1. Ограничение  0  1 , как   1 , даёт гарантию режима статистического равновесия. дящая Для пуассоновского распределения вида (2.58) произвофункция имеет вид (с учетом разложения x 2 x3 e  1 x    ... ) 2! 3! x   k 0 k 0 G ( z )   Pk z k   e  0 ( 0 z ) k  e  0 (1 z ) . k! (2.60) Вычисление производной производящей функции подтверждает известный результат для пуассоновского распределения dG ( z ) dz  E ()   0 . z 1 66 Теперь для системы M/D/1 подставляя (2.60) в (2.57) получаем выражение производящей функции для случайной величины n в рассматриваемой модели (2.41) Gn ( z )  (1   0 )( z  1)e   0 (1 z ) z  e  0 (1 z ) . (2.61) Дифференцируя (2.61) можно найти среднюю занятость системы M/D/1, а разлагая в ряд по степеням z можно найти вероятности занятия буферной памяти. К сожалению, разложение Gn (z ) в ряд в общем случае представляет собой довольно сложную задачу. Вернёмся к системе M/G/1. Найдём P(  k ) - вероятность поступления ровно k пакетов за случайное время обслуживания  . Пусть w() - плотность распределения  . Тогда:  P(  k )   P(  k ) w()d . (2.62) В выражении (2.62) P(  k ) - вероятность поступления k пакетов при условии фиксации конкретного значения  (условная вероятность). Для пуассоновского потока P(  k )  ( ) k e   . k! Знание P(  k ) позволит найти порождающую функцию моментов для случайной величины . Для G (z ) теперь можно    ( ) k e   записать G ( z )   P(  k ) z k      k 0 k 0 0 k!  w()dz k .  Изменяя порядок суммирования и интегрирования с учётом того, что под знаком суммы – экспонента, получим:  G ( z )   e  (1 z ) w()d 67 Данный интеграл представляет собой преобразование Лапласа плотности вероятности w() . (Напомним, по определению преобразование Лапласа в данном контексте может быть  записано как F ( s)   e  s w()d , где s – комплексная перемен0 ная. Кроме того, если s принимает только мнимые значения, то преобразование Лапласа и преобразование Фурье совпадают, что позволяет нам считать производящую функцию аналогом характеристической функции). С учетом этого замечания последнее выражение для G (z ) запишется в виде G ( z )  F (1  z ) . (2.63) Конкретный вид функции F () определяется, естественно, заданной плотностью w() . Например, все сообщения имеют одинаковую длину  0 , что соответствует системе M/D/1. Тогда w()  (   0 ) . Подставляя эту плотность в выражение для G (z ) , получаем результат в виде (2.60). Если w()  e  , что соответствует системе M/M/1, то  преобразование Лапласа этой плотности дает F ( s)  , и для s порождающей функции G (z ) получаем G ( z )  F ((1  z ))   1  . (1  z )   (1  z )  1 Можно привести и другие примеры. Зная порождающую функцию G (z ) из (2.63) можно найти E () . По определению: E ( )  dG ( z ) dz Но из (2.63) 68 . z 1 dG ( z ) dz  z 1 dF ((1  z )) dz  Далее, т.к. F ( s)   e  s   z 1 dF ((1  z )) d ((1  z ))   z 1 dF ( s) . ds s 0  dF ( s) w()d , то      w()d  E () . ds s 0 Поэтому E ()  E () . (2.64) 1  - как в системе M/M/1, то E ()     1 . Теперь   из (2.56) P0  1  E ()  1   , что ранее было получено другим способом, и из (2.57) Если E ()  Gn ( z )  (1  )( z  1) F ((1  z )) . z  F ((1  z )) (2.65) Проверим формулу (2.65). Для системы M/M/1 F ((1  z ))  Тогда Gn ( z )  1 . (1  z )  1 1  - здесь   1 и z  1 , что необходимо для схо1  z димости Gn (z ) . Разложим (1  z ) 1 в ряд по степеням z:   Gn ( z )  (1  )  (z ) k   (1  ) k z k .    k 0 k 0 Pk Коэффициент при zk – это Pk, т. е. Pk  (1  ) k  P0  k , что было получено ранее. Теперь найдём Е(n) – среднее число сообщений в буфере. Зная порождающую функцию Gn (z ) , это можно сделать согласно ее свойствам: 69 E ( n)  dGn ( z ) dz . z 1 При этом выражение для Gn (z ) возьмем из общей формулы (2.57): Gn ( z )  1  E ()( z  1)G ( z ) . z  G ( z ) z  G ( z )( z  1)G ( z)  z  G ( z ) ( z  1)G ( z) . dGn ( z )  1  E () dz z  G ( z)2 / / При вычислении Е(n) по последней формуле следует следить за тем, чтобы подстановка z=1 не привела к возникновению не0 определенности типа . Покажем подробнее, как это следует сделать. z  G ( z)2  ( z  1) 2 1  E()2 Из (2.55): ( z  1) z  G ( z )  ( z  1)1  E ()  E ( 2 )  E () 2  ... z! Далее ( z  1)G ( z )/  G ( z )  ( z  1) dG ( z )  dz    . из (2..54)   G ( z )  ( z  1) E ()  ( E ( 2 )  E ())( z  1)  z  G ( z)/  1  E()  E( 2 )  E()( z  1) . z  G ( z)/ ( z  1)G ( z)  1  E()( z  1)G ( z)  E( 2 )  E()( z  1) 2 G ( z) G (1)  1. z  G ( z )( z  1)G ( z )/  ( z  1)1  E ()G ( z )  ( z  1) 2 1  E ()      ( z  1) 2 ( z  1) 3 ...   E ()  ( E ( )  E ())( z  1)  G ( z ) E ( )  E ()  2 2 2 70 2 z  G ( z)( z  1)G ( z)/  z  G ( z)/ ( z  1)G ( z) ={сократим сразу на ( z  1) 2 и подставим z=1}= E (  1  E ()E ()     )  E ( )  E ( 2 )  E ( )  2 2 E ( ) E ( ) E ( 2 ) E ( ) 2 2  E ( )  E ( )    E ( )  E ( )   E 2 ( )  2 2 2 2 2 С учётом E ()   E ( n)  dGn ( z ) dz  z 1   1  2  (1  ) , 2(1  ) (2.66) где  2  E ( 2 )  E 2 () - дисперсия случайной величины  . 2.6. Упрощенный вывод формулы для Е(n) системы M/G/1 Строгий вывод формулы для E(n) через производящую функцию, как видно, довольно сложен. Проще E(n) можно получить из (2.42). Возведём (2.42) в квадрат, возьмём математическое ожидание от обеих частей и положим j   : n 2j  n 2j 1  U 2 (n j 1 )   2j  2n j 1U (n j 1 )  2n j 1 j  2U (n j 1 ) j . (*) При j   из (2.42) следует E (U (n))  E ()   . Кроме того: E (U 2 (n))  E (U (n))   и EnU (n)  E (n) оба равенства следуют из определения U(n). Будем считать, что  j и n j 1 независимы, тогда E (n j 1 j )  E (n j 1 ) E ( j ) . С учетом сделанных замечаний формулу (*) перепишем в виде: E (n 2 )  E (n 2 )  E (U 2 (n)  E ( 2 )  2E (nU (n))  2E (n) E ()  2EU (n) Учтем также, что EU (n)  E (U (n)) E () т. к. случайные величины n и  независимы. Теперь 71 0    E ( 2 )  2E (n)  2E (n) E ()  2E () E (U (n)) , E ( 2 )    2 2 откуда E (n)  . 2(1  ) Т.к. E ( 2 )   2   2 , то для E(n) окончательно запишем  2  (1  ) , E ( n)  2(1  ) что совпадает с (2.66) Здесь  2 - дисперсия числа клиентов, поступающих в течение времени обслуживания. Найдём  2 . По определению дисперсии   2   k  E ()P(  k ) . (2.67) k 0 Поток заявок на обслуживание пуассоновский, поэтому для P(  k ) используем выражение (2.62), а E ()   , поэтому   ( ) k e       k  E () w()d . k! л 0 0 2  2 (2.68) Изменим порядок интегрирования и суммирования с учётом следующих соотношений: (k  ) 2  k 2  2k   2 , k 2 P(  k )  E (k 2 )   2k   E 2 (k )   ( ) 2 , 2 kP(  k )  2E (k )  2 ,  2  P(  k )   2 . В последних трех формулах использованы свойства распределения Пуассона. Теперь (2.68) преобразуется к виду  w()  ( )  2   2   2 ) d . Если в последней формуле учесть, что 72    w()d  E () E ()   ,     2 1 2 2 2 2  (  ) w()d    (   ) w()d   (   ) w()d   , 2 2 то для  2 можно окончательно записать  2    2  2 , (2.69) где  2 - дисперсия распределения времени обслуживания. Подставим теперь (2.69) в (2.66):  2  (1  ) E ( n)   2(1  )   2  2  (1  )    2  2       1  (1   2  2 ) 1  (1  2 )   2(1  ) 1   2   1   2  E ( n)  т. е.     1  (1   2  2 ) .  1   2  , (2.70) Формула (2.70) называется формулой Поллячека-Хинчина. Из формулы Литтла E ( n) 1    (2.71) E (T )   1  (1   2  2 ) .   (1  )  2  Здесь 1 - среднее время обслуживания.  В системе M/M/1 время обслуживания распределено 1 экспоненциально. Дисперсия этого распределения  2  2 . Под ставляя в (2.70), получаем: E (n)   , что совпадает с полу1  ченным ранее. Для системы M/D/1 все клиенты требуют одного времени обслуживания 1 , при этом  2  0 . Тогда:  73 E ( n)    (1  ) , 1  2 E (T )  1  (1  ) . (1  ) 2 (2.72) Можно считать, что система M/D/1 - это частный случай M/M/1 с наименьшей длиной очереди и задержкой. В заключение найдем среднее время ожидания E(W) для M/G/1: E (W )  E (T )  1 .  Подставим сюда E(T) из (2.71): 1 ) E (  2 ) 2  , 2(1  ) 2(1  )  ( 2  E (W )  где E ( 2 )   2  (2.73) 1 - второй момент распределения времени об2 служивания. 2.7. Система обслуживания G/M/1. Рассматриваемая система имеет один обслуживающий прибор при дисциплине обслуживания FIFO. Согласно описанной выше классификации систем массового обслуживания здесь предполагается, что промежутки времени между поступлениями распределены независимо с некоторой плотностью w(t ) и средним значением 1 . Время обслуживания распределено по экспоненциальному закону при средней интенсивности обслуживания . Будем рассматривать только установившийся режим. Ключевым понятием при описании системы, как и раньше, является состояние системы, где под состоянием понимается число клиентов в системе в некоторый фиксирован74 ный момент времени. Диаграмма состояний системы представлена на рис.2.17. νj nj n j 1 j 1 j t Рис.2.17. К определению состояния системы G/M/1 На рис.2.17 показана последовательность моментов поступления требований, отождествляемая с последовательностью точек временной оси, порождающей марковскую цепь с дискретными состояниями. Здесь введены следующие обозначения: n j - число клиентов в системе в момент поступления j-го требования на обслуживание,  j - число клиентов, обслуженных между поступлением j-1 и j-го требования. Согласно рисунку можно записать n j  n j 1  1   j . (2.74) Предполагая, что установившийся режим работы системы существует (в работе [4] показано, что для этого необходимо  выполнение условия   1 , где, как обычно,   ), вероятность  k-го состояния системы определим как qk  lim P(n j  k ) . j  (2.75) Определим теперь для рассматриваемой цепи вероятности перехода из одного состояния в другое в виде plk  Pn j  k / n j 1  l  . (2.76) По сути дела, вероятность перехода вида (2.76) есть вероятность того, что за промежуток времени между поступлениями будет обслужено l  k  1 требование. Из рис. 2.17 и оп75 ределения (2.76) следует, что число находящихся в системе требований в промежутке времени между поступлениями требований j-1 и j не может быть больше, чем l  1 . Поэтому plk  0 при k  l  1 , т.е. переход из состояния l в состояние k невозможен. На рис.2.18 представлена диаграмма вероятностей переходов марковской цепи, где указаны только переходы из состояния l. Pl ,l  2 . . 1  Pl , l 1 . . l-2 l-1 Pl , l 1 .l . . l+1 l+2 Pl1 Рис.2.18. Диаграмма вероятностей переходов марковской цепи для системы G/M/1 Если бы вероятности возможных переходов из одного состояния в другое были найдены, то, как показано в [4], для случая установившегося режима работы системы собственно вероятности состояний, введенные формулой (2.75), могли бы быть найдены из решения системы линейных алгебраических уравнений, матричная форма записи которых имеет вид q  qP , (2.77) где: q  [q0 , q1 , q2 , ] - матрица-строка вероятностей состояний, размерность которой определяется интересующим нас набором состояний, P – матрица, элементы которой совпадают с вероятностями plk перехода за один шаг. Задача состоит в том, чтобы найти эти вероятности перехода. Для этого рассмотрим четыре области на плоскости (l, k), изображенные на рис.2.19. 76 Для области 1 , где для индексов l и k справедливо соотношение k  l  1 , выше было выяснено, что здесь plk  0 . В области 2 для индексов l и k соотношение определяется неравенствами k  l  1  1линия , что соответствует тому случаю, когда требование Рис.2.19. Границы изменения индексов l и k при выводе формул для plk . не ждет, а сразу поступает на обслуживание. (Последняя единица в системе неравенств характеризует то, что мы рассматриваем однолинейную систему). За время между поступлениями требований закончится обслуживание l 1  k требований. Но в области 2 l=0 и k  1, поэтому ни одно требование не покинет систему. Т.к. время обслуживания распределено экспоненциально, вероятность этого события равна e t . Поэтому для единственной в этой области вероятности p 01 можно записать  p01   e t w(t )dt , (2.78) где w(t ) - плотность вероятности интервалов между приходом требований. Теперь рассмотрим область 3 , которая характеризуется неравенствами 1линия  k  l  1 . В этой области сосредоточены ве77 роятности p11 , p12 , p 22 , p32 , p 42 и т.д. Это – случай, когда обслуживающая линия занята на протяжении всего промежутка времени между поступающими требованиями, и они попадают в накопитель для ожидания. Т.к. время обслуживания в данной системе распределено экспоненциально, то число обслуживаний за время промежутка между поступающими требованиями распределено по закону Пуассона с параметром  (это будет, естественно, условная вероятность). Если ввести обозначение, что А – событие, состоящее в том, что на протяжении интервала времени t линия занята, то можно записать P(m требований обслужено / A)  (t ) m t e . m! (2.79) Как указывалось выше, чтобы перейти из состояния l в состояние k, необходимо, чтобы за время t было обслужено ровно l 1  k требований. Имея это в виду, для plk запишем   (t ) l 1k t e w(t )dt . ( l  1  k )! plk   P(l  1  k требований обслужено /A)w(t )dt   (2.80) Итак, в области 3 plk - это вероятность обслуживания l 1  k требований за промежуток времени, равный промежутку, когда обслуживающая линия остается занятой. Для области 4 соотношение между индексами l и k имеет вид: k  1линия  l  1 . Здесь ситуация такова, что поступающее требование застает требование на обслуживании и l -1 требований в очереди. Поступившее требование встает в очередь на обслуживание. Итак, в системе становится l требований, и предположим, что все их надо обслужить за время   t  , где t  время между поступающими требованиями. Если положить   t  , то с учетом того, что процесс обслуживания пуассонов() l   e , и тогда согласно вышеизложенному ский Pl ()  l! 78  () l   e w()d . l! plk  pl 0   (2.81) Таким образом, выражения (2.77), (2.78), (2.80) и (2.81) дают описание вероятностей перехода и вероятностей состояний для системы G/M/1. В фундаментальной работе [4] по теории массового обслуживания, показано, что для вероятностей состояния системы справедлив следующий результат qk  (1  ) k , k  0, 1, 2,  (2.82)  где  - единственное решение уравнения    e  (1 )t w(t )dt в об0 ласти 0    1 . Там же показано, что система G/M/1 приводит к геометрическому распределению числа требований (клиентов) в моменты поступления нового требования и распределение времени ожидания имеет такую же форму как распределение времени ожидания в системе М/М/1 при выполнении условия    . 2.8. Системы обслуживания с относительными приоритетами. Классы приоритетов вводятся в вычислительных системах, в управляющих системах, в сетях коммутации пакетов для предотвращения перегрузок. Смысл введения относительных приоритетов рассмотрим на примере, заимствованном из [6]. Пример. Рассмотрим сеть с коммутацией пакетов. Кроме обычных (информационных) пакетов по сети необходимо передавать и управляющие пакеты, которые должны обрабатываться без задержки. Эти пакеты по размеру существенно меньше информационных, они несут в себе информацию, необходимую для управления работой сети, и поэтому не могут ждать в очереди. 79 Пусть скорость обработки в обслуживающем устройстве бит . Присвоим индекс 2 пакетам данных (информациv  9600 с онным пакетам), а индекс 1 – управляющим пакетам. Средняя длина пакетов данных – 960 бит. С учетом 1 справедливости соотношения   , где µ - средняя интенсив ность обслуживания, а  - средняя длина пакета (в единицах времени), для пакетов данных можно записать  2 =0,1с. Будем также предполагать, что дисперсия длины пакета  2 в данном 2  1  случае выбирается равной   2  . Тогда для второго мо 2  мента распределения времени обслуживания пакетов данных 2 2 2  1  можно записать E ( )      3  .  2  Постоянная длина управляющих пакетов – 48 бит, по1 этому 1   0,005 с и 12  0. 1 Пусть 20% нагрузки создается управляющими пакетами, 80% пакетами данных, т.е. 1  0,2 и  2  0,8 , где  - интенсив пакет  ность поступлений с размерностью  .  с  2 2 2 В качестве системы обслуживания выберем систему M/G/1. Если приоритетов нет, то на входе системы действует комбинированный входящий поток с интенсивностью комбинированной нагрузки   1   2 . Т.к. пакеты поступают случайно с интенсивностями  1 и  2 , то второй момент распределения для комбинированного потока имеет вид:   E 2  1   E 12  2  E  22 .     80   Пусть   1   2  Т.к. 1    0,5 . 1 1 и 2  2 2 то  0,2 0,8  0,2 0,8  . Откуда     1 2  1  2    0,2 0,8  1  2  6,17 пакет . с Среднее время ожидания для пакетов любого типа (см. формулу 2.73)   E  2 E W    148 мс. 21   Итак, управляющие пакеты длиной 48 бит, требующие для передачи 5 мс, могут оказаться в очереди за пакетами длиной 100 мс и должны ждать в очереди в среднем 148 мс. Введение приоритетного обслуживания позволяет существенно уменьшить время ожидания в очереди для управляющих пакетов. Существует 2 типа приоритетов: относительный и абсолютный. Относительный приоритет характеризуется тем, что пакеты более высокого приоритета становятся в очереди впереди пакетов низшего приоритета, но не вытесняют пакетов низшего приоритета, находящихся на обслуживании. При абсолютном приоритете - обслуживание прерывается, если там находится пакет низшего приоритета и возобновляется после того, как будут обслужены пакеты с более высокими приоритетами. Рассмотрим более подробно систему с относительными приоритетами. Пусть в очереди есть клиенты r классов приоритетов, порождаемые потоками с интенсивностями 1 ,  2 ,..... r . Все потоки – пуассоновские. Введем в рассмотрение величины 1 , k  1 ,2,......r - среднее время обслуживания клиентов k-го k 81 класса. Высший приоритет принадлежит классу 1, низший – r - му классу. Рассмотрим класс p , 1  p  r . Клиент поступает в момент t 0 и ждет обслуживания W р ед. времени (см. рис.2.20) поступление клиента Wp начало обслуживания t0 t t1 Рис. 2.20. К расчету времени ожидания в системе с относительными приоритетами. Очевидно, W р - случайная величина. Она зависит от 3 величин: поступающий клиент должен ждать в течение случайного промежутка T0 пока закончится текущее обслуживание пакета, клиент должен ждать Tk единиц времени, пока закончится обслуживание всех клиентов класса k, высшего или равного классу p, которые находились в очереди в момент t 0 , клиент должен ждать случайное время Tk пока обслужатся клиенты каждого класса k, который выше класса p, поступивших в течение времени ожидания W р . Итак p p 1 k 1 k 1 W p  T0   Tk   Tk . (2.83) Усредним (2.83) p p 1 k 1 k 1 E (W p )  E (T0 )   E (Tk )   E (Tk ) . Определим составляющие формулы (2.84). 82 (2.84) Величина E (Tk ) возникает за счет E (mk ) клиентов класса k, ожидающих в системе. Каждый из них требует на обслужива1 ние в среднем ед. времени, поэтому k E ( mk ) . (2.85) E (Tk )  k Согласно формуле Литтла E (mk )   k E (Wk ) , (2.86) где E (Wk ) - среднее время ожидания. E (mk )  k E (Wk )  E (Tk )     k E (Wk ) ,  k  k . (2.87) k k k Аналогично E (Tk ) - возникает за счет поступления в среднем E (mk' ) клиентов класса в k течение промежутка E (W p ) .Интенсивность поступлений -  k , время обслуживания - 1 , поэтому k E (Tk' )   k E (W p ) k   k E (W p ) . (2.88) ' Подставим E (Tk ) и E (Tk ) в (2.84) p  1 k 1 k 1 E (W p )  E (T0 )    k E (Wk )    k E (W p ) p или: E (W p )  E (T0 )    k E (Wk ) k 1 p 1 1   k . (2.89) k 1 Решать эти уравнения следует рекуррентно, начиная с высшего класса: E (T0 )  1 E (W1 ) для p=1 E (W1 )  , откуда следует 1 E (T0 ) E (W1 )  , (2.90) 1  1 83 E (T0 )  1 E (W1 )   2 E (W2 ) . В последнюю формулу 1  1 подставим E (W1 ) и получим E (W2 )  для p=2 E (T0 )  E (T0 )(1  1 ) E (T0 ) 1  1 1  2 E (W2 )    . (2.91) 1  1   2 1  1   2 (1  1   2 )(1  1 ) Этот процесс можно продолжить, перебирая все более высокие значения р. В общем виде формула для E (W p ) будет иметь вид E (T0 )  1 E (W p )  p где  p    k ,  k  k 1 E (T0 ) , (1   p )(1   p 1 ) (2.92) k k В (2.92) осталась не определенной одна составляющая - E (T0 ) . Определим ее. Для этого рассмотрим систему M/G/1 с одним классом требований. Сравним (2.90) и (2.73), т.е. E (W1 )  E (T0 ) E (T 2 ) и E (W )  . 1  1 2(1  ) Из сравнения следует E (T 2 ) . (2.93) 2 В более общем случае для системы с несколькими классами требований (r) E (T0 )  E (T0 )  E (T 2 )  r  k 1 r   E ( 2k )    k E ( 2k ) . 2 2 k 1  2 k 1 (2.94) Вернемся к примеру в начале раздела. Очевидно, управляющим пакетам можно присвоить 1 класс приоритета, а пакетам данных – 2. При   0,5 из (2.90) и (2.91) следует: E (W1 )  74,5 мс, E (W2 )  149 мс. В системе без приоритетов E(W)=148мс. Таким образом, влияние на время ожидание пакетов 2-го класса в системе с приоритетами пренебрежимо мало, зато 1-ый класс выиграл в 2 раза. 84 При введении приоритетов действует закон сохранения, который формально можно отобразить соотношением r  k 1 k E (Wk )  E (W ) , (2.95) где E(W) - время ожидания в системе M/G/1 с дисциплиной обслуживания FIFO. Это время находится согласно формуле (2.73). В нашем примере при отсутствии приоритетов E(W )  0,5  148  74 мс. При введении приоритетов: 1 E (W1 )   2 E (W2 )  74 мс. Закон сохранения установлен Л. Клейнроком и является частным случаем более общего закона для систем с сохранением работы. 85 Литература: 1. Хинчин А. Я. Работы по математической теории массового обслуживания. – М.:Физматгиз, 1963г. 2. Саати Т. Л. Элементы теории массового обслуживания и её приложения.- М.:Сов. Радио, 1965г. 3. Кофман Л., Крюон Р. Массовое обслуживание. Теория и приложения. – М.: Мир, 1965г. 4. Клейнрок Л. Теория массового обслуживания. – М.:Машиностроение, 1979г. 5. Овчаров Л. А. Прикладные задачи теории массового обслуживания.- М.: Машиностроение, 1969г. 6. Шварц М. Сети связи. Том 1. – М.: Наука, 1992г. 7. Шварц М. Сети ЭВМ. Анализ и проектирование.-М.: Сов.Радио, 1981г. 8. Градштейн И.С., Рыжик И.М. Таблицы интегралов, сумм, рядов и произведений.-М.: Наука, 1971г. 86