Главная страница Случайная лекция Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика Мы поможем в написании ваших работ! |
Непрерывные цепи Маркова
Непрерывные цепи Маркова. 2.Анализ систем массового обслуживания с марковскими потоками требований. Система М/M/1. Анализ Случайный процесс X(t) с дискретным множеством значений образует непрерывную цепь Маркова, если . Будущие состояния зависят от прошлого только через текущее состояние. Для непрерывный цепей Маркова основным также является уравнение Чепмена –Колмогорова, для однородной цепи имеющее вид: . Здесь матрица H(t)= [ pij(t)] - матрица вероятностей перехода из состояния i в состояние j в момент времени t , а матрица Q называется матрицей интенсивностей переходов. Ее элементы имеют следующий смысл: если в момент времени t система находилась в состоянии Ei , то вероятность перехода в течение промежутка времени (t,t+Δt) в произвольное состояние Ej задается величиной qij(t)Δt + o(Δt), а вероятность ухода из состояния Ei величиной -qiiΔt + o(Δt). Таким образом, интенсивности переходов можно вычислять как соответствующие пределы при стремлении к нулю длительности временного интервала. Наиболее важным для дальнейшего использования является класс непрерывных цепей Маркова называемых «процессами гибели - размножения»(Birth – death process). Для таких систем из состояния k возможны переходы только в состояния k, k-1 и k+1 в следующие моменты времени: · в момент t объем популяции был равен k и в течение времени (t,t+Δt) не произошло изменения состояния · в момент t объем популяции был равен k-1 и в течение времени (t,t+Δt) родился один член популяции · в момент времени t объем популяции был равен k+1 и в течение времени (t,t+Δt) погиб один член популяции.
Диаграмма переходов для дискретных цепей Маркова (Рис 3) Рис.3 Диаграмма интенсивностей переходов для процесса размножения и гибели. Овалам здесь соответствуют дискретные состояния, а стрелки определяют интенсивности потоков вероятности (а не вероятности!) переходов от одного состояния к другому. Имеет место своеобразный «закон сохранения»: Разность между суммой интенсивностей, с которой система попадает в состояние k и суммой интенсивностей, с которой система покидает это состояние должна равняться интенсивности изменения потока в это состояние (производной по времени). Применение закона сохранения позволяет получать уравнения для любой подсистемы Марковской цепи типа процесса «гибели-размножения». Особенно эффективным оказывается построение решений в стационарном, установившемся режиме, когда можно полагать что вероятности в произвольный, достаточно отдаленный момент времени, остаются постоянными. Система М/M/1. Анализ. Это система с пуассоновским входным потоком заявок, экспоненциальным законом распределения времени обслуживания и одним сервером. На рис. 1. приведена простейшая схема такой системы. Она содержит буфер, который может хранить очередь бесконечной длины, состояние которой может быть отождествлено с числом заявок, содержащихся в очереди в каждый момент времени. Рис. 1. СМО типа М/М/1. Поскольку входной процесс ординарный, то в каждый момент времени к очереди может добавиться только одна заявка, поскольку сервер один, то в каждый момент времени может быть обслужена, то есть уйти из очереди только одна заявка. Таким образом, рассматриваемая СМО относится к процессу класса «гибели-размножения». Для анализа необходимо конкретизировать параметры системы. Распределение вероятностей входного потока и времени обслуживания позволяет полагать интенсивности вероятностей в модели постоянными. Здесь t – среднее время обслуживания в сервере. На рис 2 приведена диаграмма интенсивностей переходов для рассматриваемой системы. Рис. 2 Диаграмма интенсивности переходов для СМО типа М/М/1.
Полученное ранее общее решение позволяет сразу записать вероятность того, что в стационарном состоянии в очереди будет находиться k заявок Найдем начальное значение вероятности, учитывая сходимость соответствующего ряда . Окончательно получаем формулу для вероятности длины очереди . Лекция №4 по дисциплине “Теория распределение информации» Наименование темы: Анализ систем массового обслуживания с марковскими потоками требований 1. Система с несколькими серверами: M/M/m 2.Система обслуживания с m серверами явными потерями: M/M/m/Loss 1. Система с несколькими серверами: M/M/m Рассмотрим сначала простой случай системы, содержащей два сервера, любой из которых доступен для поступающих на вход заявок. Системы с несколькими серверами такого типа называют полнодоступными. По сравнению с односерверной системой производительность будет выше. Сравнение с односерверной системой интенсивность обслуживания в которой в среднем вдвое выше, то есть мы ответим на вопрос что эффективнее удвоение скорости обработки или распараллеливание обработки. Система M/M/2 может быть представлена как процесс размножения-гибели с параметрами: Таким образом, в системе с двумя серверами время задержки сокращается. Нетрудно убедиться, что производительность системы M/M/2 также выше. Получилось, что производительность системы без блокировки также как и для системы с одним сервером совпадает с входной нагрузкой, тогда как максимальная производительность могла равняться 2μ . Найдем теперь для сравнения характеристики качества обслуживания для односерверной системы с вдвое большей пропускной способностью сервера μ.
Рис. 1. Нормированные графики среднего времени задержки в системе с одним и с двумя серверами одной и той же производительности и с одним серверов, работающим с вдвое большей скоростью. На рис 1. Представлены нормированные графики средгнего времени задержки в системе с одним и с двумя серверами одной и той же производительности и с одним серверов, работающим с вдвое большей скоростью. Как видно из сравнения, увелечение вдвое скорости работы сервера оказывается более эффективным, чем введение паралельного сервера той же производительности. Рассмотрим теперь общий случай СМО с m серверами. Диаграмма интенсивностей переходов для такой системы представлена на рис. 2.
Рисунок 2. Диаграмма интенсивностей переходов для СМО типа M/M/m. Интенсивности переходов могут быть определены следующим образом: 2.Система обслуживания с m серверами явными потерями: M/M/m/Loss Система без образования очереди для заявок, поступивших в моменты, когда все m серверов были заняты. Такие заявки будут просто теряться. В телефонии это типичный случай коммутирования на конечном коммутационном поле. Опишем такую систему подходящим процессом типа гибели-размножения. Его параметры могут быть определены так Такая система оказывается также эргодичной и диаграмма интенсивностей переходов, приведенная на рис. 3 Рис. 3 Диаграмма интенсивностей переходов для СМО типа M/M/m:Loss. Основной характеристикой QoS для этой системы является средняя доля времени, когда все серверы оказываются занятыми. В этом случае говорят о том, что в системе наступила блокировка.
Дата добавления: 2014-03-13; просмотров: 703; Нарушение авторских прав Мы поможем в написании ваших работ! |