Очередь М/М/Ц

В теории массового обслуживания , дисциплине математической теории вероятностей , очередь M/M/c (или модель Эрланга – C) с несколькими серверами ) — это модель массового обслуживания . В обозначениях Кендалла оно описывает систему, в которой поступления формируют единую очередь и управляются процессом Пуассона , имеется c серверов, а время обслуживания заданий распределено экспоненциально. Это обобщение очереди M/M/1 , учитывающее только один сервер. Модель с бесконечным количеством серверов — это очередь M/M/∞ .

Определение модели

Очередь M/M/c — это случайный процесс, пространство состояний которого представляет собой набор {0, 1, 2, 3, ...}, где значение соответствует количеству клиентов в системе, включая всех, кто в данный момент обслуживается.

• Поступления происходят со скоростью λ в соответствии с процессом Пуассона и переводят процесс из состояния i в i +1.
• Время обслуживания имеет экспоненциальное распределение с параметром μ . Если заданий меньше c , некоторые серверы будут простаивать. Если заданий больше c , они помещаются в очередь в буфере.
• Буфер имеет бесконечный размер, поэтому количество клиентов, которые он может содержать, не ограничено.

Модель можно описать как цепь Маркова с непрерывным временем и матрицей скорости перехода.

$Q={\begin{pmatrix}-\lambda &\lambda \\\mu &-(\mu +\lambda )&\lambda \\&2\mu &-(2\mu +\lambda )&\lambda \\&&3\mu &-(3\mu +\lambda )&\lambda \\&&&&\ddots \\&&&&c\mu &-(c\mu +\lambda )&\lambda \\&&&&&c\mu &-(c\mu +\lambda )&\lambda \\&&&&&&c\mu &-(c\mu +\lambda )&\lambda \\&&&&&&&\ddots \\\end{pmatrix}}$

в пространстве состояний {0, 1, 2, 3, ...}. Модель представляет собой тип процесса рождения-смерти . Мы пишем ρ = λ /( c µ ) для обозначения загрузки сервера и требуем ρ < 1, чтобы очередь была стабильной. ρ представляет собой среднюю долю времени, в течение которого каждый из серверов занят (при условии, что задания, обнаруживающие более одного свободного сервера, выбирают свои серверы случайным образом).

Диаграмма пространства состояний для этой цепочки показана ниже.

Стационарный анализ

Количество клиентов в системе

Если интенсивность трафика больше единицы, то очередь будет неограниченно расти, но если загрузка сервера $\rho ={\frac {\lambda }{c\mu }}<1$ тогда система имеет стационарное распределение с функцией массы вероятности

$\pi _{0}=\left[\left(\sum _{k=0}^{c-1}{\frac {(c\rho )^{k}}{k!}}\right)+{\frac {(c\rho )^{c}}{c!}}{\frac {1}{1-\rho }}\right]^{-1}$$\pi _{k}={\begin{cases}\pi _{0}{\dfrac {(c\rho )^{k}}{k!}},&{\mbox{if }}0<k<c\\[10pt]\pi _{0}{\dfrac {(c\rho )^{k}c^{c-k}}{c!}},&{\mbox{if }}c\leq k\end{cases}}$

где π _k — вероятность того, что система содержит k клиентов.

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

${\text{ C}}(c,\lambda /\mu )={\frac {\left({\frac {(c\rho )^{c}}{c!}}\right)\left({\frac {1}{1-\rho }}\right)}{\sum _{k=0}^{c-1}{\frac {(c\rho )^{k}}{k!}}+\left({\frac {(c\rho )^{c}}{c!}}\right)\left({\frac {1}{1-\rho }}\right)}}={\frac {1}{1+\left(1-\rho \right)\left({\frac {c!}{(c\rho )^{c}}}\right)\sum _{k=0}^{c-1}{\frac {(c\rho )^{k}}{k!}}}}$

которая называется формулой Эрланга C и часто обозначается C( c , λ / μ ) или E2 _{, c} ( λ / μ ). Среднее количество заявок в системе (в обслуживании и в очереди) определяется выражением

${\frac {\rho }{1-\rho }}{\text{ C}}(c,\lambda /\mu )+c\rho .$

Период занятости сервера

Период занятости очереди M/M/c может относиться к:

• период полной занятости: период времени между прибытием, в результате которого обнаруживается c в системе -1 клиентов, до момента отправления, в результате которого система покидает систему с c -1 клиентами.
• период частичной занятости: период времени между прибытием, при котором система оказывается пустой, и отъездом, в результате которого система снова остается пустой.

Писать T _k = min( t: k заданий в системе в момент времени 0 ⁺ и k − 1 рабочих мест в системе в момент времени t ) и η _k ( s ) для преобразования Лапласа – Стилтьеса распределения T _k . Затем

1. Для k > c и T _k имеет то же распределение, что T _c .
2. Для k = c ,
   $\eta _{c}(s)={\frac {c\mu }{k\mu +s+\lambda -\lambda \eta _{c}(s)}}.$
3. Для k < c ,
   $\eta _{k}(s)={\frac {k\mu }{k\mu +s+\lambda -\lambda \eta _{k+1}(s)}}.$

Время ответа

Время ответа — это общее количество времени, которое клиент проводит как в очереди, так и в процессе обслуживания. Среднее время реагирования одинаково для всех трудосберегающих дисциплин обслуживания и составляет

${\frac {{\text{ C}}(c,\lambda /\mu )}{c\mu -\lambda }}+{\frac {1}{\mu }}.$

Клиенты в порядке очереди

Клиент либо получает немедленное экспоненциальное обслуживание, либо должен дождаться обслуживания k клиентов, прежде чем обслужит свое собственное обслуживание, таким образом испытывая распределение Эрланга с параметром формы k + 1.

Клиенты в дисциплине совместного использования процессоров

В очереди с общим процессором служебная мощность очереди распределяется поровну между заданиями в очереди. В очереди M/M/c это означает, что когда в системе имеется c или меньше заданий, каждое задание обслуживается со скоростью μ . Однако, когда в системе имеется более c заданий, скорость обслуживания каждого задания уменьшается и составляет ${\frac {c\mu }{n}}$ где n — количество рабочих мест в системе. Это означает, что прибытия после интересующей работы могут повлиять на время обслуживания интересующей работы. Было показано, что преобразование Лапласа – Стилтьеса распределения времени отклика является решением интегрального уравнения Вольтерра, из которого можно вычислить моменты. Было предложено приближение для распределения времени отклика.

Конечная емкость

В очереди M/M/ c / K только K клиентов могут стоять в очереди одновременно (включая тех, кто находится в обслуживании). ). Любые дальнейшие поступления в очередь считаются «потерянными». Мы предполагаем, что K ≥ c . Модель имеет матрицу скорости перехода

$Q={\begin{pmatrix}-\lambda &\lambda \\\mu &-(\mu +\lambda )&\lambda \\&2\mu &-(2\mu +\lambda )&\lambda \\&&3\mu &-(3\mu +\lambda )&\lambda \\&&&&\ddots \\&&&&c\mu &-(c\mu +\lambda )&\lambda \\&&&&&c\mu &-(c\mu +\lambda )&\lambda \\&&&&&&&\ddots \\&&&&&&&c\mu &-(c\mu )\\\end{pmatrix}}$

в пространстве состояний {0, 1, 2, ..., c , ..., K }. В случае, когда c = K , очередь M/M/ c / c также известна как модель Эрланга–Б.

Переходный анализ

См. Такач для временного решения. и Стадже за результаты напряженного периода.

Стационарный анализ

Стационарные вероятности определяются выражением

$\pi _{0}=\left[\sum _{k=0}^{c}{\frac {\lambda ^{k}}{\mu ^{k}k!}}+{\frac {\lambda ^{c}}{\mu ^{c}c!}}\sum _{k=c+1}^{K}{\frac {\lambda ^{k-c}}{\mu ^{k-c}c^{k-c}}}\right]^{-1}$

$\pi _{k}={\begin{cases}{\frac {(\lambda /\mu )^{k}}{k!}}\pi _{0}&{\text{for }}k=1,2,\ldots ,c\\{\frac {(\lambda /\mu )^{k}}{c^{k-c}c!}}\pi _{0}&{\text{for }}k=c+1,\ldots ,K.\end{cases}}$

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

$L={\frac {\lambda }{\mu }}+\pi _{0}{\frac {\rho (c\rho )^{c}}{(1-\rho )^{2}c!}}$

а среднее время пребывания клиента в системе равно

$W={\frac {1}{\mu }}+\pi _{0}{\frac {\rho (c\rho )^{c}}{\lambda (1-\rho )^{2}c!}}$

Среднее время пребывания клиента в очереди составляет

$W_{q}=\pi _{0}{\frac {\rho (c\rho )^{c}}{\lambda (1-\rho )^{2}c!}}$

Среднее количество клиентов в очереди можно получить, используя эффективную скорость поступления. Эффективная скорость поступления рассчитывается по формуле

$\mathbb {\lambda _{a}} =\lambda (1-p_{K})$

Таким образом, мы можем получить среднее количество клиентов в очереди по формуле

$L_{q}=\lambda _{a}W_{q}$

Реализацию приведенных выше вычислений на Python можно найти.

Ограничения на интенсивный трафик

Записав X ( t ) для числа клиентов в системе в момент времени t , можно показать, что при трёх различных условиях процесс

${\hat {X}}_{n}(t)={\frac {X(nt)-\mathbb {E} (X(nt))}{\sqrt {n}}}$

сходится к диффузионному процессу.

1. Зафиксируйте µ и c , увеличьте λ и масштабируйте на n = 1/(1 − ρ ) ² .
2. Зафиксируйте µ и ρ , увеличьте λ и c и масштабируйте на n = c .
3. Зафиксируйте как константу β, где
   $\beta =(1-\rho ){\sqrt {s}}$

и увеличьте λ и c, используя шкалу n = c или n = 1/(1 − ρ ) ² . Этот случай называется режимом Халфина–Уитта .

См. также

• Решение спектрального расширения
• Очередь M/G/k