Реферат: Дисциплины обслуживания. Модель с приоритетами. Дисциплины обслуживания с приоритетами, зависящими от времени - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Дисциплины обслуживания. Модель с приоритетами. Дисциплины обслуживания с приоритетами, зависящими от времени

Банк рефератов / Информатика, информационные технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 712 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

Министерство образования Республики Беларусь Учреждение образования «Белорусск ий государственный университет информатики и радиоэлектроники» Кафедра Сетей и устройств телекоммуникаций РЕФЕРАТ На тему: « Дисциплины обслуживания. Модель с приоритетами. Дисциплины обслуживания с приоритетами, зависящими от времени » МИНСК, 2008 Дисциплины обслуживания. Модель с приоритетами. Дисциплина обслуживания – это способ определения того, какое требование в очереди должно обслуживаться следующим. Решение может основываться на одной из приведенных ниже х а рактеристик или на их совокупности: 1) мера, определяемая относительным временем поступления рассматриваем о го требования в очередь; 2) мера требуемого или полученного до сих пор времени обслуживания; 3) функция, определяющая принадлежность требования к той или иной группе. Примерами дисциплин обслуживания являются постоянно используемая м о дель «первый пришел - первый обслужен» (FCFS-first came-first served) , называ е мая в русскоязычной литературе «дисциплина обслуживания в порядке поступл е ния»-ОПП. Приведем здесь список некоторых типичных дисциплин обслужив а ния. ОПП-обслуживание в порядке поступления (FCFS); ООП – обслуживание в обратном порядке, т.е. последнее поступившее треб о вание обслуживается первым (LCFS); ПК – первоочередное обслуживание требований с кратчайшей длительностью обслуживания (SPT/SJE); ПКД – первоочередное обслуживание требований с кратчайшей длительностью дообслуживания (SRPT); ПКС – первоочередное обслуживание требований с кратчайшей средней дл и тельностью обслуживания (SEPT); ПКСД – первоочередное обслуживание требований с кратчайшей средней дл и тельностью дообслуживания (SERPT); ПКОВ – первоочередное обслуживание требований с кратчайшим обязател ь ным временем (SIPT). Если сравнивать эти дисциплины по среднему времени ожидания попарно, и обозначать тот факт, что среднее время ожидания для дисциплины D 1 ,больше или равно среднему времени ожидания для дисциплины D 2 следующим образом: D 1 D 2 , то можно построить сл е дующую диаграмму ПО ОПП ПК ПКД ОП Итак, основным предметом анализа различных дисциплин обслуживания б у дем считать расчет среднего времени ожидания требования в очереди или средн е го времени пребывания в системе. Предположим, что требования принадлежат одному из P различных приор и тетных классов, обозначаемых индексом p =1,2,3… P . Каждому требованию, нах о дящемуся в системе в момент времени t ставится в соответствие значение некот о рой приоритетной функции q p (t). Чем больше значение этой функции, тем выше приоритет требования. Всякий раз, когда принимается решение для выбора треб о вания на обслуживание, выбор делается в пользу требования с наибольшим знач е нием приоритетной функции. В простейшем случае в качестве приоритетной функции выбирается просто значение p . В этом случае приоритет требования тем больше, чем больший номер класса принадлежности оно имеет. Рассмотрим до с таточно общую модель, основанную на системе M/G/1. Предположим, что треб о вания из приоритетного класса p образуют пуассоновский поток с интенсивн о стью p требований в секунду. Время обслуживания каждого требования из этого класса выбирается независимо в соответствие с распределением с плотностью в е роятности b p (x) со средним значением . Введем следующие определения Здесь интерпретируется как доля времени, в течение которого сервер занят ( <1), а каждый из парциальных коэффициентов p – как доля времени, в течение которого сервер занят обслуживанием заявок из приоритетного класса с н о мером p . Если требование в процессе обслуживания может быть удалено из сервера и возвращено в очередь при поступлении требования с более высоким приоритетом, то говорят, что система работает с абсолютным приоритетом, если обслуживание любого требования, находящегося в сервере не может быть прервано, то говорят что СМО работает с относительным приоритетом. Основная модель расчета среднего времени ожид а ния Будем использовать далее следующие обозначения для среднего значения вр е мени ожидания в очереди требований из приоритетного класса p - W p , и среднего времени пребывания в системе для требований этого класса - T p : . Основное внимание будем уделять системам с относительным приоритетом. Рассмотрим процесс с момента поступления некоторого требования из приор и тетного класса p . Будем далее называть это требование меченым. Первая соста в ляющая времени ожидания для меченого требования связана с требованием, кот о рое оно застает в сервере. Эта составляющая равна остаточному времени обсл у живания другого требования. Обозначим теперь и будем использовать это обозн а чение и далее, среднюю задержку меченого требования, связанную с наличием другого требования на обслуживании W 0 . Зная распределение времени между с о седними поступлениями входных требований для каждого приоритетного класса, можно всегда вычислить эту величину. В нашем предположении пуассоновского закона для потока заявок каждого класса можно записать . Вторая составляющая времени ожидания для меченого требования определяе т ся тем, что перед меченым требованием обслуживаются другие требования, кот о рые меченое требование застало в очереди. Обозначим далее число требований из класса i , которое застало в очереди меченое требование (из класса p ) и которые обслуживаются перед ним N ip . Среднее значение этого числа будет определять в е личину среднего значения этой составляющей задержки . Третья составляющая задержки связана с требованиями, поступившими после того как пришло меченое требование, однако получившими обслуживание раньше его. Число таких требований обозначим M ip . Среднее значение этой составляющей задержки находится аналогично и соста в ляет . Складывая все три составляющие, получаем, что среднее время ожидания в очереди для меченого требования определяется формулой . Очевидно, что независимо от дисциплины обслуживания число требований, N ip и M ip в системе не может быть произвольным, поэтому существует некоторый набор соотношений, связывающий между собой задержки для каждого из приор и тетного класса. Ва жность этих соотношений для СМО позволяет называть их ЗАКОНАМИ СОХРАНЕНИЯ. Основой законов сохранения для задержек является тот факт, что незаконченная работа в любой СМО в течение любого интервала времени занятости не зависит от порядка обслуживания, если система является консервативной (требования не исчезают внутри системы и сервер не простаивает при непустой очер е ди). Распределение времени ожидания существенно зависит от порядка обслужив а ния, но если дисциплина обслуживания выбирает требования независимо от вр е мени их обслуживания (или любой меры, зависящей от времени обслуживания), то распределение числа требований и времени ожидания в системе инвариантно отн о сительно порядка обслуживания. Для СМО типа M/G/1 можно показать, что для любой дисциплины обслужив а ния должно выполняться следующее важное равенство Это равенство означает, что взвешенная сумма времен ожидания никогда не изменяется, независимо от того, насколько сложна или искусно подобрана дисц и плина обслуживания. Если удается сократить задержку для одних требований, то она немедленно возрастет для других. Для более общей системы с произвольным распределением времени поступл е ния требований G/G/1 закон сохранения может быть записан в виде . Общий смысл этого соотношения таков: взвешенная сумма времен задержки остается постоянной. Просто в правой части стоит разность средней незаверше н ной работы и остаточного времени обслуживания. Если предположить пуассоно в ский характер входного потока, то выражение для незавершенной работы можно зап и сать в виде . Подставляя его в предыдущее выражение, сразу получается приведенный ранее закон сохранения для СМО типа M/G/1. Рассмотрим теперь расчет среднего времени ожидания для СМО с обслужив а нием в порядке приоритета, задаваемого приоритетной функцией . На рис. 1 приведена схема функционирования СМО с такой дисциплиной о б служивания: поступающее требование ставится в очередь слева от требования с равным или большим приоритетом. Рис. 1 СМО с обслуживанием в порядке приоритета. Воспользуемся формулой для W p . Исходя из механизма функционирования, можно сразу вып и сать Все требования более высокого, чем у меченого приоритета будут обслужены раньше. Из формулы Литтла число требований класса i находящихся в очереди, будет равно: Требования более высокоприоритетных классов, поступившие в систему после меченого требования, пока оно находится в очереди, также будут обслужены п е ред ним. Так как меченое требование будет находиться в очереди в среднем W p секунд, то число таких требований будет равно . Непосредственно из формулы (*) получаем: Эта система уравнений может быть решена рекуррентно, начиная с W 1 ,W 2 и т.д. Полученная формула позволяет рассчитывать характеристики качества обсл у живания для всех приоритетных классов. На рисунке 2 показано, как изменяется нормированная величина времени ожидания в очереди для СМО с пятью приор и тетными классами с равной интенсивностью потока требований каждого приор и тетного класса и равным средним временем обслуживания требований каждого класса (нижний рисунок детализирует кривые при значениях малой нагрузки). Рис. 2 Обслуживание в порядке приоритетов в случае относительных приорит е тов (Р=5, Р = /5, ). Особую задачу представляет определение законов распределения времени ожидания. Рассмотрим теперь систему с абсолютными приоритетами и обслуживанием в порядке приоритета с дообслуживанием. Применим подход полностью аналоги ч ный рассмотренному ранее. Средняя задержка в системе меченого требования также состоит из трех составляющих: первая составляющая- это среднее время обслуживания, вторая – это задержка из-за обслуживания тех требований равного или более высокого приоритета, которые меченое требование застало в системе. Третья составляющая средней задержки меченого требования представляет собой задержку за счет любых требований, поступающих в систему до ухода меченого требования и имеющих строго больший приоритет. Расписывая все эти три с о ставляющие общего времени нахо ж дения в системе, получим . Весьма интересной задачей является выбор приоритетов для заявок различных классов. Поскольку имеет место закон сохранения, оптимизация имеет смысл только при рассмотрении некоторых дополнительных атрибутов каждого класса требований. Предположим, что можно оценить каждую секунду задержки заявки приоритетного класса p некоторой стоимостью C p . Тогда средняя стоимость с е кунды задержки для системы может быть выражена через среднее число требований ка ж дого класса, находящихся в системе Решим задачу нахождения дисциплины обслуживания с относительными пр и оритетами для системы M/G/1, которая минимизирует среднюю стоимость з а держки C . Пусть имеется P приоритетных классов заявок с заданной интенсивн о стью поступления и средним временем обслуживания. Перенесем в левую часть постоянную сумму и выразим правую часть через известные параметры Задача состоит в минимизации суммы в правой части этого равенства путем выбора соответствующей дисциплины обслуживания, т.е. выбора последовател ь ности индексов p . Обозначим В этих обозначениях задача выглядит так: нужно минимизировать сумму пр о изведений при условии Условие независимости суммы функций g p от выбора дисциплины обслужив а ния определяется законом сохранения. Иначе говоря задача состоит в минимиз а ции площади под кривой произведения двух функций , при условии , что площадь под кривой одной из них постоянна. Решение состоит в том, что сначала упорядочим последовательность значений f p : . А затем выберем для каждого f p свое значение g p , так, чтобы минимизировать сумму их произведений. Интуитивно ясно, что оптимальная стратегия выбора с о стоит в подборе наименьшего значения g p для наибольшего f p , далее для оста в шихся значений следует поступать тем же образом. Поскольку g p = W p p , то м и нимизация сводится к минимизации значений средней задержки. Таким образом, решение рассматриваемой задачи оптимизации состоит в том, что из всех во з можных дисциплин обслуживания с относительным приоритетом минимум сре д ней стоимости обеспечивает дисциплина с упорядоченными приоритетами в с о ответствие с неравенств а ми . Дисциплины обслуживания с приоритетами, зависящими от времени На практике часто встречается задача назначения приоритетов в зависимости от времени поступления заявки. Например, для того, чтобы никакие требования не задерживались в системе очень долго, несмотря на общую нагрузку, организ у ют дисциплину обслуживания, при которой чем дольше заявка находится в сист е ме, тем ее приоритет становится выше. Рассмотрим приоритетные функции, линейно зависящие от времени с крути з ной нарастания, зависящей от номера класса, к которому принадлежит требов а ние. Предположим, что некоторое меченое требование поступает в момент и п о лучает в момент t приоритет, определяемый значением приоритетной функции Всякий раз, когда сервер готов к обслуживанию нового требования он выбир а ет из очереди требование с наивысшим мгновенным приоритетом- наибольшим значением приоритетной функции. Требования из класса с большим значением p наращивают приоритет с большей скоростью, чем требования из низшего приор и тетного класса. На рисунке 3 показан пример того, как поступившее позже тр е бование, но из высшего приоритетного класса, может получить обслуживание раньше, чем поступившее ранее требование из менее приоритетного класса. Это произойдет, если сервер освободится позже момента t 0 . При освобождении се р вера до этого момента, обслуживание получит первое из поступивших требов а ний. Рис. 3 Взаимодействие между приоритетными функциями для СМО с приоритетами, зависящими от времени. Исследуем эту систему при экспоненциальном распределении времени обсл у живания. Найдем среднее число требований , поступивших позже меченого , из классов с p i , которые будут обслужены раньше меченого. Очевидно, что для таких тр е бований скорость нарастания приоритетной функции меньше скорости нарастания приоритетной функции меченого требования и , следовательно число таких треб о ваний равно нулю. Теперь определим число таких требований для классов с большей, чем у меченого скоростью нарастания приоритетной функции p < i . Из рассмотрения рисунка 3 можно видеть, что задержка меченого требования в си с теме для этого случая Wp=t 0 - связана с интервалом времени на котором пост у пают заявки, опережающие меченое требование V I = i - соотношением Отсюда получаем, что этот интервал равен Следовательно, при интенсивности i входящего потока для требований i -го класса находим среднее число «обгоняющих» требований Рассмотрим теперь меченое требование из класса p , поступающее в момент =0 и находящееся в очереди в течение времени t p . Рис. 4 График приоритета q p ( t ), используемый для получения . На рисунке 4 показано, что значение функции приоритета этого требования к моменту поступления на сервер будет равно b p t p . При поступлении меченого тр е бования оно застает в очереди n i требований из класса i . Одно из таких требов а ний показанное на рисунке 4 поступило в момент t=-t 1 . Определим теперь сре д нее число требований из класса i , которые поступают до нулевого значения м о мента времени, находятся в нулевой момент еще в очереди и получают обслуж и вание раньше меченого требования. Из рисунка 4 можно видеть, что этому усл о вию удовлетворяет требование из класса i , которое поступает в момент -t 1 и ож и дает в очереди в течение времени Из рассмотрения соотношений на рисунке видно, что Тогда среднее число требований При i > p Подставив вычисленные средние значения для «обгоняющих» требований п о лучим систему линейных уравнений для величин задержки меченого требования Производя преобразования, можно свести решение этой системы уравнений к рекурсивной форме Полученная формула представляет собой главный результат анализа дисци п лины обслуживания с приоритетами, зависящими от времени. Типичная характ е ристика СМО с проанализированной дисциплиной обслуживания приведена на рисунке 5 Штриховая линия показывает характеристику для системы без пр и оритетов. Видно, что действие закона сохранения проявляется здесь в том, что х о тя одна часть заявок, получившая высший приоритет будет иметь меньшее время ожидания, чем в системе без приоритетов с обслуживанием в порядке поступл е ния, другая часть заявок при этом обязательно будет задержана на большее, чем в бе с приоритетной системе время. Оптимизация назначения приоритетов Рассмотрим систему M/G/1 с интенсивностью поступающего пуассоновского потока требований в секунду и произвольной функцией плотности вероятности для времени обслуживания с заданным средним временем обслуживания. Пусть плата за требование Y является случайной величиной с произвольной функцией распределения . Система функционирует следующим образом: новое требование, поступившее в систему «предлагает» неотрицательную плату Y «организатору очереди». После этого требованию предоставляется место в очереди такое, что все требования внесшие м еньшую плату оказываются позади , большую впереди данного треб о вания. В каждый момент времени сервер, завершив обслуживание очередного требования, принимает на обслуживание требование, оказавшееся впереди всей очереди. До полного завершения обслуживания требование не покидает сервер. Требования, внесшие одинаковую плату, обслуживаются в порядке поступления. Найдем среднее время ожидания в очереди для требования, внесшего плату Y=y . Это время складывается из трех составляющих. Во-первых, это время на д о обслуживание требования, находящегося в данный момент в сервере. Во-вторых – время обслуживания требований, которые поступили раньше и внесли большую или равную плату. Наконец меченому требованию придется ждать обслуживания всех требований поступивших позже его, но внесли большую плату. Среднее чи с ло требований, плата которых лежит в интервале ( u,u+du ) определяется по фо р муле Литтла : , где . Используя обозначения для нижнего и верхнего предела функции (u) можно записать суммарное выражение для времени ожидания в очереди для меченого требования в виде: Используя ряд соотношений и обозначений можно найти, что при разрывной функции распределения вероятности это соотношение может быть приведено к виду При абсолютно непрерывной функции плотности вероятности получим . Таким образом, мы получили конечное среднее время ожидания для всех тр е бований, которые вносят плату выше, чем некоторое критическое значение В пределе, когда размер платы стремится к бесконечности, среднее время ож и дания стремится к W 0 . Нетрудно убедиться, что когда размер платы для всех тр е бований одинаков Это известный результат для СМО типа M/G/1 при обслуживании в порядке поступления, как и следовало ожидать, поскольку равная плата равносильна ее отсутствию с точки зрения распределения приоритетов. При распределении приоритетов можно рассмотреть и другие стоимостные з а дачи. Определим оптимальное распределение платы за приоритеты в следующих предположениях. Пусть имеется зависимость стоимости от времени задержки в очереди для каждого требования, т.е. есть возможность определить, сколько стоит каждая секунда ожидания в очереди. Опишем эту зависимость с помощью сл у чайного коэффициента нетерпения . Очевидно, что общие затраты клиента при обслуживании будут состоять из платы за место в очереди и потерь от времени ожидания. Для требования с фикс и рованным коэффициентом нетерпения эти затраты равны Пусть для всей совокупности клиентов можно определить функцию распред е ления вероятностей коэффициентов нетерпения Сформулируем следующую задачу оптимизации: найти функцию y , которая минимизирует среднюю стоимость С при условии ограничения всей средней пл а ты некоторой заданной величиной B . Определим Преобразуя минимизируемый интеграл, получим Из закона сохранения в непрерывной форме следует, что решение задачи минимизации стоимости сводится к нахождению такой функции, при которой минимальна площадь под кривой произвед е ния : . В то время как площадь под кривой, определяемой первым сомножителем должна оставаться постоянной. Путем рассуждений о согласованности возрастания и убывания функций, вх о дящих в произведение, можно сделать вывод, что решением задачи являются все функции, удовлетворяющие условию Множество S такое, что . Выберем самую простую строго возрастающую функцию – линейную. Таким образом, будем считать, что плата пропорциональна коэффициенту нетерпения. . Применяя ограничение средней платы получим, что, если считать средний коэффициент нетерпения равный A Это и есть функция оптимальной платы. В качестве примера рассмотрим систему с показательным распределением пл а ты Время ожидания можно непосредственно вычислить: Используя рассмотренное правило оптимальной платы можно найти распред е ление коэффициента нетерпения Следовательно, средняя стоимость получается: Описанная оптимизация является глобальной и позволяет найти функцию пл а ты, которые минимизируют общую среднюю стоимость.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Учительница английского языка перебила ученика, стремительно вбежавшего в класс, словами: "In English, please!", и все узнали об инфаркте трудовика только через полчаса.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

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

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru