Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Лекція
Содержание
- 1. Лекція
- 2. Основні питанняВизначення ймовірностей станів СРІ Розподіл часу
- 3. Постановка задачі Вважається, що повністю доступна СРІ
- 4. Визначення ймовірностей станів СРІ
- 5. Визначення ймовірностей станів СРІОтримаємо вирази для станів
- 6. Друга формула Ерланга Дану формулу часто називають С-формулою Ерланга.Agner Krarup Erlang (1878-1929)
- 7. Вигляд функцій Ерланга
- 8. Розподіл часу очікування у випадку дисципліни черги
- 9. Формула Літтла Формула Літтла встановлює співвідношення між
- 10. Доведення формули ЛіттлаРассмотрим любую СМО (одноканальную, многоканальную,
- 11. Доведення формули ЛіттлаОбозначим: - α(t) –
- 12. Доведення формули ЛіттлаВид функций α(t) и δ(t)
- 13. Доведення формули ЛіттлаОчевидно, что для любого момента
- 14. Доведення формули ЛіттлаРассмотрим очень большой промежуток времени
- 15. Доведення формули ЛіттлаНо этот интеграл представляет собой
- 16. Доведення формули ЛіттлаОбозначим эти времена t1, t2,…Правда,
- 17. Доведення формули ЛіттлаРазделим правую и левую часть
- 18. Доведення формули ЛіттлаНо величина Tλ есть не
- 19. Доведення формули ЛіттлаЭто и есть формула Литтла:
- 20. Доведення формули ЛіттлаТочно таким же образом выводится
- 21. Аналіз системи M/G/1Вхідний потік: Час обслуговування: Інтенсивність
- 22. Зміна незавершеної роботи Незавершеною роботою R(t) у момент
- 23. Формула Полячека-Хінчина(Формула ПХ)Наслідок 1.Наслідок 2.Наслідок 3.
- 24. Залежність середнього числа заявок у системі M/G/1/W від інтенсивності вхідного навантаження
- 25. Система M/D/v/W Постановка задачі у даному випадку
- 26. Система M/D/v/W
- 27. Система M/D/v/W
- 28. Система M/D/v/W
- 29. Криві Кроммеліна для V=1
- 30. Дисципліни вибору з черги Практичний інтерес являють
- 31. Дисципліни вибору з черги
- 32. Розподіл часу очікування в системі M/D/1 при
- 33. ЛЕКЦІЯ ОБСЛУГОВУВАННЯ ЗАЯВОК ЗА ПРІОРИТЕТНИМИ ДИСЦИПЛІНАМИ
- 34. Основні поняттяДисципліна обслуговування з очікуванням, згідно з
- 35. Дисципліни пріоритетного обслуговування Можливі такі дисципліни
- 36. Закон збереження роботиНезавершеною роботою R(t) у момент
- 37. Закон збереження роботиЗакон збереження для системи типу
- 38. Cередній час очікування в черзі
- 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. Скачать презентанцию
Основні питанняВизначення ймовірностей станів СРІ Розподіл часу очікування у випадку дисципліни черги FIFOФормула Літтла Формула Полячека-Хінчина
Слайды и текст этой презентации
Слайд 2Основні питання
Визначення ймовірностей станів СРІ
Розподіл часу очікування у випадку
дисципліни черги FIFO
Слайд 3Постановка задачі
Вважається, що повністю доступна СРІ з v приладами
обслуговує найпростіший потік заявок з параметром λ. При цьому використовується
дисципліна обслуговування з очікуванням. Заявки можуть утворювати чергу необмеженої довжини. Заявки, що перебувають на очікуванні, обслуговуються по черзі. Тривалість зайняття приладу вважається випадковою величиною з експоненціальним законом розподілу і параметром інтенсивності обслуговування μ.Необхідно визначити ймовірності різних станів СРІ, функцію розподілу часу очікування початку обслуговування, середній час очікування та середню довжину черги.
Модель системи
M/M/v/W
Слайд 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 при виборі з черги
у випадковому порядку (суцільні криві) і в порядку надходження (пунктир)
Слайд 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 і будь-якої відносної дисципліни обслуговування, що зберігає
роботу, має виконуватися рівність
Слайд 46Висновок
На основі аналізу отриманих співвідношень можна зробити такий висновок.
Якщо система
з пріоритетом завантажена слабко, то різниця в середньому часі очікування
для заявок з різними пріоритетами мала, але вона стає помітною, коли навантаження на систему зростає. Наприклад, збільшення інтенсивності потоку заявок з найбільшим пріоритетом приводить до зростання часу очікування як для заявок із цим пріоритетом, так і для інших заявок. Тому важливо контролювати призначення високих пріоритетів і за можливістю зменшувати час обслуговування заявок.
Слайд 49Порівняльна оцінка дисциплін обслуговування
Для порівняльної оцінки дисциплін обслуговування на наступному
слайді наведені залежності часу затримки заявок у системі від їх
пріоритету. При цьому використані такі дані:Вважається, що час обслуговування заявок є випадковим і має експоненціальний закон розподілу.
Слайд 50Залежність затримки заявок від пріоритету
Висновок: Дисципліна обслуговування з абсолютним пріоритетом
у більшій мірі зменшує затримки високопріоритетних заявок за рахунок збільшення
затримок заявок з низьким пріоритетом.
Слайд 58СИСТЕМИ ЗМІШАНОГО ТИПУ
У СРІ змішаного типу вхідні заявки залишаються в
системі до закінчення обслуговування або залишають систему залежно від виконання
деяких умов. До таких систем відносяться:1. Системи, у яких заявка, що надійшла, залишається в системі й обслуговується тільки в тому випадку, якщо довжина черги не перевищує деякого заданого значення.
2. Системи, у яких заявка, що надійшла, залишається в системі тільки за умови, якщо час очікування в черзі не перевищує деякої величини. При цьому час очікування може бути як випадковою, так і постійною величиною. Це системи з обмеженням на час очікування.
3. Системи, у яких заявка, що надійшла, повністю обслуговується тільки за умови, якщо загальний час перебування заявки в системі не перевищує деякої межі.
Слайд 59Системи з обмеженою довжиною черги
Постановка задачі
Нехай у систему, що
має v обслуговуючих приладів, надходить найпростіший потік заявок з інтенсивністю
λ. Заявка, що надійшла, залишає систему не обслуженою тільки в тому випадку, якщо в момент її надходження довжина черги s=N. Кожна заявка обслуговується одним пристроєм. Час обслуговування має експоненціальний закон з параметром μ.
Слайд 60Системи з обмеженою довжиною черги
Для цієї задачі з виразу для
фінальних станів СРІ можуть бути отримані такі формули для сталого
режиму обслуговування.Імовірність того, що в системі немає жодної заявки, дорівнює
