СМО M/G/1/∞, СМО с многомерным входящим потоком, СМО с приоритетами. Характеристики СМО. (Лекция 5)

Сентябрь 14, 2022

Главная
Математика
СМО M/G/1/∞, СМО с многомерным входящим потоком, СМО с приоритетами. Характеристики СМО. (Лекция 5)

Содержание

2. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Одноканальная СМО с произвольной длительностью обслуживания и неограниченной
3. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 СМО М/G/1/∞ в стационарном режиме : ρ =
4. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 СМО М/G/1/∞
5. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 L – средняя длина очереди, Ƭ - среднее
6. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Определение среднего времени дообслуживания заявки Число заявок за
7. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Определение среднего времени дообслуживания заявки
8. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Характеристики СМО М/G/1/∝ Данные для расчета: интенсивность входного
9. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Характеристики СМО М/G/1/∝ L- среднее число заявок в
10. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Проверка формулы Поллячека – Хинчина Формула для расчета
11. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 СМО с многомерным входным потоком где n -
12. СМО с многомерным входным потоком СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Условие стационарности: Для
13. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Характеристики заявок i-го типа: wi, ui, Li, ni.
14. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Характеристики СМО при многомерном потоке Ср. длина очереди
15. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Многофазные СМО Для стационарного режима n-фазной СМО :
16. Системы массового обслуживания с приоритетами и их характеристики
17. СМО с приоритетами Во многих СМО доход (или потери) зависят от времени пребывания заявки в CМО:
18. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Приоритет – это преимущество в очереди, характеризуется натуральным
19. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Организация обслуживания с относительными приоритетами Заявки k-го приоритета
20. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Схема СМО с относительными приоритетами
21. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 в СМО поступают N простейших потоков с интенсивностями
22. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 В некоторый момент времени в СМО поступает заявка
23. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 – длительность обслуживания заявок более высоких приоритетов, поступивших
24. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Обозначим: Тогда:
25. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 где Rk = ρ1 + ρ2 + …
26. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Распределение времени ожидания при относительных приоритетах W1
27. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 СМО с абсолютными приоритетами
28. Обслуживание с абсолютными приоритетами обслуживающий канал занят обслуживанием заявки k-го приоритета; на вход системы поступает заявка
29. Обслуживание с абсолютными приоритетами при k > j (у прибывшей заявки более высокий приоритет) – обслуживание
30. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Организация обслуживания с абсолютными приоритетами Обслуживание прерванных заявок
31. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Среднее время ожидания в очереди wk заявок k-го
32. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Разность длительностей ожидания заявок k-го приоритета первое слагаемое
33. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Условие, при котором абсолютные приоритеты дают выигрыш во
34. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Распределение времени ожидания при абсолютных приоритетах
35. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 справедлив для СМО, удовлетворяющих следующим требованиям: 1.Отсутствие отказов
36. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 4.Время обслуживания не зависит от входных потоков 5.При
37. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Закон сохранения времени ожидания при любой дисциплине обслуживания
38. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 СМО со смешанными приоритетами В одноканальную СМО поступают
39. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Среднее время ожидания в очереди заявок k-го приоритета
40. СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Распределение времени ожидания при смешанных приоритетах
42. Скачать презентацию

Слайд 2

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Одноканальная СМО с произвольной

длительностью обслуживания и неограниченной очередью – СМО М/G/1/∞

Время обслуживания заявки распределено по произвольному (General) закону В(t) с плотностью вероятности b(t).
Среднее время
обслуживания
Второй начальный
момент

Слайд 3

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
СМО М/G/1/∞ в стационарном

режиме : ρ = λ*Ƭ < 1

В произвольный момент t в очереди находится L заявок
поступает очередная заявка
дисциплина обслуживания – FIFO
среднее время W ожидания заявки в очереди
Т0 – время, необходимое для завершения обслуживания ранее выбранной заявки,
Т1 – время на облуживание заявок, стоящих в очереди перед поступившей заявкой.

Слайд 4

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
СМО М/G/1/∞

Слайд 5

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5

L – средняя

длина очереди,
Ƭ - среднее время обслуживания,
λ- интенсивность входного потока.
где ρ - загрузка СМО, ρ < 1.

Слайд 6

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Определение среднего времени дообслуживания

заявки

Число заявок за время t n = λ t >> 1
Равные стороны треугольников – времена дообслуживания То1, То2, …, Тоi, …, Тоn.
Для всех n заявок обслуживание завершилось на отрезке (0,t).

Слайд 7

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Определение среднего времени дообслуживания

заявки

Слайд 8

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Характеристики СМО М/G/1/∝
Данные

для расчета:
интенсивность входного потока λ,
среднее время обслуживания Ƭ
второй начальный момент Ƭ(2)

где u – ср. время пребывания заявки в системе

Формула Поллячека –Хинчина

Слайд 9

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Характеристики СМО М/G/1/∝
L-

среднее число заявок в очереди

n – среднее число заявок в системе

Слайд 10

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Проверка формулы Поллячека –

Хинчина

Формула для расчета среднего времени пребывания в очереди для СМО М/М/1/∝:

Для экспоненциального распределения Ƭ(2) = 2 Ƭ2 подставим в формулу (3) и получим:

Слайд 11

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
СМО с многомерным входным

потоком

где
n - число типов заявок;
λi и Ƭi, i = 1…n,
загрузка заявками i-го типа ρi = λi Ƭi.
коэффициент простоя η СМО
η = 1 – R

Слайд 12

СМО с многомерным входным потоком
СГУ, ИТ и КС, Курс "МВПиС". Лекция

Условие
стационарности:

Для многоканальных СМО:

Слайд 13

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Характеристики заявок i-го типа:

wi, ui, Li, ni.

Вероятность появления заявок i-го типа:

Ср. время пребывания заявки i-го типа в очереди:

Слайд 14

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Характеристики СМО при многомерном

потоке

Ср. длина очереди заявок i-го типа:

Ср. время пребывания заявки i-го типа в системе:

Ср. число заявок i-го типа в системе:

Слайд 15

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Многофазные СМО
Для стационарного режима

n-фазной СМО :
Расчет таких СМО можно проводить на основании всех известных соотношений в зависимости от типа СМО.

Слайд 16

Системы массового обслуживания с приоритетами и их характеристики

Слайд 17

СМО с приоритетами
Во многих СМО доход (или потери) зависят от

времени пребывания заявки в CМО:
Д = kД / u, (1) П = kП*u, (2)
u = w + Ƭ (3)
Ƭ − уменьшается, если увеличить скорость обслуживания μ = 1/Ƭ.
w − можно уменьшить за счет увеличения времени ожидания других заявок, назначая приоритеты.

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5

Слайд 18

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Приоритет – это преимущество

в очереди,
характеризуется натуральным числом:
1, 2, …, М.
Приоритеты: относительный и абсолютный, смешанный.
Относительный приоритет не прерывает обслуживание уже поступившей в канал заявки.

СМО с приоритетами

Слайд 19

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Организация обслуживания с относительными

приоритетами

Заявки k-го приоритета накапливаются в очереди Оk.
Дисциплина обслуживания в очереди Оk – FIFO.
Заявки из (k+1)-й очереди не выбираются на обслуживание, если есть хотя бы одна заявка в k-й очереди, k = 1, 2, …, М – 1.

Слайд 20

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Схема СМО с относительными

приоритетами

Слайд 21

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
в СМО поступают N

простейших потоков с интенсивностями λ1 ,…, λn
времена обслуживания – случайные величины с известными средними Ƭ1 ,…, Ƭn и вторыми начальными моментами Ƭ1(2) ,…, Ƭn(2)
дисциплина обслуживания – относительные приоритеты
Определим среднее время пребывания в очереди wk заявки k-го приоритета в стационарном режиме.

Слайд 22

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
В некоторый момент времени

в СМО поступает заявка k-го приоритета. Тогда она ждет в очереди случайное время Wk:
где То – время дообслуживания заявки;
– длительность обслуживания заявок данного и более высоких приоритетов, поступивших в СМО ранее данной заявки;

Слайд 23

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
– длительность обслуживания
заявок

более высоких приоритетов, поступивших в СМО позже данной заявки за время wk, которые будут обслужены ранее данной заявки.
Для средних времен имеем:

Слайд 24

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Обозначим:
Тогда:

Слайд 25

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
где Rk = ρ1

+ ρ2 + … + ρk; Rk = R.
Остальные характеристики вычисляются по формулам:

Слайд 26

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Распределение времени ожидания при

относительных приоритетах

W1 < W < WN

Слайд 27

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
СМО с абсолютными приоритетами

Слайд 28

Обслуживание с абсолютными приоритетами
обслуживающий канал занят обслуживанием заявки k-го приоритета;
на

вход системы поступает заявка j-го приоритета;
при k ≤ j (у прибывшей заявки более низкий или такой же приоритет) заявка j-го приоритета заносится в конец соответствующей очереди;

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5

Слайд 29

Обслуживание с абсолютными приоритетами
при k > j (у прибывшей заявки более

высокий приоритет) – обслуживание заявки k-го приоритета прерывается;
прерванная заявка заносится в начало очереди k-го приоритета и диспетчер переключает канал на обслуживание заявки j-го приоритета.

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5

Слайд 30

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Организация обслуживания с абсолютными

приоритетами

Обслуживание прерванных заявок может производиться:
1) от начала обслуживания
2) от момента прерывания (дообслуживание).

Слайд 31

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Среднее время ожидания в

очереди wk заявок k-го приоритета равно:
WkA = WkН + WkП
где WkН – среднее время ожидания начала
обслуживания
WkП – среднее время ожидания в прерванном состоянии

Слайд 32

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Разность длительностей ожидания заявок

k-го приоритета

первое слагаемое определяет влияние заявок более высокого приоритета, прерывающих обслуживание данного потока,
второе учитывает уменьшение времени ожидания заявок k-го приоритета за счет прерываний обслуживания заявок с меньшими приоритетами.

Слайд 33

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Условие, при котором абсолютные

приоритеты дают выигрыш во времени ожидания

Для заявок k-го приоритета
WkA < WkO (ΔWk < 0)

Слайд 34

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Распределение времени ожидания при

абсолютных приоритетах

Слайд 35

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
справедлив для СМО, удовлетворяющих

следующим требованиям:
1.Отсутствие отказов в обслуживании
2.Все входные потоки независимые и простейшие
3.Система обслуживания простаивает только в том случае, когда на ее входе нет заявок на обслуживание

Закон сохранения времени ожидания

Слайд 36

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
4.Время обслуживания не зависит

от входных потоков
5.При наличии прерываний время обслуживания имеет экспоненциальное распределение.
Применение:
для оценки достоверности приближенных результатов, полученных при анализе сложных дисциплин обслуживания и проведении имитационного моделирования.

Закон сохранения времени ожидания

Слайд 37

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Закон сохранения времени ожидания
при

любой дисциплине обслуживания

где R = ρ1 + ρ2 + … + ρN.

Слайд 38

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
СМО со смешанными приоритетами
В

одноканальную СМО поступают N потоков заявок. Выделяются три группы потоков:
N1 первых потоков имеют абсолютные приоритеты
потоки N1 + 1, …, N1 + N2 - относительные приоритеты
потоки N1 + N2 + 1, …, N – бесприоритетное обслуживание.

Слайд 39