Приложения теории массового обслуживания. Учебник для студентов высших учебных заведений, обучаемых по направлениею
 Скачать 1.27 Mb.
|
|
7.3 Система с ограниченной очередью M/M/m/r Полнодоступная СРИ с m серверами и ограниченным количеством мест ожидания в очереди r обслуживает пуассоновский поток требований с дисци- плиной обслуживания очереди FIFO. Интервал времени между требованиями и длительность их обслуживания распределены экспонентно. Интенсивность входной нагрузки Λ. Необходимо определить стационарное распределение вероятностей состояний системы P k (k = 0…m+r) и характеристики QoS. При ограниченной очереди, где количество мест ожидания r < ∞, имеем комбинированную систему M/M/m/r – с очередью и потерями. Если в момент поступления требования в системе есть хотя бы один свободный сервер, то оно сразу начинает обслуживаться. Если все серверы системы заняты, то требование становится в очередь при условии, что в ней ожидает меньше, чем r требований (есть места для ожидания). Если же в очереди есть уже r ранее поступивших требований, то текущее требование теряется. Итак, требованию отказывается в обслуживании, если в системе уже есть l = m + r требований. Из этих l требований m обслуживаются, а r ожидают в очереди. Очевидно, если r = 0, то система описывается моделью M/M/m и задача решается с помощью первого распределения Эрланга (7.11). Если r = ∞, то система описывается моделью M/M/m/∞ и задача сводится к предыдущей. Для комбинированной системы M/M/m/r, частично аналогичной системе M/M/m/∞, уравнения (7.22) и (7.23) определяют стационарное распределение вероятностей состояний системы P k для k = 1 … m и k = m … l соответственно. Поэтому вероятность P 0 определяется из условия нормирования l k k P 0 1, откуда подстановкой всех значений P k формул (7.22) и (7.23) получаем: 1 ! ! 1 0 0 l m k m k m m k k m m k P (7.36) Поскольку сумма от k = m до l может быть рассчитана по формуле суммы r = l – m членов геометрической прогрессии со знаменателем Λ / m, то 1 1 1 0 0 1 1 ! ! m m m k P r m m k k (7.37) Вероятность полной занятости системы P ЗН (ожидания или потери требо- вания) в этом случае определяется аналогично (7.26), но сумма будет не до ∞, а только до l. Заменив эту сумму подобно, как в формулах (7.36) и (7.37), имеем: m m P m m P m P r m l m k m k m l m k k P 1 1 ! ! 1 0 0 зн (7.38) 45 Подстановка P 0 из (7.37) в (7.38) дает m m m k m m m P r m m k k r m 1 1 ! ! 1 1 ! 1 1 0 1 зн Учитывая, что m m m 1 1 , данную формулу можно переписать так: 1 1 0 1 зн 1 ! ! 1 ! r m m k k r m m m m m k m m m m P (7.39) Очевидно, если r = ∞, то формула (7.37) совпадает с (7.24), а формула (7.39) – с C-формулой Эрланга (7.27). Если r = 0, то (7.37) совпадает с (7.9), а формула (7.39) – с B-формулой Эрланга (7.11). Из этого явствует, что при изменении длины очереди от ∞ до 0 величина вероятности P ЗН модели M/M/m/r находится в диапазоне значений, полученных по формулам (7.27) и (7.11) для моделей M/M/m/∞и M/M/m/0 соответственно. Таким образом, (7.39) есть обобщающее решение для полнодоступных систем с потерями, с неограниченной и ограниченной очередями при условии обслуживания пуассоновского потока требований и экспонентной продолжительности их обслуживания. Формулу (7.39) можно упростить таким же способом, как это получено в (7.29) с учетом (7.28) 1 1 зн ) ( 1 1 r m r E P (7.40) В системе с ограниченной до r очередью событие потери требования состоится в том случае, когда при поступлении требования в очереди уже есть r требований, которые поступили раньше. Ведь вероятность потери требования P B равна вероятности того, что в системе уже есть l = m + r требований (потому r = l – m ) или система в состоянии P l . Для пуассоновского потока вероятность P B = P l при любом законе длительности обслуживания. 46 Поэтому, в соответствии с (7.23) и (7.37) получим: m m m k m m P m P P r m m k k m r m l B m l m 1 1 ! ! ! ! 1 1 0 0 (7.41) Вероятность ожидания при ограниченной до r очереди P w>0 (r) или долю ожидающих требований рассчитаем так: P w>0 (r) = P ЗН – P B . Подставив сюда (7.39) и (7.41) соответственно имеем 1 1 0 ) ( 0 1 ! ! 1 ! r m m k k r m r w m m m m k m m m m P (7.42) Эту вероятность можно рассчитать аналогично формуле (7.38), но с верхней границей суммирования l – 1, что дает аналогичный результат : 0 1 0 1 ) ( 0 1 ! ! P m m m m m P m P r m l m k m k m l m k k r w P Формулу (7.41) с учетом (7.38) можно записать так: 1 зн 0 1 1 ! r r m B m m m P P m P m l m Учитывая (7.28), данную формулу можно упростить: 1 зн 1 ) 1 ( r r B P P (7.43) Подставив в (7.43) формулу (7.40) имеем 1 ) ( 1 1 r m r B E P Формулу (7.42) можно переписать не как разность (7.39) и (7.41), а как разность (7.40) и (7.43), что дает 47 1 0 ) ( 1 1 ) ( r m r w E r P Из (7.43) и учетом (7.16), где k = l и r = l – m, следует, что 1 1 ) 1 ( 1 1 1 зн r m r r l P P P Для односерверной системы M/M/1/r из (7.37), (7.39), (7.42) и (7.43) можно рассчитать: – вероятность P 0 (сервер и места в очереди свободные) из (7.37) – 2 1 1 0 1 1 1 1 1 r r P ; – вероятность P зн из (7.39) или P зн = 1 – P 0 , что дает 2 1 зн 1 ) 1 ( r r P ; – вероятность P w>0 (r) из (7.42) и подстановкой (7.28) дает 2 ) ( 0 1 ) 1 ( r r r w P ; – вероятность P B из (7.43) и подстановкой выше найденного P зн дает 2 1 1 ) 1 ( r r B P Из (7.18) следует, что в системе M/M/1/r состояния системы имеют распределение 2 0 1 ) 1 ( r k k k P P В системе M/M/1/∞ из этой формулы имеем геометрическое распределение состояний системы ) 1 ( k k P Таким образом, все характеристики качества обслуживания системы M/M/m/r найдены. 48 7.4 Система с неограниченной очередью M/D/m/∞ В ТКС, основанных на технологии коммутации пакетов, применяется дисциплина обслуживания с очередью. Есть системы, где время обслуживания постоянно, например, процесс обслуживания требований управляющими устройствами узлов коммутации или пакетов одинаковой длины. В модели M/M/m/∞ с экспонентным временем обслуживания требований вероятность ожидания рассчитана по C-формуле Эрланга (7.27). Для модели M/D/m/∞ с дисциплиной очереди FІFO есть решение К.Д. Кроммелина [3], на базе уравне- ний состояний Фрая. Решение системы уравнений методом производных функ- ций так сложно, что для инженерных расчетов вместо точных аналитических формул применяются соответствующие диаграммы (кривые Кроммелина). В [8] предложен более простой метод расчета модели M/D/m/∞, в котором используется C-формула Эрланга. Необходимо найти все характеристики качества обслуживания QoS: – среднюю продолжительность ожидания требований в системе W; – среднюю длину очереди Q; – среднее количество требований в системе N; – вероятность ожидания P w>0 ; – среднюю продолжительность ожидания требований в очереди t q Характеристики качества обслуживания модели M/M/m/∞ между собой функционально зависимы. Средняя длительность ожидания для любого требования W (которое ожидает и не ожидает) есть средним значением времени ожидания, отнесенным ко всем требованиям. Если же известна средняя длительность ожидания только задержанных требований t q , то для определения W необходимо умножить эту длительность на вероятность P w> 0 , показывающую среднюю долю задержанных требований. Поэтому, из (7.34) и (7.33) получаем 0 w q P t W (7.44) По формуле Литтла за W единиц времени ожидания в очередь поступит ΛW требований и поэтому W Q (7.45) Из этих соотношений характеристик QoS следует, что для анализа модели M/M/m/∞ с экспонентным (М) распределением длительности обслуживания надо рассчитать лишь среднюю длительность ожидания требований в очереди t q (7.34) и вероятность ожидания P w> 0 (7.27), так как среднюю длительность ожидания требований W (M) найдем из (7.33). Для расчета вероятности P w> 0 в модели M/D/m/∞ с постоянной длительностью обслуживания данный в п. 7.2 алгоритм определения состояний статистического равновесия системы применять нельзя. Теперь вероятность окончания обслуживания требования (при экспонентном распределении x пропорциональна mμ) определяется не количеством занятых серверов m (рис. 7.2), а моментами начала обслуживания, и потому будет зависеть от размещения исследуемого интервала на оси времени – процесс не будет эргодическим (см. п. 7.1). 49 Если теоретическое решение очень сложное, то нередко достаточно получить приближенное выражение, на котором может строиться весь метод расчета. Признанным методом аналитических приближений есть имитационное моделирование, позволяющее эффективно проверять качество используемых предположений. По результатам имитационного моделирования с применением алгоритма [9] установлено, что время ожидания W при постоянной (D) и экспонентной (M) длительности обслуживания в таком соотношении: 2 2 2 1 ) ( 2 ) ( ) ( m m m C m m W W m M D (7.46) Формула (7.46) определяет, что для многоканальной системы при m = Λ средняя длительность ожидания при постоянной и экспонентной длительности обслуживания отличаются в 2 раза, что соответствует такому же соотношению, установленному формулой Поллачека-Хинчина для односерверной системы. С возрастанием емкости системы m это соотношение спадает и имитационное моделирование свидетельствует, что в широком диапазоне изменения m и Λ точность оценки средней длительности ожидания (7.46) не хуже ±10 %. Вероятность ожидания P w>0 находим из функции распределения состояний системы P k и здесь вероятность P w>0 равна вероятности того, что при поступления требования оно застает все m серверов занятыми (7.25). Это можно записать так: 1 0 0 1 m k k m k k w P P P (7.47) В условиях неограниченного количества серверов (m = ∞) требования обслуживаются без потерь. При постоянной продолжительности обслуживания, когда нет потерь, свойства потока освобождений совпадают со свойствами потока поступления требований, так как происходит только сдвиг во времени на величину x между моментом поступления требования и моментом окончания его обслуживания. При этом состояние системы полностью определяется свойствами потока требований, а функции распределения количества требований в системе P k и количества требований P і , поступивших за время x , полностью совпадают с распределением Пуассона e i i i P P k ! (7.48) При конечном m и бесконечном количестве мест ожидания требования также обслуживаются без явных потерь. Однако, сейчас требования, поступаю- щие после занятия всех серверов системы, попадают в очередь на ожидание, и в случае освобождения хотя бы одного из m занятых серверов подаются из очереди на обслуживание. Теперь на серверы системы поступают требования из основного потока с интенсивностью Λи из очереди с интенсивностью ΛW. Таким образом, с учетом (7.45) суммарная интенсивность нагрузки на серверы системы увеличивается до величины = + Q. (7.49) 50 Интенсивность нагрузки равна среднему количеству требований в системе N (6.3). Из приведенных доводов получаем простой метод расчета характеристик качества обслуживания системы M/D/m/∞, состоящий из шести шагов: 1. По (7.29) при заданных Λ и m рассчитывается С m (Λ) для модели M/M/m/∞. 2. По (7.46) для заданных Λ и m определяется W (D) (аппроксимация). 3. По (7.45) для Λ и рассчитанного значения W (D) определяется Q. 4. По (7.49) рассчитывается суммарная интенсивность нагрузки 5. По (7.47) и (7.48) для рассчитывается вероятность ожидания P w>0 6. По рассчитанными W (D) и P w >0 из формулы (7.44) определяется t q Следует отметить, что при m близких к Λ, т.е. в диапазоне емкостей системы < m ( 2 / ), дополнительный поток требований из очереди сильно увеличивает не только суммарную интенсивность нагрузки , но и ее суммарную дисперсию 2 , которая для пуассоновского потока равна . Поэтому, в данном диапазоне емкостей системы для повышения точности расчета P w>0 и t q надо на шаге 5 вместо распределения Пуассона (7.48) использовать распределение нормального закона (Гаусса) с подстановкой (7.49) и 2 / 2 Q . Для исключения бесконечной очереди обязательно m > Λ. Оценка степени точности предложенного метода расчета характеристик QoS модели M/D/m/∞ проверена имитационным моделированием, результаты которого [9] подтвердили, что в широком диапазоне изменения m и Λ относительная ошибка расчета всех характеристик QoS не превышает ±10 %. Результатами имитационного моделирования с такой же точностью оценки определено и соотношения вероятностей ожидания при экспонентной и постоянной продолжительности обслуживания в моделях M/M/m/∞ и M/D/m/∞: 1 0 0 2 2 1 ) ( m m C P m w , (7.50) где P w > 0 – вероятность ожидания при постоянной, а С m (Λ) – при экспонентной продолжительности обслуживания. Из (7.44) следует, что вероятность ожидания при любых условиях – это соотношение средних длительностей ожидания в системе W и очереди t q Поэтому из (7.46) и (7.50) имеем среднюю продолжительность ожидания требований в очереди t q(D) при постоянной длительности обслуживания: 3 2 1 1 2 1 0 ) ( ) ( 2 1 2 ) ( 2 1 ) ( m m m m m m C m m m C P W t m w D D q . (7.51) 51 Анализируя формулы (7.46), (7.50) и (7.51) замечаем, что одноименные характеристики QoS в моделях M/M/m/∞ и M/D/m/∞ при экспонентной и постоянной продолжительности обслуживания связаны между собой такой аппроксимирующей функцией: k k m m k F 1 2 ) ( , (7.52) где k = 1, 2 и 3 для характеристик P w > 0 , W (D) и t q(D) соответственно. Итак, путем применения аппроксимирующей функции (7.52) могут быть рассчитаны основные характеристики качества обслуживания в модели M/D/m/∞ через C-формулу Эрланга, справедливую для модели M/M/m/∞: ) ( 2 ) ( 0 k F C P m w , ) 1 ( ) ( ) ( k F m C W m D , (7.53) 2 1 ) ( k F m t D q где k = 1 для всех приведенных характеристик. Имитационным моделированием установлено, что при замене в (7.53) коэффициента k = 1 на k = 0,01 (может быть не целым) точность оценки основных характеристик качества обслуживания повышается до ±5 %. Кроммелином рассмотрена система с очередью, в которой обслуживание ожидающих требований выполняется в порядке поступления (упорядоченная очередь). Но есть примеры систем с очередью, в которых обслуживание ожидающих требований выполняется при случайном выборе их из очереди. Однолинейная система с постоянной продолжительностью обслуживания и случайным выбором из очереди ожидающих требований исследована Берком [3]. Анализ распределения времени ожидания W в однолинейной системе с постоянной продолжительностью обслуживания при случайном выборе требований из очереди и выборе требований в порядке поступления показывает, что для небольших значений продолжительности ожидания (от 0,1 до 3 x ) качество обслуживания требований выше при случайном выборе из очереди. Для больших значений продолжительности ожидания (> 3 x ) качество обслуживания требований при случайном выборе из очереди существенно хуже, чем при обслуживании требований в порядке очереди. Следует напомнить вывод, сделанный в конце подраздела 7.2, что дисциплина выбора из очереди (в порядке поступления, случайном порядке или любой другой дисциплине) не влияет на среднее время ожидания требования начала обслуживания W, но влияет на дисперсию времени ожидания. |