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

Содержание

СГУ, ИТ и КС, Курс "МВПиС". Лекция 5 Одноканальная СМО с произвольной длительностью обслуживания и неограниченной очередью – СМО М/G/1/∞ Время обслуживания заявки распределено по произвольному (General) закону В(t) с

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

5

Слайд 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).

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

5

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

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

Слайд 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СГУ, ИТ и КС, Курс "МВПиС". Лекция 5
Среднее время ожидания в

очереди заявок k-го приоритета


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

смешанных приоритетах

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

Похожие презентации

Аттестационная работа. Магические квадраты 409
Задача о назначениях. Алгоритмы 340
delenie s ostatkom 235
Построение таблиц истинности 255
Интерактивная игра по математике "Вычитание в пределах 20"; 1 класс 289
Урок математики: Столько же, больше, меньше 703

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика