GPSS / Simulation

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	41

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

Однако исследованиями установлено, что для широкого класса ДО распределение времени ожидания можно с достаточной точностью аппроксимировать выражением вида:

P w		t 1 R e	t	R
	i		wi		,	(45)

где wi — среднее время ожидания заявок i-го типа,

R — суммарная загрузка прибора.

Очевидно, что точность этого выражения возрастает с ростом R, особенно, начиная с

R > 0.6 с отклонением вероятности P(wi t) в большую сторону, что приводит к оценкам c

запасом.

wi* R

Соответственно, P wi wi* 1 P wi wi* R e wi

Кроме того, wi зависит от ДО и поэтому, выбирая ДО, минимизирующую это время,

можно снизить вероятность превышения ограничений и, соответственно, функцию штрафа.

Определение памяти, необходимой для хранения очереди требований

Сначала вспомним, что при показательном распределении вероятность того, что в системе находится i заявок определяется выражением:

P i i 1 ,

где b . Если выразить время обслуживания b через трудоемкость: .

B

Для решения поставленной задачи необходимо минимизировать вероятность того, что в системе будет переполнение, т.е. P i l , где l — количество запросов хранимых в памяти:

l V ОП , где VОП — общий объем памяти,

V 1

V1 — объем памяти необходимый для хранения одного требования.

Откуда получаем:

				VОП	1
	V1
P i l i 1 l 1							(46)
i l 1		B

Исходя из этого условия, при заданном быстродействии можно определить требуемый объем памяти. С другой стороны, при фиксированном объеме памяти VОП данное условие — это еще один критерий повышения быстродействия обслуживающего прибора.

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	42

Сети массового обслуживания

Сетью массового обслуживания называется совокупность связанных СМО. В этом случае СМО являются элементами сети и называются узлами этой сети. Сети бывают разомкнутые и замкнутые.

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

Разомкнутые сети содержат два фиктивных узла: источник и сток заявок. При разработке модели эти два узла объединяют и называют нулевым узлом. Но при этом, 0 —интенсивность входного потока в такой сети не зависит от состояний сети и от количества заявок, уже поступивших в нее.

Классификацию РСеМО проводят:

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

2.по характеристике обслуживания заявок: экспоненциальные и неэкспоненциальные сети.

3.в зависимости от типа ДО сети бывают: приоритетные и неприоритетные.

4.по типу расчета сети различают:

РПФ-сети (РПФ — решение в форме произведения);

ЛБ-сети — сети локального баланса;

сети, допускающие точный расчет;

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

Нас в первую очередь будут интересовать РПФ-сети, т.к. они покрывают достаточно широкий круг прикладных задач, и их можно рассматривать как n независимых СМО, в

каждую из которых поступает поток заявок с интенсивностью i ( i 1, n ).

Возможность расчета данных сетей устанавливается теоремой Джексона, для которой существует две формулировки:

1)Если в однородную РСеМО, состоящую из n узлов с экспоненциальной длительностью обслуживания, поступает простейший поток событий, то, независимо от конфигурации связи, узлы данной сети можно рассматривать как независимые СМО с простейшими потоками заявок.

Состоянием сети Sj называется вектор	S j	m1 , m2 , , mn , i-ая компонента которого
определяет количество заявок в i-ом узле сети	j
			0,1,2... .
	mi

В соответствии с определением состояния существует другая формулировка теоремы Джексона:

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	43

2)В стационарном режиме вероятность состояния РСеМО может быть рассчитана как произведение вероятностей состояний СМО, составляющих сеть:

						n
P(S j ) P(m1 , m 2 , , m n ) P1 m1 P2 m 2 Pn m n Pi m i , где mi							0,	(47)
						i 1
Причем, вероятности состояний этих СМО определяются при условии, что они
функционируют независимо.
Соответственно,		величины Pi mi можно получить из формул для СМО M/M/1 и M/M/N.
Например: P(m ) m1		(1	) ,		i	b , если узел представляет собой одноканальную СМО.
i	i	i				i i

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

1)входной поток должен быть простейшим;

2)сеть должна быть однородной;

3)длительность обслуживания во всех узлах сети должна иметь экспоненциальное распределение.

Параметры РСеМО

1)n — количество узлов

2)0 — интенсивность потока заявок

3)Ni — канальность узлов

4)bi — средняя длительность обслуживания заявок в i-ом узле.

5)P = [Pij] — матрица вероятности передач, имеющая ранг n + 1 за счет 0-го узла. Pij —

вероятность того, что заявка, покидающая i-ю СМО, поступит в j-ю систему:

	p00		. . .	p0 n
						n
P Pij	pi0		. . .	pin		, причем Pij	1 , i 1, n
						j 1
			. . .
	pn0			pnn

Т.о. матрица описывает топологию сети и маршрут заявок.

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

R j N j для Nj-канальной СМО.

Характеристики СеМО

Характеристики СеМО делятся на узловые и сетевые.

Узловые характеристики:

1. Интенсивность потока заявок входящих в i-ый узел i.

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	44

2.Коэффициент передачи i-го узла: i i 0 . Физический смысл этой характеристики — среднее число посещений заявкой i-ой СМО за время ее пребывания в разомкнутой сети 1.

3.Загрузка i i bi и коэффициент простоя i 1 i i-го узла. Иначе, с учетом п.2 —

i i 0 bi .

4.Средняя длина очереди к обслуживающему прибору li и число требований в этой системе

mi li i .

5.Времена ожидания заявок wi и пребывания заявок в i-ом узле ui wi bi .

Сетевые характеристики:

1.Суммарная длина очередей L li .

i 1n

n

2. Суммарное число заявок во всей сети M mi .

i 1

3.Суммарное время ожидания в очереди при условии, что заявка попадает в i-ую систему i

n

число раз W i wi .

i 1

4.Полное время пребывания заявок в сети U iui .

i 1n

Методика расчета РСеМО

1. Определение интенсивностей входных потоков i в i-ые узлы.

Будем рассматривать только установившийся режим. В этом случае число заявок,

поступивших в i-ую систему за некоторый промежуток времени равно числу заявок покинувших эту систему. Т.е. интенсивности входных и выходных потоков i-ой системы за определенный промежуток времени равны между собой. Интенсивность потока, входящего в i-ую систему равна сумме интенсивностей потоков поступающих в нее из других СМО (т.к.

n

мы рассматриваем только ППС): i ji .

j 0

Поскольку требования из j-ой системы в i-ую поступают с вероятностью Pji, то

n

интенсивность потока этих требований равна Pji j. В силу этого интенсивность i Pji j .

j 0

Это выражение, в свою очередь, можно развернуть в систему из (n+1)-го

1 Для замкнутой сети это будет число посещений между двумя последовательными посещениями нулевого

узла

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	45

алгебраического уравнения:

				P				P P
			0	00			0	10	1	n0		n
1				P01 0				P11 1 Pn1 n					(48)
				P				P P
		n				0					n
				0 n				1n	1	nn

2.Решая эту систему, можно определить соотношение потоков в виде i i 0 . Откуда получаем коэффициенты передач i, причем 0 = 11. Зная для РСеМО входную интенсивность 0, получаем i.

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

Nj-канальной СМО (где Nj = 1, 2, …) i N j 1 .

Подставляя выражение для j, получим

λ j bj

1 .

N j

Но

, следовательно,

j 0 bj

1 .

j

j

0

N j

Откуда следует, что

N j

0

, где j 1, n .

j b j

n

N j

Иначе говоря, необходимо, чтобы выполнялось условие 0

MIN

.

j 1

j bj

3.На основе полученных значений рассчитываются узловые характеристики. Зная их и коэффициенты передач, можно на …

4.–м шаге определить сетевые характеристики

0								1							P10
										1
								2					P12
				2
								3					P13
				3

Рис. 34. Пример разомкнутой сети массового обслуживания.

Пример.

Составляем матрицу вероятности переходов:

	0	1	0	0
P	p10	0	p12	p13	,
ij	0	1	0	0
	0	1	0	0

на основании которой строим уравнения:

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

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	46

												1								1
																	,
										1						0		1
0 1 p10												p10									p10
												p									p
	1			0		21							12									12
								3 . Откуда,									,
										2						0		2
												p10									p10
	2		1		p
					12
					p							p13									p13
	3		1
					13					3						0	,	3
												p	10								p	10

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

характеристики этой системы.

В такой модели количество узлов в сети соответствует количеству объектов реальной моделируемой системы (станков, компьютеров, клерков и пр.). Задержки обслуживания в узлах bi соответствуют задержкам при использовании реальных ресурсов. Функционирование такой системы отображается в виде потока циркулирующих заявок.

Достоинством модели на основе РСеМО является простота расчета и возможность получения этой модели в явной аналитической форме.

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

Замкнутые СеМО

Замкнутой называется сеть, в которой отсутствует как внешний источник заявок, так и их

P12

сток. Количество заявок, циркулирующих

0

2

1

в сети, всегда постоянно, и эта величина

1

P13

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

3

M

сети.

Рис. 35. Замкнутая сеть массового обслуживания.

Из постоянства М следует, что

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

2)в ЗСеМО в отличие от РСеМО всегда существует стационарный режим.

Кроме того, при анализе ЗСеМО используется такое известное из теории графов понятие,

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

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

Как и для РСеМО j-ым состоянием замкнутой сети будет вектор Sj = (m1, m2, …, mn) где

mi 0 ,M причем, сумма по всем mi:

n
mi M .	(49)

i 1

Т.к. число состояний конечно, то обозначив множество этих состояний через A(M,n) и в

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	47

силу равенства (49), можно записать, что мощность множества равна числу различных распределений M заявок по n системам и соответствует числу сочетаний с повторениями:

A M , n C M	M n 1 !
M n 1	M ! n 1 !

Таким образом, количество состояний ЗСеМО не зависит от конфигурации связей, а

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

Для ЗСеМО также справедлива теорема Джексона, т.е. вероятности состояний сети

выражаются через вероятности состояний ее СМО.

		n	mi
		Pi
P(S	)	i 1		,		(50)
j		G
			n		mi	— нормирующая константа.
где G		Pi
		A( M ,n )	i 1

Появление нормирующей константы в теореме Джексона для ЗСеМО связанно с исключением из бесконечного числа состояний РСеМО тех, которые не являются состояниями ЗСеМО.

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

n

т.е. P 0, ,0 1 i для РСеМО, то для ЗСеМО — P 0, ,0 0 .

i 1

Вероятность состояния i-ой СМО P m

X

i

m

mi P

, где

i

i

i

i 0i

1,

если N i

1

т.е. СМО M/M/ 1

1

X i mi

,

при mi

N i

mi

!

если N i

1

т.е. СМО M/M/N

(51)

1

!N mi N i ,

N

i

при mi

N i

i

Poi — вероятность того, что в i-ой системе отсутствуют заявки:

	1 i ,
P0 i		mi
	N i 1
		i
		mi !
	mi 0

							N i 1
	iN i					1
							,N i	(52)
								1
	1
N i !			i	N
					i

i – загрузка прибора i-го узла, равная ibi. Но i = i 0, следовательно, i = 0 ibi.

n	n
При этом, за 0 принимается значение, равное MAX i	. Кроме того, m0 i	M0 .
i 1	i 0

Эта величина и величины P0i не зависят от индекса суммирования A(M,n) и могут быть вынесены за знаки суммы и произведения:

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

	Е.В.Малахов. Имитационное моделирование. Конспект лекций.								48
		n				n		i bi mi
	M0 Po1 P0 n X i (mi ) i bi mi					X i mi
P (S j )		i 1				i 1			(53)
			n				n	i bi mi
	M0 Po1 P0 n		X i (mi ) i bi	mi			X i mi
		A M ,n	i 1			A M ,n	i 1

Данное выражение не зависит от интенсивностей i, но зависит от их отношения к 0.

Итак, формула, которая следует из теоремы Джексона для ЗСеМО, и позволяет рассчитывать все характеристики сети через вероятности ее состояний.

	Пример.
	Пусть М=3, тогда													P12				2
						0				1										2
1) A(M , n) C33 3 1 C53 10
												1								b
														P13						2
2)					1							b1						3		3
		0		1
1
2	P12 1 P12 0 2 P12								M											b3
2	P13 0 3 P13					Рис. 36. Пример замкнутой сети массового обслуживания.

3)Загрузка приборов — это суммы вероятностей тех состояний сети, при которых в соответствующих СМО не менее одной заявки (т.к. все СМО — M/M/1)

	j	1	2	3	P * S j													P S j P* S j G
	1	0	0	3	3 b3 3													P(1)
	2	0	1	2		2	b	2				3		b			2	P(2)
																3
	3	0	2	1		2	b	2	2						3	b		P(3)
																	3
	4	0	3	0	b 3													P(4)
						2	2
	5	1	1	1	1 b1 2 b2 3 b3													P(5)
	6	1	2	0		1	b					2	b				2	P(6)
							1									2
	7	1	0	2		1	b					3	b			3	2	P(7)
							1
	8	2	0	1		1	b		2					3		b		P(8)
							1										3
	9	2	1	0	1 b1 2						2 b2							P(9)
	10	3	0	0	1 b1 3													P(10)
			10						4
Следовательно,		1	P(i ) 1 P(i ) (вероятность простоя 1-го прибора).
			i 5					i 1

Аналогично определяется 2, 3.

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	49

Но 1 = 1b1, откуда 1 1 0 . Соответственно получаем 2 и 3. b1

Длина очереди в первой СМО определяется из следующих соображений:

в первых 4-х состояниях число заявок в этой СМО равно 0, как и число заявок в очереди;

в 5-м, 6-м и 7-м состояниях в первой СМО находится одно требование, и то — на

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

	7
вероятность этого факта равна 0 P (i ) ;
	i 1
		9
вероятность того, что в очереди одна заявка равна 1 P (i ) ;
		i 8
вероятность того, что в очереди две заявки —		2 P 10 .
7	9
Следовательно, l1 0 P(i) 1 P(i) 2 P 10 .
i 1	i 8

Теперь, анализируя этот пример, рассмотрим общий подход к расчету характеристик ЗСеМО через вероятности ее состояний:

1.Загрузка одной СМО определяется как 1 минус вероятность того, что система свободна от обслуживания заявок: i 1 P mi 0 . Как мы видели из примера, эта вероятность равна

	сумме по всем состояниям	из множества			A(M,n)			для которых mi = 0: i	1	P S j .
										A M ,n
										mi 0
	Данные выкладки (в нашем примере и не рассматривались), можно аппроксимировать и на
	Ni-канальные СМО (M/M/N):
	N i 1		M
	i k P mi k N i P mi k ,
	k 1		k N i
где
k — число заявок в i-ом узле,
P mi k — суммарная вероятность того, что в i-ом узле находится k заявок, равная										P S j ,
									A M ,n
									mi k
первая часть выражения отвечает за условие k < Ni, вторая — за k Ni.
		M
2.	Длины очередей (см. пример)	li k Ni		P mi			k
		k Ni 1
					M		mi	k
3.	Среднее количество заявок в i-ом узле mi		kP
				k 1
4.	Время ожидания в очереди	i-й СМО	w		li		,	а среднее время пребывания в ней
				i		i

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	50

ui mi i .

Для проверки полученных величин можно воспользоваться соотношением:

n	n
i	li M
i 1	i 1

Для ЗСеМО понятие времени пребывания в сети не имеет смысла. Вместо него используется понятие времени цикла U, т.е. длины промежутка времени между двумя последовательными посещениями одной и той же заявкой i-ой СМО:

	n	n	i		mi		1	n		M
	U i ui							mi			(54)
			0				0			0
	i 1	i 1			i			i 1

Это выражение представляет собой формулу Литтла для ЗСеМО.

Недостатком описанного метода является то, что, во-первых, не получено решение в явной аналитической форме и, во-вторых, его большая трудоемкость уже при n > 3 1.

Поэтому предлагались алгоритмы, упрощающие расчет и легко реализуемые на компьютере. Один из них — алгоритм Бьюзена.

Алгоритм Бьюзена

Пусть в сети все узлы одноканальные: Ni = 1, тогда:

1)Xi(mi) = 1;

2)ibi = di.

Всоответствии с этим формула теоремы Джексона примет вид:

		n
		dimi
P(S j	) P(m1, ,mn )	i 1
			n
		dimi
		A M,n	i 1

	Обозначив через G M	n
	нормализую щую константу,	mi
	равную сумме в знаменателе di
		i 1	(55)
		G M

Для рекуррентного определения констант G(1), …, G(M) введем вспомогательную функцию g(r,j) 2. Причем, g M , n G M .

j
Итак, g r, j dimi
	, где r 0,M ,			j 1, n . Разобьем эту сумму на две:
A r, j i 1

1 Есть информация, что при первых расчетах, использующих такой подход, анализировались характеристики ЭВМ с 1 центральным процессором, 4 каналами ввода/вывода и 16 накопителями на магнитных дисках. Т.е. n = 21, на ввод/вывод, соответственно, могло быть направлено 16 задач (заявок). Таким образом,

A M,n C 16	C 16	7 109 . При быстродействии ЭВМ, на которой проводился расчет, В = 105, он занял
16 21 1	36

20 часов.

2 Запись означает, что сеть содержит r заявок в j узлах.

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.