Теория массового обслуживания
Теория очередей связывает поток заявок, время обслуживания, число каналов и дисциплину очереди с задержкой и пропускной способностью.
Элементы СМО
- поток заявок с интенсивностью ;
- время обслуживания или интенсивность одного канала;
- число каналов ;
- ёмкость очереди;
- дисциплина: FIFO, LIFO, приоритет, fair sharing;
- правила отказа, ожидания и повторной попытки.
Обозначение Кендалла A/S/c/K/N/D описывает распределение прихода, распределение обслуживания, число каналов, ёмкость, размер источника и дисциплину. Короткая запись M/M/1 означает пуассоновский вход, экспоненциальное обслуживание и один канал.
Закон Литтла
Для устойчивой системы на длинном интервале:
— среднее число заявок в системе, — среднее время в системе. Аналогично для очереди: .
Закон не требует экспоненциальных распределений, но требует согласованного интервала и устойчивого потока.
M/M/1
Коэффициент загрузки:
Стационарный режим существует при . Тогда:
W=\frac{1}{\mu-\lambda}$$ $$L_q=\frac{\rho^2}{1-\rho},\qquad W_q=\frac{\rho}{\mu-\lambda}$$ При приближении $\rho$ к единице задержка растёт нелинейно. Поэтому «CPU ещё не 100%» не означает безопасный запас. ## Приоритетные очереди - **без вытеснения**: текущая работа завершается; - **с вытеснением**: более важная заявка прерывает менее важную; - **старение приоритета**: приоритет ожидающей заявки растёт, уменьшая риск голодания. Приоритет снижает задержку одного класса за счёт другого, но не увеличивает мощность системы. ## Практические вопросы - поток пакетный или близок к пуассоновскому; - есть ли тяжёлый хвост времени обработки; - создают ли timeout и retry новый входной поток; - где находится фактическая очередь; - что происходит при заполнении ёмкости; - измеряются ли перцентили, а не только среднее. Для сложных распределений: [[Методы статистического моделирования СМО]]. ## Самопроверка - Почему задержка резко растёт около полной загрузки? - Что даёт и чего не даёт приоритет? - В каких условиях применим закон Литтла?