Очереди

Очереди ожидания

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

Модель, первоначально созданная Erlang для телефонной системы 1909 года, позволяет моделировать управление трафиком, планирование и определение размеров инфраструктуры и обработки.

обозначение Кендалла

Очередь имеет 6 критериев, отмеченных: T/X/C/K/P/Z.

• T: вероятностное распределение времени прибытия. Клиенты могут уйти, если они приходят, когда очередь заполнена. T может принимать следующие значения
  • M для марковского процесса / экспоненциального закона
  • G для общего права
  • D детерминированный закон
  • E (k) для закона Эрланга
  • так далее

• X: вероятностное распределение времени обслуживания. Клиент принимается непосредственно бесплатным сервером, после завершения обслуживания клиент уходит. Распределение представлено теми же символами, что и в Т.
• C: количество серверов. В простых очередях все серверы имеют одинаковое распределение вероятностей времени обслуживания.

• K: емкость очереди. Если очередь имеет конечное число, клиент теряется, когда очередь заполнена. Серверы учитываются в емкости очереди (1 на сервер).

• P: численность населения. Размер популяции конечен или бесконечен. В случае конечной популяции скорость поступления заявок зависит от количества заявок в системе.
• Z: служебная дисциплина
  • FCFS/FIFO (первым пришел, первым обслужен / первым пришел, первым обслужен): в порядке очереди
  • LCFC/FILO (последний пришел – первый обслужен/первый пришел последним): последний пришел – первый обслужен/первый пришел – обслужен последним
  • RANDOM: случайное обслуживание клиентов в списке ожидания
  • HL (hold in line): если приходит «важный» клиент, он занимает первое место в очереди (по «важности» первых клиентов)
  • PR (упреждение): если приходит «важный» клиент, он обслуживается напрямую, а «менее важный» клиент покидает сервис, чтобы перейти в очередь
  • PS (совместное использование процессора): все клиенты обслуживаются одновременно со скоростью, обратно пропорциональной количеству клиентов
  • так далее

Через очередь могут проходить различные классы клиентов, характеризующиеся:

• Различные процессы прибытия
• Разное время обслуживания
• Различные расходы
• А планирование в очереди согласно своему классу

Мы будем использовать обозначение T/X/C, когда очередь имеет бесконечную емкость, размер популяции бесконечен, а обслуживание подчиняется дисциплине FIFO. Это эквивалентно написанию T/X/C/∞/∞/FIFO.

Показатели эффективности

Изучение очереди направлено на расчет или оценку производительности системы. Этот расчет выполняется в устойчивом состоянии, чтобы рассчитать: пропускную способность X, количество клиентов Q, скорость использования сервера U, время отклика R. В общем случае рассчитываются ожидания этих параметров.

В контексте одиночных очередей система эргодический. Затем мы пытаемся вычислить устойчивость системы. Возьмем следующее:

• A(T): количество поступлений в систему от 0 до T
• D(T): количество запусков системы от 0 до T
• Xe(T) = A(T)/T: средний расход на входе между 0 и T
• Xs(T) = D(T)/T: средний выходной поток между 0 и T
• Q(T): среднее количество клиентов от 0 до T
• р_к: время пребывания k-го клиента прибыло
• : среднее время пребывания между 0 и T

очередь устойчива тогда и только тогда, когда предел при стремлении T к бесконечности средней скорости ввода равен пределу при стремлении T к бесконечности средней скорости вывода. Другими словами, когда предел по мере Т стремится к бесконечности D(T)/A(T)=1. В стабильной очереди количество клиентов остается конечным.

Пусть Q — среднее количество клиентов, R — среднее время ответа, а X — средняя пропускная способность, закон Литтла гарантируется в устойчивое состояние для стабильной системы, что Q = RX (тогда T больше не учитывается).