3. Время ожидания для m/g/1

Если рассматривать только клиентов, которые задержаны, можно найти моменты распределения времени ожидания для классических дис­циплин организации очереди (Abate & Whitt, 1997 [1]).

FCFS. Обозначая как /-ый момент распределения времени обслужи­вания /я., мы можем найти к-ый момент распределения времени ожидания с помощью следующей рекурсивной формулы, где среднее время обслу­живания выбрано как единица времени (m_t = s = 1):

А -г-i fk\ rtij+i

^{mk,F =} Т^~А J7T'^mk-^j’^F’ ^mw ^{= 1}- ^¹³‘⁸^

LCFS. Из полученного выше момента m_kF распределения времени ожидания для FCFS мы можем найти момент m_{k L} для распределения вре­мени ожидания LCFS. Три первых момента равны:

ITt2 F ГПз F + 3 • ГП] _F • m2F mi,L=mi,F, ^m2,L= JZTJ’ ^mi.L⁼ —^: ^¹³‘⁹^

4. Ограниченная длина очереди: m/g/1/к

В реальных системах длина очереди, например размер буфера, всегда будет конечна. Прием заявок, когда буфер полон, блокирован. Например, в Интернете эта стратегия применяется в маршрутизаторах и названа страте­гией «отбрасываниехвоста». При такой стратегии существует простое отно­шение между вероятностями состоянийp(i) (/ = 0, 1,2, ...) для бесконечной системы М/G/l и вероятностью состояний р_к(\), 0 = 0, 1,2к) М/G/1/к для системы, в которой общее количество мест ожидания для клиентов конеч­но и равно к, включая обслуживаемого клиента (Keilson, 1966 [59]):

^{РМ =} ' = (13.10)

^мк) ■ ^<13Л1)

где А < 1 - предложенная нагрузка

Qk = Y,p(j) ■

i=k (13.12)

Для такой стратегии существует алгоритм вычисления р (/) при про­извольном распределении времени пребывания в системе (М/G/l), осно­ванный на анализе марковской вложенной цепи (Kendall, 1953 [62]), где тот же самый подход используется для (GI/M/1).

Заметим, что это справедливо только для А< 1, но для конечного буфера мы также получаем статистическое равновесие при А >1. В этом случае нельзя применять подход, описанный в этой секции. Для М/М/1/к мы можем использовать конечную диаграмму переходов состояний, и для M/D/1/к мы обсуждаем простой подход в секции 13.5.8, который приме­ним для общих распределений времени пребывания в системе.

4. Приоритетные системы организации очередей: M/G/1

Существование времени ожидания обычно создает неудобства кли­енту или лишние расходы. В соответствии с различными стратегиями организации очереди времена ожидания могут быть распределены среди клиентов согласно нашему предпочтению.

1. Комбинация нескольких классов клиентов

В этом случае клиенты разделены на N классов (потоков нагрузки). Предположим, что клиент класса / создает Пуассоновский поток с интен­сивностью Х₍ [в единицу времени] и среднее время обслуживания - j. [еди­ница времени]. Второй момент распределения времени обслуживания обозначим m_2j, предложенная нагрузка будет А = Х.х s_r

Вместо того чтобы рассматривать отдельные процессы поступления вызовов, мы можем рассмотреть полный процесс поступления вызовов, кото­рый также является Пуассоновским потоком вызовов с интенсивностью:

N

я.= (13.13)

1=1

В результате распределение времени обслуживания тогда становится взвешенной суммой распределений времени обслуживания отдельных классов (секция 3.2.2 - комбинация параллельных процессов). Полное среднее время обслуживания равно:

(13.14)

<=1 А

и полный второй момент:

X

т₂= ih.rn*. (13-15)

i=i

Полная предложенная нагрузка:

N N

^А= Z^/= X (^13Л6)

i=i ;=1

среднее время ожидания обслуживания в случайный момент времени становится (13.4):

И = i.X. ш_г <13.17)

- 1.^.1-,

2. s

г-т-тч

N

• = Y.4-тц (13.18)

1=1 ¹

N

= 'Ey,. (13.19)