Основные понятия теории вероятностей, позволяющие задать времена поступления заявок и времен их обслуживания. Понятие потока событий. Типы потоков. Примеры
MU2 = ---- - интенсивность решения задач вторым процессором.
teta
По графу запишем систему линейных дифференциальных
уравнений А.Н.Колмогорова.
dP00(t)
--------- = LA*P00(t) + MU1*P10(t) + MU2*P01(t)
dt
dP10(t)
--------- = LA*P00(t) - (MU1 + LA)*P10(t) + MU2*P11(t)
dt
dP01(t)
--------- = - (LA + MU2)*P01(t) + MU1*P11(t)
dt
dP11(t)
--------- = LA*P10(t) + LA*P01(t) - (MU1 + MU2)*P11(t)
dt
P00(t) + P10(t) + P01(t) + P11(t) = 1
Пусть начальные условия заданы вектором вероятностей:
P00(0) = 1, P10(0) = P01(0) = P11(0) = 0.
Решение этой системы при заданных начальных условиях
позволяет определить вероятности состояний как функции времени.
Последние, в свою очередь, позволяют определить требуемые
характеристики вычислительной системы.
Поскольку марковский процесс, описывающий работу
вычислительной системы, является эргодическим, существует
стационарный режим, при котором вероятности состояний стремятся
к постоянным величинам.
При этом система дифференциальных уравнений Колмогорова
вырождается в систему линейных уравнений:
-LA*P00 + MU1*P10 + MU2*P01 = 0
LA*P00 - (MU1 + LA)*P10 + MU2*P11 = 0
-(LA + MU2)*P01 + MU1*P11 = 0
LA*P10 + LA*P01 - (MU1 + MU2)*Р11 = 0
P00 + P10 + P01 + P11 = 1
Выражения для вероятностей в установившемся режиме имеют
вид:
MU1*MU2*(2*LA + MU1 + MU2)
P00 = ----------------------------- * Р11;
LA**2 * (LA + MU2)
MU1
P01 = -------------- * Р11;
LA + MU2
MU2*(LA + MU1 + MU2)
P10 = ------------------------- Р11;
LA*(LA + MU2)
LA**2
P11 = ----------------------------------------------------------
MU1*MU2
LA**2 * ----------- * (2*LA+MU1+MU2)+LA*(MU1+MU2)
LA + MU2
Вероятность отказа совпадает с вероятностью состояния, в
котором оба процессора заняты, т. е. Ротк = Р11.
Коэффициенты загрузки процессоров KSIi (i = 1,2) представляют
собой вероятности пребывания соответствующих процессоров в занятом
состоянии:
KSI1 = Р10 + Р11;
KSI2 = Р01 + Р11.
Примерами потоков с ограниченным последействием являются
потоки Эрланга. Они образуются путем закономерного просеивания
простейшего потока. Под закономерным просеиванием будем понимать
такую процедуру, в результате которой безусловно исключается
некоторая последовательность событий в исходном потоке.
Если из исходного простейшего потока исключить (К - 1)
событие, а каждое К-е сохранить, то получим поток Эрланга К-го
порядка.
+-+ +-+ +-+
-|+|--+---+--+--|+|------+--+----+---|+|-+----->t
+-+ +-+ +-+
<- K-1-> <- Ti -><- K-1 ->
<------- Tk* ------->
Случайная величина Тк* интервала между соседними событиями
потока Эрланга К-го порядка представляет сумму К независимых
случайных величин, подчиненных показательному закону
распределения
k
Tk* = SUMMA Ti. Плотность распределения имеет вид:
i = 1
k-1
LA(LA*TAUk) -LA*TAUk
fk(TAUk) = -------------------- e
(K -1)!
Обычно случайную величину Tk* нормируют коэффициентом К,
т. е.
Tk*
Tkн = -----
К
Для нормированного потока Эрланга К-го порядка
1 1
M(Tkн) = -------- D(Tkн) = ----------------
LA (LA*K)**2
Таким образом, при неограниченном увеличении порядка К
нормированный поток Эрланга приближается к регулярному потоку с
1
постоянными интервалами, равными -------- .
LA
Нормированный поток Эрланга в зависимости от порядка К
позволяет получить любую степень последействия, от полного
отсутствия (К = 1) до жесткой статистической связи (К =
бесконечности). Благодаря этому реальный поток событий с
последействием можно в некоторых случаях аппроксимировать
нормированным потоком Эрланга соответствующего порядка, имеющим
примерно те же математическое ожидания и дисперсию, что находит
широкое применение при моделировании произвольных потоков.
Правила использования вероятностных характеристик
в блоках модели.
GENERATE
-----------------
Q-схема Блок-диаграмма Оператор Примечание
+-----+
+--+ LA | +--------+ GENERATE_A,B,C,D,E
|ИС+------> |A, B, С, D, E |
+--+ +-----+--------+
V
Оператор GENERATE позволяет описывать входной поток, операнды харак-
теризуют свойства входного потока транзактов. Следует иметь в виду,
что модельное время в GPSS - целое без знака 0, 1, 2, ... Следова-
тельно, все параметры закона распределения случайных интервалов меж-
ду соседними событиями в потоке, имеющие смысл времени, должны быть
с помощью масштаба времени приведены к целому формату.
Если параметры А,В - const, то оператор GENERATE описывает рав-
нономерный закон распределения длины интервала между соседними собы-
тиями в потоке.
1
--- +-------------+ А - среднее (МО) = 1 / LA
2*В | S - площадь | А >= В
0 +------+------+
А-В А А+В S = 2B*h = 1, h = 1 / (2*B)
В - может быть отличен от const и тогда он рассматривается как
модификатор, в этом случае длина интервала определяется как А*В.
С - задержка начала генерации.
D - число генерируемых транзактов (емкость источника).
---------->
Е - приоритет транзактов. Целое без знака 0, 1, 2 ...
Предположим, что распределение интервалов приходов через определенный блок GENERATE не является равномерным. Для входов транзактов в модель через блок GENERATE пользователь в этом случае выполняет два действия.
1. Определяет функцию, описывающую соответствующее распределение интервалов времени.
2. В качестве операнда А блока GENERATE определяет функцию, а операнд
В либо определяется по умолчанию, либо задается равным нулю.
При необходимости вычислить в процессе моделирования очередное значе-
ние интервала прихода в блоке GENERATE интерпретатор определяет зна-
чение операнда А путем вычисления соответствующей функции. Это зна-
чение далее непосредственно используется в качестве очередного интер-
вала времени. Все делается так, как если бы пользователь определил
равномерное распределение в блоке GENERATE со значением среднего,
равным значению функции, и с размахом, равным нулю. При нулевом зна-
чении размаха значение функции используется как бы детерминированным образом, однако, поскольку сами значения функции вычисляются некото-
рым случайным образом, значения интервалов времени также случайны.
Пример.
GENERATE_10, 2, 20, , 3 0.25 +-------+
С | |
+------+-------> t ---+---+---+----
0 20 8 10 12
Момент начала генерации A-B А A+B
ПРИМЕЧАНИЕ: Если бы операнд С отсутствовал, первый транзакт появился
бы в момент времени, определяемый операндом А (в нашем примере 10).
ADVANCE
Q-схема Блок-диаграмма Оператор Примечания