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

Рис. 3. Пример графа состояний

Описание марковской модели. Для описания поведения системы в виде марковской модели следует определить понятие состояния системы; выявить все состояния, в которых может находиться система; указать, в каком состояний находится система в начальный момент; построить граф состояний, т. е. изобразить все состояния, например, кружками и возможные переходы из состояния в состояние — стрелками, соединяющими состояния (на рис. 3 выделено пять состояний); разметить граф, т. е. для каждого перехода указать интенсивность потока событий, переводящих систему из состояния z _i в состояние z _j

(8)

где p_ij (t, t + — вероятность перехода из состояния z_i в состояние z_j за время от t до t + .

Для стационарных марковских процессов интенсивности переходов не зависят от времени: _ij (t) = _ij, тогда p_ij (t, t + .

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

Уравнения Колмогорова для вероятностей состояний. Исчерпывающей количественной характеристикой марковского процесса является совокупность вероятностей состояний, т. е. вероятностей p_i (t) того, что в момент t процесс будет находиться в состоянии z_i (t = 1,..., n).

Рассмотрим, как определяются вероятности состояний по приведенному на рис. 3 графу состояний, считая все потоки простейшими. В случайный момент времени t система может находиться в одном из состояний z_i с вероятностью p_i (t). Придадим t малое приращение и найдем, например, p₂ (t + ) — вероятность того, что в момент t + t система будет в состоянии Z₂. Это может произойти, во-первых, если система в момент t была в состоянии Z₂ и за время не вышла из него; во-вторых, если в момент t система была в состоянии z₁ или z₂ и за время перешла в состояние Z₂.

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

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

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

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

,

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

.

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

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

(8)

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

Представим уравнения Колмогорова в общем виде:

(9)

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

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

(10)

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

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

(11)

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

(12)

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

Модель размножения и гибели. Разновидностью марковской модели с дискретным числом состояний и непрерывным временем является модель размножения и гибели. Она характерна тем, что ее граф состояний имеет вид цепи (рис. 4). Особенность этого графа состоит в том, что каждое из средних состояний z₁,..., z_n-1 связано прямой и обратной стрелками с каждым из соседних состояний — п z_j равым и левым, а крайние состояния z₀ и z_n — только с одним соседним состоянием.

λ0,1 λ1,2 z0 z1 λ0,1 λ1,2

Рис. 4. Графсостояний модели размножения и гибели

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

(13)

(14)

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

Контрольные вопросы

1. Простейший поток и его свойства.

2. Основная характеристика экспоненциального распределения.

3. Пуассоновский поток.

4. Поток Эрланга и его основные свойства.

5. Какой процесс называется Марковским описание Марковской модели?

6. Для чего используется уравнение Колмогорова?

7. Граф состояний модели размножения и гибели и основные формулы.

Литература

40.

41.

42.

43.

44.

Лекция 10. ХАРАКТЕРИСТИКИ ВЫЧИСЛИТЕЛЬНЫХ
СИСТЕМ (2 часа)

План

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

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

3. Методы приближённой оценки характеристик вычислительных систем

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

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

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

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

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

z₀ — прибор свободен, очереди нет;

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

z₂ — прибор занят, одна заявка в очереди;

z_k — прибор занят, (k — 1) заявок стоит в очереди.

Рис. 5. Граф состояний СМО

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

Коэффициент загрузки. Предельная вероятность состояния

(1)

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

. (2)

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

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

Это означает, что отношение

(3)