Главная > Разное > Теоретические основы проектирования компьютерных сетей
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

1.9 Многофазные системы

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

Многофазные СМО принято кодировать в виде последовательности символов типа:

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

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

Если какой - либо символ принимает конечное значение, то возникает вопрос о поведении многофазной СМО в ситуации, когда буфер перед соответствующей однофазной СМО уже полон, а на вход этой СМО поступает следующий запрос. Обычно рассматриваются два варианта: поступающий запрос теряется и поступающий запрос остается на приборе, где он закончил обслуживание, временно блокируя дальнейшую работу этого прибора.

Известные результаты для широкого круга многофазных СМО довольно исчерпывающе описаны в справочнике [210]. Здесь мы кратко коснемся трех простых многофазных СМО.

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

Вспоминая, что эрганговская случайная величина с параметрами есть сумма независимых случайных величин с параметром приходим к выводу, что все характеристики рассматриваемой СМО легко получить из характеристик соответствующей однофазной СМО типа Анализ такой СМО можно провести с использованием так называемого метода фаз Эрланга. Соответствующие результаты можно получить также из формул для системы

Так, для производящей функции распределения числа запросов в системе из формулы Поллячека - Хинчина см., например, формулу (1.45), с учетом равенства: получаем:

(1.122)

где коэффициент загрузки определяется как

Обозначим - корни уравнения

(1.123)

по модулю большие единицы.

Разлагая правую часть уравнения (1.122) на простые дроби и используя свойства производящей функции получаем:

(1.124)

где коэффициенты определяются следующим образом:

(1.126)

Рассмотрим теперь следующую многофазную СМО:

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

Обозначим число запросов в системе в момент времени - стационарную вероятность состояния рассматриваемой СМО, то есть

(1.127)

Можно показать, что условием существования пределов (1.127) является выполнение неравенств

(1.128)

Далее считаем эти неравенства выполненными.

Используя - метод», можно получить систему дифференциальных уравнений для вероятностей откуда, переходя к пределу при получим следующую систему уравнений для стационарных вероятностей

где

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

(1.130)

где

Вероятность находится из условия нормировки:

(1.131)

и имеет вид

(1.132)

Из (1.130), (1.131) и формул видим, что стационарные вероятности рассматриваемой СМО представимы в мультипликативном виде:

(1.133)

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

Этот факт, позволяющий рассчитывать распределение вероятностей состояний многофазной системы как произведение вероятностей состояний однофазных СМО, образующих данную СМО, следует из теоремы Берка ([154]), которая формулируется следующим образом.

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

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

В заключение раздела кратко рассмотрим многофазную СМО типа

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

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

Будем рассматривать двумерный процесс где есть момент окончания обслуживания запроса на первой фазе, - число запросов на первой фазе, - число запросов на второй фазе в момент времени Несложно видеть, что этот процесс является двумерной цепью Маркова с дискретным временем.

Обозначим одношаговые вероятности переходов этой цепи

Введем производящую функцию

Аналогично вложенной цепи для системы M\G\1, изученной в разделе 6, вероятности переходов зависят от значения , но не зависят от и I отдельно. Это делает введенное определение производящей функции корректным.

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

где

Составим из производящих функций матричную производящую функцию R(z) и введем в рассмотрение матрицу , состоящую из элементов

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

Обозначим

(1.134)

Утверждение 22. Векторная производящая функция удовлетворяет матричному функциональному уравнению:

(1.135)

Здесь I - тождественная матрица.

Условия существования пределов (1.134) и алгоритмы решения уравнения (1.135) можно найти, например, в [71], [252].

Распределение вероятностей состояний системы в произвольные моменты времени можно найти, используя теорию процессов марковского восстановления по аналогии с тем, как это сделано в подпункте 1.6.1.

<< Предыдущий параграф Следующий параграф >>
Оглавление