GPSS / Simulation

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

31

Пусть в систему поступает 5 ППС

с одинаковыми интенсивностями и временем

БП

обслуживания заявок любого типа. Отличаются эти заявки

wk

k = 5

k = 4

только различными

приоритетами k 1,5 . Зависимость

времени

ожидания

wОП

от

загрузки

R будет

выглядеть

k

следующим образом:

k = 3

Т.е. при изменении R, например, путем снижения

быстродействия обслуживающего прибора, при R 1 время

k = 2

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

k = 1

мало отличается от wБП. Тогда как характеристики

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

заявок

с

высоким

приоритетом не

1 R

Рис. 28. Зависимость времени ожидания в

изменяются (или меняются

в малой степени). Поэтому

очереди от загрузки прибора.

говорят,

что

высокоприоритетные

заявки

обладают

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

СМО общего вида (M/G/1) с абсолютными приоритетами (СМО АП)

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

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

Обслуживание заявок в СМО с АП происходит по

1

следующей схеме:

П

i

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

приоритетом обслуживаемая

в

данный

момент

низкоприоритетная заявка будет возвращена в очередь.

Прерванная заявка

будет

обслуживаться

заново.

Рис. 29. Схема обслуживания в СМО заявок

с абсолютниыми приоритетами.

Время дообслуживания

заявок

распределено по

экспоненциальному закону, независимо от коэффициента вариации i закона обслуживания.

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

Если М входных потоков — простейшие с интенсивностью i, заявки i-ых типов характеризуются первым и вторым начальными моментами bi и bi(2), а дообслуживание выполняется от точки прерывания, то среднее время ожидания в СМО АП заявок с абсолютным приоритетом k 1,M будет равно:

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

	Е.В.Малахов. Имитационное моделирование. Конспект лекций.							32
				k
		R k 1 bk		i bi2 1 i2
	w АП			i 1			,	(35)
		1 R k 1		2 1 R k 1 R k 1
	k

j
где Rj i — суммарная загрузка от первых j	потоков заявок, т.е. заявок с высокими
i 1
приоритетами.
Первое слагаемое представляет собой время,	которое тратится в очереди вследствие

прерывания от более приоритетных заявок.

Сопоставление формул (34) и (35) показывает, что при переходе к абсолютным

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

					M
w w АП wОП			R k 1 bk		i bi 2
					i k 1
k	k	k	1 R k 1		2 1 R k 1 R k 1

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

1 R k

1

M

wk

0 R k 1 bk

i bi 2

2 i k 1

wk

Если k = 1, то формула (35) примет вид:

b 2

АП

w АП

w АП

wОП w БП .

2 1

1 1

БП

1

1

1

1

1

Если k = М, то

ОП

M

R

b

i bi2 1 i2

1

M k

w АП

i 1

w АП

wОП

wБП .

M 1 M

M

1 RM 1

2 1 RM 1 RM 1

M

M

M

Рис. 30. Сопоставление графиков

Эти

зависимости

времени

ожидания

заявок

k-го

типа

зависимости времени ожидания в

очереди заявок с различными

можно представить на следующем графике:

типами приоритетами.

СМО со смешанными приоритетами (СМО СП)

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

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

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

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

33

Пусть в

СМО

поступает M типов

заявок.

Если

wk

заявки обслуживать без приоритетов (в режиме FIFO), то

для некоторой

части

М1

заявок (типа 1,M 1 )

среднее

w*

СП

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

FIFO

(см. рис.).

Если перейти к относительным приоритетам, то для

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

1

M

M k

1

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

Рис. 31. Зависимость времени ожидания в

предельно допустимые значения w*. Эту ситуацию можно

очереди от приоритета заявок со

смешанными приоритетами двух типов.

изменить, если М1 классам заявок

присвоить относительные

приоритеты,

а заявки типа

M 1 1,M обслуживать в бесприоритетном режиме.

Рассмотрим систему с дисциплиной обслуживания со смешанными приоритетами и

тремя классами заявок:

заявкам типа 1,M 1

присваиваются

абсолютные приоритеты,

M2

заявкам

типа

M 1 1,M 1 M 2 —

относительные

приоритеты,

а

остальные M3

заявок

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

Таким образом, заявки первого класса обладают

wk

абсолютными приоритетами по отношению ко второму и

АП

третьему,

а

заявки

второго —

относительными

по

СП

отношению к третьему.

FIFO

Определим

средние

времена

ожидания

заявок

ОП

различных классов.

Для

заявок

первого

класса

характерна

1

M

M+M

M k

независимость

времени

ожидания

от

характеристик

1

1

2

Рис. 32. Зависимость времени ожидания в

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

очереди от приоритета заявок со

время

ожидания

wср

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

смешанными приоритетами трех классов.

совпадает с w

АП , где

k 1,M

1

, выведенным ранее.

k

Заявки второго и третьего классов можно рассматривать как заявки с относительными

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

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

С учетом этого:

w

k

wОП w

k

, где

w

k

— "добавка" за счет прерывания, причем все

k

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

		RM bk					M 1
Очевидно, что wk		1		, где k M 1 1,M , RM 1			i	(36)
		1 RM	1				i 1

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

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

Для заявок второго класса величина wkОП будет определяться также по выведенной ранее формуле для ДО ОП (34):

			M
			i b 2							j
	wkОП		i 1				, где k M 1 1,M 1 M 2 , R j			i
		2 1	R k 1	1 R k
										i j

Для заявок третьего класса эта формула претерпит следующие изменения.

Т.к. эти заявки обладают самым низким приоритетом, то загрузка со стороны всех M1+M2

M 1 M 2

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

RM 1 M 2

i .

Загрузка прибора с учетом и самих

i 1

M

заявок третьего класса R i

. Следовательно, для них

i 1

M

i bi 2

wОП w БП

i 1

,

(37)

2 1

RM 1 M 2 1 R

k

k

В общем виде выражение для времени ожидания заявок в СМО M/G/1 с тремя классами

требований примет вид:

k

R k 1 bk

λ i bi 2

i 1

,

где k 1,M 1

2 1

R k 1

1 R k

1 R k 1

M

λ i bi 2

RM

bk

i 1

wk

1

,

где k M 1

1,M 1 M 2

(38)

1 R

2 1

R

1 R

M 1

k 1

k

M

RM 1 bk

λ i bi 2

i 1

,

где k M 1

M 2 1,M

1 R

M 1

2 1

R

1 R

M 1 M 2

Из данной системы уравнений для СМО с ДО СП и тремя классами заявок могут быть получены частные случаи для расчета среднего времени ожидания с более простыми дисциплинами обслуживания:

1."Чистые" ДО:

ДО АП — M2 = M3 = 0 ДО ОП — M1 = M3 = 0 ДО БП — M1 = M2 = 0

2.Смешанные ДО: АП + ОП — M3 = 0 АП + БП — M2 = 0

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

0 0 0 02 0 0 0 Q 2 2 0 0

2 2 2 0

1 0 2 2 2 2 2

2 0 0 2 2 2 2

3 0 0 0 1 1 1 Q

4 0 0 0 0 1 1

5 0 0 0 0 0 0 6 0 0 0 0 0 0

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

ОП + БП — M1 = 0

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

Для формального описания такой дисциплины вводится квадратная матрица приоритетов:

Q = [qij]. Ранг матрицы равен M. Каждый элемент qij должен отражать приоритетность i-го типа заявок по отношению к j-му, и может принимать соответственно: 0 — БП обслуживание, 1 — i-я заявка обладает более высоким ОП по отношению к j-й, 2 — более высокий АП i-го требования (т.е. оно может прерывать обслуживание заявок j-го потока).

Причем, если элемент qij = 0, то это не означает, что заявки потоков i и j обслуживаются в режиме FIFO. Возможно, что заявка потока j обладает приоритетом по отношению к требованиям i-го типа и, следовательно, заявки потока i не имеют и не могут иметь приоритет по отношению к заявкам потока j. И наоборот, если qij 0, то элемент матрицы, симметричный данному относительно главной диагонали, должен быть равен 0. Кроме того, между заявками одного потока не может быть приоритетов, т.е. qij = 0.

Примером матрицы может служить такая:

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

Рассмотрим такой пример.

Предположим, поступают 4 потока, т.е. M = 4. Матрица Q имеет следующий вид:

Т.е. заявка с большим номером имеет более высокий абсолютный приоритет (а не наоборот). Тогда время ожидания потока k определится выражением:

bk i

i bi 2

wk

i M k 1

i M k 2

, где k M ,

(39)

i

1

i

i

i M k 1

2

1

1

i M k 3

i M k 4

М — множество всех потоков требований в СМО;

Мk1 — подмножество потоков, заявок имеющих более высокий АП по сравнению с

1 Так, ДО БП будет соответствовать нулевая матрица и т.д.

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

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

заявками k-го типа;

Мk2 — подмножество потоков заявок, по отношению к которым заявки k-го типа не обладают более высоким АП;

Мk3 — подмножество потоков заявок, имеющих более высокий АП или ОП по отношению к заявкам типа k;

Мk4 — подмножество потоков заявок, по отношению к которым заявки k-го типа не обладают более высоким АП и ОП.

В приведенном примере Мk1 и Мk3, а также Мk2 и Мk4 совпадают. Вычисления по этой формулы сводятся к просмотру матрицы приоритетов, выделению подмножеств и накоплению соответствующих сумм.

Применение моделей на основе СМО M/G/1

Такие модели наиболее широко применяются в анализе систем обработки данных (СОД) 1.

СОД, естественно, ориентированы на применение вычислительной техники.

При их анализе решаются 3 группы задач:

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

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

2.Определение дисциплины обслуживания запросов;

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

Рассмотрим одну разновидность СОД, которые предназначены для управления различными объектами. Эти системы называют управляющими системами или системами контроля.

Особенностью этой группы систем обработки данных является то, что они функционируют в реальном масштабе времени, т.е. согласованно с темпом поступления требований на решение определенных задач. Это означает, что заявки должны обслуживаться некоторое ограниченное время T Pi ui* , где TРi — время реакции системы на запрос i-го типа, ui* — предельно допустимое время пребывания заявок i-го типа в системе.

При расчете системы уравнений, в зависимости от требований к временным характеристикам рассматриваются три варианта:

1. Ограничение на время обработки требований не задано

Исходные данные для расчета следующие:

1 Спектр сфер деятельности, где используются эти системы, трудно охватить: различные предприятия,

банки, библиотеки и пр. Соответственно, достаточно велико разнообразие и самих СОД.

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

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

i — интенсивность поступления заявок i 1,M ;

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

математическим ожиданием i и вторым начальным моментом (i 2 ) .

Несмотря на то, что ограничений на время реакции не задано, считается, что чем дольше

заявки пребывают в системе, тем ниже качество функционирования этой системы. Критерием эффективности такой системы является функция штрафа:

M
F i i wi ,	(40)

i 1

где i — коэффициент штрафа, определяющий стоимость задержки заявки i-го типа на единицу времени. Соответственно, оптимизацией системы будет снижение F.

Задержки, т.е. времена wi, зависят от двух факторов: быстродействия обслуживающего прибора и дисциплины обслуживания.

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

Очевидно, что в этом случае система должна работать в стационарном режиме R < 1. т.е.

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

В случае неоднородного потока запросов имеем:

M	M
R i	i bi
i 1	i 1
Но bi является зависимостью	от трудоемкости и быстродействия: b	i	, где	B —
	i	B
быстродействие обслуживающего центра (обслуживающего прибора). Откуда получаем:
M
B i i — граничное значение быстродействия.				(41)

i 1

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

и .

Запросы могут быть ранжированы по важности, т.е. иметь свои коэффициенты i. Если же если у нас запросы одинаковы, и соответственно, коэффициенты i = = const, то функция штрафа (40) упрощается:

M

F i wi L ,

i 1

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

Вторым способом снижения функции штрафа F является назначение приоритетов. Эта

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

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

процедура имеет смысл, очевидно, в том случае, если она минимизирует F по сравнению с

ДО БП: F ОП F БП . Рассмотрим эти две функции:

M

i bi 2

M

F

БП

i 1

i i

2 1 R

i 1

1

M

M

i

F

ОП

i bi 2

i

1 Ri 1

1 Ri

2 i 1

i 1

Подставив эти выражения в условие эффективности перехода к относительным

приоритетам, получим:

M

1 R

M

i

i

1 R

i i

1 R

i 1

i 1

i 1

i

Это выражение можно привести к следующему виду:

M

i

i 1

R

i

R Ri 0 , где

M 1

0

bi 1

Ri

bM 1

i 1 bi

1

Истинность этого выражения зависит только от разности

i

i 1

, которая должна быть

bi

bi 1

положительной. Т.е. должно выполняться условие

	i		i 1
				, при i 1,M 1 .			(42)
	bi		bi 1

Это и есть условие эффективности перехода к относительным приоритетам, не зависящее от интенсивностей входных потоков.

Если i = = const, то это условие примет вид bi < bi+1, из которого следует, что для получения выигрыша при использовании ДО ОП заявкам с меньшей длительностью обслуживания должны присваиваться более высокие относительные приоритеты.

Условие эффективности перехода от ДО БП к ДО АП имеет такой же вид только при экспоненциальном распределении времени обслуживания заявок, т.е. при bi 1. Это связанно с тем, что это условие и условие выигрыша ДО АП по отношению к ДО ОП зависят от второго начального момента времени обслуживания заявок bi( 2 ) .

2.Системы с относительными ограничениями на время пребывания

ивремя ожидания заявок.

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

налагаются на среднее значения времён: w	i	w*	или u	i	u* , где	w*	и u *	— предельные
		i			i	i	i

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

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

ограничения на средние времена ожидания (пребывания) заявок в СМО.

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

улучшения быстродействия обслуживающего прибора k y		Bmin	, где Bmin — быстродействие
		B

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

Получить эти величины можно, исходя из закона сохранения времени ожидания (32):

M
i wi	const , которая, очевидно, в данном случае равна Rw БП
i 1

При условии ограничений wi wi* можно записать:

M

i wi* Rw БП

i 1

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

wБП было меньше чем минимальное из ограничений всех потоков заявок w БП										M
										MIN wi* .
										i 1
Но
				M
		w БП		i bi2 1 i2
				i 1
				2 1 R
	i	M			1	M
где bi		, а R i bi				i i		. Выполняя подстановку, получим:
	B	i 1			B i 1
				M
				i i2 1 i2					M
				i 1					MIN wi* .	(43)
						M
									i 1
			2B B i i
						i 1

Решая соответствующее этому неравенству квадратное уравнение относительно B,

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

M	wi w БП 0 .
i
i 1

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

					Е.В.Малахов. Имитационное моделирование. Конспект лекций.				40
	Мы отметили,				что при B = Bmin существует хотя			wСП B
								wi	2
бы одна ДО, при которой удовлетворяются
ограничения по временам. Очевидно, что чем больше
разность B - Bmin, тем проще найти требуемую ДО и									2
тем больше коэффициент запаса по времени
ожидания заявок. Действительно, если при некотором
быстродействии				B1	даже для	БП ДО выполняются			1
данные ограничения, то при быстродействии B2 < B1								k
и ДО БП для некоторых требований время ожидания
wi	заявок	может			превысить	допустимое	wi* . В	Рис. 33. Сопоставление графиков зависимости
								времени ожидания в очереди заявок с
результате необходимо искать ДО, например, ДО СП								различными типами приоритетами при
								различном быстродействии прибора.
1, для которой w			i	w* 2.
					i
	Точного и универсального решения эта задача не имеет и определение оптимальной ДО
предполагает использование эвристических алгоритмов, сводящихся к перебору дисциплин,
близких к оптимальной. Принято считать, что ДО будет близка к оптимальной, если более
высокие приоритеты давать требованиям с более жесткими ограничениями.

3.Системы с абсолютными ограничениями на время ожидания (пребывания) заявок

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

Критерием эффективности таких систем с M потоками заявок может служить функция штрафа:

M
F i i P wi wi* ,	(44)

i 1

где i — штраф за превышение допустимого времени ограничения одной заявкой типа i. А все произведение — штраф за превышение ограничений заявками i-го типа, поступающих в систему за единицу времени.

Основной элемент, к минимизации которого следует стремиться — P wi wi* —

вероятность превышения допустимого времени ожидания (или допустимого времени пребывания P ui ui* ). Эта величина должна быть меньше некоторой малой величины (на практике имеет порядок 10-5).

1Этот поиск может осуществляться, например, путем имитационного моделирования.

2Вполне логичным был бы вопрос: "Зачем искать такое быстродействие B2?". Во-первых, невозможно обеспечить быстродействие, стремящееся к бесконечности. Во-вторых, прямо пропорционально росту быстродействия обслуживающего прибора растет и стоимость оборудования, которое играет роль или эмулируется этим прибором, что выражено коэффициентом улучшения быстродействия kу.

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