Московский Государственный Инженерно-
Физический Институт
(Технический Университет)
Кафедра «Компьютерные системы и технологии»
Реферат на тему:
"Основные понятия теории вероятностей, позволяющие задать времена поступления заявок и времен их обслуживания. Понятие потока событий. Типы потоков. Правила использования вероятностных характеристик в блоках модели. Примеры."
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**2P11 = ---------------------------------------------------------- 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_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 распределением
Правила использования вероятностных характеристик
в блоках модели.
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/