GPSS / Simulation

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

Конспект лекций
по спецкурсу “Имитационное моделирование”
Содержание
Элементы теории массового обслуживания ...............................................................................	3
Системы массового обслуживания (СМО) ..................................................................................	3
Дисциплины и режимы обслуживания заявок ........................................................................	3
Параметры и характеристики СМО .........................................................................................	4
Сети массового обслуживания (СеМО) .......................................................................................	4
Параметры и характеристики разомкнутых сетей ..................................................................	5
Параметры и характеристики замкнутых сетей ......................................................................	5
Потоки событий..............................................................................................................................	5
Свойства и характеристики потоков событий.........................................................................	5
Закон Пуассона и простейший поток .......................................................................................	6
Поток Эрланга и гиперэкспоненциальное распределение .....................................................	9
Марковские процессы ...................................................................................................................	12
Марковские процессы с дискретным временем ........................................................................	12
Марковские процессы с непрерывным временем .....................................................................	14
Алгоритм расчета марковской цепи ...........................................................................................	16
Системы локального баланса ......................................................................................................	16
Системы массового обслуживания .............................................................................................	18
Система М/М/1 .............................................................................................................................	19
Система М/М/N ............................................................................................................................	22
СМО M/M/1/ /K...........................................................................................................................	23
Система M/G/1..............................................................................................................................	25
Неоднородные СМО ....................................................................................................................	27
СМО без приоритетов (СМО БП)...........................................................................................	28
СМО с относительными приоритетами (СМО ОП)..............................................................	29
СМО общего вида (M/G/1) с абсолютными приоритетами (СМО АП)..............................	31
СМО со смешанными приоритетами (СМО СП) ..................................................................	32
Применение моделей на основе СМО M/G/1 ............................................................................	36
1. Ограничение на время обработки требований не задано .................................................	36
2. Системы с относительными ограничениями на время пребывания и время ожидания
заявок.........................................................................................................................................	38
3. Системы с абсолютными ограничениями на время ожидания (пребывания) заявок....	40

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

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	2
Определение памяти, необходимой для хранения очереди требований ............................	41
Сети массового обслуживания.....................................................................................................	42
Разомкнутые сети массового обслуживания (РСеМО) ............................................................	42
Параметры РСеМО...................................................................................................................	43
Характеристики СеМО ............................................................................................................	43
Методика расчета РСеМО .......................................................................................................	44
Замкнутые СеМО .........................................................................................................................	46
Алгоритм Бьюзена....................................................................................................................	50
Применение моделей СеМО .......................................................................................................	53
Двухфазная ЗСеМО..................................................................................................................	53
Трехфазная модель...................................................................................................................	55
Преобразования сетей. .................................................................................................................	56
Агрегирование СМО. ...............................................................................................................	58
Допущения в аналитических моделях на основе СеМО ..........................................................	60
Элементы сетевого моделирования............................................................................................	62
Элементы сетей. ...........................................................................................................................	62
Временнóе моделирование сетей................................................................................................	64
Литература ......................................................................................................................................	70

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

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

Элементы теории массового обслуживания

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

СМО представляют собой модели, состоящие из двух типов объектов: обслуживающих приборов и заявок (объектов нуждающихся в обслуживании)

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

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

ОП

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

Количество заявок, одновременное обслуживание которых допустимо в одном обслуживаемом приборе образуют канальность этого прибора. Соответственно различают одноканальные и n-канальные приборы.

Дисциплины и режимы обслуживания заявок

Если длина очереди превышает 1, то необходимо задать правило выборки из неё заявок для обслуживания или, другими словами, необходимо выбрать дисциплину обслуживания (ДО),

которые бывают:

1. Статические ДО не меняются в процессе обслуживания заявок. При работе с такими ДО вводится понятие приоритета, т.е. право заявки на преимущественное обслуживание. Если все заявки равноправны, то такая ДО называется бесприоритетной (БП).

1.1.БП ДО бывают следующих видов:

обслуживание в порядке поступления FIFO;

обслуживание в обратном порядке или стековая ДО LIFO;

ДО в случайном порядке RAND;

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

системами если q 0, то такая ДО называется ДО с разделением процессора PS.

Пусть в системе существуют заявки различных

i

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

типа имели меньшее время ожидания в очереди,

чем

ОП

заявки других типов. В этом случае всем заявкам

назначаются приоритеты, которые делятся на

два

	класса:	Рис. 2. СМО с несколькими потоками
		событий.
	1.2. Если приоритеты учитываются только в момент

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

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

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

1.3.Абсолютные приоритеты (АП). При ДО с АП заявка, поступившая в очередь,

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

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

остальные обслуживаются в бесприоритетном режиме, то такая ДО называется ДО со

смешанными приоритетами (СП). Это наиболее тяжелый режим функционирования СМО со статистической ДО.

2.Динамические ДО меняются в зависимости от режима функционирования СМО.

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

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

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

Параметры и характеристики СМО

i — интенсивность входного потока заявок

b — длительность обслуживания одной заявки

— интенсивность обслуживания b 1

w — среднее время ожидания в очереди

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

СеМО представляют собой совокупность конечного числа М обслуживающих центров,

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

Различают замкнутые СеМО (ЗСеМО) и разомкнутые СеМО (РСеМО).

Для замкнутых сетей количество заявок в сети постоянно — заявки не поступают в сеть извне и не покидают её. Количество заявок является параметром сети.

Разомкнутые сети имеют два фиктивных узла: источник заявок и сток или поглотитель заявок. В такой сети количество заявок — случайная величина.

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

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

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

однородной.
			Параметры и характеристики разомкнутых сетей
0	— интенсивность входного потока заявок
N	— количество узлов
Bj(t)	—	закон	распределения	длительности	u
	обслуживания для j-го узла j 1, N				w	b
					i
ДОj	— дисциплина обслуживания в j-ом узле
Pj	— вероятность попадания в j-ый узел				i	ОП
U(uj)	— время пребывания заявок в сети
W(wj)	— суммарное время ожидания в очередях					ОП
lj	— среднее количество заявок в j-ой очереди				Рис. 3. Размкнутая сеть массового
j
	— загрузка узлов в сети				обслуживания.

Параметры и характеристики замкнутых сетей

Они аналогичны параметрам разомкнутых сетей, за исключением 0. Вместо 0

используется М — количество заявок в сети.

0 используется как характеристика интенсивности движения заявок в сети.

ОП1	ОП2
М

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

Во всех параметрах и характеристиках в случае разнородной сети добавляется индекс i —

класс заявок.

Потоки событий

Потоком событий считается последовательность событий происходящих одно за другим в определённые интервалы времени.

0	t1	t2	…	tk tk+1
		T
				t
		Рис.	5. Потоки событий.

Свойства и характеристики потоков событий

Т — средняя величина интервала времени между соседними событиями. Если Т = const, то

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

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

мы имеем равномерное распределение событий (тактовый генератор).

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

Стационарным потоком называется поток, характеристики которого не изменяются во времени.

Поток является стационарным, если количество событий попадающих на любой произвольный интервал времени не зависит от положения на числовой оси, а зависит только от его ширины 1.

Если для любых двух не пересекающихся интервалов 1 и 2 количество событий попадающих на один из интервалов не зависит от того, сколько событий произошло на другом интервале, то такой поток называется потоком события без последействия. Противоположный потоку без последействия — регулярный поток или поток с последствием.

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

Закон Пуассона и простейший поток

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

	P , m	m	e ,	(1)
		m!

которая носит название закона Пуассона.

Пуассоновский поток — это нестационарный, ординарный поток без последействия.

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

D m E m .

(2)

1 Например, поток поступления заявок в АТС не может считаться стационарным, т.к. интенсивность изменяется в достаточно широких пределах. Однако в интервале времени с 9 до 21 поток может рассматриваться как стационарный.

8	9	16	21	24	t,ч

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

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

Отношение среднеквадратичного отклонения случайной величины к её математическому ожиданию даст коэффициент вариации :

	D			1		.	(3)
	E
Пусть F( ) вероятность того, что интервал времени Т между соседними событиями не
превышает некоторой величины :
F P T .
Тогда вероятность противоположной ситуации
P T 1 F ,
но это, в свою очередь является вероятностью того, что за время не произойдет ни
одного события.
Для пуассоновского потока
P , m 0 e , тогда
F 1 e							(4)
Дифференцируя это равенство, получим
f e							(5)

Выражения (4) и (5) описывают функцию распределения и плотность распределения,

известного как показательное или экспоненциальное, которым характеризуется простейший поток.

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

E 1

Дисперсия этого потока:

D 1 2

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

Объединяя эти результаты, определим, что простейший поток — это стационарный,

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

Другими словами, простейший поток — это стационарный пуассоновский поток.

Простейший поток обладает следующими особенностями:

1. Сумма нескольких n стационарных потоков с достаточно малым (приблизительно

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

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

одинаковым) последействием представляет собой поток близкий к простейшему с

интенсивностью равной сумме интенсивностей входных потоков:

n

0 i

i1

2.Прореживание потока с интенсивностью (когда каждая заявка исключается из потока с вероятностью P, независимо от того исключены ли другие заявки) приводит к простейшим потокам с интенсивностями i pi :

	1
	pi
	1-pi
	2

Рис. 6. Прореживание потока событий.

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

	1	1 2
P 1	P d e d 1 1 e 0.63
	0	o

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

Следствием этого является то, что простейший поток создаёт наиболее тяжелый режим функционирования системы по сравнению с другими потоками и используется для определения предельных значений характеристик качества обслуживания. Если реальный поток отличен от простейшего, то система будет работать не хуже рассчитанной

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

	T
0	T-	t

Рис. 7. Отсутствие последействия.

Рассмотрим это свойство. Допустим, что заявка поступила в момент времени 0. По формуле распределения мы можем определить вероятность того, что следующая заявка поступит в момент времени t:

F t 1 e t

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

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

Предположим, что прошло некоторое время . Возникает вопрос, какова вероятность того,

что следующая заявка поступит не раньше, чем в момент времени t, то есть, что t T , или

T t :

F	t P T t		T	P T t T	.
				P T

P T t T — это, фактически вероятность того, что момент времени T находится

в интервале , t :

P T t F t F .

P T не что иное, как 1 F τ .

F t	F t F			1 e t 1 e		1 e F t .
	1 F			1 1 e

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

Коэффициент вариации этого потока равен 1:

		D				1 2		1 .	(6)
	E				1

Поток Эрланга и гиперэкспоненциальное распределение

Поток, который образуется выделением каждой k-той заявки (или удалением каждой k - 1

заявок) из простейшего потока называется потоком Эрланга k-го порядка.

	k = 1
	(простейший	t
	поток)
	k = 2	t

k = 3

t

k = 4

t

Рис. 8. Формирование потока Эрланга.

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

Ti

i 1k

Т.к. исходный поток является стационарным и ординарным, и математическое ожидание для интервала времени — E 1 , то можно записать, что T kE k λ .

Дисперсия для потока Эрланга k-го порядка

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

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

10

k

Dk Di kD k 2 .

i 1

Коэффициент вариации

Dk

k 2

1

.

(7)

E k

k

k

Плотность распределения интервала времени между последовательными заявками по закону Эрланга k-го порядка

	f t	λ λt k 1	e λt .	(8)
		k 1 !

Формирование потока заявок можно представить в виде некоторого генератора заявок,

который функционирует следующим образом.

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

Рис. 9. Генератор потока заявок с показательным распределением.

Теперь представим себе, что данный генератор состоит из k последовательно соединённых элементарных блоков, каждый из которых характеризуется показательным распределением времени пребывания заявок с параметром k :

k	k		k
1	2		k

Рис. 10. Генератор потока заявок с распределением Эрланга.

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

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

	f t	k k t k 1	e k t .	(9)
		k 1 !

Если k = 1, то мы получаем экспоненциальное распределение.

Однако в этом генераторе элементарные блоки могут соединяться не только последовательно, но и параллельно.

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