Міністерство освіти Республіки Білорусь
Заклад освіти «Білоруський державний університет інформатики і радіоелектроніки»
Кафедра Мереж і пристроїв телекомунікацій
РЕФЕРАТ
На тему:
«Дисципліни обслуговування. Модель з пріоритетами. Дисципліни обслуговування з пріоритетами, залежними від часу »
МІНСЬК, 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 утворюють Пуассонівський потік з інтенсивністю l p вимог у секунду. Час обслуговування кожної вимоги з цього класу вибирається незалежно у відповідність з розподілом із щільністю ймовірності b p (x) з середнім значенням
Введемо такі визначення
Тут r інтерпретується як частка часу, протягом якого сервер зайнятий (r <1), а кожен з парціальних коефіцієнтів r p - як частка часу, протягом якого сервер зайнятий обслуговуванням заявок з пріоритетного класу з номером 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, l Р = l / 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 r p, то мінімізація зводиться до мінімізації значень середньої затримки. Таким чином, рішення даної задачі оптимізації полягає в тому, що з усіх можливих дисциплін обслуговування з відносним пріоритетом мінімум середньої вартості забезпечує дисципліна з впорядкованими пріоритетами у відповідність з нерівностями
Дисципліни обслуговування з пріоритетами, залежними від часу
На практиці часто зустрічається задача призначення пріоритетів в залежності від часу надходження заявки. Наприклад, для того, щоб ніякі вимоги не затримувалися в системі дуже довго, незважаючи на загальне навантаження, організують дисципліну обслуговування, при якій чим довше заявка знаходиться в системі, тим її пріоритет стає вище.
Розглянемо пріоритетні функції, лінійно залежать від часу з крутизною наростання, що залежить від номера класу, до якого належить вимога.
Припустимо, що деякий мічені вимога надходить в момент t і отримує в момент t пріоритет, який визначається значенням пріоритетної функції
Кожного разу, коли сервер готовий до обслуговування нової вимоги він вибирає з черги вимога з найвищим миттєвим пріоритетом-найбільшим значенням пріоритетної функції. Вимоги з класу з великим значенням p нарощують пріоритет з більшою швидкістю, ніж вимоги з нижчого пріоритетного класу. На малюнку 3 показаний приклад того, як надійшла пізніше вимогу, але з вищого пріоритетного класу, може отримати обслуговування раніше, ніж надійшла раніше вимога з менш пріоритетного класу. Це відбудеться, якщо сервер звільниться пізніше моменту t 0. При звільненні сервера до цього моменту, обслуговування отримає перше з надійшли вимог.
Рис. 3 Взаємодія між пріоритетними функціями для СМО з пріоритетами, залежними від часу.
Досліджуємо цю систему при експоненційному розподілі часу обслуговування.
Знайдемо середнє число вимог, що надійшли пізніше міченого, з класів з p ³ i, які будуть обслужені раніше міченого. Очевидно, що для таких вимог швидкість наростання пріоритетної функції менше швидкості наростання пріоритетної функції міченого вимоги і, отже число таких вимог дорівнює нулю. Тепер визначимо число таких вимог для класів з більшою, ніж у міченого швидкістю наростання пріоритетної функції p <i. З розгляду малюнка 3 можна бачити, що затримка міченого вимоги в системі для цього випадку Wp = t 0 - t пов'язана з інтервалом часу на якому надходять заявки, що випереджають мічені вимога V I = t i - t співвідношенням
Звідси отримуємо, що цей інтервал дорівнює
Отже, при інтенсивності l i вхідного потоку для вимог i-го класу знаходимо середнє число «обженуть» вимог
Розглянемо тепер мічені вимога з класу p, що надходить в момент t = 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
Підставивши обчислені середні значення для «обженуть» вимог отримаємо систему лінійних рівнянь для величин затримки міченого вимоги
Заклад освіти «Білоруський державний університет інформатики і радіоелектроніки»
Кафедра Мереж і пристроїв телекомунікацій
РЕФЕРАТ
На тему:
«Дисципліни обслуговування. Модель з пріоритетами. Дисципліни обслуговування з пріоритетами, залежними від часу »
МІНСЬК, 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 утворюють Пуассонівський потік з інтенсивністю l p вимог у секунду. Час обслуговування кожної вимоги з цього класу вибирається незалежно у відповідність з розподілом із щільністю ймовірності b p (x) з середнім значенням
Введемо такі визначення
Тут r інтерпретується як частка часу, протягом якого сервер зайнятий (r <1), а кожен з парціальних коефіцієнтів r 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, l Р = l / 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 r p, то мінімізація зводиться до мінімізації значень середньої затримки. Таким чином, рішення даної задачі оптимізації полягає в тому, що з усіх можливих дисциплін обслуговування з відносним пріоритетом мінімум середньої вартості забезпечує дисципліна з впорядкованими пріоритетами у відповідність з нерівностями
Дисципліни обслуговування з пріоритетами, залежними від часу
На практиці часто зустрічається задача призначення пріоритетів в залежності від часу надходження заявки. Наприклад, для того, щоб ніякі вимоги не затримувалися в системі дуже довго, незважаючи на загальне навантаження, організують дисципліну обслуговування, при якій чим довше заявка знаходиться в системі, тим її пріоритет стає вище.
Розглянемо пріоритетні функції, лінійно залежать від часу з крутизною наростання, що залежить від номера класу, до якого належить вимога.
Припустимо, що деякий мічені вимога надходить в момент t і отримує в момент t пріоритет, який визначається значенням пріоритетної функції
Кожного разу, коли сервер готовий до обслуговування нової вимоги він вибирає з черги вимога з найвищим миттєвим пріоритетом-найбільшим значенням пріоритетної функції. Вимоги з класу з великим значенням p нарощують пріоритет з більшою швидкістю, ніж вимоги з нижчого пріоритетного класу. На малюнку 3 показаний приклад того, як надійшла пізніше вимогу, але з вищого пріоритетного класу, може отримати обслуговування раніше, ніж надійшла раніше вимога з менш пріоритетного класу. Це відбудеться, якщо сервер звільниться пізніше моменту t 0. При звільненні сервера до цього моменту, обслуговування отримає перше з надійшли вимог.
Рис. 3 Взаємодія між пріоритетними функціями для СМО з пріоритетами, залежними від часу.
Досліджуємо цю систему при експоненційному розподілі часу обслуговування.
Знайдемо середнє число вимог, що надійшли пізніше міченого, з класів з p ³ i, які будуть обслужені раніше міченого. Очевидно, що для таких вимог швидкість наростання пріоритетної функції менше швидкості наростання пріоритетної функції міченого вимоги і, отже число таких вимог дорівнює нулю. Тепер визначимо число таких вимог для класів з більшою, ніж у міченого швидкістю наростання пріоритетної функції p <i. З розгляду малюнка 3 можна бачити, що затримка міченого вимоги в системі для цього випадку Wp = t 0 - t пов'язана з інтервалом часу на якому надходять заявки, що випереджають мічені вимога V I = t i - t співвідношенням
Звідси отримуємо, що цей інтервал дорівнює
Отже, при інтенсивності l i вхідного потоку для вимог i-го класу знаходимо середнє число «обженуть» вимог
Розглянемо тепер мічені вимога з класу p, що надходить в момент t = 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 Штрихове лінія показує характеристику для системи без пріоритетів. Видно, що дія закону збереження проявляється у тому, що хоча одна частина заявок, що отримала найвищий пріоритет буде мати менший час очікування, ніж у системі без пріоритетів з обслуговуванням у порядку надходження, інша частина заявок при цьому обов'язково буде затримано на більше, ніж у беспріорітетной системі час.
Рис. 5
Система функціонує в такий спосіб: нова вимога, що надійшла в систему «пропонує» неотрицательную плату Y «організатору черги». Після цього вимогу надається місце в черзі таке, що всі вимоги внесли меншу плату опиняються позаду, велику попереду цієї вимоги. У кожний момент часу сервер, завершивши обслуговування чергової вимоги, приймає на обслуговування вимога, що виявилося попереду всієї черги. До повного завершення обслуговування вимога не покидає сервер. Вимоги, які внесли однакову плату, обслуговуються в порядку надходження.
Знайдемо середній час очікування в черзі для вимоги, який вніс плату Y = y. Цей час складається з трьох складових. По-перше, цей час на дообслужіваніе вимоги, що знаходиться в даний момент на сервері. По-друге - час обслуговування вимог, які надійшли раніше і внесли більше або рівну плату. Нарешті міченого вимогу доведеться чекати обслуговування всіх вимог надійшли пізніше його, але внесли велику плату. Середнє число вимог, плата яких лежить в інтервалі (u, u + du) визначається за формулою Літтла:
Використовуючи позначення для нижнього і верхнього границі функції b (u) можна записати сумарне вираз для часу очікування в черзі для міченого вимоги у вигляді:
Використовуючи ряд співвідношень і позначень можна знайти, що при розривної функції розподілу ймовірності це співвідношення може бути приведене до вигляду
При абсолютно неперервної функції щільності ймовірності отримаємо
Таким чином, ми отримали кінцеве середній час очікування для всіх вимог, які вносять плату вище, ніж деяке критичне значення
У межі, коли розмір плати прагне до нескінченності, середній час очікування прагне до W 0. Неважко переконатися, що коли розмір плати для всіх вимог однаковий
Це відомий результат для СМО типу M/G/1 при обслуговуванні в порядку надходження, як і слід було очікувати, оскільки рівна плата рівносильна її відсутності з точки зору розподілу пріоритетів.
При розподілі пріоритетів можна розглянути й інші вартісні завдання. Визначимо оптимальний розподіл плати за пріоритети в наступних припущеннях. Нехай є залежність вартості від часу затримки в черзі для кожної вимоги, тобто є можливість визначити, скільки коштує кожна секунда очікування в черзі. Опишемо цю залежність за допомогою випадкового коефіцієнта нетерпіння a.
Очевидно, що загальні витрати клієнта при обслуговуванні будуть складатися з плати за місце в черзі і втрат від часу очікування.
Для вимоги з фіксованим коефіцієнтом нетерпіння ці витрати рівні
Нехай для всієї сукупності клієнтів можна визначити функцію розподілу ймовірностей коефіцієнтів нетерпіння
Сформулюємо наступну задачу оптимізації: знайти функцію y a, яка мінімізує середню вартість С за умови обмеження всієї середньої плати деякою заданою величиною B.
Визначимо
Перетворюючи мінімізіруемий інтеграл, одержимо
Із закону збереження в безперервній формі
випливає, що рішення задачі мінімізації вартості зводиться до знаходження такої функції, при якій мінімальна площа під кривою твори:
У той час як площа під кривою, яка визначається перший співмножником повинна залишатися постійною.
Шляхом міркувань про узгодженість зростання і зменшення функцій, що входять у твір, можна зробити висновок, що рішенням задачі є всі функції, що задовольняють умові
Безліч S таке, що
Виберемо найпростішу суворо зростаючу функцію - лінійну. Таким чином, будемо вважати, що плата пропорційна коефіцієнту нетерпіння.
Застосовуючи обмеження середньої плати
отримаємо, що, якщо вважати середній коефіцієнт нетерпіння рівний A
Це і є функція оптимальної плати.
В якості прикладу розглянемо систему з показовим розподілом плати
Час очікування можна безпосередньо обчислити:
Використовуючи розглянуте правило оптимальної плати можна знайти розподіл коефіцієнта нетерпіння
Отже, середня вартість виходить:
Описана оптимізація є глобальною і дозволяє знайти функцію плати, які мінімізують загальну середню вартість.
Отримана формула являє собою головний результат аналізу дисципліни обслуговування з пріоритетами, залежними від часу. Типова характеристика СМО з проаналізованої дисципліною обслуговування наведена на рисунку 5 Штрихове лінія показує характеристику для системи без пріоритетів. Видно, що дія закону збереження проявляється у тому, що хоча одна частина заявок, що отримала найвищий пріоритет буде мати менший час очікування, ніж у системі без пріоритетів з обслуговуванням у порядку надходження, інша частина заявок при цьому обов'язково буде затримано на більше, ніж у беспріорітетной системі час.
Рис. 5
Оптимізація призначення пріоритетів
Розглянемо систему M/G/1 з інтенсивністю надходить пуассоновского потоку l вимог у секунду і довільної функцією щільності ймовірності для часу обслуговування з заданим середнім часом обслуговування. Нехай плата за вимогу Y є випадковою величиною з довільною функцією розподілуСистема функціонує в такий спосіб: нова вимога, що надійшла в систему «пропонує» неотрицательную плату Y «організатору черги». Після цього вимогу надається місце в черзі таке, що всі вимоги внесли меншу плату опиняються позаду, велику попереду цієї вимоги. У кожний момент часу сервер, завершивши обслуговування чергової вимоги, приймає на обслуговування вимога, що виявилося попереду всієї черги. До повного завершення обслуговування вимога не покидає сервер. Вимоги, які внесли однакову плату, обслуговуються в порядку надходження.
Знайдемо середній час очікування в черзі для вимоги, який вніс плату Y = y. Цей час складається з трьох складових. По-перше, цей час на дообслужіваніе вимоги, що знаходиться в даний момент на сервері. По-друге - час обслуговування вимог, які надійшли раніше і внесли більше або рівну плату. Нарешті міченого вимогу доведеться чекати обслуговування всіх вимог надійшли пізніше його, але внесли велику плату. Середнє число вимог, плата яких лежить в інтервалі (u, u + du) визначається за формулою Літтла:
Використовуючи позначення для нижнього і верхнього границі функції b (u) можна записати сумарне вираз для часу очікування в черзі для міченого вимоги у вигляді:
Використовуючи ряд співвідношень і позначень можна знайти, що при розривної функції розподілу ймовірності це співвідношення може бути приведене до вигляду
При абсолютно неперервної функції щільності ймовірності отримаємо
Таким чином, ми отримали кінцеве середній час очікування для всіх вимог, які вносять плату вище, ніж деяке критичне значення
У межі, коли розмір плати прагне до нескінченності, середній час очікування прагне до W 0. Неважко переконатися, що коли розмір плати для всіх вимог однаковий
Це відомий результат для СМО типу M/G/1 при обслуговуванні в порядку надходження, як і слід було очікувати, оскільки рівна плата рівносильна її відсутності з точки зору розподілу пріоритетів.
При розподілі пріоритетів можна розглянути й інші вартісні завдання. Визначимо оптимальний розподіл плати за пріоритети в наступних припущеннях. Нехай є залежність вартості від часу затримки в черзі для кожної вимоги, тобто є можливість визначити, скільки коштує кожна секунда очікування в черзі. Опишемо цю залежність за допомогою випадкового коефіцієнта нетерпіння a.
Очевидно, що загальні витрати клієнта при обслуговуванні будуть складатися з плати за місце в черзі і втрат від часу очікування.
Для вимоги з фіксованим коефіцієнтом нетерпіння ці витрати рівні
Нехай для всієї сукупності клієнтів можна визначити функцію розподілу ймовірностей коефіцієнтів нетерпіння
Сформулюємо наступну задачу оптимізації: знайти функцію y a, яка мінімізує середню вартість С за умови обмеження всієї середньої плати деякою заданою величиною B.
Визначимо
Перетворюючи мінімізіруемий інтеграл, одержимо
Із закону збереження в безперервній формі
випливає, що рішення задачі мінімізації вартості зводиться до знаходження такої функції, при якій мінімальна площа під кривою твори:
У той час як площа під кривою, яка визначається перший співмножником повинна залишатися постійною.
Шляхом міркувань про узгодженість зростання і зменшення функцій, що входять у твір, можна зробити висновок, що рішенням задачі є всі функції, що задовольняють умові
Безліч S таке, що
Виберемо найпростішу суворо зростаючу функцію - лінійну. Таким чином, будемо вважати, що плата пропорційна коефіцієнту нетерпіння.
Застосовуючи обмеження середньої плати
отримаємо, що, якщо вважати середній коефіцієнт нетерпіння рівний A
Це і є функція оптимальної плати.
В якості прикладу розглянемо систему з показовим розподілом плати
Час очікування можна безпосередньо обчислити:
Використовуючи розглянуте правило оптимальної плати можна знайти розподіл коефіцієнта нетерпіння
Отже, середня вартість виходить:
Описана оптимізація є глобальною і дозволяє знайти функцію плати, які мінімізують загальну середню вартість.