Системы массового обслуживания

План лекции

1. Основные понятия и характеристики СМО

2. Классификация систем массового обслуживания

3. Пуассоновский поток и марковские процессы

4. Формула Литтла

5. Модель M/M/1

6. Модель M/M/c (многоканальная)

7. Модель M/M/1/K (с ограниченной очередью)

8. Программная реализация

1. Основные понятия

Система массового обслуживания (СМО / Queueing System) — это система, в которой поступающие заявки обслуживаются каналами обслуживания с образованием очередей при занятости каналов.

Примеры СМО:

• Кассы в магазине, билетные кассы
• Серверы в компьютерной сети
• Call-центры, больницы
• Процессоры, принтеры, базы данных

Основные элементы СМО

Характеристики СМО

2. Классификация: нотация Кендалла

Нотация Кендалла: $A / B / c / K / N / D$

Пример: $M/M/1$ — экспоненциальный поток, экспоненциальное обслуживание, 1 канал.

Классификация по типу

3. Пуассоновский поток заявок

Простейший (пуассоновский) поток обладает тремя свойствами:

1. Стационарность — вероятность поступления $k$ заявок за интервал $\tau$ зависит только от длительности $\tau$, а не от его положения на оси времени
2. Ординарность — заявки поступают по одной, а не пачками
3. Отсутствие последействия — число заявок на непересекающихся интервалах независимо

Вероятность поступления $k$ заявок за время $\tau$:

$$P_k(\tau) = \frac{(\lambda \tau)^k}{k!} e^{-\lambda \tau}$$

Свойства пуассоновского потока

Интервалы между поступлениями распределены по экспоненциальному закону:

$$f(t) = \lambda e^{-\lambda t}, \quad t \geq 0$$

Математическое ожидание интервала: $E[T] = 1 / \lambda$

Дисперсия: $D[T] = 1 / \lambda^2$

Свойство суперпозиции: сумма $n$ независимых пуассоновских потоков с интенсивностями $\lambda_1, \ldots, \lambda_n$ — пуассоновский поток с интенсивностью $\lambda = \sum_{i=1}^{n} \lambda_i$.

Марковские процессы

Граф состояний для $M/M/1$:

Уравнения Колмогорова

Уравнения равновесия (для стационарного режима):

Для каждого состояния: интенсивность входящего потока = интенсивности исходящего потока

$$\lambda p_0 = \mu p_1$$

$$\lambda p_{i-1} + \mu p_{i+1} = (\lambda + \mu) p_i, \quad i \geq 1$$

Условие нормировки: $\sum_{i=0}^{\infty} p_i = 1$

Из первого уравнения: $p_1 = \rho p_0$, $p_2 = \rho^2 p_0$, ...

$$p_i = \rho^i p_0, \quad i = 0, 1, 2, \ldots$$

4. Формула Литтла

Формула Литтла (1961) — один из важнейших законов теории СМО:

$$L = \lambda W$$

$$L_q = \lambda W_q$$

Где:

• $L$ — среднее число заявок в системе
• $W$ — среднее время пребывания заявки в системе
• $L_q$ — среднее число заявок в очереди
• $W_q$ — среднее время ожидания

Дополнительно: $W = W_q + 1 / \mu$

Формула Литтла справедлива для любых СМО с любыми распределениями при стационарном режиме.

Формула Литтла — интерпретация

$$L = \lambda W \quad \Longleftrightarrow \quad \text{«сколько в системе»} = \text{«скорость входа»} \times \text{«время в системе»}$$

Примеры:

• В магазине: $\lambda = 10$ чел/ч, $W = 0.5$ ч $\Rightarrow$ $L = 5$ человек в магазине
• На сервере: $\lambda = 100$ запр/с, $W = 0.01$ с $\Rightarrow$ $L = 1$ запрос в системе
• На дороге: $\lambda = 30$ авт/мин, $W = 2$ мин $\Rightarrow$ $L = 60$ автомобилей на участке

5. Модель M/M/1

Условия: пуассоновский вход ($\lambda$), экспоненциальное обслуживание ($\mu$), 1 канал, неограниченная очередь, бесконечный источник.

Условие существования стационарного режима: $\rho = \lambda / \mu < 1$

Стационарные вероятности:

$$p_i = (1 - \rho) \rho^i, \quad i = 0, 1, 2, \ldots$$

$$p_0 = 1 - \rho \quad \text{— вероятность простоя канала}$$

M/M/1: основные характеристики

M/M/1: проверка формулы Литтла

$$L = \frac{\lambda}{\mu - \lambda}, \quad W = \frac{1}{\mu - \lambda}$$

$$L = \lambda W \; \checkmark$$

$$L_q = \frac{\lambda^2}{\mu(\mu - \lambda)}, \quad W_q = \frac{\lambda}{\mu(\mu - \lambda)}$$

$$L_q = \lambda W_q \; \checkmark$$

$$W = W_q + \frac{1}{\mu} \; \checkmark$$

Пример: M/M/1

Сервер обрабатывает запросы: $\lambda = 3$ запр/мин, $\mu = 5$ запр/мин.

$$\rho = \frac{\lambda}{\mu} = \frac{3}{5} = 0.6$$

$$p_0 = 1 - 0.6 = 0.4 \quad \text{(40\% времени сервер простаивает)}$$

$$L = \frac{0.6}{1 - 0.6} = 1.5 \quad \text{заявки в системе}$$

$$L_q = \frac{0.6^2}{1 - 0.6} = 0.9 \quad \text{заявки в очереди}$$

$$W = \frac{1}{5 - 3} = 0.5 \text{ мин} = 30 \text{ с}$$

$$W_q = \frac{0.6}{5 \cdot 0.4} = 0.3 \text{ мин} = 18 \text{ с}$$

M/M/1: влияние нагрузки

$$L = \frac{\rho}{1 - \rho}, \quad W = \frac{1}{\mu(1 - \rho)}$$

Вывод: при $\rho \to 1$ характеристики растут гиперболически — система становится нестабильной.

6. Модель M/M/c

Условия: пуассоновский вход ($\lambda$), экспоненциальное обслуживание ($\mu$), $c$ каналов, неограниченная очередь.

Условие стационарности: $\rho_c = \dfrac{\lambda}{c\mu} < 1$

$$p_0 = \left[ \sum_{k=0}^{c-1} \frac{(c\rho_c)^k}{k!} + \frac{(c\rho_c)^c}{c! (1 - \rho_c)} \right]^{-1}$$

$$p_n = \begin{cases} \dfrac{(c\rho_c)^n}{n!}\, p_0 & \text{при } n \leq c \\[6pt] \dfrac{c^c \rho_c^n}{c!}\, p_0 & \text{при } n > c \end{cases}$$

M/M/c: основные характеристики

$$L_q = \frac{p_0 (c\rho_c)^c \rho_c}{c!\, (1 - \rho_c)^2}$$

$$W_q = \frac{L_q}{\lambda}$$

$$W = W_q + \frac{1}{\mu}$$

$$L = \lambda W$$

Вероятность ожидания (формула Эрланга C):

$$P(W_q > 0) = \frac{(c\rho_c)^c}{c!\,(1 - \rho_c)}\, p_0$$

Пример: M/M/c

$\lambda = 3$ запр/мин, $\mu = 2$ запр/мин, сравним $c = 1, 2, 3$.

$c = 1$: $\rho = 3/2 > 1$ — стационарный режим не существует!

$c = 2$: $\rho_c = 3/4 = 0.75$

$$p_0 = \left[1 + \frac{3}{2} + \frac{(3/2)^2}{2!\,(1 - 0.75)}\right]^{-1} = \frac{1}{1 + 1.5 + 4.5} = \frac{1}{7} \approx 0.143$$

$$L_q = \frac{(1/7) \cdot (1.5)^2 \cdot 0.75}{2! \cdot (0.25)^2} = \frac{0.241}{0.125} \approx 1.93$$

$$W_q = 1.93 / 3 \approx 0.64 \text{ мин}, \quad W = 0.64 + 0.5 = 1.14 \text{ мин}$$

Пример: M/M/c — сравнение

Вывод: добавление третьего канала сокращает очередь в 10 раз и время ожидания — более чем в 10 раз.

7. Модель M/M/1/K

Условия: 1 канал, очередь ограничена длиной $K - 1$ (всего $K$ мест в системе).

Если $K$ мест заняты — заявка получает отказ.

Стационарный режим существует всегда (при $\rho < 1$ и при $\rho \geq 1$).

$$p_i = \begin{cases} \dfrac{1 - \rho}{1 - \rho^{K+1}} \rho^i & \text{при } \rho \neq 1 \\[6pt] \dfrac{1}{K + 1} & \text{при } \rho = 1 \end{cases}$$

M/M/1/K: основные характеристики

$$L = \frac{\rho}{1 - \rho} - \frac{(K + 1)\rho^{K+1}}{1 - \rho^{K+1}}, \quad \rho \neq 1$$

$$L_q = L - (1 - p_0)$$

$$\lambda_{\text{эфф}} = \lambda(1 - p_K)$$

$$W = \frac{L}{\lambda_{\text{эфф}}}, \quad W_q = \frac{L_q}{\lambda_{\text{эфф}}}$$

Вероятность отказа: $P_{\text{отк}} = p_K = \dfrac{(1 - \rho)\rho^K}{1 - \rho^{K+1}}$

Относительная пропускная способность: $Q = 1 - p_K$

Пример: M/M/1/K

$\lambda = 3$, $\mu = 2$, $K = 5$ (5 мест в системе: 1 обслуживание + 4 в очереди).

$$\rho = 1.5$$

$$p_0 = \frac{1 - 1.5}{1 - 1.5^6} = \frac{-0.5}{1 - 11.39} = \frac{0.5}{10.39} \approx 0.048$$

$$P_{\text{отк}} = p_5 = \frac{0.5 \cdot 1.5^5}{10.39} = \frac{0.5 \cdot 7.59}{10.39} \approx 0.365$$

$$Q = 1 - 0.365 = 0.635 \quad \text{(63.5\% заявок обслуживаются)}$$

$$\lambda_{\text{эфф}} = 3 \cdot 0.635 = 1.906$$

$$L = \frac{1.5}{1 - 1.5} - \frac{6 \cdot 1.5^6}{1 - 1.5^6} = \frac{-1.5}{-0.5} - \frac{6 \cdot 11.39}{10.39} = 3 - 6.58 = \approx 2.51$$

8. Программная реализация

import math

def mm1(lam, mu):
    rho = lam / mu
    if rho >= 1:
        return None
    p0 = 1 - rho
    L = rho / (1 - rho)
    Lq = rho**2 / (1 - rho)
    W = 1 / (mu - lam)
    Wq = rho / (mu * (1 - rho))
    return {'rho': rho, 'p0': p0, 'L': L, 'Lq': Lq, 'W': W, 'Wq': Wq}

result = mm1(3, 5)
print(f"L={result['L']:.2f}, W={result['W']:.2f}")
# L=1.50, W=0.50

Программная реализация: M/M/c

def mmc(lam, mu, c):
    rho_c = lam / (c * mu)
    if rho_c >= 1:
        return None

    a = lam / mu
    p0_sum = sum(a**k / math.factorial(k) for k in range(c))
    p0_sum += a**c / (math.factorial(c) * (1 - rho_c))
    p0 = 1 / p0_sum

    Lq = p0 * a**c * rho_c / (math.factorial(c) * (1 - rho_c)**2)
    Wq = Lq / lam
    W = Wq + 1 / mu
    L = lam * W
    P_wait = a**c * p0 / (math.factorial(c) * (1 - rho_c))

    return {'p0': p0, 'L': L, 'Lq': Lq, 'W': W, 'Wq': Wq, 'P_wait': P_wait}

print(mmc(3, 2, 2))
# {'p0': 0.143, 'L': 3.43, 'Lq': 1.93, 'W': 1.14, 'Wq': 0.64, 'P_wait': 0.643}

Программная реализация: M/M/1/K

def mm1k(lam, mu, K):
    rho = lam / mu

    if abs(rho - 1) < 1e-10:
        p0 = 1 / (K + 1)
    else:
        p0 = (1 - rho) / (1 - rho**(K + 1))

    L = 0
    for i in range(K + 1):
        L += i * p0 * rho**i

    pK = p0 * rho**K
    Q = 1 - pK
    lam_eff = lam * Q
    Lq = max(L - (1 - p0), 0)
    W = L / lam_eff if lam_eff > 0 else 0
    Wq = Lq / lam_eff if lam_eff > 0 else 0

    return {'p0': p0, 'pK': pK, 'Q': Q, 'L': L, 'Lq': Lq, 'W': W, 'Wq': Wq}

print(mm1k(3, 2, 5))
# {'p0': 0.048, 'pK': 0.365, 'Q': 0.635, 'L': 2.51, 'Lq': 1.56, 'W': 1.32, 'Wq': 0.82}

Заключение

Ключевые выводы лекции

Вопросы для самоконтроля

1. Что такое система массового обслуживания? Назовите основные элементы.
2. Расшифруйте нотацию Кендалла $A/B/c/K/N/D$.
3. Какие свойства имеет пуассоновский поток заявок?
4. Сформулируйте и докажите формулу Литтла.
5. Выведите формулы для $L$, $L_q$, $W$, $W_q$ модели $M/M/1$.
6. При каком условии существует стационарный режим $M/M/c$?
7. Чем отличается $M/M/1$ от $M/M/1/K$?
8. Что такое вероятность отказа и относительная пропускная способность?

Рекомендуемые ресурсы