WinNavigator

Frigate

Norton Commander

WinNC

Dos Navigator

Servant Salamander

Turbo Browser

Winamp, Skins, Plugins

Необходимые Утилиты

Текстовые редакторы

Юмор

File managers and best utilites

Реферат: Модели систем массового обслуживания Классификация систем массового обслуживания. Классификация смо реферат

Классификация систем массового обслуживания и их основные элементы

СодержаниеВведение..................................................................................................1. Классификация СМО и их основные элементы ...............................2. Обслуживание с ожиданием..............................................................3. Пример использования СМО с ожиданием......................................Расчеты...................................................................................................Выводы...................................................................................................Список литературы................................................................................Приложение 1.........................................................................................Приложение 2.........................................................................................ВВЕДЕНИЕ

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

В теории систем массового обслуживания (в дальнейшем просто -CMÎ) обслуживаемый объект называют требованием. В общем случае под требованием обычно понимают запрос на удовлетворение некоторой потребности, например, разговор с абонентом, посадка самолета, покупка билета, получение материалов на складе.

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

Совокупность однотипных обслуживающих устройств называется îáñëóæèâàþùèìè óñòðîéñòвами. Такими системами могут быть телефонные станции, аэродромы, билетные кассы, ремонтные мастерские, склады и базы снабженческо-сбытовых организаций и т.д.

В теории СМО рассматриваются такие случаи, когда поступление требований происходит через случайные промежутки времени, а продолжительность обслуживания требований не является постоянной, т.е. носит случайный характер. В силу этих причин одним из основных методов математического описания СМО является аппарат теории случайных процессов .

Основной задачей теории СМО является изучение режима функционирования обслуживающей системы и исследование явлений, возникающих в процессе обслуживания. Так, одной из характеристик обслуживающей системы является время пребывания требования в очереди. Очевидно, что это время можно сократить за счет увеличения количества обслуживающих устройств. Однако каждое дополнительное устройство требует определенных материальных затрат, при этом увеличивается время бездействия обслуживающего устройства из-за отсутствия требований на обслуживание, что также является негативным явлением. Следовательно, в теории СМО возникают задачи оптимизации: каким образом достичь определенного уровня обслуживания (максимального сокращения очереди или потерь требований) при минимальных затратах, связанных с простоем обслуживающих устройств.Раздел І. Классификация СМО и их

основные элементы

СМО классифицируются на разные группы в зависимости от состава и от времени пребывания в очереди до начала обслуживания, и от дисциплины обслуживания требований.

По составу СМО бывают одноканальные (с одним обслуживающим устройством) и многоканальными (с большим числом обслуживающих устройств). Многоканальные системы могут состоять из обслуживающих устройств как одинаковой, так и разной производительности.

По времени пребывания требований в очереди до начала обслуживания системы делятся на три группы:

1) с неограниченным временем ожидания (с ожиданием),

2) с отказами;

3) смешанного типа.

В СМО с неограниченным временем ожидания очередное требование, застав все устройства занятыми, становится в очередь и ожидает обслуживания до тех пор, пока одно из устройств не освободится.

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

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

В системах с определенной дисциплиной обслуживания поступившее требование, застав все устройства занятыми, в зависимости от своего приоритета, либо обслуживается вне очереди, либо становится в очередь.

Основными элементами СМО являются:входящий поток требований, очередь требований, обслуживающие устройства, (каналы) и выходящий поток требований.

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

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

Среднее число требований, поступающих в систему обслуживания за единицу времени, называется интенсивностью поступления требований и определяется следующим соотношением:

где Т - среднее значение интервала между поступлением очередных требований.

Для многих реальных процессов поток требований достаточно хорошо описывается законом распределения Пуассона. Такой поток называется простейшим.

Простейший поток обладает такими важными свойствами:

1) Свойством стационарности, которое выражает неизменность вероятностного режима потока по времени. Это значит, что число требований, поступающих в систему в равные промежутки времени, в среднем должно быть постоянным. Например, число вагонов, поступающих под погрузку в среднем в сутки должно быть одинаковым для различных периодов времени, к примеру, в начале и в конце декады.

2) Отсутствия последействия, которое обуславливает взаимную независимость поступления того или иного числа требований на обслуживание в непересекающиеся промежутки времени. Это значит, что число требований, поступающих в данный отрезок времени, не зависит от числа требований, обслуженных в предыдущем промежутке времени. Например, число автомобилей, прибывших за материалами в десятый день месяца, не зависит от числа автомобилей, обслуженных в четвертый или любой другой предыдущий день данного месяца.

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

При простейшем потоке требований распределение требований, поступающих в систему подчиняются закону распределения Пуассона:

вероятность того, что в обслуживающую систему за время t поступит именно k требований:

где. - среднее число требований, поступивших на обслуживание в единицу времени.

На практике условия простейшего потока не всегда строго выполняются. Часто имеет место нестационарность процесса (в различные часы дня и различные дни месяца поток требований может меняться, он может быть интенсивнее утром или в последние дни месяца). Существует также наличие последействия, когда количество требований на отпуск товаров в конце месяца зависит от их удовлетворения в начале месяца. Наблюдается и явление неоднородности, когда несколько клиентов одновременно пребывают на склад за материалами. Однако в целом пуассоновский закон распределения с достаточно высоким приближением отражает многие процессы массового обслуживания. Почему такое предположение в ряде важных случаев оказывается верным, дает ответ общая теорема А.Я.Хинчина, которая представляет исключительную теоретическую и практическую ценность. Эта теорема имеет место в случае, когда входящий поток можно представить в виде суммы большого числа независимых потоков, ни один из которых не является сравнимым по интенсивности со всем суммарным потоком. Приведем “не строгую” формулировку этой теоремы (полная формулировка и доказательство приведены в).

Теорема (А.Я.Хинчин) Если входящий поток представляет собой сумму большого числа независимых между собой стационарных и ординарных потоков, каждый из которых вносит малый вклад в общую сумму, то при одном дополнительном условии аналитического характера (которое обычно выполняется на практике) поток близок к простейшему.

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

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

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

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

Случайная величина полностью характеризуется законом распределения, который определяется на основе статистических испытаний.

На практике чаще всего принимают гипотезу о показательном законе распределения времени обслуживания.

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

При показательном законе распределения времени обслуживания вероятность события, что время обслуживания продлиться не более чем t, равна:

где v - интенсивность обслуживания одного требования одним обслуживающим устройством, которая определяется из соотношения:

, (1)

где - среднее время обслуживания одного требования одним обслуживающим устройством.

Следует заметить, что если закон распределения времени обслуживания показательный, то при наличии нескольких обслуживающих устройств одинаковой мощности закон распределения времени обслуживания несколькими устройствами будет также показательным:

где n - количество обслуживающих устройств.

Важным параметром СМО является коэффициент загрузки , который определяется как отношение интенсивности поступления требований к интенсивности обслуживания v.

(2)

где a - коэффициент загрузки; - интенсивность поступления требований в систему; v - интенсивность обслуживания одного требования одним обслуживающим устройством.

Из (1) и (2) получаем, что

Учитывая, что - интенсивность поступления требований в систему

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

Для СМО с ожиданием количество обслуживаемых устройств п должно быть строго больше коэффициента загрузки (требование установившегося или стационарного режима работы СМО) :

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

Для СМО с отказами и смешанного типа это условие может быть ослаблено, для эффективной работы этих типов СМО достаточно потребовать, чтобы минимальное количество обслуживаемых устройств n было не меньше коэффициента загрузки : Раздел ІІ.Обслуживание с ожиданием

1. Постановка задачи.

СМО с ожиданием распространены наиболее широко. Их можно разбить на 2 большие группы - разомкнутые и замкнутые. Эти системы определяют так же, как системы с ограниченным входящим потоком.

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

В подобных системах общее число циркулирующих требований конечно и чаще всего постоянно.

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

Мы рассмотрим здесь классическую задачу теории массового обслуживания в тех условиях, в каких она была рассмотрена и решена К.Эрлангом. на n одинаковых приборов поступает простейший поток требований интенсивности . Если в момент поступления имеется хотя бы один свободный прибор, оно немедленно начинает обслуживаться. Если же все приборы заняты, то вновь прибывшее требование становится в очередь за всеми теми требованиями, которые поступили раньше и ещё не начали обслуживаться. Освободившийся прибор немедленно приступает к обслуживанию очередного требования, если только имеется очередь. Каждое требование обслуживается только одним прибором, и каждый прибор обслуживает в каждый момент времени не более одного требования. Длительность обслуживания представляет собой случайную величину с одним и тем же распределением вероятностей F(x). Предполагается, что при x0.

где - постоянная.

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

Выбор распределения (1) для описания длительности обслуживания произведен не случайно. Дело в том, что в этом предположении задача допускает простое решение, которое с удовлетворительной для практики точностью описывает ход интересующего нас процесса. Распределение (1) играет в теории массового обслуживания исключительную роль, которая в значительной мере вызвана следующим его свойством:

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

Действительно, пусть означает вероятность того, что обслуживание, которое ужо продолжается время а, продлится еще не менее чем . В предположении, что длительность обслуживания распределена показательно, . Далее ясно, что и . А так как всегда и , и, следовательно,

Требуемое доказано.

Несомненно, что в реальной обстановке показательное время обслуживания является, как правило, лишь грубым приближением к действительности. Так, нередко время обслуживания не может быть меньше, чем некоторая определенная величина. Предположение же (1) приводит к тому, что значительная доля требовании нуждается лишь в кратковременной операции, близкой к 0. Позднее перед нами возникает задача освобождения от излишнего ограничения, накладываемого предположением (1). Необходимость этого была ясна уже самому Эрлангу, и он в ряде работ делал усилия найти иные удачные распределения для длительности обслуживания. В частности, им было предложено так называемое

www.coolreferat.com

Реферат - СМО, классификация систем, основные характеристики.

или

По времени пребывания требований в очереди до начала обслуживания системы делятся на три группы: 1) с неограниченным временем ожидания (с ожиданием), 2) с отказами; 3) смешанного типа.

Основными элементами СМО являются: входящий поток требований, очередь требований, обслуживающие устройства, (каналы) и выходящий поток требований.

[pic] где Т — среднее значение интервала между поступлением очередных требований.

Простейший поток обладает такими важными свойствами:

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

www.ronl.ru

Реферат - Модели систем массового обслуживания Классификация систем массового обслуживания

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

кафедра сетей и устройств телекоммуникаций

РЕФЕРАТ

На тему:

«Модели систем массового обслуживания. Классификация систем массового обслуживания»

МИНСК, 2008

Математическое введение в теорию цепей Маркова. (Markov’schain)

Дискретные цепи Маркова. Будем говорить, что задана дискретная цепь Маркова, если для последовательности случайных величин выполняется равенство />.

Это означает, что поток случайных величин определяется только вероятностью перехода от предыдущего значения случайной величины к последующему. Зная начальное распределение вероятностей, можно найти распределение на любом шаге. Величины inможно интерпретировать как номера состояний некоторой динамической системы с дискретным множеством состояний (типа конечного автомата). Если вероятности переходов не зависят от номера шага, то такая цепь Маркова называется однородной и ее определение задается набором вероятностей />.

Для однородной Марковской цепи можно определить вероятности перехода из состояния i в состояние j за m шагов

Цепь Маркова называется неприводимой, если каждое ее состояние может быть достигнуто из любого другого состояния. Состояние i называется поглощающим, если для него pii =1.

Состояние называется возвратным, если вероятность попадания в него за конечное число шагов равна единице. В другом случае состояние относится к невозвратным. Возвратное состояние может быть периодическим и апериодическим в зависимости от наличия кратных шагов возврата. Введем вероятности возврата в состояние i через n шагов после ухода из этого состояния: />

Они позволяют определить среднее число шагов или, иначе говоря, среднее время возврата:/>.

Состояние называется возвратным нулевым, если среднее время возвращения в него равно бесконечности, и возвратным ненулевым, если это время конечно. Известны две важные теоремы:

Теорема 1.

Состояния неприводимой цепи Маркова либо все невозвратные, либо все возвратные нулевые, либо все возвратные ненулевые. В случае периодической цепи все состояния имеют один и тот же период.

Вторая теорема рассматривает вероятности достижения состояний в стационарном (то есть не зависящем от начального распределения вероятностей) режиме. Соответствующее распределение вероятностей также называют стационарным. Нахождение стационарного распределения вероятностей достижения состояний одна из основных задач теории телетрафика.

Теорема 2.

Для неприводимой и апериодической цепи Маркова всегда существуют предельные вероятности, не зависящие от начального распределения вероятностей. Более того, имеет место одна из следующих двух возможностей:

А) все состояния цепи невозвратные или все возвратные нулевые, и тогда все предельные вероятности равны нулю и стационарного состояния не существует;

Б) все состояния возвратные ненулевые и тогда существует стационарное распределение вероятностей:

Состояние называется эргодическим, если оно апериодично и возвратно ненулевое. Если все состояния цепи Маркова эргодичны, то вся цепь называется эргодической. Предельные вероятности эргодической цепи Маркова называют вероятностями состояния равновесия, имея в виду, что зависимость от начального распределения вероятностей полностью отсутствует.

Цепь Маркова с конечным числом состояний (конечная цепь), удобно изображать в виде ориентированного графа, называемого диаграммой переходов. Вершины графа ассоциируются с состояниями, а ребра с вероятностями переходов.

Вычисления вероятностей достижения состояний производится прямыми методами или с помощью z-преобразования.

Цепь Маркова.

Введем матрицу вероятностей переходов и вектор-строку вероятностей на шаге n

/>.

Распределение вероятностей на произвольном шаге тогда будет подчиняться матричному соотношению:

/>.

Оно позволяет рекуррентно вычислять все вероятности состояний. Для нахождения предельного распределения (стационарного) нужно решить уравнение:

Его можно решать как систему линейных алгебраических уравнений, если цепь конечна.

Для примера (рис. 1) имеем:

/>.

и решение матричного уравнения сводится к решению системы трёх уравнений:

Коэффициенты первого уравнения в этой системе дополняют до единицы сумму коэффициентов второго и третьего уравнений; это свидетельствует о линейной зависимости между ними. Поэтому для решения системы уравнений нужно ввести дополнительное нормирующее условие. В данном примере: />.

Решая систему полученных уравнений, имеем:

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

/>.

Обозначая соответствующие преобразования, получим: />

Все полученные здесь математические результаты относились к однородным Марковским процессам, где вероятности переходов не зависят от времени. В более общем случае такая зависимость имеет место.

Рассмотрим вероятности перехода системы из состояния i на m-том шаге в состояние j на n-том шаге для n > m.

Можно показать, что эти вероятности связаны между собой, так называемым уравнениями Чепмена-Колмогорова.(Chapman — Kolmogorov)

/>.

Для однородных цепей Маркова эти уравнения упрощаются так как

/>.

И сводятся к анализируемым выше.

Непрерывные цепи Маркова.

Случайный процесс 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) погиб один член популяции

--PAGE_BREAK--

Рис. 1. Возможные переходы в состояние Ек.

Будем искать вероятность того, что в момент времени t объем популяции равен k, обозначив его Pk(t). Можно записать соотношения для вероятности достижения состояния k в момент времени t+Δt:

/>.

Определим граничные и нормирующие условия:

Выразим вероятности переходов за интервал Δt через интенсивности

Вер(+1)=λkΔt+o(Δt) ; Вер(-1)=μkΔt+o(Δt).

Вероятность нуля рождений 1- λkΔt+o(Δt), а нуля гибелей 1- μkΔt+o(Δt).

Таким образом, вероятность того, что состояние k сохранится неизменным, будет равно произведению [1- λkΔt+o(Δt)][ 1- μkΔt+o(Δt)].

Тогда уравнения Чепмена-Колмогорова приобретают вид

Раскрывая скобки и проводя деление на Δt, получим:

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

В соответствие этой системе уравнений можно поставить наглядную диаграмму интенсивностей переходов, которая аналогична диаграмме переходов для дискретных цепей Маркова (Рис. 2)

Рис. 2 Диаграмма интенсивностей переходов для процесса размножения и гибели.

Овалам здесь соответствуют дискретные состояния, а стрелки определяют интенсивности потоков вероятности (а не вероятности!) переходов от одного состояния к другому.

Имеет место своеобразный «закон сохранения»:

Разность между суммой интенсивностей, с которой система попадает в состояние k и суммой интенсивностей, с которой система покидает это состояние должна равняться интенсивности изменения потока в это состояние (производной по времени).

Применение закона сохранения позволяет получать уравнения для любой подсистемы Марковской цепи типа процесса «гибели-размножения». Особенно эффективным оказывается построение решений в стационарном, установившемся режиме, когда можно полагать что вероятности в произвольный, достаточно отдаленный момент времени, остаются постоянными.

Приравнивая производную по времени нулю, получаем систему разностных уравнений

Полагая, что интенсивности λ-1=λ-2 = λ-3=…0; μ0= μ-1= μ-2= μ-3 =…=0, второе уравнение выписывать отдельно далее не потребуется. Итак, стационарный режим в цепи Маркова будет описываться системой разностных уравнений и условием нормировки для вероятностей

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

/>.

Интенсивность потока вероятностей в состояние k равна интенсивности потока из этого состояния.

Решать уравнение баланса можно, сначала определив при k =0 значение

/>.

Затем, построив систему уравнений для k =1, можно получить />.

Далее получаем

Из условия нормировки: />.

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

/>.

Для большинства реальных систем массового обслуживания это неравенство выполняется.

Классификация систем массового обслуживания.

Используется трех -, четырех -, шести – компонентное символическое обозначение системы массового обслуживания, предложенное Кендаллом (Candall) и развитое в работах Г.П.Барашина.

a/b/c:d/e/f

a– распределение поступающего потока запросов.

b– закон распределения времени обслуживания.

Типовые условные обозначения:

М – экспоненциальное (Марковское) распределение,

D– детерминированное распределение,

Ek– эрланговское распределение k-го порядка,

HMk– гиперэкспоненциальное,

HEk– гиперэрланговское распределение порядка k,

GI– произвольное распределение независимых промежутков между заявками,

G– произвольное распределение длительностей обслуживания.

c– структура системы обслуживания (обычно число серверов).

d– дисциплина обслуживания (параметры после двоеточия иногда опускают).

Обычно используется сокращенное символическое обозначение, например FFвместо FIFO, LF, PRи т.п.

e– максимальное число запросов, воспринимаемое системой, может употребляться символ ¥.

f– максимальное число запросов к системе обслуживания.

В некоторых публикациях последними символами отражают качественные характеристики системы обслуживания. Некоторые общие результаты и основы математического аппарата, необходимого для анализа можно получить, рассматривая системы G/G/m.

Формула Литтла (Little).

Рассмотрим временную диаграмму работы системы массового обслуживания (рис. 3), отразив на ней последовательность поступления требований, помещение требований в очередь и обработки серверами системы.

Временная диаграмма работы системы массового обслуживания.

В общем случае ясно, что с увеличением числа требований растет время ожидания. Установим соотношение между средним числом требований в системе, интенсивностью потока и среднего времени пребывания в системе. Обозначим число поступающих в промежутке времени (0, t)требований как функцию времени α(t).

Число исходящих из системы заявок (обслуженных) на этом интервале обозначим δ(t).На рисунке 4 показаны примеры функциональных зависимостей этих двух случайных процессов от времени.

Рис. 4 Зависимость между средним числом требований в системе, интенсивностью потока и средним времени пребывания в системе.

продолжение --PAGE_BREAK--

Число требований, находящихся в системе в момент t будет равно:

/>.

Площадь между двумя рассматриваемыми кривыми от 0 до t — дает общее время, проведенное всеми заявками в системе за время t.

Обозначим эту накопленную величину γ(t) .Если интенсивность входного потока равна λ, а средняя интенсивность за время t: />, то время, проведенное одной заявкой в системе, усредненное по всем заявкам будет равно:

/>.

Наконец, определим среднее число требований в системе в промежутке (0,t): />.

Из последних трех уравнений следует, что: />, (где />).

Если в СМО существует стационарный режим, то при t→ ∞, будут иметь место соотношения:

Последнее соотношение означает, что среднее число заявок в системе равно произведению интенсивности поступления требований в систему на среднее время пребывания в системе. При этом не накладывается никаких ограничений на распределения входного потока и времени обслуживания. Впервые доказательство этого факта дал Дж.Литтл и это соотношение носит название формула Литтла.

Интересно, что в качестве СМО можно рассмотреть только очередь из заявок в буфере. Тогда формула Литтла приобретает иной смысл — средняя длина очереди равна произведению интенсивности входного потока заявок на среднее время ожидания в очереди: />.

Если наоборот рассматривать СМО только как серверы, то формула Литтла дает:

/>,

где />– среднее число заявок в серверах, а/>– среднее время обработки в сервере.

В любом случае: />.

Одним из основных параметров, которые используются при описании СМО, является коэффициент использования (utilization factor). Это фундаментальный параметр, так как он определяется как отношение интенсивности входного потока к пропускной способности системы. Поскольку пропускная способность СМО содержащей m серверов может быть определена как: />, то коэффициент использованияможет быть определен как:

/>.

Нетрудно видеть, что коэффициент использования равен в точности интенсивности нагрузки, если СМО с одним сервером и в m раз меньше для систем с m серверами. Величина коэффициента использования равна среднему значению от доли занятых серверов и />.

Если в СМО типа G/G/1существует стационарный режим и можно определить вероятность того, что в некоторый случайный момент сервер будет свободный, то

/>.

ЛИТЕРАТУРА

Л.Н. Волков, М.С. Немировский, Ю.С. Шинаков. Системы цифровой радиосвязи: базовые методы и характеристики. Учебное пособие.-М.: Эко-трендз, 2005.

М.В. Гаранин, В.И. Журавлев, С.В. Кунегин. Системы и сети передачи информации. — М.: Радио и связь, 2001.

Передача дискретных сообщений./Под ред. В.П. Шувалова. – М.: Радио и связь, 1990.

Основы передачи дискретных сообщений./Под ред. В.М. Пушкина. – М.: Радио и связь, 1992.

Н.В. Захарченко, П.Я. Нудельман, В.Г. Кононович. Основы передачи дискретных сообщений. –М.: Радио и связь, 1990.

www.ronl.ru

Лекция - СМО, классификация систем, основные характеристики.

или

Основными элементами СМО являются: входящий поток требований, очередь требований, обслуживающие устройства, (каналы) и выходящий поток требований.

[pic] где Т — среднее значение интервала между поступлением очередных требований.

Простейший поток обладает такими важными свойствами:

www.ronl.ru

Модели систем массового обслуживания. Классификация систем массового обслуживания

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

кафедра сетей и устройств телекоммуникаций

РЕФЕРАТ

На тему:

«Модели систем массового обслуживания. Классификация систем массового обслуживания»

МИНСК, 2008

Математическое введение в теорию цепей Маркова. (Markov’schain)

Дискретные цепи Маркова. Будем говорить, что задана дискретная цепь Маркова, если для последовательности случайных величин выполняется равенство.

Это означает, что поток случайных величин определяется только вероятностью перехода от предыдущего значения случайной величины к последующему. Зная начальное распределение вероятностей, можно найти распределение на любом шаге. Величиныinможно интерпретировать как номера состояний некоторой динамической системы с дискретным множеством состояний (типа конечного автомата). Если вероятности переходов не зависят от номера шага, то такая цепь Маркова называется однородной и ее определение задается набором вероятностей.

Для однородной Марковской цепи можно определить вероятности перехода из состоянияiв состояниеjзаmшагов

Цепь Маркова называется неприводимой, если каждое ее состояние может быть достигнуто из любого другого состояния. Состояниеiназывается поглощающим, если для негоpii=1.

Состояние называется возвратным, если вероятность попадания в него за конечное число шагов равна единице. В другом случае состояние относится к невозвратным. Возвратное состояние может быть периодическим и апериодическим в зависимости от наличия кратных шагов возврата. Введем вероятности возврата в состояниеiчерезnшагов после ухода из этого состояния:

Они позволяют определить среднее число шагов или, иначе говоря, среднее время возврата:.

Состояние называетсявозвратным нулевым, если среднее время возвращения в него равно бесконечности, ивозвратным ненулевым, если это время конечно. Известны две важные теоремы:

Теорема 1.

Теорема 2.

Б) все состояния возвратные ненулевые и тогда существует стационарное распределение вероятностей:

Состояние называетсяэргодическим, если оно апериодично и возвратно ненулевое. Если все состояния цепи Марковаэргодичны, то вся цепь называетсяэргодической. Предельные вероятности эргодической цепи Маркова называют вероятностями состояния равновесия, имея в виду, что зависимость от начального распределения вероятностей полностью отсутствует.

Вычисления вероятностей достижения состояний производится прямыми методами или с помощью z-преобразования.

Цепь Маркова.

Введем матрицу вероятностей переходов и вектор-строку вероятностей на шаге n

Распределение вероятностей на произвольном шаге тогда будет подчиняться матричному соотношению:

Его можно решать как систему линейных алгебраических уравнений, если цепь конечна.

Для примера (рис. 1) имеем:

и решение матричного уравнения сводится к решению системы трёх уравнений:

Решая систему полученных уравнений, имеем:

Обозначая соответствующие преобразования, получим:

Рассмотрим вероятности перехода системы из состояния i на m-том шаге в состояние j на n-том шаге для n > m.

Можно показать, что эти вероятности связаны между собой, так называемым уравнениями Чепмена-Колмогорова.(Chapman - Kolmogorov)

Для однородных цепей Маркова эти уравнения упрощаются так как

И сводятся к анализируемым выше.

Непрерывные цепи Маркова.

Случайный процесс 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 – deathprocess).Для таких систем из состояния k возможны переходы только в состояния k, k-1 и k+1 в следующие моменты времени:

· в момент t объем популяции был равен k и в течение времени (t,t+Δt) не произошло изменения состояния

· в момент t объем популяции был равен k-1 и в течение времени (t,t+Δt) родился один член популяции

· в момент времени t объем популяции был равен k+1 и в течение времени (t,t+Δt) погиб один член популяции

Рис. 1. Возможные переходы в состояние Ек.

Будем искать вероятность того, что в момент времени t объем популяции равен k , обозначив его Pk(t). Можно записать соотношения для вероятности достижения состояния k в момент времени t+Δt:

Определим граничные и нормирующие условия:

Выразим вероятности переходов за интервал Δt через интенсивности

Вер(+1)=λkΔt+o(Δt) ; Вер(-1)=μkΔt+o(Δt).

Вероятность нуля рождений 1- λkΔt+o(Δt) , а нуля гибелей 1- μkΔt+o(Δt).

Тогдауравнения Чепмена-Колмогороваприобретают вид

Раскрывая скобки и проводя деление на Δt, получим:

Рис. 2 Диаграмма интенсивностей переходов для процесса размножения и гибели.

Имеет место своеобразный «закон сохранения»:

Приравнивая производную по времени нулю, получаем систему разностных уравнений

Полагая, что интенсивности λ-1=λ-2= λ-3=…0; μ0= μ-1= μ-2= μ-3=…=0, второе уравнение выписывать отдельно далее не потребуется. Итак, стационарный режим в цепи Маркова будет описываться системой разностных уравнений и условием нормировки для вероятностей

Интенсивность потока вероятностейвсостояние k равна интенсивности потока из этого состояния.

Решать уравнение баланса можно, сначала определив при k =0 значение

Затем, построив систему уравнений для k =1, можно получить.

Далее получаем

Из условия нормировки:.

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

Для большинства реальных систем массового обслуживания это неравенство выполняется.

Классификация систем массового обслуживания.

a/b/c :d/e/f

a – распределение поступающего потока запросов.

b – закон распределения времени обслуживания.

Типовые условные обозначения:

М – экспоненциальное (Марковское) распределение,

D – детерминированное распределение,

Ek– эрланговское распределение k-го порядка,

HMk– гиперэкспоненциальное,

HEk– гиперэрланговское распределение порядка k,

GI – произвольное распределение независимых промежутков между заявками,

G – произвольное распределение длительностей обслуживания.

c – структура системы обслуживания (обычно число серверов).

d – дисциплина обслуживания (параметры после двоеточия иногда опускают).

Обычно используется сокращенное символическое обозначение, например FF вместо FIFO, LF, PR и т.п.

e – максимальное число запросов, воспринимаемое системой, может употребляться символ ¥.

f – максимальное число запросов к системе обслуживания.

Формула Литтла (Little).

Временная диаграмма работы системы массового обслуживания.

В общем случае ясно, что с увеличением числа требований растет время ожидания. Установим соотношение между средним числом требований в системе, интенсивностью потока и среднего времени пребывания в системе. Обозначим число поступающих в промежутке времени(0 ,t)требований как функцию времениα(t).

Число исходящих из системы заявок (обслуженных) на этом интервале обозначимδ(t).На рисунке 4 показаны примеры функциональных зависимостей этих двух случайных процессов от времени.

Число требований, находящихся в системе в момент t будет равно:

Площадь между двумя рассматриваемыми кривыми от 0 до t - дает общее время, проведенное всеми заявками в системе за время t.

Обозначим эту накопленную величину γ(t) . Если интенсивность входного потока равна λ, а средняя интенсивность за время t:,то время, проведенное одной заявкой в системе, усредненное по всем заявкам будет равно:

Наконец, определим среднее число требований в системе в промежутке (0,t):.

Из последних трех уравнений следует, что:, (где).

Если в СМО существует стационарный режим, то при t→ ∞ , будут иметь место соотношения:

Интересно, что в качестве СМО можно рассмотреть только очередь из заявок в буфере. Тогда формула Литтла приобретает иной смысл - средняя длина очереди равна произведению интенсивности входного потока заявок на среднее время ожидания в очереди:.

Если наоборот рассматривать СМО только как серверы, то формула Литтла дает:

где– среднее число заявок в серверах, а– среднее время обработки в сервере.

В любом случае:.

Одним из основных параметров, которые используются при описании СМО, являетсякоэффициент использования (utilizationfactor). Это фундаментальный параметр, так как он определяется как отношение интенсивности входного потока к пропускной способности системы. Поскольку пропускная способность СМО содержащей m серверов может быть определена как:, токоэффициент использованияможет быть определен как:

Если в СМО типаG/G/1существует стационарный режим и можно определить вероятность того, что в некоторый случайный момент сервер будет свободный, то

ЛИТЕРАТУРА

1. Л.Н. Волков, М.С. Немировский, Ю.С. Шинаков. Системы цифровой радиосвязи: базовые методы и характеристики. Учебное пособие.-М.: Эко-трендз, 2005.

2. М.В. Гаранин, В.И. Журавлев, С.В. Кунегин. Системы и сети передачи информации. - М.: Радио и связь, 2001.

3. Передача дискретных сообщений./Под ред. В.П. Шувалова. – М.: Радио и связь, 1990.

4. Основы передачи дискретных сообщений./Под ред. В.М. Пушкина. – М.: Радио и связь, 1992.

5. Н.В. Захарченко, П.Я. Нудельман, В.Г. Кононович. Основы передачи дискретных сообщений. –М.: Радио и связь, 1990.

superbotanik.net

Смотрите также

..:::Новинки:::..

Windows Commander 5.11 Свежая версия.

Новая версия
IrfanView 3.75 (рус)

Обновление текстового редактора TextEd, уже 1.75a

System mechanic 3.7f
Новая версия

Обновление плагинов для WC, смотрим :-)

Весь Winamp
Посетите новый сайт.

WinRaR 3.00
Релиз уже здесь

PowerDesk 4.0 free
Просто - напросто сильный upgrade проводника.

..:::Счетчики:::..