GPSS / Simulation

Е.В.Малахов. Имитационное моделирование. Конспект лекций.							51
j	j	это в свою		j 1		j
		очередь
g r,j d imi	dimi			d imi	d j	dimi , где
A r,j i 1	A r,j i 1		A r , j 1	i 1		A r 1, j i 1
m j 0	m j 0

j

dimi — сумма по тем состояниям множества A, для которых mj = 0,

A r,j i 1 m j 0

j
dimi — сумма по тем состояниям множества A, для которых mj > 0.
A r,j i 1
m j 0
Используя вспомогательную функцию, запишем, что
g r, j g r, j 1 d j	g r 1, j .	(56)

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

Начальными условиями для расчета будут следующие: для r = 0 — g 0, j 1 ; для j = 0 — g r,0 0 ; для j = 1 — g r,1 d1r .

При таких условиях формулу (56) иллюстрирует следующая таблица:

	Количество			Номер узла (j)
	заявок (r)
		1	…	j	…		n
	0	1	…	1	…		1
	1	g(1,1) = d1	…	g 1, j g 1, j 1 d j	…	g 1, n
						g 1, n	1 d n
	r	g r,1 d r	…	g r, j	…	g r, n
				g r, j 1 d j g r 1, j		g r, n 1 d n		g r 1, n
		1
						....
	M	g M ,1 d M	…	g M , j	…	g M , n
				g M , j 1 d j g M 1, j		g M , n 1 d n		g M 1, n
		1

Алгоритм расчета нормализующих констант:

1.Заполняется нулевая строка матрицы элементами равными 1.

2.Заполняется первый столбец элементами g r,1 d1r .

3.Все остальные элементы, включая последний определяются суммой величины g(r,j-1),

стоящей в строке слева, и величины g(r-1,j), стоящей в столбце выше, помноженной на значение dj. Расчет заканчивается вычислением величины g(M,n), равной требуемой

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

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

52

нормализующей константе G(M).

Далее. Пусть Pi mi

k — вероятность того, что в i-ом узле находится не меньше k

требований.

n

d mj

j

k

n

m j

A M ,n

j 1

d i

d j

G M k

P (m

k )

mi k

A

M k ,n

j 1

d

k

.

(57)

G M

G M

G M

i

i

i

Тогда вероятность того, что в i-й СМО находится ровно k заявок, определится как

разность:

в соответствии с

G M k d k 1G M k 1

предыдущим выражением d k

Pi (mi k) Pi (mi k) Pi (mi

k 1 )

i

i

.

G M

Итак, P m

k d k

G M k di

G M k 1

.

(58)

i

i

i

G M

Откуда получаем, что при

k 1 загрузка i-го узла

d

G M 1

задается входным

i

i

G M

потоком с интенсивностью

G M 1

.

i

i

G M

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

РСеМО позволяют рассчитывать только характеристики последнего типа.

Примеры характеристик:

Пропускная способность (продуктивность)	Время реакции
Производительность устройства	время выполнения операций
[операций/единицу времени]	[единицы времени]
Системная производительность	время реакции системы
[задач/единицу времени] 1	[единицы времени]
Пропускная способность	время передачи пакета
[количество пакетов/сек]	[мс]

Недостаток этих моделей заключается в том, что если РСеМО дают возможность получить решение в явной аналитической форме, то ЗСеМО допускают только использование

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

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

	Е.В.Малахов. Имитационное моделирование. Конспект лекций.									53
численных процедур. Хотя, необходимо отметить, что использование эффективных численных
алгоритмов типа алгоритма Бьюзена позволяет снизить трудоемкость расчета ЗСеМО до уровня
аналитических моделей.
		Применение моделей СеМО
		Двухфазная ЗСеМО
Модели	такого типа	могут использоваться, например, для анализа					вычислительной
			системы		коллективного				доступа
		2	(многотерминального			комплекса).			Или	в
1		1	задаче	об	автопредприятии		и	нескольких
	1
			пунктах		использования		а/м		(складах,
	a	N	арендаторах и т.п.)
M		b	Здесь		— интенсивность				движения
Рис. 37. Двухфазная замкнутая сеть массового			заявок	определяет		количество			запросов
	обслуживания.
			пользователей в единицу времени;

a — интервал обслуживания первой фазы; b — интервал обслуживания второй фазы;

M — количество заявок в сети;

N — количество пользователей.

Наиболее простым расчет будет в случае, если принять M = N. Например, для терминального комплекса — это количество активных пользователей, тогда состояния сети

P(m1,m2) будут входить в множество A(M,2), где m1 + m2 = M, и определяется как

P m1 , m 2			M ! m1		P 0, M ,				(59)
			M m1	!
					M			m1		1
где a		,	P 0, M			M !
	b
					m1 0 M m1				!

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

определяет его загрузку: 1 1 P 0, M . Среднее количество заявок m1 находящихся в этом

		M		1	P 0, M
	узле равно:	m1 P m1 , m 2	M			. А среднее	число		пользователей,
		m1 0
	"обдумывающих" ответ, или автомашин, находящихся в эксплуатации m							1 P(0, M )		.
							2
	Загрузка	канала второго	прибора		равна доле времени, в		течении		которого заявка

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

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

задерживается в нем: 2 m 2 1 P 0, M .

M M

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

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

b

. Из двух последних выражений получим: U

Ma

a

.

i

b U 1

1

1 P 0, M

Минимизировать

это время

мы можем

не только

за счет

1

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

1

числа

его

каналов

(количества

бригад, занятых

подготовкой

автомашин, или использованием мультипроцессорной системы):

N

В этом случае мы должны обеспечить отсутствие очереди к

a

данному прибору при условии его максимальной загрузки.

тогда

Рис. 38. Использование

мультироцессорной системы

будет соответствовать комплексной производительности данной

в двухфазной сети.

системы.

Подобные модели широко используются

Канал передачи

для анализа информационных систем и

вычислительных сетей различного назначения.

Станция

Станция

Станция

Например, сети с моноканалом в качестве

1

1

1

среды передачи пакетов (типа общей шины). В

Рис. 39. Сеть ЭВМ типа "общая шина".

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

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

формально неразличимы.

Если теперь рассмотреть фрагмент более

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

передаваемого пакета (хотя бы для определения

Маршру-

Маршру-

тизатор 2

тизатор 1

адреса), то

очевидно,

что такая модель уже

не

подходит. Тем более, если каждый узел еще имеет

ЛВС 1

ЛВС 2

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

Маршру-

переходим к более совершенной модели:

тизатор N

ЛВС N

Рис. 40. Фрагмент многоуровневой сети ЭВМ смешанной топологии.

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

Е.В.Малахов. Имитационное моделирование. Конспект лекций.			55
	P1	2.1
		b1
1
a	PN	2.N
		bN
Рис. 41. Модель сети ЭВМ в виде двухфазной ЗСеМО.

где a — время передачи;

bi — время подготовки или обработки запроса абонентом.

Если же у нас существуют различные маршруты передачи пакетов, то и первый узел можно представить в виде нескольких СМО.

Расчет этих моделей производится по общим алгоритмам, рассмотренным выше.

Интенсивность движения заявок при этом соответствует пропускной способности или производительности сети.

Трехфазная модель.

Ее мы рассмотрим тоже на примере вычислительной сети. В предыдущем примере рассматривался только фрагмент сети (маршрутизаторы, host-машины или сервера). Для того,

чтобы представить обмен между станциями различных локальных сетей (ЛВС) (типа университетской сети) модель предыдущего примера необходимо расширить:

			P1	3.1
	P1			c11
		2.1
		b1	PN	3.N
				c1N
1
			P1
a				K.1
	PN			cK1
		2.N
		bN	PN	K.N
				cKN
Рис. 42. Трехфазная модель замкнутой сети массового обслуживания.

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

Все рассмотренные модели относятся к классу циклических сетей, СМО которых соединены последовательно и которые не имеют внутренних циклов.

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

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

Преобразования сетей.

Вернемся к примеру двухфазной сети такого

P

1-P

система

вида:

1

Нас

интересовало в

этой модели

время

S

реакции системы, т.е.

время пребывания заявок в

узле S,

который

мы

рассматривали

как

N

Рис. 43. Пример двухфазной ЗСеМО с

одноканальную СМО.

Однако под узлом

S мы

ветвлением.

можем понимать и некую сложную систему, представив которую также в виде сети, получим аналогичную модель, только на более высоком уровне детализации. Узел S может представлять сеть, рассмотренную в разделе РСеМО, и может быть показан в виде трехфазной сети. В

результате будет получена четырехфазная сеть и т.п.

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

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

толерантных (подобных) СеМО отличается на допустимую величину.

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

Соответственно, характеристики этих СМО и характеристики сети в целом можно рассчитывать как на основе вероятностей состояний этих систем, так и на основе вероятностей состояний сети в целом.

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

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

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

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

	Е.В.Малахов. Имитационное моделирование. Конспект лекций.		57
0
1
b1		2
2		1
1	1		3
	d1	N	d3
N	0	d2
b2
3
b3

Рис. 44. Преобразование ветвящейся замкнутой сети массового обслуживания в циклическую.

При этом, j-й системе исходной сети со средним временем обслуживания bj, в которую поступает поток заявок с интенсивностью j, ставится в соответствие система с входным потоком заявок интенсивностью 0, которые обслуживаются за среднее время dj = jbj.

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

Дальнейшее упрощение возможно в том случае, если диапазон или разброс значений dj

достаточно велик.

					n
Тогда из сети можно удалить j-й узел, для которого выполняется условие d j MIN d i
					i 1
	d j	n	d
(или		MIN		i	для Nj-канальных СМО). В этом случае мы получим сеть, толерантную
	N j	i 1	Ni

данной, безразмерные характеристики которой, как и характеристики оставшихся СМО, будут мало отличаться от характеристик исходной сети и ее узлов. Мы рассмотрели первый вариант

преобразований.

2. -й вариант — "Развал" сети. Преобразование ЗСеМО в РСеМО, толерантную ей.

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

Т.к. загрузка систем различна, то в одних узлах будет скапливаться больше заявок, в

других — меньше. Наибольшее число заявок будет находиться в "узком месте" сети, или в СМО, загрузка которой максимальна.

В таком узле при M, стремящемся к , j будет стремиться 1 (или к Nj), а интенсивность потока на выходе, соответственно, будет стремиться N j b j .

Таким образом, ЗСеМО становится подобной РСеМО, в которой рассматриваемый узел

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

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

играет роль нулевого узла. Условием толерантности таких сетей будет выполнение неравенства:

n	j
MAX
j 1		1 1, для всех i	1, N	, i j .	(60)
j
	j

На практике, при М>20 это условие становится более "мягким": вместо знака '>>'

используется знак '>'.

Агрегирование СМО.

3-й метод — метод агрегирования заключается в преобразовании исходной сети к некоторой более простой эквивалентной за счет исключения из нее части узлов (СМО), и

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

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

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

Метод агрегирования основывается на теореме Нортона, которая гласит: предельное распределение числа сообщений в i–м узле исходной сети совпадает с соответствующим распределением эквивалентной сети, если интенсивность обслуживания эквивалентного узла э

равна интенсивности поступления заявок в i-й узел исходной сети i, при условии, что bi

принимается равным 0.

Метод состоит из следующих этапов:

1.В СеМО выделяется подсеть Q.

2.В выделенной подсети замыкается накоротко вход и выход.

3.В замкнутой подсети рассчитывается вектор интенсивности (t), зависящий от числа заявок

вэтом узле t 1, M .

4.В исходной сети подсеть Q заменяется эквивалентным узлом, интенсивность обслуживания

вкотором равна интенсивности циркуляции заявок в выделенной подсети (t).

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

1 Знак '>>' ("намного больше") означает "по крайней мере, на порядок".

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

	Е.В.Малахов. Имитационное моделирование. Конспект лекций.						59
	Рассмотрим двухфазную циклическую				Q	P1
	модель.						2.1
	Выделим из неё подсеть и выполним						b1
					1
	замену.
						PN
	Состояния сети	можно поставить		в	a		2.N
	зависимость от числа заявок в первом узле.				M		bN
	Число состояний:
	A C M	C M	M 1
	M n 1	M 1

Граф состояний совпадает с графом

марковского	процесса		для		системы
M/M/1/ /K, для которой вероятности
состояний	определяются				как
P i 1 P i , где				— загрузка

прибора.

	1	2
M	= 1/a	(i)
	(i) = ( (1), …, (M))

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

			(M-i)
(M)	(M-1) (M-i+1)				(1)
1	2		i		M

Рис. 46. Граф марковского процесса преобразованной сети.

Вданном случае интенсивность входного потока меняется в зависимости от числа заявок

вэквивалентном узле. Поэтому обозначим через (i) отношение i . Тогда, в соответствии с

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

P1 M P0

P1 M P0

P M 1 P

2

1

M M i P

M i P

P

P

i 1

0

i 1

i

M 1 P

1 P

P

P

M

0

M

M 1

М

Из нормирующего условия Pi

1 получим выражение для P0:

i 0

M

M

1

0

0

(61)

P

1 M M M 1 M 1 1 или P

1

j

i 1

j i

Загрузка первого узла при этом: 1 1 P0 .

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

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

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

1

N b

Рис. 47. Вариант обслуживающего прибора подсети.

Если бы эта подсеть представляла собой одну N-канальную СМО со средним временем обслуживания заявок в каналах, равным b, то при M N

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

интенсивность		обслуживания				заявок	в	эквивалентном	узле,
i MIN N , i
	b	, где	i 1, M — число заявок в эквивалентном узле. Т.е.

при i = 1, 1 1

b

; при i = 2, 1

2

и т.д.

b

При рассмотрении подсети Q,

выделенной в нашем

P1

2.1

примере,

введем

дополнительные

ограничения:

узлы

b1

подсети должны быть равнозагружены, т.е. i const, и,

PN

соответственно, Pi bi есть

также величины

постоянные.

2.N

bN

При равнозагруженных узлах, вероятности состояний

(i)

сети равны.

Из всего пространства

состояний

подсети

Рис. 48. "Замыкание" подсети.

A(i,N) выделим подмножество A1

тех

состояний,

при

которых

в

j–м

узле

находится

хотя

бы

1

заявка.

Очевидно,

это подмножество

A A i, N

A i, N 1

C i

C i

C i 1

.

1

i N 1

i N 2

i N 2

Тогда загрузка j–го узла j

как вероятность того, что в j–м узле есть хотя бы одна заявка,

определится через соотношение:

A`1, j

Ci 1

i

i N 2

(62)

j

A i, N

i N 1

Ci

i N 1

С другой стороны, в силу предположения о

равнозагруженности

узлов, справедливо

N

равенство j N j .

В

правую

часть

этого равенства

подставим

полученное выше

j 1

выражение, а в левую — формулу, которая соответствует определению загрузки прибора:

N

Ni

j

j bj

. В результате получим j b j

.

i N

j 1

1

N

Ni

Но j

Pj i . Следовательно, ( (i) выносим за знак суммы): i Pj b j

.

i N 1

j 1

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

Ni

1

N

, где b Pj b j (сумма констант).

i N 1

b

j 1

Допущения в аналитических моделях на основе СеМО

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

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