Характеристики вычислительных систем, представленных в виде моделей СМО

2
1. Модель размножения и гибели
1.1 Граф модели размножения и гибели
Имея в распоряжении размеченный граф состояний, можно легко написать уравнения Колмогорова для вероятностей состояний, а также написать и решить уравнения для финальных вероятностей. Для некоторых случаев удается получить решение этих уравнений в аналитическом виде.
Разновидностью марковской модели с дискретным числом состояний и непрерывным временем является модель размножения и гибели. Граф состояний этой модели имеет вид цепи. Интенсивности переходов из одного состояния в другое обозначены как λij , а времена переходов распределены по показательному закону, т.е. все потоки, переводящие систему по стрелкам графа – простейшие.

3
1. Модель размножения и гибели
1.1 Граф модели размножения и гибели
Особенность этого графа в том, что все состояния системы (S0,S1,…,Sn) можно вытянуть в одну цепочку, в которой каждое из соседних состояний связано прямой и обратной стрелкой с каждыми из соседних состояний – правым и левым, а крайние состояния S0 и Sn только с одним соседним состоянием
Такая схема часто встречается в теории массового обслуживания.
Рассмотрим возможные состояния системы (S0,S1,…,Sn) и их вероятности:
Очевидно, что для любого момента времени (условие нормировки):

4
1. Модель размножения и гибели
1.2 Дифференциальные уравнения Колмогорова
Составим дифференциальные уравнения Колмогорова для всех вероятностей, используя приведенный граф состояний исходной модели.
Для этого зафиксируем момент времени t и найдем вероятность p0(t+∆t) того, что в момент времени t+∆t система будет находиться в состоянии S0.
Исходя из представленной схемы графа состояний, это может произойти двумя способами:
во – первых (событие А) - в момент t система находилась в состоянии S0, а за время ∆t не перешла из него в состояние S1;
во – вторых (событие В) – в момент t система находилась в состоянии S1, а за время ∆t перешла в состояние S1.
Складывая эти две возможности (по теореме сложения вероятностей) получим:

5
1. Модель размножения и гибели
1.2 Дифференциальные уравнения Колмогорова
Вероятность события А найдем по теореме умножения вероятностей. Вероятность того, что в момент t система находилась в состоянии S0, равна p0(t) . Вероятность того, что за время ∆t не придет ни одной заявки, равна exp(-λ01∆t). Учитывая, что значение λ01∆t – мало, можно записать:
Окончательно, для вероятности события A имеем:

6
1. Модель размножения и гибели
1.2 Дифференциальные уравнения Колмогорова
Найдем вероятность события p(B). Вероятность того, что в момент t система была в состоянии S1, равна p1(t).
Вероятность того, что за время ∆t система перейдет в состояние S0, равна – 1- exp(-λ10∆t) или
Окончательно, для вероятности события В получим:

7
1. Модель размножения и гибели
1.2 Дифференциальные уравнения Колмогорова
Суммируя вероятности событий А и В, окончательно получим,
Перенося в левую часть p0(t), деля на ∆t и переходя к пределу, получим дифференциальное уравнение для p0(t):

8
1. Модель размножения и гибели
1.2 Дифференциальные уравнения Колмогорова
Аналогично, могут быть получены дифференциальные уравнения и для всех остальных вероятностей состояний:

9
1. Модель размножения и гибели
1.3 Финальные стационарные уравнения Колмогорова
Вначале, после включения рассматриваемой системы в работу, протекающий в ней процесс не будет стационарным. Этот начальный процесс называется переходным – нестационарным. Однако, спустя некоторое время этот переходный процесс затухает и система перейдет в установившейся – стационарный режим работы.
Для стационарного режима вероятностные характеристики не зависят от времени. В этом стационарном режиме работы все вероятности p0(t), p1(t), …., pn(t) стремятся к постоянным пределам p0, p1, …, pn, а все их производные стремятся к нулю.

10
1. Модель размножения и гибели
1.3 Финальные стационарные уравнения Колмогорова
Заменим в системе обыкновенных дифференциальных уравнений все вероятности их пределами , а все производные положим равными нулю. В этом случае получим систему уже не дифференциальных, а алгебраических уравнений:
К этим уравнениям необходимо добавить условие нормировки:

11
1. Модель размножения и гибели
1.3 Финальные стационарные уравнения Колмогорова
Разрешим полученную систему относительно неизвестных p0, p1, …, pn.
Для первого уравнения имеем :
Для второго уравнения имеем :
Подставляя первое уравнение во второе, получим :
Аналогичное соотношение получим и для состояния S2
Обобщая полученные соотношения можно записать и для произвольного состояния Sk
где k=0,1…,n

12
1. Модель размножения и гибели
1.3 Финальные стационарные уравнения Колмогорова
Итоговая система преобразованных уравнений имеет следующий вид :
Из первого уравнения можно получить
Из второго уравнения можно получить
Обобщая полученные соотношения для произвольного состояния Sk имеем:

13
1. Модель размножения и гибели
1.3 Финальные стационарные уравнения Колмогорова
В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева – направо (с начала и до данного состояния Sk), а в знаменателе – произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до Sk).
Заметим, что все вероятности состояний выражены через одну вероятность – вероятность нахождения системы в начальном состоянии - р0.
Подставим, эти выражения в нормировочное условие получим:

14
2. Модель вычислительной системы в виде одноканальной СМО с очередью
Характеристики вычислительной системы
Рассмотрим систему с одним каналом и неограниченной очередью, в которой отсутствуют ограничения по длине очереди и по времени ожидания. Интенсивность входного потока заявок λ, среднее время обслуживания tобс.
Необходимо найти финальные вероятности состояний, а также:
Lсист – среднее число заявок в системе;
Wсист – среднее время пребывания заявки в системе;
Lочер – среднее число заявок в очереди;
Wочер – среднее время пребывания заявки в очереди;
Рзан – вероятность того, что канал занят.
Состояния системы:
S0 – канал свободен, очереди нет;
S1 – канал занят, очереди нет;
S2 – канал занят, 1 заявка в очереди;
….
Sn – канал занят, (n-1) заявка в очереди.

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

16
Если обозначить λ/μ=ρ, то получим:
2. Модель вычислительной системы в виде одноканальной СМО с очередью
Коэффициент загрузки
Заметим, что среднее время обслуживания tобс и интенсивность обслуживания μ связаны следующей зависимостью:
μ=1/tобс.
Заметим также, что абсолютную пропускную способность вычислять не надо – рано или поздно заявка будет обслужена, так как очередь неограничена; следовательно, А=λ. Относительная пропускная способность – вероятность того, что заявка будет обслужена, – Q=1.
Предельная вероятность состояния p0 может быть найдена из следующей формулы:

17
2. Модель вычислительной системы в виде одноканальной СМО с очередью
Коэффициент загрузки
Из математики известно, что ряд в приведенной формуле сходится при ρ<1. При этом сумма ряда равна 1/(1-ρ). Тогда для финальной вероятности p0 получим следующую формулу:
p0=1-ρ
Полученная вероятность p0 означает, что канал обработки (сервер) свободен и очереди нет. Дополнительная величина к p0, равная 1-p0=1-1+ρ=ρ означает, что канал занят обслуживанием, т.е. отношение ρ=λ/μ является мерой загрузки канала (сервера) и называется коэффициентом загрузки.
Таким образом, для такой системы финальные вероятности существуют, если величина ρ=λ/μ<1. Если ρ>=1, то очередь при t→∞ растет неограниченно.
Заметим, что СМО справляется с потоком заявок при ρ=1, только если этот поток – регулярный, и время обслуживания тоже неслучайно, равно интервалу между заявками. В этом идеальном случае очередь в СМО вообще отсутствует, канал будет непрерывно занят и регулярно выпускать обслуженные заявки.

18
2. Модель вычислительной системы в виде одноканальной СМО с очередью
Коэффициент загрузки
Финальные вероятности, как уже было сказано, образуют геометрическую прогрессию со знаменателем ρ.
Как это ни странно, максимальной из них оказывается р0 – вероятность того, что канал будет вообще свободен. Как бы ни была нагружена система с очередью, если только она вообще справляется с потоком заявок (ρ<1), самое вероятное число заявок в системе будет 0.
Далее вычислим среднее число заявок в системе.

19
2. Модель вычислительной системы в виде одноканальной СМО с очередью
Среднее число заявок в системе
Обозначим среднее число заявок в системе - Lsys.
Случайная величина Z – число заявок в системе – имеет возможные значения 0,1,2,3..k, с вероятностями р0, р1, р2, … рk. Тогда будем иметь:
(19.1)
Учитывая, что
и подставляя в формулу (19.1) получим
Но величина
это производная по ρ от величины ρk

20
2. Модель вычислительной системы в виде одноканальной СМО с очередью
Среднее число заявок в системе
Учитывая последнее, можно записать формулу (19.1) в следующем виде:
Меняя местами операции дифференцирования и суммирования получим следующее выражение
Учитывая, что сумма бесконечной убывающей прогрессии равна 1/(1-ρ) , ее производная равна 1/(1-ρ)2 , окончательно получим:
(20.1)
(20.2)
(20.3)

21
2. Модель вычислительной системы в виде одноканальной СМО с очередью
Длина очереди
Средняя длина очереди равна среднему числу заявок в системе минус среднее число обслуживаемых заявок.
Ранее было показано, что среднее число обслуживаемых заявок равно ρ. Учитывая это, можно записать, что средняя длина очереди в СМО равна:

2. Модель вычислительной системы в виде одноканальной СМО с очередью
22
Среднее время пребывания заявки в системе и в очереди
Выведем важную формулу, связывающую для предельного стационарного режима среднее число заявок Lsys, находящихся в системе массового обслуживания, и среднее время пребывания заявки в системе Wsys.
Пусть дана любая система массового обслуживания и связанные с ней два потока событий: поток заявок, прибывающих в систему, и поток заявок, покидающих СМО. Если в системе установился предельный стационарный режим, то среднее число заявок, прибывающих в систему за единицу времени, равно среднему числу заявок, покидающих ее: оба потока имеют одну и ту же интенсивность λ.
Пусть Х(t) – число заявок, прибывших в СМО до момента t, Y(t) – число заявок, покинувших систему до момента t. И та, и другая функция являются случайными и меняются скачком: в моменты прихода заявок Х(t) увеличивается на 1, Y(t) уменьшается на 1 в моменты ухода заявки.

2. Модель вычислительной системы в виде одноканальной СМО с очередью
23
Среднее время пребывания заявки в системе и в очереди
На временной диаграмме процесса поступления и ухода заявок изображены функции Х, Y. Обе линии – ступенчатые; верхняя – Х(t), нижняя – Y(t). Очевидно, что для любого момента времени их разность
Z(t) = Х(t) – Y(t) – есть не что иное, как число заявок, находящихся в СМО.

2. Модель вычислительной системы в виде одноканальной СМО с очередью
24
Среднее время пребывания заявки в системе и в очереди
Рассмотрим очень большой промежуток времени Т и вычислим для него среднее число заявок, находящихся в СМО. Оно будет равно интегралу от функции Z(t) на этом промежутке, деленному на длину интервала Т:
Но этот интеграл есть не что иное, как площадь заштрихованной фигуры, приведенной на слайде № 23.
Фигура состоит из прямоугольников, высота которых равна 1, а основание – равно времени пребывания соответствующей заявки в системе. Обозначим эти времена t1, t2, t3…tn

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

2. Модель вычислительной системы в виде одноканальной СМО с очередью
26
Среднее время пребывания заявки в системе и в очереди
Разделим и умножим правую часть полученного ранее выражения на λ, тогда получим:
Но Тλ -- есть не что иное, как среднее число заявок, пришедшее за время Т. Если мы разделим сумму всех времен ti на среднее число заявок, то получим среднее время пребывания заявки в системе Wsys. Итак, среднее время пребывания заявки в системе составит:
А средне время пребывания заявки в очереди составит:

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