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

Московский Государственный Инженерно-

Физический Институт

(Технический Университет)

Кафедра «Компьютерные системы и технологии»

Реферат на тему:

"Основные понятия теории вероятностей, позволяющие задать времена

поступления заявок и времен их обслуживания. Понятие потока событий. Типы

потоков. Правила использования вероятностных характеристик в блоках модели.

Примеры."

2002 г

Основные понятия теории вероятностей, позволяющие задать

времена поступления заявок и времен их обслуживания.

Каждая система массового обслуживания обладает определенной

структурой, характеризующейся совокупностью параметров. Основным

компонентом структуры СМО являются каналы обслуживания.

В зависимости от числа каналов различают одноканальные и

многоканальные СМО. В свою очередь, многоканальные СМО могут

содержать одинаковые и различные по производительности каналы

обслуживания.

Производительность канала обслуживания обратна длительности

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

каналу обслуживания для обслуживания заявки. В общем случае это

случайная величина с функцией распределения F(TAUоб), плотностью

___

распределения f(TAUоб) и математическим ожиданием TAUоб. Типы

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

математическими ожиданиями при одинаковых законах распределения.

При этом принимается допущение о независимости длительностей

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

для большинства реальных систем. Наряду с математическим

ожиданием длительности обслуживания используется понятие

___

интенсивности потока обслуживания MU = 1 / TAUоб - величины,

обратной средней длительности обслуживания и характеризующей

количество заявок, которое может быть обслужено в единицу

времени постоянно загруженным каналом обслуживания. Наибольшее

число результатов получено для длительности обслуживания с

экспоненциальной плотностью распределения.

- MU*TAUоб

f(TAUоб) = MU * е

Если в момент появления заявки на входе СМО хотя бы один канал

свободен от обслуживания, ее обслуживание может быть начато

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

заявка застает СМО полностью загруженной, то есть когда все m

каналов обслуживания заняты обслуживанием. В этом случае начало

обслуживания задерживается, заявка может занять место в

соответствующей очереди. Таким образом, вторым важным компонентом

структуры СМО является очередь, параметром которой является

число мест в очереди n. В приоритетных системах общая очередь

может быть разделена на несколько очередей по числу различаемых

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

___

число мест ni, i = 1,N. На число мест в очереди может быть

наложено ограничение, это может быть сделано как для каждой

очереди в отдельности, так и для всей совокупности очередей в

целом. При этом возможны конфликтные ситуации, решением которых

может быть отказ системы принять заявку.

В зависимости от числа мест в очереди различают СМО с

отказами, и, соответственно, СМО без отказов. В СМО с отказами

число мест в очереди конечно и вследствие вероятностного

характера как входящего потока, так и процессов обслуживания,

существует ненулевая вероятность того, что поступившая на вход

СМО заявка застанет все каналы занятыми обслуживанием и все

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

есть она получит отказ. В СМО без отказов заявка либо сразу

назначается на обслуживание, если в момент ее поступления

свободен хотя бы один канал обслуживания, либо безусловно

принимается в очередь на обслуживание.

Потоки событий. Типы потоков

Переход системы в некоторое состояние Si называется

событием. В процессе работы система неоднократно может

возвращаться в состояние Si. Последовательность таких

однородных событий образует поток событий Si', Si", ... .

Поток событий удобно отображать в виде отметок на оси

времени, соответствующих моментам наступления событий.

T1 T2 Ti

--+----+--+---+--+-----+---------> t

0

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

поодиночке.

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

регулярным или детерминированным и полностью характеризуется

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

поток называется случайным и характеризуется совместным законом

распределения системы случайных величин (Т1, Т2, ....., Тn).

На практике наиболее часто приходится иметь дело с

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

----

событиями Ti (i = 1, n) - непрерывные случайные величины. Такой

случайный поток характеризуется многомерной плотностью вероят-

ности f(TAU1, TAU2,......,TAUn), где TAUi - конкретные значения

случайных величин Тi.

Поток назывется стационарным, если его характеристики не

изменяются во времени. Вероятность попадания того или иного числа

m событий на участок оси времени t,t+TAU зависит только от TAU

и не зависит от t. Интенсивность или плотность потока событий,

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

LA = const.

В узком смысле стационарность означает независимость плотно-

сти вероятности f(TAU1, TAU2,......,TAUn) от выбора начала отсчета.

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

называется потоком с последействием, ибо для любого момента

времени последующее течение потока находится в вероятностной

зависимости от предыдущего.

Если случайные величины Ti являются независимыми, то

случайный поток называется потоком с ограниченным

последействием и для него справедливо:

f(TAU1, TAU2,......,TAUn) = f1(TAU1)*f2(TAU2)*.......*fn(TAUn).

Случайный поток событий называется потоком без

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

число событий, попадающих на один из них, не зависит от того,

сколько событий попало на другие участки. Условие отсутствия

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

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

fi(TAUi) = f(TAUi), i=1,2,....,n

Поток называется пуассоновским, если число m событий потока,

попадающих на участок TAU, распределено по закону Пуассона

m -a

pm = (a / m!) * e

где а - среднее число событий, попадающих на участок TAU, равное

для стационарного потока a = LA*TAU.

Определим функцию распределения длины интервала T в стационар-

ном пуассоновском потоке

F(TAU) = P(T < TAU)

Выразим F(TAU) через вероятность P(T >= TAU)= F0(TAU) того,

что в интервал TAU не попадает ни одно из событий:

0 -a -a

F(TAU) = 1 - F0(TAU) = 1 - p0 = 1 - a /0! * e = 1 - e

Для стационарного пуассоновского потока справедливо:

-LA*TAU -LA*TAU

F(TAU) = 1 - e , f(TAU) = LA*e ,

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

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

1

M(Ti) = SIGMA(Ti) = ------ .

LA

где LA - интенсивность потока, характеризующая среднее

число событий в единицу времени

1

LA = ------- - величина, обратная среднему времени

M(Ti)

между событиями.

Cтационарный пуассоновский поток является примером случайно-

Го потока без последействия. Для него интервал времени от нача-

ла отсчета до наступления первого события представляет собой неп-

рерывную случайную величину T1, распределенную по экспоненциаль-

ному закону с функцией плотности распределения

-LA*TAU1

f1(TAU1) = LA*e = f(TAU1) = f(TAUi) = f(TAU),

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

Стационарный пуассоновский поток событий, обладающий свойствами

ординарности, стационарности и отсутствия последействия, называется

простейшим потоком.

Если процесс переходов в системе происходит под

воздействием простейшего потока, то такой процесс является

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

НМЦ совпвдает с интенсивностью потока переходов LA.

Пример.

Двухпроцессорная вычислительная система предназначена для

обработки простейшего потока задач, поступающих с интенсивностью

LA. Производительность процесоров, соответственно, равны B1

и B2, причем B1 > B2. Трудоемкость задач представляет случайную

величину со средним значением teta.

Задача в первую очередь принимается на обслуживание

процессором, имеющим большую производительность. Если оба

процессора заняты, пользователь получает отказ.

Определить в установившемся режиме вероятность отказа Ротк,

коэффициенты загрузки процессоров KSI1, KSI2.

Рассмотрим возможные состояния системы, которые

определяются состояниями процессоров:

S00 - оба процессора простаивают;

S10 - первый процессор занят решением задач, второй

простаивает;

S01 - второй процессор занят, первый простаивает;

S11 - оба процессора заняты решением задач.

Граф функционирования системы имеет вид:

+-----+ LA

MU2 | S00 +-------------+

+-------->| |<----------+ |

| +-----+ MU1 | |

| | V

+--+--+ +-+---+

| S01 | | S10 |

| | | |

+---+-+ +-+---+

^ | | ^

| | LA +-----+ LA | |

| +-------->| S11 |<---------+ |

+-----------| +------------+

MU1 +-----+ MU2

B1

Здесь MU1 = ---- - интенсивность решения задач первым

teta

процессором;

B2

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-схема Блок-диаграмма Оператор Примечания

+---+ |

-->| K |--> V ADVANCE A,B задержка на

+---+ +-------+ случайное время

Активность, | A, B | со средним зна-

имеющая слу- +---+---+ чением А = 1/LA

чайную дли- | и равномерным

тельность V распределением

Блок ADVANCE задерживает продвижение транзакта на заданный интервал

модельного времени.

А-Средний интервал времени. Обязателен. Операнд должен быть именем,

константой, СЧА либо СЧА* параметр.

В-половина временного интервала либо модификатор-функция.

Необязателен. Операнд должен быть пустым, положительной константой, СЧА

либо СЧА* параметр.

Пример. ADVANCE 100,50

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

между 50 и 150 включительно (т.е. 100 плюс-минус 50) и задерживает

вошедший транзакт на данный интервал модельного времени.

Источники:

1. Шрайбер Т. Дж. Моделирование на GPSS.

2. Феррари Д. Оценка производительности вычислительных систем.

3. http://gpss-forum.narod.ru/

4. http://yevgeny.nm.ru/

5. http://www.gpss.ru/