Анализ систем массового обслуживания с приоритетами
Лекция №15
по дисциплине “Теория распределение информации»
Наименование темы: Анализ систем массового обслуживания с приоритетами
1. Основная модель расчета среднего времени ожидания
2. Дисциплины обслуживания с приоритетами, зависящими от времени
1. Основная модель расчета среднего времени ожидания
Будем использовать далее следующие обозначения для среднего значения времени ожидания в очереди требований из приоритетного класса p - Wp, и среднего времени пребывания в системе для требований этого класса - Tp:
.
Основное внимание будем уделять системам с относительным приоритетом. Рассмотрим процесс с момента поступления некоторого требования из приоритетного класса p. Будем далее называть это требование меченым. Первая составляющая времени ожидания для меченого требования связана с требованием, которое оно застает в сервере. Эта составляющая равна остаточному времени обслуживания другого требования. Обозначим теперь и будем использовать это обозначение и далее, среднюю задержку меченого требования, связанную с наличием другого требования на обслуживании W0. Зная распределение времени между соседними поступлениями входных требований для каждого приоритетного класса, можно всегда вычислить эту величину. В нашем предположении пуассоновского закона для потока заявок каждого класса можно записать
.
Вторая составляющая времени ожидания для меченого требования определяется тем, что перед меченым требованием обслуживаются другие требования, которые меченое требование застало в очереди. Обозначим далее число требований из класса i, которое застало в очереди меченое требование (из класса p) и которые обслуживаются перед ним Nip. Среднее значение этого числа будет определять величину среднего значения этой составляющей задержки
.
Третья составляющая задержки связана с требованиями, поступившими после того как пришло меченое требование, однако получившими обслуживание раньше его. Число таких требований обозначим Mip. Среднее значение этой составляющей задержки находится аналогично и составляет
.
Складывая все три составляющие, получаем, что среднее время ожидания в очереди для меченого требования определяется формулой
.
Очевидно, что независимо от дисциплины обслуживания число требований, Nip и Mip в системе не может быть произвольным, поэтому существует некоторый набор соотношений, связывающий между собой задержки для каждого из приоритетного класса. Важность этих соотношений для СМО позволяет называть их ЗАКОНАМИ СОХРАНЕНИЯ. Основой законов сохранения для задержек является тот факт, что незаконченная работа в любой СМО в течение любого интервала времени занятости не зависит от порядка обслуживания, если система является консервативной (требования не исчезают внутри системы и сервер не простаивает при непустой очереди).
Распределение времени ожидания существенно зависит от порядка обслуживания, но если дисциплина обслуживания выбирает требования независимо от времени их обслуживания (или любой меры, зависящей от времени обслуживания), то распределение числа требований и времени ожидания в системе инвариантно относительно порядка обслуживания.
Для СМО типа M/G/1 можно показать, что для любой дисциплины обслуживания должно выполняться следующее важное равенство
Это равенство означает, что взвешенная сумма времен ожидания никогда не изменяется, независимо от того, насколько сложна или искусно подобрана дисциплина обслуживания. Если удается сократить задержку для одних требований, то она немедленно возрастет для других.
Для более общей системы с произвольным распределением времени поступления требований G/G/1 закон сохранения может быть записан в виде
.
Общий смысл этого соотношения таков: взвешенная сумма времен задержки остается постоянной. Просто в правой части стоит разность средней незавершенной работы и остаточного времени обслуживания. Если предположить пуассоновский характер входного потока, то выражение для незавершенной работы можно записать в виде
.
Подставляя его в предыдущее выражение, сразу получается приведенный ранее закон сохранения для СМО типа M/G/1.
Рассмотрим теперь расчет среднего времени ожидания для СМО с обслуживанием в порядке приоритета, задаваемого приоритетной функцией
.
На рис.1 приведена схема функционирования СМО с такой дисциплиной обслуживания: поступающее требование ставится в очередь слева от требования с равным или большим приоритетом.
Рис. 1 СМО с обслуживанием в порядке приоритета.
Воспользуемся формулой для Wp. Исходя из механизма функционирования, можно сразу выписать
Все требования более высокого, чем у меченого приоритета будут обслужены раньше. Из формулы Литтла число требований класса i находящихся в очереди, будет равно:
Требования более высокоприоритетных классов, поступившие в систему после меченого требования, пока оно находится в очереди, также будут обслужены перед ним. Так как меченое требование будет находиться в очереди в среднем Wp секунд, то число таких требований будет равно
.
Непосредственно из формулы (*) получаем:
Эта система уравнений может быть решена рекуррентно, начиная с W1,W2 и т.д.
Полученная формула позволяет рассчитывать характеристики качества обслуживания для всех приоритетных классов. На рисунке 7.2. показано, как изменяется нормированная величина времени ожидания в очереди для СМО с пятью приоритетными классами с равной интенсивностью потока требований каждого приоритетного класса и равным средним временем обслуживания требований каждого класса (нижний рисунок детализирует кривые при значениях малой нагрузки).
Рисунок 2.Обслуживание в порядке приоритетов в случае относительных приоритетов (Р=5, Р= /5, ).
Особую задачу представляет определение законов распределения времени ожидания.
Рассмотрим теперь систему с абсолютными приоритетами и обслуживанием в порядке приоритета с дообслуживанием. Применим подход полностью аналогичный рассмотренному ранее. Средняя задержка в системе меченого требования также состоит из трех составляющих: первая составляющая- это среднее время обслуживания, вторая – это задержка из-за обслуживания тех требований равного или более высокого приоритета, которые меченое требование застало в системе. Третья составляющая средней задержки меченого требования представляет собой задержку за счет любых требований, поступающих в систему до ухода меченого требования и имеющих строго больший приоритет. Расписывая все эти три составляющие общего времени нахождения в системе, получим
.
Весьма интересной задачей является выбор приоритетов для заявок различных классов. Поскольку имеет место закон сохранения, оптимизация имеет смысл только при рассмотрении некоторых дополнительных атрибутов каждого класса требований. Предположим, что можно оценить каждую секунду задержки заявки приоритетного класса p некоторой стоимостью Cp. Тогда средняя стоимость секунды задержки для системы может быть выражена через среднее число требований каждого класса, находящихся в системе
Решим задачу нахождения дисциплины обслуживания с относительными приоритетами для системы M/G/1, которая минимизирует среднюю стоимость задержки C. Пусть имеется P приоритетных классов заявок с заданной интенсивностью поступления и средним временем обслуживания. Перенесем в левую часть постоянную сумму и выразим правую часть через известные параметры
Задача состоит в минимизации суммы в правой части этого равенства путем выбора соответствующей дисциплины обслуживания, т.е. выбора последовательности индексов p.
Обозначим
В этих обозначениях задача выглядит так: нужно минимизировать сумму произведений при условии
Условие независимости суммы функций gp от выбора дисциплины обслуживания определяется законом сохранения. Иначе говоря задача состоит в минимизации площади под кривой произведения двух функций , при условии , что площадь под кривой одной из них постоянна.
Решение состоит в том, что сначала упорядочим последовательность значений fp: .
А затем выберем для каждого fp свое значение gp, так, чтобы минимизировать сумму их произведений. Интуитивно ясно, что оптимальная стратегия выбора состоит в подборе наименьшего значения gp для наибольшего fp , далее для оставшихся значений следует поступать тем же образом. Поскольку gp=Wpp, то минимизация сводится к минимизации значений средней задержки. Таким образом, решение рассматриваемой задачи оптимизации состоит в том, что из всех возможных дисциплин обслуживания с относительным приоритетом минимум средней стоимости обеспечивает дисциплина с упорядоченными приоритетами в соответствие с неравенствами
.
2. Дисциплины обслуживания с приоритетами, зависящими от времени
На практике часто встречается задача назначения приоритетов в зависимости от времени поступления заявки. Например, для того, чтобы никакие требования не задерживались в системе очень долго, несмотря на общую нагрузку, организуют дисциплину обслуживания, при которой чем дольше заявка находится в системе, тем ее приоритет становится выше.
Рассмотрим приоритетные функции, линейно зависящие от времени с крутизной нарастания, зависящей от номера класса, к которому принадлежит требование.
Предположим, что некоторое меченое требование поступает в момент и получает в момент t приоритет, определяемый значением приоритетной функции
Всякий раз, когда сервер готов к обслуживанию нового требования он выбирает из очереди требование с наивысшим мгновенным приоритетом- наибольшим значением приоритетной функции. Требования из класса с большим значением p наращивают приоритет с большей скоростью, чем требования из низшего приоритетного класса. На рисунке 3. показан пример того, как поступившее позже требование, но из высшего приоритетного класса, может получить обслуживание раньше, чем поступившее ранее требование из менее приоритетного класса. Это произойдет, если сервер освободится позже момента t0 . При освобождении сервера до этого момента, обслуживание получит первое из поступивших требований.
Рис.3. Взаимодействие между приоритетными функциями для СМО с приоритетами, зависящими от времени.
Исследуем эту систему при экспоненциальном распределении времени обслуживания.
Найдем среднее число требований , поступивших позже меченого , из классов с p i , которые будут обслужены раньше меченого. Очевидно, что для таких требований скорость нарастания приоритетной функции меньше скорости нарастания приоритетной функции меченого требования и , следовательно число таких требований равно нулю. Теперь определим число таких требований для классов с большей, чем у меченого скоростью нарастания приоритетной функции p< i. Из рассмотрения рисунка 7.3. можно видеть, что задержка меченого требования в системе для этого случая Wp=t0- связана с интервалом времени на котором поступают заявки, опережающие меченое требование VI = i - соотношением
Отсюда получаем, что этот интервал равен
Следовательно, при интенсивности i входящего потока для требований i-го класса находим среднее число «обгоняющих» требований
Рассмотрим теперь меченое требование из класса p, поступающее в момент =0 и находящееся в очереди в течение времени tp.
Рисунок 4. График приоритета qp(t), используемый для получения .
На рисунке 4. показано, что значение функции приоритета этого требования к моменту поступления на сервер будет равно bptp. При поступлении меченого требования оно застает в очереди ni требований из класса i . Одно из таких требований показанное на рисунке 7.4. поступило в момент t=-t1. Определим теперь среднее число требований из класса i , которые поступают до нулевого значения момента времени, находятся в нулевой момент еще в очереди и получают обслуживание раньше меченого требования. Из рисунка 7.4. можно видеть, что этому условию удовлетворяет требование из класса i , которое поступает в момент -t1 и ожидает в очереди в течение времени
Из рассмотрения соотношений на рисунке видно, что
Тогда среднее число требований
При i > p
Подставив вычисленные средние значения для «обгоняющих» требований получим систему линейных уравнений для величин задержки меченого требования
Производя преобразования, можно свести решение этой системы уравнений к рекурсивной форме
Полученная формула представляет собой главный результат анализа дисциплины обслуживания с приоритетами, зависящими от времени. Типичная характеристика СМО с проанализированной дисциплиной обслуживания приведена на рисунке 5. Штриховая линия показывает характеристику для системы без приоритетов. Видно, что действие закона сохранения проявляется здесь в том, что хотя одна часть заявок, получившая высший приоритет будет иметь меньшее время ожидания, чем в системе без приоритетов с обслуживанием в порядке поступления, другая часть заявок при этом обязательно будет задержана на большее, чем в бесприоритетной системе время.
Рис. 5 для СМО с относительными приоритетами, зависящими от времени (Р=5, р=/5,).
Анализ систем массового обслуживания с приоритетами