Системы массового обслуживания с приоритетами: оптимизация дисциплин ожидания

В приоритетных системах массового обслуживания входящий поток заявок разделяется на несколько классов (например, класс 1 — высший приоритет, класс 2 — низший приоритет). Каждому классу присуща своя интенсивность поступления (лямбда) и свое среднее время обслуживания. Дисциплины приоритетного обслуживания фундаментально делятся на две категории: относительные (без прерывания) и абсолютные (с прерыванием, или вытесняющие). При относительном приоритете заявка высшего класса становится в самое начало очереди, но если сервер уже занят обслуживанием заявки низшего класса, он обязан завершить эту работу до конца. Такая система широко используется на производственных конвейерах, где прерывание обработки детали технологически невозможно или приводит к браку.

В системах с абсолютным приоритетом (Preemptive Priority) появление заявки высшего класса приводит к немедленному жесткому прерыванию обслуживания менее важной заявки. Сервер моментально переключается на важного клиента. Недообслуженная заявка низшего приоритета либо возвращается в начало своей очереди (с запоминанием оставшегося времени обслуживания или с потерей всего прогресса), либо навсегда покидает систему (потерянная заявка). Абсолютные приоритеты являются краеугольным камнем планировщиков задач в операционных системах компьютеров, где критические системные прерывания (interrupts) обязаны перехватывать ресурсы центрального процессора в микросекундные сроки, вытесняя любые фоновые пользовательские процессы.

Аналитический расчет таких систем опирается на формулы Кобхэма, выведенные в 1950-х годах. Формула Кобхэма позволяет алгебраически рассчитать математическое ожидание времени ожидания в очереди для каждого отдельного класса приоритета. В системе с относительными приоритетами время ожидания заявки k-го класса зависит не только от загрузки системы заявками равного или более высокого класса, но и от так называемого остаточного времени обслуживания той заявки (любого класса), которая случайно оказалась на сервере в момент прибытия нашего клиента. Формулы демонстрируют жестокий математический закон сохранения: улучшение качества обслуживания (сокращение времени ожидания) для высокоприоритетных клиентов неминуемо достигается исключительно за счет многократного и непропорционального ухудшения времени ожидания для всех низших классов.

Для коммерческой оптимизации систем вводится концепция динамических приоритетов и функций штрафа. Если заявка низшего класса слишком долго находится в буфере, ее приоритет может искусственно повышаться алгоритмом (метод старения), чтобы предотвратить бесконечное зависание (starvation). В логистических задачах каждому классу присваивается удельная стоимость ожидания (например, 100 долларов штрафа за каждую минуту простоя VIP-заказа и 5 долларов для обычного). Задача аналитика сводится к поиску такой оптимальной дисциплины извлечения заявок (индексы Клейнрока или правило cu-rule), которая глобально минимизирует суммарные ожидаемые финансовые потери всей корпоративной системы, превращая теорию очередей в мощный инструмент финансового риск-менеджмента.