АМСОИ - Конспект лекций (1032044)
Текст из файла
Кафедра ИУ5 МГТУ им. Н.Э. БауманаКОНСПЕКТ ЛЕКЦИЙ ПО ПРЕДМЕТУАналитические моделисистем обработки информацииСоставительЛектор:Сидякин А.А.Постников В.М.Москва, 2013От составителяКонспект составлялся человеком, потому не гарантируется отсутствие ошибок и опечаток.Вёрстка осуществлялась из онлайн-версии конспекта при помощи системыLATEX. Онлайн-версия конспекта лекций доступна на wiki-ресурсе:http://www.iu5bmstu.ru/1Содержание123456789Лекция №1 – СМО41.1СМО .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.2СеМО . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5Лекция №2 – Методика разработки формализованных схем72.1Задача для примера . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.2Методика разработки формализованных схем . . . . . . . . . . . . . . . . . . . . . .82.3Анализ разомкнутых СМО с обратной связью . . . . . . . . . . . . . . . . . . . . . .8Лекция №3 – Анализ характеристик103.1Анализ характеристик функционирования СМО М/М/1 . . . . . .
. . . . . . . . . . .103.2Анализ характеристик функционирования СМО Мn/Мn/1 . . . . . . . . . . . . . . .103.3Анализ характеристик функционирования СМО с эрланговскими потоками . . . . .11Лекция №4 - Анализ последовательных СМО134.113Анализ последовательно соединённых СМО . . . . . . . . . . .
. . . . . . . . . . . .Лекция №5 - Анализ СМО с ограниченной очередью155.1Анализ СМО с ограниченной длиной очереди . . . . . . . . . . . . . . . . . . . . . .155.1.1Буфер с с ёмкостью 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .165.1.2Буфер с с ёмкостью 2 . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .165.1.3Две СМО . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17Лекция №6 - Анализ СМО с отказом186.118Оценка характеристик функционирования систем с отказом . . . . . . . . . . . . .
.Лекция №7 - Анализ разомкнутых СеМО207.1Разомкнутые сети массового обслуживания . . . . . . . . . . . . . . . . . . . . . . .207.1.1Пример разомкнутой СеМО . . . . . . . . . . . . . . . . . . . . . . . . . . . .217.1.2Ещё пример разомкнутой СеМО . . . . . . . . . . . . . . . . . . . . . . . . .22Лекция №8 - Приоритетное обслуживание в СМО238.1Приоритетное обслуживание заявок в СМО . .
. . . . . . . . . . . . . . . . . . . . .238.1.1Относительные приоритеты . . . . . . . . . . . . . . . . . . . . . . . . . . . .248.1.2Абсолютные приоритеты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25Лекция №9 - Замкнутые СМО269.1Модель ремонтника . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .269.2Метод фонового потока . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .279.3Метод узкого места . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .28210 Лекция №10 - Анализ замкнутых СМО методом Базена10.1 Задача на сравнение с методом узкого места . . . . .
. . . . . . . . . . . . . . . . . .329291Лекция №1 – СМО1.1СМОСистемы массового обслуживания.µλυ2υ20Здесь:– λ - интенсивность входного потока заявок;– ν - интенсивность обслуживания. Отношение дисперсии к квадрату матожидания;– ν02 - квадрат коэффициента вариаций. Отношение среднего квадратического отклонения кматожиданию;– µ - очередь.Обозначения:– a - тип входного потока: M - пуассоновский поток;– b - тип обслуживания: M - экспоненциальное;– c - количество аппаратов: 1 - один обслуживающий аппарат;– d - ёмкость очереди: ∞ - очередь бесконечна;– e - дисциплина выбора заявок из очереди на обслуживание: F IF O - очередь;– f - количество источников заявок: ∞ - бесконечный поток.Существует ”Эрландовский входной поток”:Kэрл =41ν21.2СеМОСеть массового обслуживания.СМО 1СМО 2Параметры:– ρ=λµ< 1 - загрузка системы;– Q - количество заявок в очереди;– L = Q + ρ - количество заявок в системе;– W - время ожидания (время нахождения в очереди);– T =W+1µ= W + t0 - время нахождения в системе.Таблица 1: Расчёт загрузкиСМО M/M/1 СМО M/M/2ρQLWTλµρ21−ρρ1−ρρ·t01−ρt01−ρλ2·µ2·ρ31−ρ22·ρ1−ρ2ρ2 ·t01−ρ2t01−ρ2Q=λ·WL=λ·T5Зависимость примерно такая:L9410.50.90.95ρДальше что-то происходит:Q22 · ρ3 · (1 − ρ)2·ρ==22Q1(1 − ρ ) · ρ1+ρL22 · ρ · (1 − ρ)2==2L1(1 − ρ ) · ρ1+ρT2t02 · (1 − ρ)µ12===2T1(1 − ρ ) · t02µ2 · (1 + ρ)1+ρОдин обслуживающий аппарат более эффективен, чем два, равных в сумме ему по производительности.
Поэтому выбирая между одним, обрабатывающим 10 заявок в час, и двумя, в суммеоба тоже обрабатывающими 10 в час, надо выбирать его.622.1Лекция №2 – Методика разработки формализованных схемЗадача для примераИмеется мастерская по обслуживанию серверов.Поток клиентов составляет λ клиентов/час.Убыток от клиентов в очереди составляет S = 15 долларов/клиентов в часЕсть возможность нанять сотрудников C1 или C2 .C1 обслуживает µ1 = 3 клиента в час, требует денег S1 = 6 долларов/час.C2 обслуживает µ2 = 4 клиента в час, требует денег S2 = 10 долларов/час.Задача руководителя: оптимизировать работу мастерской.Считается, что поток клиентов подчиняется закону Пуассона, а обслуживание клиентов -экспоненциальному.Для оценки эффективности работы фирмы следует использовать следующие выражение,показывающие убытки фирмы:S∑ = ni · Si + S · QS - зарплата;n - количество сотрудников i-го типа;S · Q - убытки от пребывания клиентов в очереди.Если работают сотрудники C1 или сотрудники C2 , то их работу можно описать в видеработы многоканальной СМО: количество ОА равно количеству сотрудников, а производительностьравна работе сотрубников.Рассмотрим пять вариантов работы:Вот и выбрали лучший вариант.72.2Методика разработки формализованных схемВключает пять этапов:1) разработка структурной схемы исследуемой СОИ.
Схема включает, как правило, коммутаторы, маршрутизаторы, сервера и рабочие станции и прочее оборудование. Количество запросовв системе равно количеству рабочих станций - они их генерируют, потому на них очередейнет, а есть очереди на канале и сервере;2) выделение основных компонентов СОИ и схемы их взаимодействия;3) представление компонентов СОИ в виде СМО;4) разработка формализованных схем СМО;5) разработка формализованной схемы исследуемой СОИ.Если сервер многоядерный или многопроцессорный, то его можно представить в видемногоканального ОА.2.3Анализ разомкнутых СМО с обратной связьюPµλБОАP - вероятность повторного поступления заявки на обслуживание.λ=λ+λ·Pλ = λвх · (1 − P )α=11−P- среднее количество проходов заявки через ОА за время пребывания этой заявки в СМО.λвх =λ=α·λ1−PОсновные формулы для расчёта рассматриваемой системы:загрузка ОА:ρ=α·λλλ==α·µµµ8количество заявок в очереди:Q=ρ21−ρколичество заявок в системе:L=Q+ρ=ρ1−ρопределяем времена:W =QλвхT =LλвхW∑ = α · WT∑ = α · TЕсли в процессе анализа окажется, что ρ = α ·λµ≥ 1, то значит где-то ошибка, потому чтоможет быть только ρ < 1.
Тогда надо уменьшать вероятность, или повышать производительность,или ставить дополнительные ОА.Пример.Исходные данные:λ = 4, µ = 10, P = 0.51=21−P4ρ=2·= 0.810α=0.82Q== 3.20.20.8L==40.23.2= 0.8W∑ =44T∑ = = 14933.1Лекция №3 – Анализ характеристикАнализ характеристик функционирования СМО М/М/1− ttP (t) = 1−e0- вероятность того или иного времени обслуживания и времени пребывания.t0 =T =1µt01−ρПример:λ = 10 заявок/сек.Найти такую µ, чтобы с вероятностью P = 0.95 среднее время предывания было меньше1 секунды.ρ=λµ=10µP (T0.095 ) < 1Среднее время: T <13= 0.333 секунды.0.333 =1µ · (1 −10µ)=µ1=µ · (µ − 10)µ − 100.333 · (µ − 10) = 1µ≥3.24.330.333= 13 заявок/сек.Анализ характеристик функционирования СМО Мn/Мn/1Mn - означает, что у каждого входного потока свои функции распределения (разные типызаявок).При анализе СМО данного типа находится среднее число заявок в системе и среднее времяожидания, которое является общим и одинаковым для всех типов заявок.Пример:µ1µ2µ3λ1λ2Бλ3Найти характеристики функционирования СМО.Ищем общую загрузку СМО:10ОАρ=n∑λii=1<1µiНаходим среднее время обслуживания заявок разных типов:t0 =n∑λii=1λ· tiОпределяем второй момент времени обслуживания:(2)t0 =n∑λii=1λ(2)· tiДалее находим среднее время ожидания (будет общим для всех):(2)W =λ · t02 · (1 − ρ)Дальше таблица:Суммарная загрузка ρ = 0.25 + 0.2 + 0.15 = 0.6 < 1∑λ = ni=1 λi = 0.63 заявок в секунду.∑t0 = ni=1 λλi · ti = 0.94 секунд.∑(2)(2)t0 = ni=1 λλi · ti = 2.89 секунд.(2)W =3.3λ·t02·(1−ρ)= 2.28 секунд.Анализ характеристик функционирования СМО с эрланговскими потокамиМ/Ек/1 - обслуживание у такой СМО эрланговское.µ, u2λν2 =БОА1Используется формула Поллячека-Хинчина, она касается среднего количества заявок в очереди:11Q=ν02 =ρ2 · (1 + ν02 )2 · (1 − ρ)1=1= 0.52ν02 = 0L=Q+ρ=Q+λµQλLT =λW =Tr/Ек/1 - у такой СМО ещё и поток заявок эрланговский.Для неё есть формула Файнберга:Q=ρ2 · (ν 2 + ν02 )2 · (1 − ρ)Пример сравнения экспоненциального и регулярного:Определить, насколько улучшатся характеристики функционирования СМО при переходеот экспоненциального обслуживания к регулярному при загрузке ρ = 0.8?Ищем и сравниваем:124Лекция №4 - Анализ последовательных СМО4.1Анализ последовательно соединённых СМОµ1λБµ2ОА1Бµм...ОА2T2T1БОАмλвыхTмЕсть теорема Джексона для таких систем:m∑Q=Qii=1m∑L=Lii=1W =m∑Wii=1T =m∑Tii=1Если входной поток пуассоновский, а время обслуживания в каждой СМО подчинено экспоненциальному закону, то выходной поток с каждой СМО будет тоже пуассоновский, и входнойпоток тоже будет пуассоновский.
Это не так очевидно, на самом деле, так что не надо кричать проКапитана - это надо проверять расчётами.222νвых= νвх+ ρ · (ν02 − νвх)22νвых= (1 − ρ) · νвх+ ρ · ν02 − ρ2 + ρ)Если будет выявлено узкое место (ОА, который обслуживает дольше всех), то надо к немупоставить ещё параллельный ОА (очередь при этом у них будет одна общая).Время пребывания можно уменьшить за счёт следующих параметров:– увеличить интенсивность времени обслуживания µ;– увеличить количество обслуживающих аппаратов;– сделать обслуживание более регулярным (уменьшить квадрат коэффициента ковариаций ν),то есть уменьшить дисперсию.13Функция экспоненциального распределения времени пребывания:P (t) = 1 − e− Ttгде:t - время пребывания;T - среднее время пребывания.1455.1Лекция №5 - Анализ СМО с ограниченной очередьюАнализ СМО с ограниченной длиной очередиM/M/1/0µλОАPоткλоткВероятность отказа - вероятность того, что заявка, поступающая в систему, застаёт ОАзанятым, а очередь полностью заполнена.Тут два состояния:λ01P0µP1P + Pобслуж = 1n∑Pi = 1i=0где:n - число возможных состояний системыν 2 = νвх · Pi + (1 − Pi ) = Pi + 1 − Pi = 0155.1.1Буфер с с ёмкостью 1Рассмотрим буфер с ёмкостью 1:µλсистλОАm= 1PоткλоткТеперь стало 3 состояния:λλ01P02P1µP2µP0 · λ = P1 · µP1 · (λ + µ) = P0 · λ + P2 · µP2 · µ = P1 · λ5.1.2Буфер с с ёмкостью 2Рассмотрим буфер с ёмкостью 2:µλсистλОАm= 2PоткλоткТеперь стало 4 состояния:λ0P0λ1µP1λ2µ16P23µP3Для частного случая, когда все вероятности равны и λ = µ:Pотк = P3 =14λотк = Pотк · λ =5.1.314·λДве СМОТеперь рассмотрим две СМО:µµλвых = 0.5 λλОА1Pотк1ОА2λотк1 = 0.5 λPотк2λотк2P0 · λвх2 = P1 · µP0 · λвых1 = P1 · µ1P0 · λвх2 = P1 · µ2Тут какие-то расчёты и короче: до выхода второго ОА будет добираться только треть начального количества заявок, поступающих на вход всей системы ( 31 · λ).1766.1Лекция №6 - Анализ СМО с отказомОценка характеристик функционирования систем с отказомµλОАmPоткλоткλ=µρ=λ=1µКоличество состояний системы m + 2Поскольку λ = µ, то все состояния равновероятны.Вероятность отказа:P = Pm+1 =1m+2Интенсивность отказа:λотк = λ · Pотк =λm+2Поток заявок, попадающий в систему:λобсл = λ − λотк = λ · (1 −1m+1)=·λm+2m+2λ=λКоэффициент использования ОА:U=m+1∑Pi = 1 − P0 = 1 −i=11m+1=m+2m+2Количество заявок в очереди:Q=m+1∑m+1∑i=1i=1(i − 1) · Pi =i · Pi −m+1∑i=1m+1m+1∑∑1m m+1Pi =·i−Pi =·m + 2 i=12m+2i=118Количество заявок в системе (с учётом, что у нас есть отказы):L=Q+UЕсли бы не было отказов, то было бы:L=Q+ρЕщё способ:L=m+1∑i=1m+1∑ m+11i · Pi =·=m + 2 i=12Среднее время ожидания W определяется тремя способами:– учитываются и заявки отказа (у них время ожидания 0), и попавшие в систему.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
