АНАЛИТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Matn

План

1. Потоки заявок

Простейший поток. При аналитическом моделировании характеристики системы вычисляются наиболее просто для потока заявок, называемого простейшим. Простейший поток — это поток заявок, который обладает следующими свойствами: 1) стационарность; 2) отсутствие последействия; 3) ординарность.

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

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

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

Любой поток, обладающий этими свойствами, является простейшим.

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

F()=l-e ^-. (1)

Такое распределение называется экспоненциальным (показательным) и имеет плотность

f()=, (2)

математическое ожидание длины интервала

(3)

дисперсию

(4)

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

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

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

(5)

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

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

3. Интервал времени между произвольным моментом времени и моментом поступления очередной заявки имеет экспоненциальное распределение с таким же математическим ожиданием 1/, что и интервал времени между двумя последовательными заявками.

4. Простейший поток создает тяжелый режим функционирования системы, поскольку, во-первых, большее число (63 %) промежутков времени между заявками имеет длину меньшую, чем ее математическое ожидание 1/, и, во-вторых, коэффициент вариации,

{spoiler=Подробнее}

Рис. 1. Распределение Пуассона

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

и характеризующий степень нерегулярности потока, равен единице, в то время как у детерминированного потока коэффициент вариации = 0, а для большинства законов распределения 0<<1.

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

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

(6)

где Р (k, — вероятность того, что за время т в систему поступит точно k заявок; — интенсивность потока заявок.

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

Следует подчеркнуть, что распределение Пуассона дискретно. Стационарный пуассоновский поток является простейшим.

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

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

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

Рис. 2. Потоки Эрланга

Потоком Эрланга го порядка называется поток, у которого интервалы времени между моментами поступления двух последовательных заявок представляют собой сумму k независимых случайных величин, распределенных по экспоненциальному закону с параметром . Поток Эрланга получается из простейшего путем исключения (k — 1) заявок с сохранением каждой k-й заявки (рис. 2). Плотность распределения интервала времени между двумя соседними заявками в потоке Эрланга k-го порядка

(7)

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

2. Марковские модели

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

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

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

Процесс называется процессом с дискретными состояниями, если его возможные состояния z₁, z₂,... можно заранее перечислить, т. е. состояния системы принадлежат конечному множеству, и переход системы из одного состояния в другое происходит мгновенно.

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

Рис. 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 — только с одним соседним состоянием.