Очередь M/M/1: стационарность, загрузка и закон Литтла

Если различаешь ожидание в очереди и полное время в системе, листай до «Теперь сам».

Как думаешь, удвоится ли задержка при удвоении загрузки

Сервер обслуживает в среднем десять запросов в секунду. При поступлении пяти запросов среднее время в модели равно двум десятым секунды. При девяти оно уже секунда, хотя обслуживание одного запроса занимает в среднем ту же десятую секунды. Запас между потоком и производительностью важнее простого отношения «запросов стало вдвое больше».

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

Представь кассу, перед которой очередь то растёт, то сокращается. Если средняя скорость прихода близка к средней скорости обслуживания, случайная длинная серия приходов разбирается долго: свободных промежутков почти нет. При небольшом потоке та же серия рассасывается быстрее. Средняя свободная мощность определяет цену таких всплесков.

Механизм: баланс между соседними размерами очереди

Состояние N(t) - число клиентов в системе, включая того, кого сейчас обслуживают. За малое время приходит клиент с вероятностью примерно λ·dt. Если система непуста, обслуживание завершается с вероятностью примерно μ·dt. Экспоненциальное время не хранит возраст обслуживания, поэтому одного числа клиентов достаточно для марковского состояния. При другом распределении сервиса этого состояния может не хватить.

В стационарном режиме поток переходов из n в n+1 равен обратному: πₙλ=πₙ₊₁μ. Значит πₙ₊₁=ρπₙ. Нормировка геометрического ряда даёт π₀=1-ρ, но только при ρ<1. При равенстве ряд не суммируется, при большем отношении тем более. Поэтому стационарную формулу нельзя продолжить за границу загрузки и принять отрицательное среднее за ответ.

Суммируя n(1-ρ)ρⁿ, получаем L=ρ/(1-ρ). Закон Литтла следует из учёта суммарного времени пребывания всех клиентов за длинный период при устойчивом режиме: площадь под графиком числа клиентов равна сумме их времён в системе, с учётом граничных клиентов. После деления на длительность периода возникает L=λW.

Правило

Прежде чем применять стационарные средние, проверь λ<μ, единицы измерения и состав состояния. Время W включает обслуживание; время ожидания до начала обслуживания равно Wq=W-1/μ. Для непуассоновского трафика закон Литтла может сохраняться, а формулы M/M/1 - нет.

Разбор: задержка при приближении к пределу

from fractions import Fraction

MU = Fraction(10)


def stationary(arrival, service):
    rho = arrival / service
    if rho >= 1:
        return None
    length = rho / (1-rho)
    time = 1 / (service-arrival)
    waiting = time - 1/service
    assert length == arrival * time
    return rho, length, time, waiting


print("lambda: rho, L, W, Wq")
for arrival in (Fraction(5), Fraction(8), Fraction(9), Fraction(99, 10)):
    values = stationary(arrival, MU)
    print(str(arrival), *(str(x) for x in values))
print("lambda=10:", stationary(Fraction(10), MU))
rho = Fraction(4, 5)
print("Конечный буфер: K, L")
for capacity in (2, 5, 20, 100):
    weights = [rho**n for n in range(capacity+1)]
    total = sum(weights)
    probabilities = [w / total for w in weights]
    assert sum(probabilities) == 1
    length = sum(n*p for n, p in enumerate(probabilities))
    assert length < rho / (1-rho)
    print(capacity, f"{float(length):.6f}")

lambda: rho, L, W, Wq
5 1/2 1 1/5 1/10
8 4/5 4 1/2 2/5
9 9/10 9 1 9/10
99/10 99/100 99 10 99/10
lambda=10: None
Конечный буфер: K, L
2 0.852459
5 1.868332
20 3.804506
100 4.000000

Все основные величины посчитаны рационально, поэтому различия не связаны с округлением. При загрузке 99 процентов среднее число клиентов 99, а при 50 процентах всего один. Это эффект очереди в стационарной модели, не обещание точных значений конкретного сервера без проверки предпосылок.

Состояние ноль означает отсутствие и ожидающих, и обслуживаемого. Среднее число только ожидающих Lq=ρ²/(1-ρ): из общего числа в среднем вычитается один занятый сервер с вероятностью ρ. Его нельзя путать с общим L при интерпретации метрик.

Разбор: конечный буфер - другая система

При ограничении на K клиентов состояние K блокирует новые поступления. Геометрическая стационарная формула нормируется конечной суммой, поэтому существует и при ρ≥1, но появляются потери. В законе Литтла для принятых клиентов используется эффективная интенсивность λ·(1-π_K), а не весь предложенный поток.

Программа показывает нормировку конечной цепи при ρ=4/5 и растущем буфере: среднее приближается к бесконечной модели снизу. Это сравнение моделей, а не разрешение использовать формулу неограниченной очереди для потерь конечного буфера.

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

Значение μ - интенсивность, обратная среднему времени обслуживания. Подставив в формулу время вместо интенсивности, ты получишь неверные единицы и величины. Нельзя также объявить приход пуассоновским только по измеренному среднему: всплески и корреляции меняют задержки. Стационарность требует, чтобы параметры и режим не менялись на рассматриваемом масштабе.

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

При планировании мощности модель показывает, почему работа почти на пределе делает задержки чувствительными к небольшим изменениям потока. Она помогает выбрать запас и поставить вопросы к измерениям: независимы ли приходы, как распределено время сервиса, есть ли ограничения буфера? После этого модель сравнивают с реальными метриками, а не подменяют ими проверку предпосылок.

Теперь сам

Поступает восемь запросов в секунду, обслуживается в среднем десять. Найди загрузку, общее время в системе и время ожидания до обслуживания.