Три очереди: M/M/1, конечная ёмкость и бесконечно много серверов

Если различаешь ёмкость системы и число серверов, выводишь нормировку и учитываешь потери в законе Литтла, переходи к «Теперь сам».

Как думаешь, двойная скорость входа всегда даёт двойную очередь

У одного сервера интенсивность обслуживания μ=3 в минуту. При λ=1 средняя стационарная нагрузка равна 1/2 заявки. При λ=2 она уже равна 2 заявкам, то есть выросла в четыре раза. При приближении λ к 3 среднее растёт без ограничения. Линейный рост входа не означает линейного роста ожидания.

Теперь ограничим всю систему тремя заявками, включая обслуживаемую. Нагрузка не сможет превысить 3, даже если вход быстрее сервера. Но исчезнувшие заявки не стали обслуживаться быстрее: часть нового входа будет отклоняться. Нужны одновременно показатели нагрузки и потерь.

На что это похоже

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

Общий язык - число заявок в системе k. Для всех трёх моделей приход увеличивает k на 1, завершение уменьшает на 1. Разница появляется в допустимых состояниях и скорости уходов. Эти две детали и меняют равновесное распределение.

Механизм: что означают M/M/1 и состояние k

Первая M означает экспоненциальные независимые межприходные интервалы, то есть пуассоновский вход. Вторая - экспоненциальное обслуживание. Число после них задаёт число серверов; дополнительное K - полную вместимость системы, а не только места ожидания. Интенсивности λ,μ положительны. Сервер не простаивает, если есть работа; обслуживание каждой заявки независимо от входа. Для расчёта времени ниже используем порядок FIFO, первым пришёл - первым обслужен.

У M/M/1 из состояния k≥1 выходят два конкурирующих события: приход интенсивности λ и завершение интенсивности μ. При k=0 завершаться нечему. Локальный баланс между k и k+1 даёт πₖλ=πₖ₊₁μ, значит πₖ=π₀ρ^k, где ρ=λ/μ. Это следствие границы в нуле: общий баланс последовательно передаёт равенство потоков на следующие пары соседей.

Чтобы превратить веса в вероятности, суммируем их. Бесконечный ряд Σρ^k конечен только при ρ<1. Тогда π₀=1−ρ, πₖ=(1−ρ)ρ^k. При ρ=1 одинаковые веса не нормируются; при ρ>1 они растут. Бесконечную систему с такими интенсивностями нельзя описывать стационарной геометрической формулой с отрицательными «вероятностями».

Правило

M/M/1 при λ<μ имеет среднюю нагрузку L=ρ/(1−ρ)=λ/(μ−λ) и полное среднее время W=1/(μ−λ). Для M/M/1/K πₖ=ρ^k/(Σⱼ₌₀ᴷρ^j), k=0,…,K, при любом ρ>0. Для M/M/∞ стационарный закон Pois(λ/μ). В устойчивой системе закон Литтла связывает L и W: L=λэффW, где λэфф считает именно принятые заявки.

L включает обслуживаемых, W включает и ожидание, и обслуживание. У бесконечной M/M/1 среднее число ожидающих Lq=L−ρ, а среднее время в очереди Wq=W−1/μ=ρ/(μ−λ). Эти величины нельзя смешивать с L и W при сравнении систем.

Разбор: равновесие бесконечной очереди и время заявки

При λ=2,μ=3 имеем ρ=2/3, π₀=1/3, L=2, W=1 минуту. Среднее обслуживание длится 1/3 минуты, остальное среднее время 2/3 минуты приходится на ожидание. Дисциплина обслуживания не вошла в баланс численности: благодаря отсутствию памяти важно лишь, что занятый сервер завершает работу с интенсивностью μ.

Почему прибывший видит то же распределение, что наблюдатель времени? Доля времени состояния k равна πₖ, а интенсивность новых приходов из него всегда λ. Приходы, застающие k, имеют средний поток πₖλ. После деления на весь поток λ получаем долю πₖ. Это принцип PASTA: независимый пуассоновский вход видит доли времени. Маршрутизация, зависящая от состояния, потребовала бы нового анализа.

В FIFO заявка, увидевшая k в системе, ждёт k завершений перед своим и ещё своё обслуживание, в среднем (k+1)/μ. Усредняя по πₖ, получаем W=(L+1)/μ=1/(μ−λ). Отсюда L=λW. Общий смысл закона Литтла можно увидеть на временной диаграмме: площадь под числом активных заявок равна сумме их времён пребывания. Деление на длинное время наблюдения даёт среднее число, а число принятых заявок на единицу времени умножается на среднее пребывание. Для такого предела нужны устойчивость и существование соответствующих средних.

import math
from fractions import Fraction


def finite_queue(arrival, service, capacity):
    weights = [Fraction(arrival, service) ** k
               for k in range(capacity + 1)]
    total = sum(weights)
    pi = [w / total for w in weights]
    mean = sum(k * p for k, p in enumerate(pi))
    effective = arrival * (1 - pi[-1])
    return pi[0], pi[-1], mean, mean / effective


for arrival, service, capacity in [(2, 3, 3), (2, 2, 3), (4, 2, 3)]:
    p0, full, mean, time = finite_queue(arrival, service, capacity)
    print("λ μ K =", arrival, service, capacity,
          "π0 πK L W =", p0, full, mean, time)
print("бесконечная M/M/1, λ=2 μ=3: L=2, W=1")
mean = 3 * (1 - math.exp(-2))
print("M/M/∞, λ=6 μ=2 t=1: параметр =", f"{mean:.6f}")
print("P(пусто в t=1) =", f"{math.exp(-mean):.6f}")
print("стационарный параметр = 3")

λ μ K = 2 3 3 π0 πK L W = 27/65 8/65 66/65 11/19
λ μ K = 2 2 3 π0 πK L W = 1/4 1/4 3/2 1
λ μ K = 4 2 3 π0 πK L W = 1/15 8/15 34/15 17/14
бесконечная M/M/1, λ=2 μ=3: L=2, W=1
M/M/∞, λ=6 μ=2 t=1: параметр = 2.593994
P(пусто в t=1) = 0.074721
стационарный параметр = 3

Первые строки относятся к конечной ёмкости, а не к бесконечной модели. Дроби точные. В четвёртой строке отдельно показан бесконечный вариант λ=2,μ=3, поэтому его L=2 не противоречит первой строке с K=3. В последних строках уже бесконечно много серверов, а не мест ожидания.

Разбор: конечный буфер и очередь без ожидания

Для K=3, λ=μ веса состояний 0,1,2,3 одинаковы. Каждое имеет вероятность 1/4, средняя нагрузка 3/2, вероятность полной системы 1/4. В бесконечной модели с теми же интенсивностями стационара не было; конечная сумма изменила ответ. При ρ≠1 можно записать π₀=(1−ρ)/(1−ρ^(K+1)), но сумма весов работает и при ρ=1, без деления на ноль.

Доля отклонённых приходов равна πK по принципу PASTA. Принятая интенсивность λэфф=λ(1−πK). Поэтому W=L/λэфф, а не L/λ для всех входящих попыток. Например, при λ=4,μ=2,K=3 из программы получаем πK=8/15, λэфф=28/15, L=34/15, W=17/14. Перегрузка здесь проявилась потерями, а не отсутствием стационара.

У M/M/∞ при k заявках работают k независимых серверов. Суммарная интенсивность завершений kμ, поэтому баланс πₖλ=πₖ₊₁(k+1)μ даёт πₖ=π₀(λ/μ)^k/k!. Сумма весов exp(λ/μ), откуда π₀=exp(−λ/μ) и весь закон Pois(λ/μ). Ожидания в очереди нет; среднее время в системе 1/μ, поэтому L=λ/μ согласуется с Литтлом.

Для пустой при старте M/M/∞ закон в момент t тоже пуассоновский, но параметр m(t)=(λ/μ)(1−exp(−μt)). Условно на N(t)=n неупорядоченные приходы равномерны на [0,t]. Приход в момент s сохраняется до t с вероятностью exp(−μ(t−s)). Усреднение даёт p=(1−exp(−μt))/(μt) при t>0. По независимости приходов и обслуживаний это прореживает пуассоновский счётчик λt до Pois(λtp), то есть нужной формулы. При t→∞ параметр стремится к λ/μ. Если в начале уже были заявки, их ещё не завершённые обслуживания добавляются отдельно: формула пустого старта сама их не учитывает.

Что ломается без этого

Считают K местами только для ожидающих и получают лишнее состояние. В используемом обозначении K включает заявку в сервере. Или при λ≥μ выдают формулу бесконечной очереди за описание конечной: первая не нормируется, вторая имеет конечную сумму весов.

Ещё одна ошибка - смотреть только среднюю длину буфера. Малая нагрузка при высокой потере не означает хорошего обслуживания. Указывай и вероятность отказа, и принятое число заявок; иначе ограничение ёмкости может скрыть проблему входного потока.

Зачем это в работе

Эти модели дают первые проверки для серверов, сетевых буферов и числа активных независимых сессий. Они показывают нелинейный рост ожидания при приближении входа к мощности и различие потерь и задержек. Реальное время обработки может быть неэкспоненциальным, а поступления зависимыми; тогда полученные числа относятся к модели, и совпадение одной средней интенсивности не подтверждает её предпосылок.

Теперь сам

В M/M/1 λ=1,μ=2. Найди L, W и среднее число ожидающих Lq. Теперь добавь K=1: какие состояния остались и чему равна вероятность отказа?