Разомкнутые СМО с ожиданием и терпеливыми заявками

Будем рассматривать СМО разомкнутого типа, содержащую mоднотип-

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

лением времени обслуживания со средним значением

TОБ

или, что эквивалент-

но, простейшим потоком обслуживаний с интенсивностью m = 1/ t ОБ

мо от типа обслуживаемой заявки.

независи-

При полностью загруженных каналах обслуживания заявки могут ждать обслуживания в общей очереди, число мест в которой равно n. Дисциплина ожидания - FIFO, заявки становятся в очередь в порядке поступления, при пе- реполнении очереди вновь поступившая заявка получает отказ. Дисциплина обслуживания также FIFO, выбор заявки из очереди при освобождении какого- либо из каналов обслуживания делается из начала очереди. Заявки на входе СМО относятся к одному из Мтипов, причем заявки i-го типа образуют про-

стейший поток с интенсивностью li( i = 1, M ).

Поскольку рассматривается бесприоритетная СМО с общей очередью, целесообразно рассматривать объединенный входящий поток, который будет также простейшим с интенсивностью (3.19):

M

l = е li.

i =1

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

Возможные состояния СМО будем связывать с числом заявок, находя-

щихся в СМО:

S0- в СМО нет ни одной заявки, каналы обслуживания простаивают, оче-

редь отсутствует;

S1- в СМО одна заявка, ее обслуживанием занят один из каналов обслужи-

вания, другие (m - 1)канал обслуживания простаивают, очередь отсутствует;

. . . . . . . . . . . . . . . . . . . . . .

Si- в СМО iзаявок, их обслуживанием заняты iканалов обслуживания, дру-

гие (m - i)канал обслуживания простаивают, очередь отсутствует;

. . . . . . . . . . . . . . . . . . . . . .

Sm- в СМО mзаявок, все каналы обслуживания загружены, очередь отсут-

ствует;

Sm+1 - в СМО (m +1)заявок, все каналы обслуживания загружены, послед-

няя из пришедших в СМО заявок находится в очереди;

. . . . . . . . . . . . . . . . . . . . . .

Sm+l- в СМО (m + l)заявок, все каналы обслуживания загружены, lзаявок находится в очереди (l- длина очереди);

. . . . . . . . . . . . . . . . . . . . . .

Sm+n- в СМО (m+n) заявок, все каналы обслуживания загружены, все nмест в очереди заняты ожидающими обслуживания заявками, СМО в этом состоя- нии не способна принять дополнительно ни одной заявки, все вновь приходя- щие заявки будут получать отказ (состояние «насыщения» системы).

Переходы между состояниями такой СМО будут происходить под дейст- вием входящего и выходящего потоков заявок. Граф функционирования такой системы имеет вид:

Рис. 3.7. Граф состояний разомкнутой многоканальной СМО с очередью и тер-

пеливыми заявками

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

м-lP0+ mP1 = 0,

п-(l+ im)P

+ lP

+ (i + 1)mP

= 0;

1 Јi Јm - 1,

П i i-1

i+1

н-(l+ mm)Pm+ lPm-1+ mmPm+1= 0,

(3.32)

п-(l+ mm)P

+ lP

+ mmP

= 0;

1 Јi Јn - 1,

п m+i

m+ i-1

m+ i+1

- mmPm+n+ lPm+n-1= 0.

Условие нормировки вероятностей имеет вид:

M n

еPi + еPm +i = 1. (3.33)

i =0

i =1

Решая систему уравнений, можно определить искомые вероятности.

Рассчитаем показатели эффективности СМО.

Вероятность потери заявки Pnсовпадает с вероятностью отказа PОТКи равна вероятности нахождения СМО в состоянии Sm+n:

PП = PОТК

= Pm+n.

Вероятность обслуживания PОБи интенсивность потока обслуженных заявок lОопределяются, соответственно, выражениями:

PОБ

= 1 - PП,

Среднее число занятых каналов можно определить согласно выражению:

m n

K = еip i + mеp m + i. (3.34)

i = 0

i =1

Однако более удобно определение среднего числа занятых каналов как отношение интенсивности потока обслуженных заявок lОк интенсивности об- служивания m, характеризующей производительность одного канала обслужи- вания:

M m

Найдем теперь среднюю длину очереди l:

n

l = е iPm+i. (3.36)

i =1

Далее определяется среднее число заявок в СМО

Z = K + l. (3.37)

Перейдем к определению временных характеристик.

Важным показателем эффективности СМО с ожиданием является среднее

время ожидания заявки в очереди

tОЖ, характеризующее запаздывание заявки

за счет наличия в СМО других заявок. Для определения

tОЖсформулируем

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

Если заявка застанет СМО в одном из состояний S0, S1, ..., Sm-1, ей вообще не придется ждать (tОЖ = 0), так как для этих состояний характерно наличие в системе хотя бы одного свободного канала, следовательно, задержка отсутст- вует и обслуживание заявки будет начато немедленно.

Застав СМО в состоянии Sm, когда все mканалов заняты, заявка должна будет встать в очередь (занять первое место в очереди) и ждать окончания об- служивания в одном из каналов обслуживания. Суммарный поток обслужива- ния при полностью загруженных каналах складывается из mпростейших пото- ков обслуживаний с одинаковой для всех каналов средней длительностью об-

служивания

tОБ, следовательно, суммарный поток будет характеризоваться

средней длительностью обслуживания

tОБ / m

и интенсивностью обслужива-

ния mm. Вследствие отсутствия последействия в простейшем суммарном пото- ке обслуживаний время ожидания заявки в рассматриваемой ситуации равно в среднем 1/(mm), причем вероятность этой ситуации равна Pm.

Застав СМО с вероятностью Pm+1в состоянии Sm+1(все каналы обслужи-

вания заняты, в очереди одна заявка), вновь прибывшая заявка займет второе

место в очереди и должна будет ждать в среднем 2/(mm)единиц времени и т.д.

Последнее состояние, находясь в котором СМО еще способна принять заявку в очередь, Sm+n-1имеет вероятность Pm+n-1, время ожидания заявки, за- ставшей СМО в состоянии Sm+n-1, равно в среднем n/(mm).Время ожидания за- явки, заставшей СМО в состоянии Sm+n, равно нулю, так как заявка получает отказ и является потерянной для СМО.

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

n-1 жi + 1 ц

TОЖ

= ез

чPm + i. (3.38)

i =0 и mmш

Между средней длиной очереди lи средним временем ожидания заявки в очереди существует связь:

l = lt ОЖ. (3.39) Определим среднее время пребывания заявки в канале обслуживания. Время пребывания в канале обслуживания tОБ- случайная величина, для

определения которой необходимо рассмотреть различные возможные ситуа-

ции.

Если заявка застает СМО в состоянии Sm+n, вероятность которого равна Pm+n= PОТК, время пребывания ее в канале обслуживания равно нулю, посколь- ку заявка получает отказ и тотчас же попадает в выходящий поток СМО.

Застав СМО в любом другом состоянии, что происходит с вероятностью

1 - Pm+n = 1 – PОТК = PОБ, заявка попадает в систему и поскольку другие виды потерь в рассматриваемой СМО отсутствуют непременно проходит обслужи- вание, то есть время пребывания в канале обслуживания в данной ситуации равно случайной величине, распределенной экспоненциально со средней дли-

тельностью обслуживания

tОБ.

Теперь нетрудно найти среднее время обслуживания:

1

T ОБ

= p. (3.40)

M ОБ

Сравним среднее время обслуживания со средним числом занятых кана-

лов K. Убедимся в справедливости соотношения, связывающего эти две ха-

рактеристики:

K = lt ОБ. (3.41)

Рассмотрим еще один показатель эффективности СМО – среднее время пребывания заявки в системе. Среднее время пребывания произвольной заявки в системе складывается из среднего времени пребывания в очереди (ожидания)

tОЖ

и из среднего времени пребывания в канале обслуживания

tОБ. Вследст-

вие независимости процессов обслуживания и ожидания справедливо соотно-

шение:

tC = t ОЖ

+ t ОБ.

Отсюда можно найти среднее число заявок в системе:

Z = lt C. (3.42)

Предельные варианты разомкнутой СМО

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

Для этой СМО с отсутствием очереди (n = 0) заявка, поступившая на вход СМО, либо сразу попадает на обслуживание, если свободен хотя бы один из каналов обслуживания, либо получает отказ и попадает в ту часть выходя-

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

Граф состояний m-канальной СМО с отказами приведен на рис.3.8.

Рис. 3.8. Граф состояний разомкнутой многоканальной СМО без очереди

Исходя из этого графа, для установившегося режима запишем алгебраи-

ческую систему уравнений в виде:

м- lP0+ mP1 = 0,

п

о-mmPm+ lPm-1= 0.

1 Ј i Ј m - 1,

(3.43)

Условие нормировки вероятностей имеет вид:

m

е Pi = 1.

i =0

Решая данную систему уравнений, можно найти вероятности пребывания системы в i-х состояниях.

Отказ получает заявка, заставшая СМО в состоянии Sm, следовательно

PОТК

= p m.

Вероятность обслуживания PОБи интенсивность потока обслуженных заявок lОравны, соответственно

PОБ = 1 – PОТК = 1 – Pm ,

lО = lPОБ = l(1 – Pm).

Среднее число занятых каналов можно определить либо как отношение

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

либо по зависимости:

LО lP

K = = ОБ,

M m

m

K = е iPi.

i = 0

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

Z = K.

Среднее время пребывания заявки в системе совпадает со средним вре-

менем ее обслуживания.

tОБ

= 1 P.

m ОБ

Рассмотрим другой предельный вариант СМО, когда число мест в очере- ди бесконечно (n ® Ґ) и на время пребывания заявки в системе не наложено ограничений. Такие СМО называются чистыми СМО с ожиданием, или СМО без потерь, поскольку любая заявка, поступающая на вход системы, либо не- медленно назначается на обслуживание, либо ставится в очередь на обслужи- вание, причем из-за отсутствия потерь все заявки из входящего потока рано или поздно будут обслужены.

Граф состояний такой СМО имеет вид:

Рис. 3.9. Граф состояний разомкнутой многоканальной СМО

с бесконечной очередью

Число состояний такой системы бесконечно велико. Следовательно, сис-

тема алгебраических уравнений для нее будет иметь бесконечную размерность.

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

Анализ рассматриваемой СМО, проведенный специальными методами, показывает, что для нее возможен установившийся режим (вероятности со- стояний отличны от нуля) при выполнении следующего условия:

l/(mm) < 1.

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

Потери в такой СМО отсутствуют, поэтому вероятность обслуживания

равна единице PОБ= 1, интенсивность потока обслуженных заявок совпадает с интенсивностью входящего потока l = lО.