Партнерка на США и Канаду по недвижимости, выплаты в крипто

30% recurring commission
Выплаты в USDT
Вывод каждую неделю
Комиссия до 5 лет за каждого referral

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

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

2. Аналитические методы моделирования систем массового обслуживания

2.1.Описание Марковской модели

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

Для описания поведения системы в виде Марковской модели следует:

· определить понятие состояния системы;

· выявить все состояния, в которых может находиться система;

· указать, в каком состоянии находится система в начальный момент;

· построить граф состояний, т. е. изобразить все состояния, например, кружками и возможные переходы из состояния в состояние стрелками, соединяющими состояния (рис.2.1);

Рис. 2.1. Граф состояний Марковского процесса

· разметить граф, т. е. для каждого перехода указать интенсивность λij потока событий, переводящих систему из состояния Zi в состояние Zj:

= lim,

где - вероятность перехода из состояния Zi в состояние Zj за время от до .

Для стационарных Марковских процессов интенсивности переходов не зависят от времени: = , тогда = .

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

2,2. Уравнения Колмогорова для вероятностей состояний

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

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

Это может произойти, во-первых, если система в момент была в состояниии за время не вышла из него; во-вторых, если в момент система была в состоянииилии за время перешла в состояние

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

Найдем вероятность перехода в состояние. Если в момент t система находилась в состоянии с вероятностью, то вероятность перехода в состояние за время равна

Аналогично для состояния

Складывая вероятности получим

Раскроем квадратные скобки, перенесем в левую часть и разделим обе части на :

Если устремить к нулю, то слева получим производную функции:

Аналогичные уравнения можно вывести для всех остальных состояний. Получается система дифференциальных уравнений:

Эта система линейных дифференциальных уравнений дает возможность найти вероятности состояний, если задать начальные условия. В левой части каждого уравнения стоит производная вероятности i-го состояния, а в правой – сумма произведений вероятностей всех состоянии, из которых ведут стрелки в данное состояние, на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность i-гo состояния. Представим уравнения Колмогорова в общем виде:

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

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

НЕ нашли? Не то? Что вы ищете?

Сумма вероятностей всех возможных состояний равна единице.

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

Для вычисления предельных вероятностей нужно все левые части в уравнениях Колмогорова (в общем виде) положить равными нулю и решить полученную систему линейных алгебраических уравнений:

(1)

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

и с его помощью решить систему уравнений (1).

2.3. Модель размножения и гибели

Разновидностью Марковской модели с дискретным числом состояний и непрерывным временем является модель размножения и гибели [3]. Она характерна тем, что ее граф состояний имеет вид цепи (рис.2.2).

Рис. 2.2. Граф процесса гибели и размножения с конечным числом состояний

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

В этой модели формулы для определения вероятностей состояний, полученные в результате решения уравнений Колмогорова, имеют вид:

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

2.4.Характеристики вычислительных систем как систем массового обслуживания

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

Выделим состояния СМО по числу заявок, находящихся в системе:

Z0 - прибор свободен, очереди нет;

Z1 - прибор занят (обслуживает заявку), очереди нет;

Z2 - прибор занят, одна заявка в очереди;

- прибор занят, заявок стоит в очереди.

Это модель размножения и гибели, но с бесконечным количеством состояний, поскольку очередь неограниченна (рис 2.3)

Рис. 2.3. Граф процесса гибели и размножения

1) Коэффициент загрузки

Предельная вероятность состояния

Обозначая , получаем

Ряд в этой формуле представляет собой геометрическую прогрессию. Известно, что при ряд сходится. Сумма членов прогрессии при этом равна , откуда .

Это вероятность того, что прибор свободен и очередь отсутствует. Значит, вероятность того, что прибор занят обслуживанием заявки,

Это означает, что отношение служит мерой загрузки СМО и является коэффициентом загрузки. Тогда - коэффициент простоя.

2) Число заявок в СМО

Вероятности состояний определяются из общей формулы размножения и гибели:

Определим среднее число заявок в системе n.

В текущий момент времени в системе может быть заявок с вероятностями

Математическое ожидание количества заявок равно

Подставим значение и , исключив первое слагаемое, равное нулю:

Вынесем за знак суммы

Но - это производная поот :

Меняя местами операции дифференцирования и суммирования, получим

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

3) Длина очереди

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

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

4) Время реакции.

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

Обозначим через X (t) число заявок, поступивших в СМО до момента времени t, а через У (t) — число заявок, покинувших СМО до момента t. Та и другая функции являются случайными и меняются скачком – увеличиваются на единицу в моменты прихода или ухода заявок (рис. 2.4).

Рис. 2.4. Время пребывания заявок в системе

Очевидно, что для любого момента времени t разность функций X (t) и Y(t)

n(t) = X (t) - Y(t) есть число заявок, находящихся в СМО. Рассмотрим большой промежуток времени Т и вычислим среднее число заявок, находящихся в системе:

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

где сумма распространяется на все заявки, поступившие в систему за время Т. Разделим правую и левую части на Т:

Разделим и умножим правую часть на :

Произведение - это среднее количество заявок, пришедших за время Т. Если разделить сумму всех времен на среднее число заявок, то получится среднее время пребывания заявки в системе, т. е. среднее время реакции:

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

Вторая формула Литтла связывает среднее время пребывания заявки в очереди и среднее число заявок в очереди подобным соотношением:

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

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

2.5. Многоканальная СМО

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

Рис. 2.5. Граф переходов многоканальной системы

Интенсивности перехода в соседнее правое состояние определяются, как и у одноканальной СМО, интенсивностью входного потока: с приходом очередной заявки система переходит в следующее правое состояние. Иначе обстоит дело с интенсивностями у нижних стрелок. Пусть система находится в состоянии — работает один канал. Он производит обслуживаний в единицу времени. Тогда Представим, что система находится в состоянии Для перехода в состояние надо, чтобы закончил обслуживание первый или второй канал. Значит, суммарная интенсивность их обслуживания Суммарный поток обслуживания каналами имеет интенсивность При интенсивность обслуживания сохраняется . Получается модель размножения и гибели. Делая выкладки, как для одноканальной СМО, получим

Средняя длина очереди

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

получим среднее число заявок в системе:

По формулам Литтла определяется среднее время пребывания заявки в очереди:

и в системе — время реакции:

2.6. Системы с нетерпеливыми заявками

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

νож = νоб = 1/τср,

где τср – среднее допустимое время пребывания заявки в системе.

Методика анализа таких систем соответствует выше изложенному. Различие заключается в том, что интенсивности обратных переходов увеличиваются на величину к νоб к = 1,2, …,m при уходах заявок из каналов обслуживания и соответственно на l νож l = 1,…, q при уходах заявок из очереди (m – число каналов обслуживания; q – число мест в очереди).

2.7. Расчет основных характеристик систем массового обслуживания

На основе применения описанной методики были получены соотношения [2,3], позволяющие вычислить вероятности нахождения в каждом из состояний системы массового обслуживания, находящейся под воздействием простейших потоков. Задача анализа СМО практически может считаться решенной, если найдены эти вероятности, так как вычисление основных характеристик системы не представляет труда. В примере, приведенном ниже, используются данные соотношения. Заметим только, что при небольших размерностях системы, т. е. при малом числе каналов обслуживания и числе мест в очереди, аналитическое моделирование проще проводить в полном соответствии с методикой:

1) определить число состояний системы;

2) построить граф состояний и разметить его;

3) составить уравнения Колмогорова для предельных состояний и решить их, заменив одно из уравнений условием нормировки;

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

2.8. Пример аналитического моделирования вычислительных систем Определить эффективность функционирования многопроцессорной вычислительной системы по заданному критерию – обобщенному показателю потерь. Моделируемая структура: многопроцессорная управляющая вычислительная система, состоящая из m процессоров, на вход которой поступают простейшие потоки заявок (k потоков с интенсивностью , i=1,2,...,k). Процессоры однотипные со средним быстродействием B (в миллионах операций в секунду). Обслуживание заявки заключается в выполнении на любом из процессоров соответствующей прикладной программы. Средняя трудоемкость всех прикладных программ одинакова и равна (в тысячах операций). Закон распределения трудоемкости каждой из программ – экспоненциальный.

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