Приложения теории массового обслуживания. Учебник для студентов высших учебных заведений, обучаемых по направлениею
 Скачать 1.27 Mb.
|
|
7.2 Система с неограниченной очередью M/M/m/∞ Полнодоступная СРИ с m серверами и неограниченным количеством мест ожидания в очереди обслуживает пуассоновский поток требований с дисциплиной обслуживания очереди FIFO. Интервал времени между требованиями и продолжительность их обслуживания имеют экспонентные законы распределения. Параметр потока требований λ, а среднее значение длительности обслуживания – x . Определить стационарное распределение вероятностей состояний системы P k (k = 0 … ∞) и характеристики QoS. Дискретные состояния системы S k изменяются при каждом событии поступления требования или окончании его обслуживания. Цепь Маркова с конечным количеством состояний дана в виде диаграммы переходов (рис. 7.2). Рисунок 7.2 – Диаграмма переходов m-серверной системы с очередью Параметр потока освобождения серверов системы µ рассчитывается по формуле (7.1). Интенсивность потока освобождения для состояний системы k = 0 … m зависит от k и определяется аналогично ее определению на диаграмме переходов рис. 7.1 – она есть переменной и равна kµ. Для состояний системы k = m … ∞ эта интенсивность неизменная и равна mµ, поскольку при этом уже есть очередь и изменение её состояния зависит от освобождения любого из всех m серверов. Поэтому, определение стационарных вероятностей состояний системы P k состоит из двух частей: для состояний системы k = 0 … m – количество занятых серверов или требований, которые обслуживаются; для состояний системы k = m … ∞ – количество занятых мест ожидания очереди, или требований, которые ожидают. Распределение количества занятых серверов определяется по алгоритму формул (7.2) – (7.8) и для состояний k = 0 … m имеем: 0 ! 1 P k P k k (k = 1, 2, … m)... (7.12) Для состояний k = m … ∞ уравнения баланса системы подобно (7.6), но при неизменной интенсивности потока освобождения серверов mµ имеем: 1 1 ) ( k k k P m P P m (7.13) Отсюда, если для состояний k = 0 … m аналогично формуле (7.7) 1 1 k k P k P , (7.14) … S m λ λ λ 2µ µ mµ … S 0 S 1 S 2 λ λ mµ mµ S m S m+ 1 λ … … 3µ 39 то для состояний k = m … ∞ 1 1 k k P m P (7.15) Результат решения уравнения (7.15) очевидный. Путем последовательной подстановки в (7.15) значений k = m + 1; k = m + 2; k = m + 3 и т.д. проверяем: m m k m k P m P m P m 1 ; m m k m m m k P P m m P m P m 1 2 ; m m k m m m m k P P m m m P m m P m P m 1 2 3 , а это (индукция) подтверждает, что для любого k = m … ∞ верно m m k k P P m (7.16) Поскольку из (7.12) для P m имеем: 0 ! 1 P m P m m , (7.17) то в итоге из (7.16) и (7.17) для состояний k = m … ∞ получается, что 0 ! 1 P m P m m k k m , (k = m … ∞)... (7.18) Формулы (7.12) и (7.18) определяют стационарное распределение вероят- ностей состояний системы P k для всех возможных значений k или состояний серверов и мест ожидания очереди. Вероятность P 0 для этого случая находим из условия нормировки 0 1 k k P , откуда подстановкой всех значений P k из (7.12) и (7.18) получаем (слагаемые, не зависящие от k, вынесены за знак 2-й суммы): 1 ! 1 ! 1 1 0 0 m k m k m m k k m m k P (7.19) Вторая сумма от k = m до ∞ существует только при условии (λ / mµ) < 1 (сходимость ряда по признакам Даламбера) и потому она рассчитывается по формуле суммы членов бесконечно убывающей геометрической прогрессии: m m m m m k k m k m k 1 1 0 (7.20) Подставив это выражение в (7.19) получаем: 1 1 0 0 ! 1 ! 1 m m m k P m m k k (7.21) 40 Использованное в (7.19) условие сходимости ряда (λ / mµ) < 1 совпадает с (7.10), которое есть условием эргодичности процесса. Это в свою очередь не позволяет бесконечно возрастать очереди, что есть залогом нормального функционирования всей системы. Поскольку Λ = λ / µ (и поэтому из (7.10) обязательно Λ < m), то уравнения (7.12), (7.18) и (7.21), окончательно определяющие стационарное распределение вероятностей состояний P k , можно записать в одной системе уравнений так: (7.24) ! ! (7.23) при ! (7.22) 1 при ! 1 1 0 0 0 0 m m m k P m k P m P m k P k P m m k k m m k k k k m Это есть второе распределение Эрланга, по которому можно рассчитать вероятность состояний (занятости серверов и мест ожидания в очереди) полнодоступной системы с неограниченной очередью при обслуживании пуассоновского потока требований. Основной характеристикой качества обслуживания этой системы есть вероятность ожидания P w>0 (W > 0 означает, что время ожидания есть), которую можно определить из функции распределения состояний системы P k . В условиях пуассоновского потока P w>0 равна вероятности занятости всех m серверов системы с учетом всех возможных состояний очереди (m серверов заняты и 0 требований в очереди, m серверов заняты и 1 требование в очереди, 2 требования в очереди и т.д., а потому не путать с состоянием P m ): m k k w P P 0 , (7.25) где k – состояние системы (0 < k m – серверы, m < k ∞ – очередь). Подстановкой (7.23) в (7.25) с учетом свойства (7.20) получим: 0 0 0 ! ! P m m m m P m P m m k m k m m k k w P (7.26) Подстановка (7.24) в (7.26) дает m m m k m m m P m m k k m w ! ! ! 1 0 0 (7.27) Формула (7.27) называется C-формулой Эрланга и обозначается С m (Λ). Для системы M/M/m/∞по ней можно рассчитать вероятность ожидания P w>0 (6.2). Данную формулу можно переписать так: 41 1 ! ! ! ! ! ! ! ) ( 0 0 0 m m m k m m m m m m m k m m m C P m m k k m m m m k k m m w Поделив числитель и знаменатель на m k k k 0 ! (см. 7.11) получаем: ) ( 1 ) ( 1 ) ( 1 ) ( ) ( m m m m m E m m E m m E m m E C Данная формула устанавливает взаимосвязь между B– и C-формулами Эрланга, а это позволяет рассчитывать значение вероятности С m (Λ) по значениям E m (Λ) формулы (7.11), приведенные в соответствующих таблицах. Очевидно, что при одинаковых условиях всегда вероятность С m (Λ) > E m (Λ). Если обозначим m , (7.28) где ρ – интенсивность удельной нагрузки (нагрузка на один сервер), то эту формулу можно записать так: ) ( 1 1 ) ( m m E C (7.29) Средняя длина очереди Q (среднее количество требований в очереди) может быть найдена из распределения вероятностей состояний системы P k при k = m+1, m+2, … , ∞ (в очереди 1, 2 и т.д. требований) по правилу вычисления математического ожидания: 1 ) ( m k k P m k Q Подставив из (7.23) вероятности состояний очереди P k имеем (слагаемые, которые не зависят от k вынесен за знак суммы): 1 0 ) ( ! m k m k m m m k P m Q 42 Известно, что 0 2 ) 1 ( i i x x ix , а потому 2 0 1 ! m m P m Q m (7.30) Из (7.17) и (7.26) следует, что вероятность состояния P m определится как 0 1 w m P m P (7.31) Подставив в (7.30) вместо вероятности 1 0 ! m P P m m , которая получена из формулы (7.17), а вместо P m ее значения из (7.31), после сокращений имеем: 0 w P m Q (7.32) Среднюю продолжительность ожидания для любого требования W получим из формулы Литтла – за W единиц времени ожидания в очередь поступит в среднем Q = ΛW требований, а поэтому с учетом (7.32) 0 1 w P m Q W (7.33) Среднюю продолжительность ожидания для задержанных требований t q получим из толкования величины Q, как интенсивности нагрузки, которая создается требованиями, ожидающими в очереди. Величина ΛP w>0 – это интенсивность потока требований из очереди, где каждое требование в среднем ожидает время t q . Итак, Q = ΛP w>0 t q , откуда с учетом (7.32) m P Q t w q 1 0 (7.34) Значения W и t q представлены в единицах средней продолжительности обслуживания. Такой нормированный вид показывает, во сколько раз эти значения возрастают или убывают по сравнению со средним временем обслуживания x . Из (7.33) и (7.34) получается очевидное соотношение: W ≤ t q Таким образом, все основные характеристики QoS найдены. Среднее количество требований в системе N (суммарно тех, что обслуживаются и тех, что ожидают обслуживания) определяется по формуле (6.3), а среднее время пребывания требования в системе T (состоит из среднего времени обслуживания и среднего времени ожидания) – по формуле (6.4). При проектировании систем распределения информации часто необходимо знать отдельные значения функции распределения времени ожидания требований в системе. Функция распределения времени ожидания в 43 системе P w>t – это вероятность того, что требование, поступающее в систему в любом из ее состояний, будет ожидать время свыше t. Для расчета этой вероятности используем условную вероятность P k(w>t) , которая толкуется как и предыдущая, но при условии поступления требования в состоянии системы k = m…∞... Поскольку ожидание возможно только в случае, когда заняты все m серверов системы, то по формуле полной вероятности получим: m k t w k k t w P P P ) ( (7.35) Требование, что ждет в очереди последним, начнет обслуживаться только при условии, если за время его ожидания t закончится обслуживание k – m + 1 требований (k – m есть длина очереди). Таким образом, время ожидания будет больше t, если за это время из очереди выйдет не больше k – m предыдущих требований. Итак, вероятность того, что требование, которое поступает в систему в состоянии k, будет ожидать время свыше t равна вероятности того, что за это же время освободится не больше i = k – m серверов. При экспонентном распределении продолжительности обслуживания поток освобождений серверов системы является пуассоновским с параметром mμ (рис. 7.2). Вероятность того, что за время t освободится точно i серверов рассчитывается по формуле Пуассона (4.5), а вероятность того, что освободится не больше k – m серверов равна сумме: m k j t m j t w k e j t m P 0 ) ( ! ) ( Подставив это выражение и (7.23) в формулу (7.35) и последовательно сокращая [2, с. 110] получим: m k m k j t m w t m j k t w e P e j t m P P 0 ) ( 0 ! ) ( Из этого по правилу определения математического ожидания рассчитаем среднюю продолжительность ожидания в системе W: m P e P dt P W w t m w t w 0 0 0 ) ( 0 , что при условии μ = 1 (означает, что W измеряется в единицах средней продолжительности обслуживания / 1 x ) дает аналогичный (7.33) результат. В системах распределения информации не всегда требования из очереди поступают на обслуживание в порядке поступления. Есть немало случаев, когда выбор из очереди случайный. Хотя дисциплина выбора из очереди не влияет на среднее время ожидания W, но случайный выбор из очереди увеличивает дисперсию времени ожидания сравнительно с выбором в порядке поступления. |