Прикладная теория организации очередей

Основные результаты в теории организации очередей

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

Формула Литтла, представленная в секции 5.3 - наиболее общий результат, который является справедливым для произвольной системы организации очереди. Теорема проста в применении и во многих случаях очень полезна.

В общем случае только системы организации очереди с Пуассонов-скими потоками вызовов просты для исследования. Относительно систем организации очереди при последовательном установлении соединения и организации очередей на сетях связи (например, компьютерных сетей) важно знать те случаи, где процесс выхода из системы организации очереди - Пуассоновский процесс. Эти системы организации очереди названы симметричными системами организации очереди, потому что они симметричны во времени, поскольку процесс поступления вызовов и процесс выхода из системы имеют один и тот же тип. Если для такой очереди рассматривать диаграмму процесса по тактам времени, невозможно решить, выполнена ли эта диаграмма при прямом или обратном процессе (обратимость). (Kelly, 1979 [60] ).

Классическая модель организации очереди играет ключевую роль в теории организации очереди, потому что другие системы будут часто сходиться к этой модели, когда число обслуживающих приборов будет увеличиваться (теорема Пальма 6.1 в секции 6.4).

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

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

Формула Полячека-Хинчина для M/G/1

Мы ранее получили среднее время ожидания для системы $$M/M/1$$ (секция 12.2.4), и позже рассматривали $$M/D/1$$ (секция 13.5). В общем случае среднее время ожидания для $$M/G/1$$ определяется следующей теоремой.

Теорема 13.1 Формула Полячека-Хинчина (1930 -32):

$$W=\frac{V}{1-A},$$ $$W=\frac{A*s}{2(1-A)}* \varepsilon,$$ $$V=A\frac s2 \varepsilon=\frac{\lambda}{2} m_2.$$

Здесь $$W$$ - среднее время ожидания обслуживания для всех клиентов, $$s$$ - среднее время обслуживания, $$A$$ - предложенная нагрузка, и е является коэффициентом формы распределения времени пребывания в системе (3.10).

Чем регулярнее процесс обслуживания, тем меньше среднее время ожидания. Соответствующий результат для процесса поступления вызовов изучен в секции 13.6. В реальной телефонной нагрузке коэффициент формы чаще всего равен 4-6, в нагрузке передачи данных 10-100.

Формула (13.2) - один из самых важных результатов в теории организации очереди, и мы изучим ее более тщательно.

Вывод формулы Полячека-Хинчина

Мы рассматриваем систему организации очереди $$M/G/1$$ и хотим найти среднее время ожидания обслуживания для произвольного клиента. Оно не зависит от дисциплины организации очереди, и поэтому можно далее принять, что это дисциплина FCFS. Из-за Пуассоновского потока вызовов ( свойство PASTA ) фактическое время ожидания клиентов равно виртуальному времени ожидания. Среднее время ожидания $$W$$ для произвольного клиента может быть разбито на две части.

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

$$m_{1,r}=\frac s2*\varepsilon,$$

где $$s$$ и $$\varepsilon$$ имеют то же самое значение, как и в (13.2). Если процесс поступления вызовов - Пуассоновский процесс, вероятность поступления нового вызова в момент обслуживания другого клиента равна $$A$$, потому что для системы с одним обслуживающим прибором мы всегда имеем $$p_0 = 1 - A$$ (предложенная нагрузка равна обслуженной нагрузке).

Вклад в среднее время ожидания обслуживаемого клиента равен:

$$V=(1-A)*0+A* \frac s2* \varepsilon\\ =\frac{\lambda}{2}*m_2$$.

Время ожидания из-за клиентов, ожидающих в очереди ( FCFS ). В среднем длина очереди - $$L$$ и определяется по теореме Литла:

$$L= \lambda*W,$$

где $$L$$ - среднее число клиентов в очереди в произвольный момент времени, $$\lambda$$ является интенсивностью поступления вызовов, и $$W$$ - среднее время ожидания, которое мы ищем.

Для каждого клиента в очереди математическое ожидание времени обслуживания - $$s$$ единиц времени. Тогда среднее время ожидания из-за клиентов, стоящих в очереди, равно:

$$L*s=\lambda *W*s=A*W.$$

Таким образом, полное время ожидания равно (13.4) и (13.5):

$$W = V+AW, \\ W=\frac{1}{1-A}\\ =\frac{A*s}{2(1-A)* \varepsilon,$$

и это отношение является Формулой Полячека-Хинчина (13.2). $$W$$ - среднее время ожидания для всех клиентов, тогда как среднее время ожидания для задержанных клиентов w становится ( $$A=D$$ = вероятности задержки)(3.20):

$$w=\frac WD=\frac{s}{2(1-A)}* \varepsilon.$$

Вышеупомянутый вывод справедлив, так как математическое ожидание по времени равно математическому ожиданию по вызовам, когда процесс поступления вызовов - Пуассоновский процесс ( свойство PASTA ).

Период занятости для M/G/1

Период занятости системы организации очереди - временной интервал с момента, когда заняты все обслуживающие приборы, до момента, пока хотя бы один прибор не становится снова свободным. Для $$M/G/1$$ средняя величина периода занятости вычисляется просто.

В какой-то момент система очередь становится пустой, она не имеет памяти из-за Пуассоновского потока вызовов. Эти моменты - точки регенерации очереди (точки равновесия), и следующее событие возникает согласно Пуассоновскому процессу с интенсивностью $$\lambda$$.

Поэтому мы должны только рассматривать только цикл с момента изменения состояния обслуживающего прибора из свободного в занятое до следующего раза, когда она изменяет состояние из свободного в занятое. Этот цикл включает период занятости продолжительностью $$T_1$$ и свободный период продолжительностью $$T_0$$. Pис.13.1 показывает пример с постоянным временем обслуживания.

(рис 13.1)

Соотношение времени, когда система является занятой, тогда равно:

$$\frac{m_{T_1}}{m_{T_0+T_1}}=\frac{m_{T_1}}{m_{T_0}+m_{T_1}}=A=\lambda *s.$$

Из $$m_{T_0} 1/ \lambda$$ мы имеем:

$$m_{T_1}=\frac{s}{1-A}.$$

В течение периода занятости обслуживается, по крайней мере, один клиент.

Время ожидания для M/G/1

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

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

$$m_{k,F}=\frac{A}{1-A} \sum_{j=1}{k} {k\choose j}*\frac{m_{j+1}}{j+1}*m_{k-j,F}, \quad m_{0,F}=1$$

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

$$m_{1,L}=m_{1,F} \quad m_{2,L}=\frac{m_{2,F}}{1-A}, \quad m_{3,L}=\frac{m_{3,F}+3*m_{1,F}*m_{2,F}}{(1-A)^2}$$

Ограниченная длина очереди: M/G/1/k

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

$$p_k(i)=\frac{p(i)}{(1-A*Q_k)}, \quad i=0,1, \dots, k-1,$$ $$p_k(k)=\frac{(1-A)*Q_k}{(1-A*Q_k)},$$

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

$$Q_k=\sum_{j=k}^{\infty}$$

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

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

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

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

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

В этом случае клиенты разделены на $$N$$ классов (потоков нагрузки). Предположим, что клиент класса $$i$$ создает Пуассоновский поток с интенсивностью $$\lambda_i$$ [в единицу времени] и среднее время обслуживания - $$s_i$$ [единица времени]. Второй момент распределения времени обслуживания обозначим $$m_{2i},$$ предложенная нагрузка будет $$A_i =\lambda_i \times s_i.$$

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

$$\lambda =\sum_{i=1}^N \lambda_i$$

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

$$s=\sum_{i=1}^N \frac{\lambda_i}{\lambda}*s_i,$$

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

$$m_2=\sum_{i=1}^N \frac{\lambda_i}{\lambda}*m_{2i}.$$

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

$$A=\sum_{i=1}^N A_i=\sum_{i=1}^N \lambda_i*s_i=\lambda s.$$

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

$$V=\frac 12* \lambda*m_2$$ $$=\frac 12*A*\frac 1s*m_2\\ =\frac 12*A* \left \{ \sum_i=1}^N \frac{\lambda_i}{\lambda}*s_i \right \}^{-1} * \left \{ \sum_{i=1}^N \frac{\lambda_i}{\lambda}*m_{2i} \right \}\\ =\frac 12*A \left \{\sum_{i=1}^N \frac{A_i}{\lambda} \right \}^{-1}* \left \{ \sum_{i=1}^N \frac{\lambda_i}{\lambda}*m_{2i} \right \}$$ $$V=\sum_{i=1}^N \frac{\lambda_i}{2}*m_{2i}$$ $$=\sum_{i=1}^N V_i.$$

Дисциплина организации очереди, сохраняющая работу

Ранее мы предполагаем, что время обслуживания клиента не зависит от дисциплины организации очереди. Пропускная способность обслуживающего прибора также предполагается постоянной и не зависит, например, от длины очереди. Дисциплина организации очереди является сохраняющей работу.

На практике это не всегда происходит именно так. Если "обслуживающий прибор" - человек, скорость обслуживания часто будет увеличиваться с длиной очереди, и после некоторого времени "прибор" может устать и уменьшить скорость обслуживания.

Введём две функции, которые широко применяются в теории организации очереди.

Функция нагрузки $$U(t) $$ обозначает время, которое требуются, чтобы обслужить клиентов, прибывших в систему в момент времени $$t$$ (рис. 13.2). Одновременно с поступлением вызова $$U(t) $$ увеличивается скачком на величину времени обслуживания поступившего вызова, а между поступлением вызовов $$U(t) $$ уменьшается линейно с наклоном -1 до нуля и остается нулевой до прибытия следующего вызова. Средняя величина

(рис 13.2) Функция нагрузки U (t) для системы организации очереди GI/G/1.

Если мы обозначим время интервала $$T_{i+1} - T_i$$ через $$a_i,$$ то получим $$U_{i+1} = max\{0, U_i + s_i - a_i\}$$,

функции нагрузки обозначается $$U=E\{U(t)\} $$. В системе организации очереди $$GI/G/1$$ функция $$U(t) $$ будет независима от дисциплины организации очереди, если обработка информации сохраняет время обслуживания.

Виртуальное время ожидания W(t) обозначает время ожидания

клиента, если вызов поступает в момент $$t$$. Виртуальное время ожидания $$W(t) $$ зависит от организации очереди. Средняя величина обозначена $$W=E\{W(t)\} $$. Если дисциплина очереди - FCFS, то $$U(t) = W(t) $$.

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

Теперь рассмотрим функцию нагрузки в случайный момент времени $$t$$. Она состоит из вклада $$V$$ от времени, оставшегося от обслуживания обслуживаемого клиента, если таковые вообще имеются, и вклада от клиентов, ждущих в очереди. Средняя величина $$U = E\{U(t)\} $$ равна:

$$U=V+\sum_{i=1}^N L_i*s_i.$$

$$L_i$$ - длина очереди для клиентов типа $$i$$. Применяя формулу Литтла, получаем:

$$U=V+\sum_{i=1}^N \lambda_i *W_i*s_i\\ =V+\sum_{i=1}^NA_i*W_i.$$

Как было сказано выше, $$U$$ независима от дисциплины организации очереди (предполагается, что система - с сохранением работы), и $$V$$ определяется выражением (13.17) для неприоритетных дисциплин организации очереди.

$$U$$ получен в предположении дисциплины FCFS, тогда мы имеем $$W_i = U$$:

$$U=V+\sum_{i=1}^NA_i*U=V+A*U,\\ U=\frac{V}{1-A},$$ $$U-V=\frac{A*V}{1-A}.$$

Согласно этим общим предположениям, подставляя (13.22) в (13.20), мы получим закон сохранения Клейнрока (1964 [65] ).

Теорема 13.2. Закон сохранения Клейнрока:

$$\sum_{i=1}^NA_i*W_i=\frac{A*V}{1-A}=conctant.$$

Среднее время ожидания для всех классов взвешенной нагрузки является независимым от дисциплины очереди.

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

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

До этого мы рассматривали приоритетные системы организации очереди для $$M/G/1$$, где клиенты разделены на $$N$$ приоритетных классов так, чтобы клиент p имел более высокий приоритет, чем клиенты $$p + 1$$, и имел право на прерывание процесса обслуживания низкоприоритетного клиента. В рассматриваемой ниже системе это обслуживание не прерывается. Предполагается, что клиенты в классе $$p$$ имеют среднее время обслуживания $$S_p$$ и интенсивность прибытия $$\lambda_p.$$ В секции 13.4.1 мы получили $$p$$

Полное среднее время ожидания $$W_p$$ клиента класса $$p$$ может быть вычислено непосредственно, учитывая следующие три вклада:

остаточное время обслуживания $$V$$ для обслуживаемого клиента;

время ожидания, из-за клиентов, стоящих в очереди с приоритетом $$p$$ или выше, который находятся уже в очередях (формула Литла):

$$\sum_{i=1}^ps_i*(\lambda_iW_i)$$.

время ожидания из-за клиентов с более высоким приоритетом, которые поступают по ходу его ожидания:

$$\sum_{i=1}^{p-1}s_i* \lambda_i*W_p$$.

Всего мы имеем:

$$W_p=V+\sum_{i=1}^ps_i* \lambda_i *W_i+ \sum_{i=1}^{p-1}s_i*\lambda_i*W_p.$$

Для клиентов класса 1, которые имеют самый высокий приоритет, предполагая дисциплину обслуживания FCFS, мы имеем:

$$W_1=V+L_1*s_i\\ =V+A_1*W_1$$ $$W_1=\frac{V}{1-A_1}.$$

$$V$$ - остаточное время обслуживания для клиента, когда поступает вызов от клиента, которого мы рассматриваем (13.18):

$$V=\sum_{i=1}^N \frac{\lambda_i}{2}*m_{2i},$$

где $$m_{2i}$$ - второй момент распределения времени обслуживания i-того класса.

Для клиента класса 2 находим:

$$W_2 = V+ L_1*s_1+ L_2*s_2 + W_2*(s_1 \lambda_1).$$

Подставляя $$W_1$$ (13.25), находим:

$$W_2=W_1+A_2*W_2+A_1*W_2,\\ W_2=\frac{W_1}{1-A_1-A_2}$$ $$W_2=\frac{V}{\{1-A_1\}\{1-(A_1-A_2)\}$$

Находим общее время ожидание (Cobham, 1954 [14] ):

$$W_p=\frac{V}{\{1-A_{p-1}'\}\{1-A_p'\}},$$

где:

$$A_p'=\sum_{i=1}^p A_i, \quad A_0=0.$$

Формула (13.30) может быть интерпретирована следующим образом. Полное время ожидания клиентов класса $$p$$ не зависит класса клиентов, ожидающих, пока обработка очереди не будет закончена {V для всех классов одинаково}.

Кроме того, время ожидания включает время ожидания клиентов, которые уже прибыли и имеют, по крайней мере, такой же приоритет $$\{A_p'\}$$, а также клиентов с более высоким приоритетом, прибывающим в течение времени ожидания $$\{ A_{p-1}'\}$$

Пример 13.4.1: Система с программным управлением

Мы рассматриваем компьютер, который обслуживает два типа клиентов. Первый тип имеет постоянное время обслуживания 0,1с. и интенсивность поступления 1 вызов/сек. Другой тип имеет экспоненциально распределенное время обслуживания со средней величиной 1,6 с. и интенсивность поступления 0,5 клиента/с.

Нагрузка от двух клиентов типов тогда - $$A_1$$ = 0,1 Эрл., соответствен-но $$A_2$$ = 0,8 Эрл.

Из (13.27) мы находим:

$$V=\frac 12*(0.1)^2+\frac{0.5}{2}*2(1.6)^2=1.2850 c.$$

Без какого-либо приоритета среднее время ожидания по формуле Полячека-Хинчина (13.2) равно:

$$W=\frac{1.2850}{1-(0.8+0.1)}=12.85c.$$

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

Тип 1 (самый высокий приоритет)

$$W_1=\frac{1.285}{1-0.01}=1.43c.,\\ W_2=\frac{W_1}{1-(A_1+A_2)}=14.28c.$$

Тип 2 (высокий приоритет):

$$W_2=6.43c.\\ W_1=64.25c.$$

Это показывает, что мы можем изменять тип 1, почти не влияя на тип 2. Однако обратное утверждение не имеет места. Константа в законе Сохранения (13.23) такая же, как в дисциплине без приоритета.

$$0.9 * 12.85 = 0.1*1.43 + 0.8 * 14.28 = 0.8 * 6.43 + 0.1 * 64.25 = 11.57$$

Дисциплина организации очереди SJF: M/G/1

Одно из основных свойств дисциплины организации очереди SJF: чем короче время обслуживания клиента, тем выше его приоритет. Вводя бесконечное число приоритетных классов, мы получаем из формулы (13.30), что клиент со временем обслуживания $$t$$ имеет среднее время ожидания $$W_t$$ (Phipps 1956):

$$W_t=\frac{v}{(1-A_t)^2},$$

где $$A_t$$ - нагрузка от клиентов со временем обслуживания меньше или равным $$t$$.

SJF -дисциплина в результате приводит к наименьшему времени ожидания. При ожидании различные приоритетные классы имеют различные затраты в единицу времени. Клиенты класса $$j$$ имеют среднее время обслуживания $$s_j$$ и платят $$c_j$$ за единицу времени ожидания. Оптимальная стратегия (минимальная стоимость) состоит в том, чтобы назначить приоритеты 1, 2, … согласно увеличивающемуся отношению $$s_j /c_j$$.

Пример 13.4.2: M/M/1 с дисциплиной очереди SJF

Мы полагаем, что случай с экспоненциально распределенными временами пребывания в системе со средней величиной $$1/ \mu$$, которая оговорена, выбран как единица времени ( $$M/M/1$$ ). Заметим, что очень длительные времена обслуживания, даже когда их немного, все равно вносят значительный вклад в полную нагрузку (рис.3.2).

Вклад в полную нагрузку от клиентов со временем обслуживания $$\le t$$ - это {(3.22), умноженное на $$A= \lambda * \mu$$ }:

$$A_t=\int_0^t x* \lambda * f(x)dx\\ =\int_0^tx* \lambda *( \mu *e^{- \mu x})dx\\ =A\{1-e^{-\mu t}(\mu t+1)\}.$$

Подставляя это в (13.32), находим $$W_t,$$ как это проиллюстрировано на рис. 13.3, где показана FCFS -стратегия. Она имеет такое же среднее время ожидания, как LCFS и SIRO, показанное для сравнения как функция фактического времени пребывания в системе.

(рис 13.3) Среднее время ожидания Wt как функция фактического времени обслуживания в M/M/1 системе для SJF- и FCFS-дисциплин, соответственно.

Среднее время ожидания для всех клиентов с SJF - меньше, чем с FCFS, но это не очевидно из рисунка. Среднее время ожидания для SJF равно:

$$W_{SJF}=\int_0^{\infty}W_tf(t)dt\\ =\int_0^{\infty}\frac{V}{(1-A_t)^2}*f(t)dt\\ =\int_0^{\infty}\frac{A*e^{-\mu t}dt}{\{1-A(1-e^{-\mu t}(\mu t +1))\}^2}$$

Это выражение вычислить не просто.

Предложенная нагрузка - 0,9 Эрл, и как единица времени выбрано среднее время обслуживания. Заметьте, что для SJF минимальное среднее время ожидания является 0,9 единиц времени, потому что вероятная предыдущая обслуживаемая работа должна быть закончена. Максимальное среднее время ожидания - 90 единиц времени. По сравнению с FCFS, при использовании SJF 93,6 % заданий имеют более короткое среднее время ожидания. Это относится к заданиям со временем обслуживания, меньшим, чем 2,747 средних значений времени обслуживания (единицы времени). Предложенная нагрузка может быть больше, чем один Эрл, но тогда только более короткие задания будут иметь конечное время ожидания

M/M/n приоритетная дисциплина организации очереди без прерывания обслуживания

Мы можем также обобщить классическую систему времени ожидания Эрланга $$M/M/n$$ на приоритетную дисциплину организации очереди без прерывания обслуживания. При этой дисциплине все классы клиентов имеют одно и то же экспоненциальное распределение времени обслуживания со средней величиной $$s= \mu^{-1}$$. Обозначая интенсивность прибытия на класс $$\lambda_i,$$ мы имеем среднее время ожидания $$Wp$$ на класс $$p$$:

$$W_p=V+\sum_{i=1}^p \frac sn*L_i+W_p\sum_{i=1}^{p-1} \frac sn \lambda_i,\\ W_p=E_{2,n}(A)*\frac sn+\sum_{i=1}^p \frac {s \lambda_i}{n}*W_i+W_p \sum_{i=1}^{p-1} \frac sn \lambda_i.$$

$$A$$ - полная предложенная нагрузка для всех классов. Вероятность $$E_{2,n} (A) $$ для времени ожидания определяется C-формулой Эрланга, обслуживание клиентов завершается со средним временем между окончаниями обслуживания $$s/n$$, когда все обслуживающие приборы заняты. Для самого высокого приоритетного класса $$p = 1$$ находим:

$$W_1=E_{2,n}(A) \frac sn +\frac 1n A_1W_1,\\ W_1=E_{2,n}(A)*\frac{s}{n-A_1}.$$

Для $$p = 2$$ подобным способом находим:

$$W_2=E_{2,n}(A) \frac sn+\frac 1nA_1W_1+\frac 1n A_2W_2+W_2 \left \{ \frac sn* \lambda_1 \right \}\\ =W_1+\frac 1n A_2W_2+\frac 1n*A_1W_2,\\ W_2=\frac{nsE_{2,n}(A)}{\{n-A_1\}\{n-(A_1+A_2)\}}.$$

В общем случае находим (Cobham, 1954 [14] ):

$$W_p=\frac{nsE_{2,n}(A)}{\{n-A_{p-1}'\}\{n-A_p'\}}$$

Дисциплина организации очереди с приоритетным возвращением к работе

Рассмотрим случай, когда продолжающееся обслуживание прервано прибытием клиента с более высоким приоритетом. После того как новый вызов будет обслужен, работа по обслуживанию прерванного вызова продолжается с того места, где оно было прервано. Эта ситуация типична для компьютерных систем. Для клиента с приоритетом $$p$$ клиенты с более низким приоритетом не существуют. Среднее время ожидания $$W_p$$ для клиента в классе $$p$$ состоит из двух вкладов.

a) Время ожидания из-за клиентов с более высоким или тем же самым приоритетом, которые уже находится в очереди. Это время ожидания определяется как время ожидания клиентом в системе без приоритета, где существуют только первые $$p$$ классов:

$$\frac{V_p}{1-A_p'} \quad \mbox{где} V_p=\sum_{i=1}^p \frac{\lambda_i}{2}*m_2,i},$$

Оно является остающимся временем обслуживания из-за клиентов с более высоким или тем же самым приоритетом, и $$A_p'$$ определяется (13.31).

б) Время ожидания из-за клиентов с более высоким приоритетом, вызовы от которых поступают в течение время ожидания или во время обслуживания клиента, которого мы рассматриваем:

$$(W_p+s_p)\sum_{i=1}^{p-1}s_i* \lambda_i=(W_p+s_p)*A_{p-1}'.$$

Таким образом, мы имеем:

$$W_p=\frac{V_p}{1-A_p'}+(W_p+s_p)*A_{p-1}'.$$

Это может быть представлено следующим образом:

$$W_p(1-A_{p-1}')=\frac{V_p}{\{1-A_p'\}}+s_p*A_{p-1}',$$

В результате получается:

$$W_p=\frac{V_p}{(1-A_{p-1}')}+\frac{A_{p-1}'}{1-A_{p-1}'}*s_p.$$

Тем же самым способом, как в секции 13.4.4, мы можем получить формулу для среднего времени ожидания для SJF дисциплины организации очереди с приоритетным возвращением к работе. Полное время реакции будет равно:

$$T_p=W_p+s_p$$

Пример 13.4.3: Система с программным управлением (см. пример 13.4.1)

Предположим, что компьютерная система в Примере 13.4.1 работает с дисциплиной "приоритетное возвращение к работе". Находим: Тип 1 - самый высокий приоритет:

$$W_1=\frac{\frac 12(0.1)^2}{1-0.1}+0=0.0056c.,\\ W_2=\frac{1.2850}{(1-0.1)(1-0.9}}+\frac{0.1}{1-0.1}*1.6=14.46c.$$

Тип приоритета 2:

$$W_2=\frac{\frac 12*0.5*(1.6)^2}{1-0.8}+0=6.40c,\\ W_1=\frac{1.2850}{(1-0.8)(1-0.9}}+\frac{0.8}{1-0.8}*0.1=64.65c.$$

Это показывает что, изменяя состав клиентов типа 1, мы можем обеспечить этим клиентам очень короткое время ожидания, не нарушая характеристик очереди для клиентов типа 2, но обратное преобразование не обеспечивает такого свойства.

Закон сохранения справедлив только для приоритетных систем организации очереди, если приоритетные времена прерывания обслуживания являются экспоненциально распределенными. В общем случае работа может прерываться несколько раз, и поэтому $$V$$ не будет определять остающееся время обслуживания.

M/M/n с приоритетным возвращением к работе

Для $$M/M/n$$ случай приоритетного возвращения к работе анализируется более сложно. Все клиенты должны иметь одинаковое среднее время обслуживания. Сначала среднее время ожидания может быть получено рассмотрением каждого класса автономно (12.15). Затем можно рассмотреть два класса вместе и получить время ожидания для двух классов и т.д. Закон сохранения справедлив, когда все клиенты имеют одинаковое экспоненциально распределенное время обслуживания.

Системы организации очереди с постоянными временами занятия

В этой секции мы сосредотачиваем свое внимание на системе организации очереди $$M/D/n$$, FCFS. Системы с постоянными временами обслуживания имеют определяющее свойство: клиенты покидают обслуживающие приборы в том же самом порядке, в котором они приняты для обслуживания.

Исторические замечания по M/D/n

Системы организации очереди с Пуассоновским потоком вызовов и постоянными временами обслуживания были проанализированы первыми. Интуитивно можно было бы думать, что анализ более систем с постоянными временами обслуживания проще, чем с экспоненциально распределенными временами обслуживания, но это явно не так. С экспоненциальным распределением иметь дело проще из-за отсутствия у него памяти: остающееся время "жизни" имеет то же самое распределение, как полное время "жизни" (секция 4.1), и поэтому мы можем забыть о периоде или моменте времени, когда начинается время обслуживания. Постоянные времена занятия требуют, чтобы мы помнили точное время начала. Эрланг первым проанализировал систему с постоянным временем обслуживания $$M/D/n$$, FCFS (Brockmeyer, 1948 [11] ):

Эрланг: 1909 n = 1 ошибка для n > 1,

Эрланг: 1917 n = 1, 2, 3 без доказательства,

Эрланг: 1920 n - произвольное, решения для n = 1, 2, 3.

Эрланг получил распределение времени ожидания, но не рассматривал вероятности состояния. Фрей (Fry (1928 [30] )) также исследовал $$M/D/1$$ и получил вероятности состояния (уравнения состояния Фрея), используя принцип статистического равновесия Эрланга. Сам Эрланг применял другие теоретические методы.

Кроммелин (1932 [20] , 1934 [21] ), британский телефонный инженер, представил общее решение для $$M/D/n$$. Он обобщил уравнения состояний Фрея для произвольного $$n$$, и получил распределение времени ожидания, теперь называемое распределением Кроммелина.

Поллячек (1930-34) представил общее, зависимое от времени поступления решение для произвольного распределения времени обслуживания. Согласно предположению о статистическом равновесии он получил явные решения для экспоненциально распределенного и постоянного времен обслуживания.

Хинчин (1932 [63] ) исследовал $$M/D/n$$ и получил распределение времени ожидания.

Вероятности состояния M/D/1

Вероятности состояний для $$M/D/1$$ могут быть получены простым способом, исходя из предположения о статистическом равновесии.

Пусть интенсивность поступления вызовов равна $$\lambda$$, а постоянное время занятия - $$h$$. Рассматриваем чистую систему с ожиданием и с единственным обслуживающим прибором.

$$\mbox{Предложенная нагрузка = Обслуженная нагрузка} =\lambda * h < 1, (13.39) $$

то есть

$$А= Y=\lambda *h = 1 -р(0),$$

в каждом состоянии, кроме нулевого, обслуженная нагрузка равна 1 Эрл.

Мы рассматриваем два периода (момента времени) $$t$$ и $$t+h$$ на расстоянии $$h$$. Каждый клиент, обслуживаемый в период $$t$$ (самое большее один период), может покинуть обслуживающий прибор в период $$t+h$$. Клиенты, прибывающие в течение интервала $$(t, t+ h) $$, находятся все еще в очереди в период $$t+h$$ (ожидание или обслуживание).

Процесс поступления вызовов - Пуассоновский процесс. Следовательно, мы имеем Пуассоновское распределение прибытия во временном интервале $$(t, t+h) $$:

$$p(i,h)=p\{j \quad calls \quad in \quad h\}=\frac{(\lambda h)^j}{j!}*e^{- \lambda h}, j=0,1,2, \dots.$$

Вероятность того, что данное состояние в период $$t+h$$ может быть получено из состояния в период $$t$$, определяется, принимая во внимание общее количество вызовов и выходы из состояния в течение $$(t, t+h) $$. Рассматривая эти периоды, получаем марковскую цепь, внедренную в первоначальный процесс обслуживания нагрузки (рис.13.4).

Мы получаем уравнения состояний Фрея для $$n = 1$$ (Fry, 1928 [30] ):

$$p(j,h)=p\{j \quad calls \quad h\}=\frac{(\lambda h)^j}{j!}*e^{- \lambda h}, j=0,1,2,\dots.$$

Выше было установлено:

$$р(0) = 1-А$$

и согласно предположению о статистическом равновесии $$p_t(i) = p_{t +h}(i)$$, мы последовательно находим:

$$p(1)=(1-A)*\{e^A-1\},\\ p(2)=(1-A)*\{-e^A*(1+A)+e^{2A}\},$$

и далее

$$p(i)=(1-A)*\sum_{j=1}^i(-1)^{i-j}*e^{jA}* \left \{\frac{(jA)^{i-j}}{(i-j)!}+\frac{(jA)^{i-j-1}}{(i-j-1)!} \right \}, i=2,3,\dots.$$

Последнее слагаемое, соответствующее $$j = i$$, всегда равняется $$e^{iA}$$, поскольку $$(-1)! \equiv \infty$$

В принципе $$p(0) $$ может быть получено из условия, что все вероятности состояния должны в сумме давать единицу.

(рис 13.4) Иллюстрация уравнений состояния Фрея для системы организации очереди M/D/1

Средние времена ожидания и период занятости M/D/1

Для Пуассоновского процесса поступления вызовов вероятность задержки $$D$$ равна вероятности того, что он не находится в нулевом состоянии (свойство PASTA ):

$$D=A=1-p(0)$$

$$W$$ обозначает среднее время ожидания для всех клиентов, и w обозначает среднее время ожидания для клиентов, которые стоят в очереди (положительное значение времени ожидания). Мы имеем для любой системы организации очереди (3.20):

$$w=\frac WD$$

$$W$$ и $$w$$ могут быть легко получены, используя формулу Поллячека-Хинчина (13.2):

$$W=\frac{A*h}{2(1-A)},$$ $$w=\frac{h}{1(1-A)}.$$

Средняя величина периода занятости была получена для $$M/G/1$$ в (13.7) и иллюстрирована для постоянных времен обслуживания на рис.13.1:

$$m_{T_1}=\frac{h}{1-A}.$$

Среднее время ожидания для задержанных клиентов, таким образом, - половина периода занятости. Это показывает, что вызовы от клиентов прибывают случайно в течение периода занятости, но мы знаем, что ни один вызов не поступает в течение последнего времени обслуживания периода занятости.

Можно показать, что распределение числа вызовов, прибывающих в течение периода занятости, можно выразить распределением Бореля (Borel ):

$$B(i)=\frac{(iA)^{i-1}}{i!} e^{-iA}, \quad i=1,2, \dots$$

Распределение времени ожидания: M/D/1, FCFS

Можно показать, что:

$$p\{W \le t\}=1-(1- \lambda)* \sum_{j=1}^{\infty} \frac{\{\lambda (j- \tau)\}^{T+j}}{(T+j)!}*e^{-\lambda(j - \tau)},$$

где $$h=1$$ выбрано как единица времени, $$t=T+ \tau , T$$ - целое число, и $$0 \le \tau < 1$$.

Граф распределения времени ожидания имеет нарушения каждый раз, когда время ожидания превышает кратное число постоянного времени занятия. Пример для распределения вероятности дополнения времени ожидания $$(p(W > t)) $$ показан на рис.13.5.

(рис 13.5) Распределение дополнения времени ожидания для всех клиентов в системе организации очереди M/M/1 и M/D/1 для дисциплины очереди (FCFS). Единица времени = среднее время обслуживания. Заметим, что среднее время ожидания для M/D/1 - только половина времени для M/M/1.

Формула (13.49) неудобна для числовой оценки. Можно показать (Iversen, 1982 [39] ), что формула времени ожидания может быть записана в более компактной форме, например, введенной Эрлангом в 1909 г.:

$$p\{W \le t \}=(1- \lambda )*\sum_{j=0}^T \frac{\{\lambda (j-t)\}^j}{j!}*e^{- \lambda (j-t)}$$

и может применяться для числовой оценки при малых временах ожидания.

Для больших времен ожидания мы обычно интересуемся составными значениями $$t$$. Можно показать (Iversen, 1982 [39] ), что для составного значения $$t$$

$$p\{W \le t\}=p(0)+p(1)+ \dots p(t).$$

Вероятности состояния $$p(i) $$ вычисляются наиболее точно, с помощью рекурсивной формулы, основанной на уравнениях состояний (13.42) Фрея:

$$p(i+1)=\frac{1}{p(0,h)} \left \{ p(i)-\{p(0)+p(1)\}*p(i,h)-\sum_{j=2}^ip(j)*p(i-j+1,h) \right \}$$

Для несоставных времен ожидания можно выразить распределение времени ожидания с помощью комбинации составных времен ожидания.

Если мы примем $$h = 1$$, то (13.50) может быть биноминальным разложением, записанным с помощью степени $$\tau$$, где $$t=T+ \tau; T$$ - целое число, $$0 \le \tau < 1$$.

$$p\{W \le T+ \tau\}=e^{\lambda \tau} \sum_{j=0}^T \frac{(- \lambda \tau)^j}{j!}*p\{W \le T-j\},$$

где $$p\{W \le T-j\}$$ определяется в (13.51).

Очень точная числовая оценка может быть получена при использовании (13.51), (13.52) и (13.53).

Вероятности состояния: M/D/n

При выводе уравнений состояния Фрея (13.41) мы получаем больше комбинаций:

$$p_{t+h}(i)=\left \{ \sum_{j=0}^n p_t(j) \right \} p(i,h)+ \sum_{j=n+1}^{n+j}p_t(j)*p(n+i-j,h)$$

При условии статистического равновесия $$(A < n) $$ можно вычислить абсолютные моменты времени выхода из состояния:

$$p(i)=\left \{ \sum_{j=0}^n p(j) \right \} p(i,h)+ \sum_{j=n+1}^{n+1}p(j)*p(in+i-j,h), i=0,1, \dots$$

Если мы знаем первые n вероятности состояний $$\{p(0), p(1)\dots, p (n-1)\} $$, система уравнений (13.55) может быть решена непосредственно подстановкой. Практически мы можем получить числовые значения, подставляя приблизительный набор значений для $$\{p(0), p(1) \dots , p(n - 1)\} $$. Затем, заменяя эти значения, согласно рекурсивной формуле (13.55), получаем новые значения. После нескольких приближений мы получим точные результаты.

Явное математическое решение может быть получено с помощью производящих функций (Erlang [11] стр. 75 (83)).

Распределение времени ожидания: M/D/n, FCFS

Распределение времени ожидания определяется распределением Кроммелина:

$$p\{W \le t \}=1-\sum_{i=0}^{n-1} \sum_{k=0}^i p(k)*\sum_{j=1}^{\infty} \frac{\{A(j- \tau)\}^{(T+j+1)n-1-i}}{\{(T+j+1)n-1-i\}!},$$

где $$A$$ - предложенная нагрузка и:

$$t=T*h+ \tau, 0 \le \tau < h.$$

В компактной форме по аналогии с (13.50):

$$p\{W \le t\}=\sum_{i=0}^{n-1} \sum_{k=0}^i p(k)\sum_{j=0}^T \frac{\{A(j-t)\}^{j*n+n-1-i}}{\{j*n+n-1-i)!}*e^{-A(j-t)}.$$

Для составных значений времени ожидания $$t$$ мы имеем:

$$p\{W \le t \}=\sum_{j=0}^{n(t+1)-1}p(j)$$

Для несоставных времен ожидания при $$t = T+ \tau, T$$ - целое число, $$0 \le \tau < 1$$ можно выразить распределение времени ожидания в элементах составных времен ожидания, поскольку для $$M/D/1$$:

$$p\{W \le t\}=p\{W \le T+ \tau\}=e^{ \lambda \tau}\sum_{j=0}^k \left \{ \frac{(- \lambda \tau)^j}{j!}*\sum_{i=0}^{k-j}p(i) \right \},$$

где $$n(T+1)-1$$ и $$p(i) $$ - вероятность состояния (13.55).

Точное среднее время ожидания всех клиентов получить $$W$$ трудно. Приближенное значение получено Молина (Molina)

$$W \approx \frac{n}{n+1}*E_{2,n}(A)*\frac{n}{n-A}*\frac{1-(\frac An)^{n+1}}{1-(\frac An)^n}.$$

Для любой системы с бесконечной очередью мы имеем (3.20):

$$w=\frac WD$$

где:

$$D=1-\sum_{j=0}^{n-1}p(j)$$

k -Эрланговский процесс поступления вызовов: Ek /D/r

Рассмотрим систему организации очереди к системе, в которой: $$n = r * k$$ обслуживающих приборов ( $$r, k$$ - целые числа), процесс поступления вызовов - общий, время обслуживания - постоянное и дисциплина организации очереди - FCFS. Клиенты, прибывающие в течение, когда обслуживающие приборы свободны, выбирают их в циклическом порядке:

$$1,2, \dots ,п- 1,п,1,2, \dots $$

Тогда некоторый обслуживающий прибор обслужит только каждого $$n$$ -ого клиента, так как клиенты из-за постоянного времени обслуживания освобождают обслуживающие приборы в том же порядке, в каком они занимают обслуживающие приборы. Ни один клиент не может догнать другого клиента в очереди.

Пусть обслуживающие приборы разбиты на группы, тогда

$$x,x+k,x+2*2, \dots, x+(r-1)*k, \quad 0 < x \le k.$$

прибор в группе обслужит только каждого $$k$$ -ого клиента. Если мы рассматриваем обслуживающие приборы в (13.62) как одну группу, то они эквивалентны системе организации очереди $$GI^{k*}/D/r$$, где процесс поступления вызовов $$GI^{k*}$$ есть свертка распределения времени прибытия отдельных $$k$$ времен.

То же самое относится к другим $$k-1$$ системам. Нагрузка в этих $$k$$ системах является взаимно коррелированной, но если рассматривать только одну систему одновременно, то она - $$GI^{k*}/D/n$$, FCFS -система организации очереди.

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

Если мы предположим, что GI -процесс поступления вызовов - Пуассоновский процесс, то $$GI^{k*}$$ становится k-Эрланговским процессом поступления вызовов. Таким образом, мы получили, что следующие системы эквивалентны относительно распределения времени ожидания:

$$M/D/r-k, FCFS \equiv E_k/D/r, FCFS$$

Поэтому система $$Ek/D/r$$ может работать с таблицами для $$M/D/n$$.

Вообще мы знаем, что нагрузка на один обслуживающий прибор и среднее времени ожидания уменьшается, когда число обслуживающих приборов увеличивается. По той же причине среднее время ожидания уменьшается, когда процесс поступления вызовов становится более регулярным. Это замечено непосредственно из вышеупомянутого разложения, где процесс поступления вызовов для $$E_k /D/r$$ становится более регулярным при увеличении $$k$$ ( $$r$$ константа). Для = 0,9 Эрл. на один обслуживающий прибор ( $$L$$ = средняя длина очереди) находим:

$$E_4/E_1/2:\qquad L = 4.5174 ,\\ Е_4/Е_2/2: \qquad L = 2.6607 ,\\ Е_4/Е_3/2: \qquad L = 2.0493 ,\\ E_4/D/2:\qquad L = 0.8100$$

Система с конечной очередью: M/D/1/k

В реальных системах мы всегда имеем конечную очередь. В компьютерных системах размер памяти конечен, и в системах ATM существуют конечные буфера. То же самое происходит для мест ожидания в гибких производственных системах ( FMS - Flexible Manufacturing Systems ).

Как показано в секции 13.3.4, вероятности состояния $$p_k(i) $$ для конечной буферной системы получены из вероятностей состояний $$p(i) $$ бесконечной буферной системы, используя (13.10) и (13.11).

Составные времена ожидания получены из вероятностей состояний и несоставных времен ожидания - из составных времен ожидания, как показано выше (секция 13.5.4).

Для бесконечной буферной системы вероятности состояния существуют только, когда предложенная нагрузка меньше, чем емкость $$(A < n) $$. Но для конечной буферной системы вероятности состояния существуют и для $$A > n$$, однако мы не можем получить их вышеупомянутым методом.

В $$M/D/1/k$$ конечные буферные вероятности состояния $$p_k (i) $$ могут быть получены для любой предложенной нагрузки следующим способом.

В системе с одним сервером и $$(k- 1) $$ местами ожидания мы имеем $$(k + 1) $$ состояний $$(0, 1 \dots , k) $$. Уравнения равновесия для вероятностей состояния $$p_k(i), i = 0, 1 \dots , k-2$$, составляя $$k-1$$ линейных уравнений между состоянием $$\{p_k(0), p_k(1), \dots , p_k(k-1)\} $$, могут быть установлены с помощью уравнений состояний Фрея. Но невозможно записать простые уравнения времени для состояния $$k- 1$$ и $$k$$. Однако первые $$(k- 1) $$ уравнения (13.41) вместе с требованием нормализации:

$$\sum_{j=0}^kp_k(j)=1$$

и фактом, что предложенная нагрузка равняется обслуженной нагрузке плюс отклоненная нагрузка ( свойство PASTA ) дают

$$A=1-p_k(0)+A*p_k(k)$$

в результате $$(k+1) $$ независимых линейных уравнений, которые легко решить.

Два подхода дают, конечно, один и тот же результат. Первый метод справедлив только для $$A<1$$, тогда как второй - для любой предложенной нагрузки.

Пример 13.5.2: "Дырявое ведро"

"Дырявое ведро" - механизм для управления процессами поступления ячеек (пакетов) от пользователя (источника) в ATM -системе. Механизм соответствует системе организации очереди с постоянным временем обслуживания (размер ячейки) и конечным буфером. Если процесс поступления вызовов - Пуассоновский процесс, то мы имеем систему $$M/D/1/k$$. Размер "вытекания" из дыры соответствует долгосрочной средней интенсивности поступления, тогда как размер "ведра" описывает допустимый избыток (число пакетов). Механизм работает как виртуальная система организации очереди, где ячейки или принимаются немедленно, или отклоняются согласно значению счетчика, который является составным значением функции нагрузки (рис.13.2). В контракте между пользователем и сетью соглашение заключается при заданном размере утечки и размере "ведра". На этом основании сеть способна гарантировать заданный уровень обслуживания.

Система организации очереди с одним обслуживающим прибором: GI/G/1

В секции 13.3 мы показали, что среднее время ожидания для всех клиентов в системе организации очереди $$M/G/1$$ определяется формулой Полячека-Хинчина:

$$W=\frac{A*s}{2(1-A)}* \varepsilon$$

где $$\varepsilon$$ - коэффициент формы распределения времени пребывания в системе.

Ранее мы анализировали следующие случаи.

$$M/M/1$$ (секция 12.2.4): $$\varepsilon = 2$$:

$$W=\frac{A*s}{(1-A)}, \quad Erlang \quad 1917.$$

$$M/M/1$$ (секция 13.5.3): $$\varepsilon 1$$:

$$W=\frac{A*s}{2(1-A)}, \quad Erlang \quad 1909.$$

Показано, что чем регулярнее распределение времени пребывания в системе, тем меньше становится нагрузка времени ожидания (для систем с потерями и с ограниченной доступностью этот эффект противоположен: чем больше коэффициент формы, тем меньше потери).

В системах с не пуассоновским поступлением моменты более высокого порядка будут также влиять на среднее время ожидания.

Общие результаты

Мы до настоящего времени принимали, что процесс поступления вызовов - Пуассоновский процесс. Для других процессов поступления вызовов редко можно найти точное выражение среднего времени ожидания, кроме случаев, где времена пребывания в системе дают основания предлагать, что или процесс поступления вызовов, или процесс обслуживания - марковские. До настоящего времени нет никаких общих точных формул, например, для $$M/G/n$$.

Для $$GI/G/1$$ можно получить теоретические верхние пределы для среднего времени ожидания. Обозначая дисперсию интервалов поступления va и дисперсию распределения времени пребывания в системе - $$v_d,$$ с помощью неравенства Кингмана (1961) мы получаем верхний предел для среднего времени ожидания:

$$GI/G/1^ W \le \frac{A*s}{2(1-A)}* \left \{ \frac{v_a+v_d}{s^2} \right \}.$$

Эта формула показывает, что мы имеем дело со стохастическими вариациями времен ожидания.

Формула (13.68) дает теоретическую верхнюю границу. Реалистическая оценка фактического среднего времени ожидания получена приближением Марчала (Marchal, 1976)

$$W \approx \frac{A*s}{2(1-A)}* \left \{ \frac{v_a+v_d}{s^2} \right \}* \left \{ \frac{s^2+v_d}{a^2+v_d} \right \}.$$

где $$a$$ - средний интервал поступления ( $$A = s/a$$ ). Это приближение получается масштабированием приближенного неравенства Кингмана, что согласуется с Формулой Полячека-Хинчина для случая $$M/G/1$$.

Как пример непуассоновского потока вызовов, мы проанализируем систему организации очереди $$GI/M/1$$, где распределение интервалов поступления - общее распределение, данное плотностью распределения $$f (t) $$. Времена обслуживания являются экспоненциально распределенными со скоростью $$\mu$$

Если систему рассматривают в произвольном момент времени, то вероятности состояния не будут отображаться марковским процессом, потому что вероятность прибытия будет зависеть от временного интервала, начиная с последнего прибытия, и свойство PASTA не будет выполняться.

Однако если систему рассматривать непосредственно до (или после) момента поступления, то она будет независима, так как интервалы поступления стохастическая независимы от времени пребывания в системе и являются экспоненциально распределенными. Моменты поступления - это точки равновесия (пункты регенерации, секция 5.2.2), и мы рассматриваем так называемую вложенную цепь Маркова.

Вероятность, что перед моментом поступления система находится в состоянии $$j$$, будем обозначать $$\pi(j) $$. Можно показать, что при статистическом равновесии будет получен следующий результат D.G. Kendall, 1953 [62] :

$$\pi(i)=(1-\alpha) \alpha^i, \quad i=0,1,2 \dots$$

где $$\alpha$$ - положительный реальный корень, удовлетворяющий уравнению:

$$\alpha=\int_0^{\infty}e^{-\mu (1- \alpha)t}f(t)dt.$$

Устойчивые вероятности состояния могут быть получены при рассмотрении двух последовательных моментов поступления $$t_1$$ и $$t_2$$ (подобно уравнениям состояния Фрея, секция 13.5.5).

Так как процесс отклонения - Пуассоновский процесс с постоянной интенсивностью $$\mu$$, когда есть клиенты в системе, то вероятность $$p (j) $$, что для $$j$$ клиентов обслуживание будет закончено между двумя моментами поступления, может быть выражена числом событий в Пуассоновском процессе в течение стохастического интервала (интервал поступления). Существуют следующие уравнения состояний:

$$\pi_{t_2}(0)=\sum_{j=0}^{\infty} \pi_{t_1}(j)* \left \{ 1- \sum_{i=0}^j p(i) \right \},\\ \pi_{t_2}(1)=\sum_{j=0}^{\infty} \pi_{t_1}(j)*p(j),\\ \vdots \qquad \vdots\\ \pi_{t_2}(i)=\sum_{j=0}^{\infty} \pi_{t_1}(j)*p(j-i+1)$$

Условие нормализации определяется обычно так:

$$\sum_{i=0}^{\infty}\pi_{t_1}(i)=\sum_{j=0}^{\infty} \pi_{t_2}(j)=1$$

Можно показать, что для вышеупомянутого геометрического распределения это единственное решение данной системы уравнений (Kendall, 1953 [62] ).

В принципе, система организации очереди $$GI/M/n$$ может быть рассмотрена с помощью того же способа, что и предыдущая. Тогда вероятность состояния $$p(j) $$ становится более сложной, так как интенсивность освобождения зависит от числа занятых каналов.

Заметим, что $$\pi (i) $$ - не вероятность нахождения системы в состоянии $$i$$ в произвольный момент времени (математическое ожидание по времени), а вероятность нахождения системы в состоянии $$i$$ непосредственно перед прибытием (вызвать математическое ожидание вызова).

Характеристики GI/M/1

Вероятность непосредственного обслуживания становится:

$$p\{непосредственно\}=\pi(0)=1- \alpha$$

Соответствующая вероятность того, чтобы выполнение заявки было отсрочено, становится:

$$D=p\{ задержка \}=\alpha$$

Среднее число занятых обслуживающих приборов в случайный момент времени (математическое ожидание по времени) равно обслуженной нагрузке (= предложенная нагрузка $$A < 1$$ ).

Среднее число ждущих клиентов, непосредственно перед прибытием клиента, может быть получено с помощью вероятности состояний:

$$L_1=\sum_{j=1}^{\infty}(1- \alpha) \alpha^i(i-1),\\ L_1=\frac{\alpha^2}{1-\alpha}.$$

Среднее число клиентов в системе перед моментом поступления вызова:

$$L_2=\sum_{i=0}^{\infty}(1-\alpha) \alpha^i*i\\ =\frac{\alpha}{1-\alpha}$$

Среднее время ожидания для всех клиентов тогда равно:

$$W=\frac{1}{\mu}*\frac{\alpha}{1-\alpha}.$$

Средняя длина очереди, по всей оси (виртуальная длина очереди) поэтому равна (формула Литтла):

$$L=A*\frac{\alpha}{1-\alpha}.$$

Среднее время ожидания для клиентов, которые стоят в очереди, равно:

$$w=\frac WD,\\ w=\frac{1}{\mu}*\frac{1}{1-\alpha}.$$

Пример 13.6.1: Средние времена ожидания GI/M/1

Для $$M/M/1$$ мы находим $$\alpha = \alpha_m = A$$. Для $$D/M/1\alphaa = \alpha_d$$ получается из уравнения:

$$\alpha_d=e^{-(1-\alpha_d)/A}$$

где $$\alpha_d$$ находится в пределах (0,1).

Можно показать, что $$0 < \alpha_d < \alpha_m < 1$$. Таким образом, система организации очереди D/M/1 будет всегда иметь среднее время ожидания меньше, чем $$M/M/1$$.

Для = 0,5 Эрл. мы находим следующие средние времена ожидания для всех клиентов (13.78):

$$М/М/1:\qquad \alpha = 0.5, \qquad W= 1, \qquad w = 2.\\ D/M/1:\qquad \alpha = 0.2032, \qquad W = 0.2550, \qquad w = 1.3423.$$

где среднее время пребывания в системе используется как единица времени ( $$\mu=1$$ ).Среднее время ожидания пропорционально прошедшему до данного момента времени с коэффициентом формы распределения интервала поступления.

Распределение времени ожидания: GI/M/1, FCFS

Когда клиент достигает системы организации очереди, число клиентов в системе геометрическое распределено и клиент, предположительно, ожидает некоторое время, равное нескольким геометрически экспоненциально распределенным фазам.

Это сводится к экспоненциально распределенному времени ожидания с параметром, данным в (13.80), когда дисциплина организации очереди - FCFS (секция 12.4 и рис.4.9).

Циклическое и совместное использование процессора

Циклическая ( RR - Round Robin ) модель организации очереди (рис.13.6) является моделью для исследования компьютерной системы с разделением времени, где мы хотим обеспечить быстрое время реакции для самых коротких работ. Эта дисциплина организации очереди также названа справедливой организацией очереди, потому что доступные ресурсы одинаково распределены среди заявок на работу (клиенты) в системе.

(рис 13.6) Циклическая система организации очереди.

Задача распределена в интервале времени $$\Delta s$$ для момента обслуживания. Если задача не закончена в этот интервал, то она возвращается в FCFS -очередь, где ставится на равных условиях с новыми задачами. Если мы допускаем уменьшение $$\Delta s$$, до нуля, то получаем дисциплину организации очереди типа "совместного использования процессора (PS - Processor Sharing).

Заявки на новые работы помещаются в FCFS -очередь, где они находятся на ожидании, пока не будут взяты на обслуживание, в пределах интервала времени (слота) $$\Delat s$$, который одинаков для всех заявок на работу. Если работа не закончена в пределах интервала времени, обслуживание прерывается и работа помещается в конце FCFS -очереди. Это продолжается, пока не будет представлено полное время обслуживания.

Мы принимаем, что очередь неограниченна и что заявки (новые работы) прибывают согласно Пуассоновскому процессу ( $$\lambda$$ ). Распределение времени обслуживания может быть общим со средней величиной s. Интервал времени может изменяться.

Если он становится конечным, и все работы будут заканчиваться за один интервал, то мы получаем просто систему организации очереди $$M/G/1$$ с дисциплиной FCFS. Если мы допускаем уменьшение интервала времени до нуля, то получаем дисциплину организации очереди типа "совместного использования процессора" (PS - Processor Sharing), которая имеет множество хороших аналитических свойств. Она была исследована Клейнроком (1967) и подробно изложена в (Kleinrock, 1976 [67] ). Модель совместного использования процессора может интерпретироваться как система организации очереди, где все работы обслуживаются непрерывно обслуживающим прибором (режим разделения времени). Если есть $$i$$ работ в системе, каждая из них получает $$1/i$$ часть емкости компьютера. Так что нет никакой очереди, и дисциплина организации очереди бессмысленна.

Когда предложенная нагрузка $$A = \lamda * s$$ меньше единицы, можно показать, что вероятности устойчивых состояний равны:

$$p(i)=(1-A)*A^I, \quad i=0,1, \dots,$$

то есть, получается, геометрическое распределение со средней величиной $$A/(1-A) $$. Среднее время пребывания в системе (среднее время реакции) для работ с продолжительностью $$t$$ равно:

$$R_t=\frac{t}{1-A}$$

Если бы эта работа была одна в системе, то ее время пребывания в системе было бы $$t$$. Так как нет очереди, мы можем говорить о средней задержке для работ с продолжительностью $$t$$

$$W_t=R_t-1=\\ =\frac{A}{1-A}*t.$$

Соответствующие средние величины для произвольной работы естественно равны:

$$R=\frac{s}{1-A},$$ $$W=\frac{A}{1-A}*s.$$

Это показывает, что мы получаем точно такие же средние величины, что и для $$M/M/1$$ (секция 12.2.4). Но фактическое среднее время ожидания становится пропорциональным продолжительности работы. Такое свойство зачастую весьма желательно. Мы не предполагаем, что имеются какие-либо предварительные знания о продолжительности работы.

Среднее время ожидания пропорционально среднему времени обслуживания. Пропорциональность не должна пониматься при этом методе так, что две работы одной той же продолжительности имеют одинаковое время ожидания. Это справедливо только в среднем. По сравнению с результатами, которые мы получили ранее для $$M/G/1$$ (формула Полячека-Хинчина (13.2)), результаты могут не соответствовать нашим интуитивным представлениям.

Очень полезное свойство модели совместно используемого процессора: процесс выхода из системы - Пуассоновский процесс, как и процесс поступления вызовов (секция 14.2). Это интуитивно объясняется тем фактом, что процесс выхода из системы получается из процесса поступления вызовов стохастическим смещением отдельных моментов поступления. Сдвиг по времени равен времени реакции со средней величиной, приведенной в (13.82) (секция 6.3.1, теорема Пальма).

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

Краткие итоги:

Для описания типа нагрузки и структуры очереди D.G. Kendall (1951 [61] ) ввел следующую систему обозначений для моделей организации очереди:

$$A/B/n$$

где

$$A$$ - процесс поступления вызовов,

$$B$$ - распределение времени обслуживания,

$$n$$ - число обслуживающих приборов.

Применяются три классических дисциплины организации очереди: FCFS (First Come - First Served): "Первый Пришел - Первый Обслужен", LCFS (Last Come - First Served) - "Последний Пришел - Первый Обслужен" и SIRO (Service In Random Orde) - "Обслуживание в Случайном Порядке".

Для компьютерных систем мы часто пробуем уменьшить полное время ожидания. Это может быть сделано с использованием дисциплин, учитывающих критерии времени обслуживания:

Shortest Job First - "Первым - Самое короткое Задание";

RR (Round Robin) - циклическая (круговая система);

PS (Processor Sharing) - совместное использование процессора;

FB (Foreground / Background) - "Передняя позиция план /Задняя позиция".

На практике клиенты часто разделяются на N приоритетных классов. Различают два типа приоритетов: Неприоритетный, Приоритетный. Если обслуживаемый клиент имеет более низкий приоритет, чем новый поступивший вызовов, то обслуживание прерывается. При этом возможно возвращение к работе.

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

Среднее время ожидания для системы $$M/G/1$$ определяется формулой Полячека-Хинчина:

$$W=\frac{V}{1-A}=\frac{A*s}{2(1-A)}* \varepsilon$$

Если мы рассматриваем только клиентов, которые задержаны, то можем найти моменты распределения времени ожидания для классических дисциплин организации очереди: FCFS, LCFS, M/G/1/k для системы, где общее количество мест ожидания для клиентов конечно и равно k.

В соответствии с различными стратегиями организации очереди, времена ожидания могут быть распределены среди клиентов согласно приоритету. В этом случае клиенты разделены на $$N$$ классов (потоков нагрузки). В результате распределение времени обслуживания становится взвешенной суммой распределений времени обслуживания отдельных классов (секция 3.2: комбинация параллельных процессов).

Ранее мы предположили, что время обслуживания клиента не зависит от дисциплины организации очереди. Пропускная способность обслуживающего прибора, таким образом, постоянна и не зависит, например, от длины очереди. Дисциплина организации очереди, как говорят, сохраняет работу.

Функция нагрузки $$U(t) $$ обозначает время, которое требуются, чтобы обслужить клиента, прибывшего в систему в момент времени $$t$$. В момент поступления вызова функция $$U(t) $$ увеличивается скачком на величину времени обслуживания, а между поступлением вызовов $$U(t) $$ - уменьшается линейно с наклоном от 1 до 0.

Используя принцип сохранения работы и функцию $$U(t) $$, можно получить закон сохранения Клейнрока: среднее время ожидания для всех классов взвешенной нагрузки не зависит от дисциплины очереди. Это справедливо только для неприоритетных дисциплин организации очереди.

Полное среднее время ожидания $$W_p$$ клиента класса $$p$$ не зависит от того, какого класса клиенты ожидают, пока обработка очереди не будет закончена {V для всех классов одинаково}.

$$\sum_{i=1}^N A_i*W_i=\frac{A*V}{1-A}=conctant$$

$$M/M/n$$ приоритетная дисциплина организации очереди без прерывания обслуживания имеет среднее время ожидания $$W_p$$ для класса $$p$$:

$$W_p=\frac{nsE_{2,n}(A)}{\{n-A_{p-1}'\}\{n-A_p'\}}$$.

$$M/M/n$$ дисциплина организации очереди с приоритетным возвращением к работе имеет среднее время ожидания $$W_p$$ для класса $$p$$:

$$W_p=\frac{V_p}{(1-A_{p-1}')(1-A_p')}+\frac{A_{p-1}'}{1-A_{p-1}'}*s_p$$.

Для $$M/M/n$$ случай приоритетного возвращения к работе анализируется более сложно. Все клиенты должны иметь одинаковое среднее время обслуживания. Сначала среднее время ожидания может быть получено рассмотрением каждого класса автономно (12.15). Затем можно рассмотреть два класса вместе и получить время ожидания для двух классов и т. д.

Системы с постоянными временами обслуживания имеют определяющее свойство: клиенты покидают обслуживающие приборы в том же самом порядке, в котором они приняты для обслуживания.

$$W$$ обозначает среднее время ожидания для всех клиентов, и $$w$$ обозначает среднее время ожидания для клиентов, которые стоят в очереди. Постоянные времена занятия требуют, чтобы мы помнили точное время начала. С экспоненциальным распределением иметь дело проще из-за отсутствия у него памяти: остающееся время "жизни" имеет то же самое распределение, как полное время "жизни" (секция 4.1), и поэтому мы можем забыть о периоде или моменте времени, когда начинается время обслуживания.

$$W$$ - среднее время ожидания для всех клиентов, и $$w$$ - среднее время ожидания для клиентов, которые стоят в очереди в системе $$M/D/1$$, определяются следующими формулами:

$$W=\frac{A*h}{2(1-A)},\\ w=\frac{h}{2(1-A)}$$.

Для распределения времени ожидания $$M/D/1$$, FCFS формула времени ожидания имеет вид:

$$p\{W \le t\}=(1-\lambda)*\sum_{j=0}^T \frac{\{\lambda (j-t)\}^j}{j!}*e^{-\lambda(j-t)}$$,

Распределение времени ожидания $$M/D/n$$, FCFS определяется распределением Кроммелина:

$$p\{W \le t\}=1-\sum_{i=0}^{n-1} \sum_{k=0}^I p(k)*\sum_{j=1}^{\infty} \frac{\{A(j- \tau)\}^{(T+j+1)n-1-i}}{\{(T+j+1)n-1-i\}!}$$,

Системы $$M/D/r * k, FCFS=E_k /D/r, FCFS$$ эквивалентны относительно распределения времени ожидания.

Для конечной системы очереди $$M/D/1/k$$ уравнения равновесия для вероятностей состояния $$p_k(i), i=0,1, \dots, k-2$$,могут быть установлены с помощью уравнений состояний Фрея. Первые $$(k-1) $$ уравнения (13.41) вместе с требованием нормализации и фактом, что предложенная нагрузка равняется обслуженной нагрузке плюс отклоненная нагрузка ( свойство PASTA ) дают в результате $$(k+1) $$ независимых линейных уравнений, которые легко решить.