Очереди

Сложность
Легкий 25%

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

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

Очередь

Модель, первоначально созданная 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 больше не учитывается).

Делиться
ru_RURU