Реферат: Дисциплины обслуживания. Модель с приоритетами. Дисциплины обслуживания с приоритетами, зависящими от времени
Третья составляющая задержки связана с требованиями, поступившими после того как пришло меченое требование, однако получившими обслуживание раньше его. Число таких требований обозначим Mip . Среднее значение этой составляющей задержки находится аналогично и составляет
.
Складывая все три составляющие, получаем, что среднее время ожидания в очереди для меченого требования определяется формулой
.
Очевидно, что независимо от дисциплины обслуживания число требований, Nip и Mip в системе не может быть произвольным, поэтому существует некоторый набор соотношений, связывающий между собой задержки для каждого из приоритетного класса. Важность этих соотношений для СМО позволяет называть их ЗАКОНАМИ СОХРАНЕНИЯ. Основой законов сохранения для задержек является тот факт, что незаконченная работа в любой СМО в течение любого интервала времени занятости не зависит от порядка обслуживания, если система является консервативной (требования не исчезают внутри системы и сервер не простаивает при непустой очереди).
Распределение времени ожидания существенно зависит от порядка обслуживания, но если дисциплина обслуживания выбирает требования независимо от времени их обслуживания (или любой меры, зависящей от времени обслуживания), то распределение числа требований и времени ожидания в системе инвариантно относительно порядка обслуживания.
Для СМО типа M/G/1 можно показать, что для любой дисциплины обслуживания должно выполняться следующее важное равенство
Это равенство означает, что взвешенная сумма времен ожидания никогда не изменяется, независимо от того, насколько сложна или искусно подобрана дисциплина обслуживания. Если удается сократить задержку для одних требований, то она немедленно возрастет для других.
Для более общей системы с произвольным распределением времени поступления требований G/G/1 закон сохранения может быть записан в виде
.
Общий смысл этого соотношения таков: взвешенная сумма времен задержки остается постоянной. Просто в правой части стоит разность средней незавершенной работы и остаточного времени обслуживания. Если предположить пуассоновский характер входного потока, то выражение для незавершенной работы можно записать в виде
.
Подставляя его в предыдущее выражение, сразу получается приведенный ранее закон сохранения для СМО типа M/G/1.
Рассмотрим теперь расчет среднего времени ожидания для СМО с обслуживанием в порядке приоритета, задаваемого приоритетной функцией
.
На рис. 1 приведена схема функционирования СМО с такой дисциплиной обслуживания: поступающее требование ставится в очередь слева от требования с равным или большим приоритетом.
Рис. 1 СМО с обслуживанием в порядке приоритета.
Воспользуемся формулой для Wp . Исходя из механизма функционирования, можно сразу выписать
Все требования более высокого, чем у меченого приоритета будут обслужены раньше. Из формулы Литтла число требований класса i находящихся в очереди, будет равно:
Требования более высокоприоритетных классов, поступившие в систему после меченого требования, пока оно находится в очереди, также будут обслужены перед ним.
Так как меченое требование будет находиться в очереди в среднем Wp секунд, то число таких требований будет равно
.
Непосредственно из формулы (*) получаем:
Эта система уравнений может быть решена рекуррентно, начиная с W1 ,W2 и т.д.