Похожие презентации:
СМО M/G/1/∞, СМО с многомерным входящим потоком, СМО с приоритетами. Характеристики СМО. (Лекция 5)
1. СМО M/G/1/, СМО с многомерным входящим потоком, СМО с приоритетами. Характеристики СМО.
СМО M/G/1/ , СМО смногомерным входящим
потоком, СМО с приоритетами.
Характеристики СМО.
Лекция 5
2. Одноканальная СМО с произвольной длительностью обслуживания и неограниченной очередью – СМО М/G/1/∞
Время обслуживания заявки распределено попроизвольному (General) закону В(t) с плотностью
вероятности b(t).
Среднее время
обслуживания
0
0
t d B(t ) t b(t )dt
Второй начальный ( 2) t 2 d B(t ) t 2 b(t )dt
0
0
момент
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
2
3. СМО М/G/1/∞ в стационарном режиме : = Ƭ < 1
СМО М/G/1/∞ в стационарномрежиме : = Ƭ < 1
В произвольный момент t в очереди находится L
заявок
поступает очередная заявка
дисциплина обслуживания – FIFO
среднее время W__ожидания
заявки
в очереди
__
__
W Т
0
Т 1
Т0 – время, необходимое для завершения
обслуживания ранее выбранной заявки,
Т1 – время на облуживание заявок, стоящих в очереди
перед поступившей заявкой.
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
3
4. СМО М/G/1/∞
СГУ, ИТ и КС, Курс "МВПиС". Лекция 54
5.
__W w,
__
T 1 L ,
L w
L – средняя длина очереди,
Ƭ - среднее время обслуживания,
- интенсивность входного потока.
__
T 1 w w w,
где - загрузка СМО, < 1.
__
__
w T0 w ,
T0
w
1
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
(1)
5
6. Определение среднего времени дообслуживания заявки
Т0t1
t2
ti
tn
t
Число заявок за время t n = t >> 1
Равные
стороны
треугольников
–
времена
дообслуживания То1, То2, …, Тоi, …, Тоn.
Для всех n заявок обслуживание завершилось на отрезке
(0,t).
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
6
7. Определение среднего времени дообслуживания заявки
t1
T 0 T0 (t )dt
t0
1 n (t )
1 n (t ) 1 2
T0 Si Ti ,
t i 1
t i 1 2
1 ( 2)
T0
2
(2)
1 n(t )
1 n (t ) 2
T0
*
Ti ,
2 t
n(t ) i 1
h (t )
1
n(t )
Ti 2
T0 lim
lim (
)
n(t )
2 t t t i 1
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
7
8. Характеристики СМО М/G/1/
Характеристики СМО М/G/1/Формула Поллячека
–Хинчина
W
Данные для расчета:
• интенсивность входного потока ,
• среднее время обслуживания Ƭ
• второй начальный момент Ƭ(2)
( 2)
2(1 )
u w
(4),
2(1 )
( 2)
(3)
где u – ср. время пребывания заявки в системе
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
8
9. Характеристики СМО М/G/1/
Характеристики СМО М/G/1/L- среднее число заявок в очереди
L w
2 ( 2)
2(1 )
(5)
n – среднее число заявок в системе
n L
2 ( 2)
2(1 )
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
(6)
9
10. Проверка формулы Поллячека – Хинчина
Формула для расчета среднего времени пребывания вочереди для СМО М/М/1/ :
2
w
1 1
1
1
Для экспоненциального распределения Ƭ(2) = 2 Ƭ2
подставим в формулу (3) и получим:
2
w
2(1 ) 1
2
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
2
10
11. СМО с многомерным входным потоком
гдеn - число типов
заявок;
i и Ƭi, i = 1…n,
загрузка
заявками i-го типа
i = i Ƭi.
коэффициент
простоя СМО
=1–R
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
11
12. СМО с многомерным входным потоком
Условиестационарности:
0
1
Для многоканальных СМО:
n
R
i 1
i
n
i 1
i 1
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
12
13.
Характеристики заявок i-го типа: wi,ui, Li, ni.
Вероятность появления заявок i-го типа:
i
Pi
0
Ср. время пребывания заявки i-го типа в очереди:
n
1
( 2)
Wi W
i i
2(1 R ) i 1
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
13
14. Характеристики СМО при многомерном потоке
Ср. длина очереди заявок i-го типа:Li Wi i W i
Ср. время пребывания заявки i-го типа в системе:
ui W i
Ср. число заявок i-го типа в системе:
ni i Li
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
14
15. Многофазные СМО
Для стационарного режима n-фазной СМО :1
n
n n1 n2 ... nn
...
1 1
1 n
Расчет таких СМО можно проводить на
основании всех известных соотношений в
зависимости от типа СМО.
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
15
16. Системы массового обслуживания с приоритетами и их характеристики
17. СМО с приоритетами
Во многих СМО доход (или потери) зависятот времени пребывания заявки в CМО:
Д = kД / u, (1)
П = kП*u, (2)
u = w + Ƭ (3)
Ƭ − уменьшается, если увеличить скорость
обслуживания = 1/Ƭ.
w − можно уменьшить за счет увеличения
времени ожидания других заявок, назначая
приоритеты.
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
17
18. СМО с приоритетами
Приоритет – это преимущество в очереди,характеризуется натуральным числом:
1, 2, …, М.
Приоритеты: относительный и абсолютный,
смешанный.
Относительный приоритет не прерывает
обслуживание уже поступившей в канал
заявки.
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
18
19. Организация обслуживания с относительными приоритетами
Заявки k-го приоритета накапливаются вочереди Оk.
Дисциплина обслуживания в очереди Оk –
FIFO.
Заявки из (k+1)-й очереди не выбираются
на обслуживание, если есть хотя бы одна
заявка в k-й очереди, k = 1, 2, …, М – 1.
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
19
20. Схема СМО с относительными приоритетами
1…
k
k+1
…
n
Д
и
с
п
е
т
ч
е
р
Канал
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
20
21.
в СМО поступают N простейших потоков синтенсивностями 1 ,…, n
времена обслуживания – случайные
величины с известными средними Ƭ1 ,…,
Ƭn
и вторыми начальными моментами
Ƭ1(2) ,…, Ƭn(2)
дисциплина
обслуживания
–
относительные приоритеты
Определим среднее время пребывания в
очереди wk заявки k-го приоритета в
стационарном режиме.
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
21
22.
Внекоторый момент времени в СМО
поступает заявка k-го приоритета. Тогда она
ждет в очереди случайное время Wk:
k
k 1
j 1
j 1
Wk T0 T j T j ,
*
где То – время дообслуживания заявки;
k
T
j
– длительность обслуживания заявок
данного и более высоких приоритетов,
поступивших в СМО ранее данной заявки;
j 1
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
22
23.
k 1Tj
*
– длительность обслуживания
j 1
заявок
более высоких приоритетов,
поступивших в СМО позже данной заявки
за время wk, которые будут обслужены
ранее данной заявки.
Для средних времен имеем:
___
__
k
__
k 1 __
W k T0 T j T j
j 1
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
*
j 1
23
24.
__W w;
Обозначим:
__
*
j
Тогда:
T
j wk
__
T j j w j j j w j ,
___
__
k
k 1
j 1
j 1
W k T0 j w j j wk , (1)
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
24
25.
N1
( 2)
Wk
i i (2)
2(1 Rk 1 )(1 Rk ) i 1
где
Rk = 1 + 2 + … + k; Rk = R.
Остальные характеристики вычисляются по
формулам:
nk uk k
Lk Wk k uk Wk k
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
25
26. Распределение времени ожидания при относительных приоритетах
WkFIFO
W
WN
W1
1
W3
W2
2
3
N
k
W1 < W < WN
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
26
27. СМО с абсолютными приоритетами
1…
k
k+1
Д
и
с
п
е
т
ч
е
р
Канал
…
n
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
27
28. Обслуживание с абсолютными приоритетами
обслуживающий канал занят обслуживаниемзаявки k-го приоритета;
на вход системы поступает заявка j-го
приоритета;
при k j (у прибывшей заявки более низкий
или такой же приоритет) заявка j-го приоритета
заносится в конец соответствующей очереди;
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
28
29. Обслуживание с абсолютными приоритетами
при k > j (у прибывшей заявки более высокийприоритет) – обслуживание заявки
k-го
приоритета прерывается;
прерванная заявка заносится в начало
очереди
k-го
приоритета
и диспетчер
переключает канал на обслуживание заявки jго приоритета.
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
29
30. Организация обслуживания с абсолютными приоритетами
Обслуживание прерванных заявок можетпроизводиться:
1) от начала обслуживания
2) от момента прерывания
(дообслуживание).
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
30
31.
Среднее время ожидания в очереди wk заявокk-го приоритета равно:
WkA = WkН + WkП
где WkН – среднее время ожидания начала
обслуживания
WkП – среднее время ожидания в прерванном
состоянии
N
Wk
А
( 2)
Rk 1 k
(3)
2(1 Rk 1 )(1 Rk ) 1 Rk 1
i 1
i i
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
31
32. Разность длительностей ожидания заявок k-го приоритета
N( 2)
i i
R
A
O
i k 1
Wk W k W k k 1 k
1 Rk 1 2(1 Rk 1 )(1 Rk )
первое слагаемое определяет влияние заявок
более высокого приоритета, прерывающих
обслуживание данного потока,
второе учитывает уменьшение времени
ожидания заявок
k-го приоритета за счет
прерываний обслуживания заявок с меньшими
приоритетами.
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
32
33. Условие, при котором абсолютные приоритеты дают выигрыш во времени ожидания
Для заявок k-го приоритетаWkA < WkO ( Wk < 0)
N
Rk 1 k (1 Rk )
i k 1
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
i
( 2)
i
2
33
34. Распределение времени ожидания при абсолютных приоритетах
WkFIFO
W
WN
ОП
W1
АП
1
W3
W2
2
3
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
N
k
34
35.
Закон сохранения времени ожиданиясправедлив
для
СМО,
следующим требованиям:
удовлетворяющих
1.Отсутствие отказов в обслуживании
2.Все
входные
потоки
независимые
и
простейшие
3.Система обслуживания простаивает только в
том случае, когда на ее входе нет заявок на
обслуживание
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
35
36.
Закон сохранения времени ожидания4.Время обслуживания не зависит от входных
потоков
5.При наличии прерываний время обслуживания
имеет экспоненциальное распределение.
Применение:
для оценки достоверности приближенных
результатов, полученных при анализе сложных
дисциплин
обслуживания
и
проведении
имитационного моделирования.
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
36
37.
Закон сохранения времени ожиданияN
i wi const
i 1
при любой дисциплине
обслуживания
N
R
( 2)
соnst
i i
2(1 R) i 1
где R = 1 + 2 + … + N.
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
37
38. СМО со смешанными приоритетами
В одноканальную СМО поступают N потоковзаявок. Выделяются три группы потоков:
1)
N1 первых потоков имеют абсолютные
приоритеты
2)
потоки N1 + 1, …, N1 + N2 относительные приоритеты
3)
потоки N1 + N2 + 1, …, N –
бесприоритетное обслуживание.
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
38
39. Среднее время ожидания в очереди заявок k-го приоритета
K( 2)
i i
R
k 1 k
i 1
k 1...N1
1 Rk 1 2(1 Rk 1 )(1 Rk )
N
( 2)
i i
RN1 k
i 1
WK
k N1 1...N1 N 2
1 RN1 2(1 Rk 1 )(1 Rk )
N
( 2)
i i
R
N1 k
i 1
k N1 N 2 1...N
1 R
2(1 RM1 М 2 )(1 R)
N1
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
39
40. Распределение времени ожидания при смешанных приоритетах
АПОП
Wk
CП
FIFO
W
1
N1
N1+N2
СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
N
k
40
41.
Спасибо за внимание!СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
41