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

1.7.4 Система M\G\1 с дисциплиной равномерного распределения процессора и дисциплиной LIFO с прерыванием обслуживания

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

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

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

Пусть есть число запросов в системе в момент времени t. Для исследования этого процесса будем использовать метод случайной замены времени. Кроме реального времени t будем рассматривать «фиктивное» время связанное с реальным соотношением . Это означает, что если в системе находится i запросов, то фиктивное время течет в i раз быстрее, чем реальное. Если система пуста или в ней находится один запрос, то фиктивное время совпадает с реальным.

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

При этом функция распределения длины запроса B(t) совпадает с функцией распределения времени обслуживания запроса.

При переходе к фиктивному времени следует пересчитать также интенсивность входящего потока. Поскольку фиктивное время течет быстрее, то интенсивность А потока в системе M\G\oo при нахождении в ней запросов определяется как:

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

Поскольку (для эргодических процессов) стационарная вероятность состояния процесса может трактоваться как средняя доля времени, проводимого процессом в данном состоянии, а реальное время течет в раз медленнее, чем фиктивное, то стационарная вероятность наличия запросов в системе M\G\1 с дисциплиной PS определяется как: где вероятности заданы формулой (1.114).

Отсюда окончательно получаем, что:

то есть, стационарное распределение числа запросов в системе M|G|1 с дисциплиной PS инвариантно относительно распределения времени обслуживания и является геометрическим. Условием существования этого распределения является выполнение неравенства

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

С использованием метода введения дополнительных переменных можно показать, что и в случае такой дисциплины распределение числа запросов в системе является геометрическим с параметром . Выходящий из системы поток при обеих дисциплинах является простейшим независимо от вида распределения (см., например, [123]).

При дисциплине LIFO с прерыванием время ожидания начала обслуживания - нулевое. Поэтому интерес представляет нахождение распределения времени пребывания запроса в системе.

Анализ поведения системы позволяет легко понять, что преобразование Лапласа - Стилтьеса этого распределения совпадает с преобразованием Лапласа - Стилтьеса распределения периода занятости системы M\G\1, не зависящим от дисциплины обслуживания и задаваемым уравнением (1.82).

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