Слайд 1Лекція
Аналіз систем, які працюють за дисципліною обслуговування з очікуванням
Слайд 2Основні питання
Визначення ймовірностей станів СРІ
Розподіл часу очікування у випадку
дисципліни черги FIFO
Формула Літтла
Формула Полячека-Хінчина
Слайд 3Постановка задачі
Вважається, що повністю доступна СРІ з v приладами
обслуговує найпростіший потік заявок з параметром λ. При цьому використовується
дисципліна обслуговування з очікуванням. Заявки можуть утворювати чергу необмеженої довжини. Заявки, що перебувають на очікуванні, обслуговуються по черзі. Тривалість зайняття приладу вважається випадковою величиною з експоненціальним законом розподілу і параметром інтенсивності обслуговування μ.
Необхідно визначити ймовірності різних станів СРІ, функцію розподілу часу очікування початку обслуговування, середній час очікування та середню довжину черги.
Модель системи
M/M/v/W
Слайд 4Визначення ймовірностей станів СРІ
Слайд 5Визначення ймовірностей станів СРІ
Отримаємо вирази для станів СРІ типу M/M/v/W
Рекурентні
співвідношення для ймовірностей станів для систем M/M/v/W мають вигляд
Слайд 6Друга формула Ерланга
Дану формулу часто називають
С-формулою Ерланга.
Agner Krarup
Erlang (1878-1929)
Слайд 8Розподіл часу очікування у випадку дисципліни черги FIFO
У даному
випадку імовірність очікування початку обслуговування понад час t визначається за
формулою
=
.
,
,
,
,
.
Слайд 9Формула Літтла
Формула Літтла встановлює співвідношення між середньою довжиною черги
в системі, інтенсивністю вхідного потоку й середнім часом перебування заявок
у системі. Вона справедлива для будь-якої системи з очікуванням, що перебуває у сталому стані.
Останнє співвідношення означає, що середнє число заявок у системі дорівнює добутку інтенсивності надходження заявок у систему на середній час їхнього перебування в системі:
При цьому не накладається жодних обмежень на тип потоку заявок і час обслуговування. Вперше доведення цього факту дав Дж. Літтл.
Слайд 10Доведення формули Літтла
Рассмотрим любую СМО (одноканальную, многоканальную, марковскую, немарковскую, с
неограниченной или ограниченной очередью) и связанные с нею два потока
событий:
- поток заявок, прибывающих в СМО;
- поток заявок, покидающих СМО.
Если в системе установился предельный, стационарный режим, то среднее число заявок, прибывающих в СМО за единицу времени, равно среднему числу заявок, покидающих её.
Оба потока имеют одну и ту же интенсивность λ.
Слайд 11Доведення формули Літтла
Обозначим:
- α(t) – число заявок, прибывших
в СМО до момента t;
- δ(t) - число
заявок, покинувших СМО до момента t.
И та и другая функции являются случайными и меняются скачком (увеличиваются на единицу) в моменты приходов заявок α(t) и уходов заявок δ(t).
Слайд 12Доведення формули Літтла
Вид функций α(t) и δ(t) показан на рисунке.
Обе
линии – ступенчатые, верхняя - α(t), нижняя - δ(t)
- α(t) – число заявок, прибывших в СМО до момента t;
- δ(t) - число заявок, покинувших СМО до момента t.
Слайд 13Доведення формули Літтла
Очевидно, что для любого момента t их разность
N(t) = α(t) - δ(t) есть не что иное, как
число заявок, находящихся в СМО
Когда линии α(t) и δ(t) сливаются, в системе нет заявок
Слайд 14Доведення формули Літтла
Рассмотрим очень большой промежуток времени T (мысленно продолжив
график далеко за пределы чертежа) и вычислим для него среднее
число заявок, находящихся в СМО
Оно будет равно интегралу от функции N(t) на этом промежутке, деленному на длину интервала T:
Слайд 15Доведення формули Літтла
Но этот интеграл представляет собой не что иное,
как площадь фигуры, залитой на рисунке.
Разглядим внимательней этот рисунок.
Фигура на
рисунке состоит из прямоугольников, каждый из которых имеет высоту, равную единице, и основание, равное времени пребывания в системе соответствующей заявки (первой, второй и т.д.)
Слайд 16Доведення формули Літтла
Обозначим эти времена t1, t2,…
Правда, под конец промежутка
T некоторые прямоугольники войдут в залитую фигуру не полностью, а
частично, но при достаточно большом T эти детали не будут играть роли
Таким образом, можно считать, что:
где сумма распространяется на все заявки, пришедшие за время T
Слайд 17Доведення формули Літтла
Разделим правую и левую часть последнего выражения на
длину интервала T
Получим
Разделим и умножим правую часть на интенсивность λ:
Слайд 18Доведення формули Літтла
Но величина Tλ есть не что иное, как
среднее число заявок, пришедших за время T
Если мы разделим сумму
всех времен ti на среднее число заявок, то получим среднее время пребывания заявки в системе
Итак:
откуда:
Слайд 19Доведення формули Літтла
Это и есть формула Литтла:
- для
любой СМО, при любом характере потока заявок, при любом распределении
времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе равно среднему числу заявок в системе, деленному на интенсивность потока заявок
Слайд 20Доведення формули Літтла
Точно таким же образом выводится вторая формула Литтла,
связывающая среднее время пребывания заявки в очереди и среднее число
заявок в очереди:
Слайд 21Аналіз системи M/G/1
Вхідний потік:
Час обслуговування:
Інтенсивність навантаження:
Середній час
очікування:
Середнє число заявок у черзі:
де
- середня незавершена робота в обслуг. приладі
,
Слайд 22Зміна незавершеної роботи
Незавершеною роботою R(t) у момент часу t в
теорії черг називається час, який має пройти до повного звільнення
системи від усіх заявок, якщо після моменту часу на її вхід не надходять нові заявки
Слайд 23Формула Полячека-Хінчина
(Формула ПХ)
Наслідок 1.
Наслідок 2.
Наслідок 3. Для моделі
M/М/1
Наслідок 4. Для моделі M/D/1
Середній час
очікування початку обслуговування
Слайд 24Залежність середнього числа заявок у системі M/G/1/W від інтенсивності вхідного
навантаження
Слайд 25Система M/D/v/W
Постановка задачі у даному випадку така сама, як
для систем з явними втратами.
Відмінність полягає лише в законі розподілу
тривалості обслуговування: замість випадкового закону розподілу тривалість обслуговування кожної заявки вважається постійною величиною, рівною h. Цей випадок вперше у 1932 р. дослідив Кроммелін.
Розглянемо підхід, що використовується у теорії Кроммеліна.
Без обмеження загальності припустимо, що h=1.
Слайд 30Дисципліни вибору з черги
Практичний інтерес являють дві основні дисципліни
вибору заявок з черги: у порядку надходження (FIFO) і у
випадковому порядку (SP). Дисципліна вибору не впливає на середній час перебування в черзі, а впливає тільки на момент більш високого порядку: при переході від упорядкованого вибору в порядку надходження до випадкового різко зростають імовірності довгого очікування. На практиці ж часто дисципліна вибору є чимось середнім між цими двома дисциплінами.
Слайд 32Розподіл часу очікування в системі M/D/1 при виборі з черги
у випадковому порядку (суцільні криві) і в порядку надходження (пунктир)
Слайд 33
ЛЕКЦІЯ
ОБСЛУГОВУВАННЯ ЗАЯВОК ЗА ПРІОРИТЕТНИМИ ДИСЦИПЛІНАМИ
Слайд 34Основні поняття
Дисципліна обслуговування з очікуванням, згідно з якою вибір заявок
для обслуговування проводиться у відповідності зі ступенем їх важливості, називається
пріоритетною дисципліною.
У будь-якій пріоритетній дисципліні мають бути визначені правила для прийняття таких рішень.
1. Яку заявку брати на обслуговування в момент готовності приладу для прийняття наступної заявки.
2. Продовжити або перервати обслуговування заявки, що перебуває в приладі.
Вважатимемо, що ступінь важливості заявки встановлюється за допомогою приписування кожному класу пріоритетного індексу i:
1≤ i≤r,
де 1 позначає найвищий ступінь важливості,
а r – найнижчий.
Слайд 35Дисципліни пріоритетного
обслуговування
Можливі такі дисципліни пріоритетного обслуговування:
1. Відносний пріоритет
(пріоритет без переривання обслуговування): обслуговування заявки будь-якого класу триває до
повного завершення.
2. Абсолютний пріоритет (пріоритет, що перериває обслуговування): обслуговування заявки нижчого класу негайно переривається, і прилад починає обслуговувати заявку більш важливого класу.
3. Динамічні пріоритети: кожній вхідній заявці призначається певний індекс пріоритету залежно від стану СРІ.
Слайд 36Закон збереження роботи
Незавершеною роботою R(t) у момент часу t у
теорії черг називається час, який має пройти до повного звільнення
системи від усіх заявок, якщо після моменту часу t на її вхід не поступають нові заявки.
Консервативною називається система, в якій заявки не зникають усередині системи і прилади, що обслуговують, не простоюють при непустій черзі.
Закон збереження роботи для пріоритетних дисциплін стверджує, що для консервативної системи незакінчена робота R(t) в СРІ в будь-який момент часу t не залежить від порядку обслуговування.
Розподіл часу очікування в загальному випадку істотно залежить від порядку обслуговування. Однак, якщо дисципліна обслуговування вибирає заявки незалежно від їхнього часу обслуговування, то середній час очікування у черзі є інваріантним щодо порядку обслуговування.
Слайд 37Закон збереження роботи
Закон збереження для системи типу M/G/1 формулюється так.
Для
будь-якої системи M/G/1 і будь-якої відносної дисципліни обслуговування, що зберігає
роботу, має виконуватися рівність
Слайд 39Відносний пріоритет.
Одноканальна СРІ
Слайд 41Відносний пріоритет. Одноканальна система
Середній час очікування у черзі.
Слайд 42Суть методу математичної індукції
Слайд 43Відносний пріоритет. Одноканальна система
Середній час очікування у черзі.
Слайд 46Висновок
На основі аналізу отриманих співвідношень можна зробити такий висновок.
Якщо система
з пріоритетом завантажена слабко, то різниця в середньому часі очікування
для заявок з різними пріоритетами мала, але вона стає помітною, коли навантаження на систему зростає. Наприклад, збільшення інтенсивності потоку заявок з найбільшим пріоритетом приводить до зростання часу очікування як для заявок із цим пріоритетом, так і для інших заявок. Тому важливо контролювати призначення високих пріоритетів і за можливістю зменшувати час обслуговування заявок.
Слайд 47 Абсолютний пріоритет.
Одноканальна СРІ
Слайд 48Абсолютний пріоритет.
Одноканальна СРІ
Слайд 49Порівняльна оцінка дисциплін обслуговування
Для порівняльної оцінки дисциплін обслуговування на наступному
слайді наведені залежності часу затримки заявок у системі від їх
пріоритету. При цьому використані такі дані:
Вважається, що час обслуговування заявок є випадковим і має експоненціальний закон розподілу.
Слайд 50Залежність затримки заявок від пріоритету
Висновок: Дисципліна обслуговування з абсолютним пріоритетом
у більшій мірі зменшує затримки високопріоритетних заявок за рахунок збільшення
затримок заявок з низьким пріоритетом.
Слайд 51Задача оптимізації призначення пріоритетів
Слайд 53Оптимальне призначення пріоритетів
Слайд 54Приклад системи з пріоритетами в системах зв'язку
Слайд 55Приклад системи з пріоритетами в системах зв'язку
Слайд 56Приклад системи з пріоритетами в системах зв'язку
Слайд 57Лекція
АНАЛІЗ СИСТЕМ РОЗПОДІЛУ ІНФОРМАЦІЇ ЗМІШАНОГО ТИПУ
Слайд 58СИСТЕМИ ЗМІШАНОГО ТИПУ
У СРІ змішаного типу вхідні заявки залишаються в
системі до закінчення обслуговування або залишають систему залежно від виконання
деяких умов. До таких систем відносяться:
1. Системи, у яких заявка, що надійшла, залишається в системі й обслуговується тільки в тому випадку, якщо довжина черги не перевищує деякого заданого значення.
2. Системи, у яких заявка, що надійшла, залишається в системі тільки за умови, якщо час очікування в черзі не перевищує деякої величини. При цьому час очікування може бути як випадковою, так і постійною величиною. Це системи з обмеженням на час очікування.
3. Системи, у яких заявка, що надійшла, повністю обслуговується тільки за умови, якщо загальний час перебування заявки в системі не перевищує деякої межі.
Слайд 59Системи з обмеженою довжиною черги
Постановка задачі
Нехай у систему, що
має v обслуговуючих приладів, надходить найпростіший потік заявок з інтенсивністю
λ. Заявка, що надійшла, залишає систему не обслуженою тільки в тому випадку, якщо в момент її надходження довжина черги s=N. Кожна заявка обслуговується одним пристроєм. Час обслуговування має експоненціальний закон з параметром μ.
Слайд 60Системи з обмеженою довжиною черги
Для цієї задачі з виразу для
фінальних станів СРІ можуть бути отримані такі формули для сталого
режиму обслуговування.
Імовірність того, що в системі немає жодної заявки, дорівнює
Слайд 61Системи з обмеженою довжиною черги
Слайд 62Системи з обмеженою довжиною черги
Слайд 63Системи з обмеженням на час перебування заявок в черзі
Слайд 64Системи з обмеженням на час перебування
Слайд 65Системи з обмеженням на час перебування
Слайд 66Системи з обмеженням на час перебування
Слайд 67Системи з обмеженням на час перебування