книги / Разработка программного обеспечения для систем управления двигателями летательных аппаратов

Определение 28. Абсолютная интервальная загрузка u(t1 , t2 ) – это значение занятого времени на некотором интервале времени [t1 , t2 ] , и ее связь с интервальной загрузкой определяется следующим образом:

u(t , t

2

)

=

(t2 − t1 )

U (t , t

2

) =

1

100%

1

(t2 − t1 )

Γ

Γ

A

ˆ

A

=

100%

(U

(t1

, t2 ) +U

(t1

, t2 ) +U

(t1 , t2 ) +U

(t1

, t2 )) =

(19)

=

Γ(t1 , t2 ) + u Γ(t1 , t2 ) + u A (t1 , t2 ) + uˆ A (t1 , t2 ) ,

u

где

Γ(t1 , t2 ),

u Γ(t1 , t2 ),

u A (t1, t2 ),

uˆ A (t1 , t2 )

– соответственно абсолют-

u

ные интервальные загрузки периодическими задачами ЖРВ, спорадическими задачами ЖРВ, обязательными апериодическими задачами МРВ, необязательными апериодическими задачами МРВ.

Определение 29. Абсолютная интервальная загрузка задачами

ЖРВ uΓ(t , t					2	) определяется следующим образом:
				1
						u	Γ(t , t			) =		Γ(t , t		) + u Γ(t , t		).	(20)
									2		u		2		2
								1		1				1
		Определение 30. Абсолютная интервальная загрузка апериодиче-
скими задачами u A (t , t							2	) определяется следующим образом:
						1
						u A (t1, t2 ) = u A (t1, t2 ) + uˆ A (t1 , t2 ).											(21)
		Определение 31. Интервальная загрузка задачей τi															(обозначаемая
U	τ	(t , t	2	) ) – это процент занятого времени на заданном интервале [t , t														2	]
	i	1															1

запросами, формируемыми задачей τi .

Определение 32. Абсолютная интервальная загрузка задачей τi

(обозначаемая ui τ (t1 , t2 ) ) – это значение занятого времени на заданном интервале [t1 , t2 ] запросами, формируемыми задачей τi .

Значение ui τ(t1 , t2 ) можно определить следующим образом:

ui τ(t1 , t2 ) =	∑	(c(t1 , τi, j ) − c(t2 , τi, j )) .	(22)
	j|τi , j Ω(t1 ,t2 )

71

С учетом (17) это определение можно уточнить следующим образом:

uiτ (t1 , t2 ) =

∑

c(t1 ,τ i, j ) +

∑

Ci, j +

j|τ i , j

ΩCF (t1 ,t2 )

jτ| i , j

ΩSF(t1 ,t2 )

)). .

(23)

+

∑

λ (t

2

τ,

i, j

) +

∑

(c(tτ,

i, j

) − c(tτ,

i, j

1

2

j|τ i , j ΩSC(t1 ,t2 )

jτ| i , j

ΩCC(t1 ,t2 )

В свою очередь абсолютные интервальные загрузки периодическими задачами ЖРВ, спорадическими задачами ЖРВ и всеми задачами ЖРВ можно представить следующим образом:

		τ (t1 , t2 ) = ∑ uiτ (t1 , t2 ),				uτ (t1	, t2 ) = ∑ uτi (t1 , t2 ),
	u
			i I (Γ)				i I (Γ)
			n				(24)
uτ			(t1 , t2 ) = ∑uiτ (t1 , t2 ),

i=1

где Γ – множество всех периодических задач ЖРВ; Γ – множество всех спорадических задач ЖРВ.

Абсолютные интервальные загрузки апериодическими задачами МРВ можно представить следующим образом:

u A (t1 , t2 ) =

m|a m

+∑

m|am ΩSC(t1 ,t

uˆ A (t1 , t2 ) =

∑c(t1 , am ) +

ΩCF(t1 ,t2∩		m|am
	) Ω( A)

			λ(t2 , am ) +	∑
	2∩			m|am ΩCC(∩t1
		) Ω( A )

∑c(t1 , am ) +

∑C(am ) +

ΩSF(∩t1 ,t2 ) Ω( A)

(c(t1, am ) − c(t2 , am )) ,

,t2 ) Ω( A)

(25)

∑ C(am ) +

	m|am ΩCF(t1 ,t2∩			ˆ			ˆ
				) Ω( A)		m|am ΩSF(t1 ,t2 )∩ Ω( A)
+	∑		λ(t2 , am ) +			∑	(c(t1, am )
m|am	ΩSC(t1 ,t2∩	ˆ			m	ˆ
		) Ω( A )				|am ΩCC(∩t1 ,t2 ) Ω( A)

− c(t2 , am )) .

	Определение 33. Суммарное время простоев на интервале
u	(t , t	2	) – это количество времени, в течение которого ни один запрос
	1

не выполнялся, вычисляемое для некоторого интервала времени [t1 , t2 ] , и его значение определяется следующим образом:

u	(t , t	2	) = (t	2	− t ) − u(t , t		2	) .	(26)
	1				1	1

72

2.6.3.7. Статический алгоритм захвата резерва

Для статических алгоритмов резерва времени, к которым относится локально-оптимальный алгоритм [91], очень важным является понятие гиперпериода.

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

Рассмотрим статический алгоритм захвата резерва. Предполагается, чтоспорадические задачи отсутствуют. Для удобства изложения предполагаем, что Oi = 0, 1 ≤ i≤ n , тоесть увсех задач ЖРВимеются нулевые смеще-

ния. Принеобходимостинесоставляеттрудаучестьненулевыесмещения.

Определение34. Эффективный крайний срок diE, j – это время оконча-

ния последнего перед di, j интервала времени, в течение которого отсутствуют запросы задач Γπ (1, π(i) −1) , то есть отсутствуют запросы задач ЖРВ сболее высокими приоритетами. Значение diE, j указывает наиболее позднее времядомомента di, j , когда τi, j можетзакончитьвыполнение.

Определение 35.

Дельта-точка

∆ i, j

– это совокупность значений

(t ∆

i, j ,

K∆

i, j ) , где t ∆

i, j

– время дельта-точки, K ∆

i, j

– резерв времени дель-

та-точки, при этом

t ∆

i, j = diE, j ,

K ∆

i, j = diE, j − ∑

d E

(27)

CvUp

i, j

,

v I (1,π

(i ))

Tv

где X

– округление до большего целого значения X .

(t∆

K∆

Значение каждой

дельта-точки

∆ i, j=

i, j ,

i, j ) вычисляется на

этапе предварительного планирования и сохраняется в памяти в виде массива. Количество дельта-точек для каждой задачи определяется гиперпе-

риодом, то есть сохраняются только ∆ i, j ,	для 1≤ ≤i n, ≤1 ≤ j		H	. То-
			Ti
n	H
гдазатраты памятиоцениваются как O(∑		) .
i=1	Ti

73

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

t ∆

i, j = H

−1)

T

+ t∆

( j

i

i,v ,

H

(28)

Ti

∆

∆

∆

K

i, j

= K i,r

( j −1)

+ K i,v

,

H

где 1 ≤ v= j−

H

( j−

1)

Ti

≤

H

,

r=

H

.

Ti

Ti

Ti

H

Определение 36. Время начала текущего гиперпериода tH опреде-

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

t

C

tH = H

.

(29)

H

Чтобы не выполнять вычислений (28), в ходе функционирования текущее время отсчитывается от начала текущего гиперпериода. Тогда рассматриваются только сохраненные в памяти дельта-точки одного гиперпериода.

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

Оценка Ki ст резерва времени для задачи Pi определяется на основе статического алгоритма захвата резерва следующим образом:

	Ki ст = K ∆		i,r − u A (tH , tC ) − u (tH , tC ) −			∑ uv τ (tH , tC ),			(30)
					v I+(i 1,n)
где	j, если		τi, j	не завершил выполнение,
	r =			τi, j завершил выполнение,
	j +1,	если
при этом значение j такое, что t ∆					i, j −1 ≤ tC− tH <	t∆	i, j .
	Для удобства обозначения предполагается, что t ∆							i, j −1 = 0 при	j = 1 .
Такжепредполагается, что u A (tH , tC ) = u A (tH , tC ) .

Соответственно оценка K ст резерва времени определяется на основе статического алгоритма захвата резерва следующим образом:

74

		K ст		= min (K	ст ) .		(31)
				i|1≤ ≤ i n	i
Определение 37. Ограничивающий запрос ЖРВ на текущий момент
времени (обозначаемый τi			, j	) – это запрос,			которому соответствует
		огр	огр
дельта-точка ∆ i	, j	, относительно которой на текущий момент времени
огр	огр
было вычислено минимальное				значение	Ki	ст	такое, что K ст = Ki	ст .
					огр		огр

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

Алгоритм 4. Статический локально-оптимальный алгоритм захвата резерва

Предварительное планирование (планирование)
Значение каждой дельта-точки ∆ i, j= (t∆	i, j , K∆	i, j ) вычисляется

и все сохраняется в памяти в виде массива. Количество дельта-точек для каждой задачи определяется гиперпериодом, то есть сохраняются

только ∆ i, j для 1≤ ≤i n, ≤ 1 ≤ j			H	. Затраты памяти оцениваются как
			Ti
n
O(∑	H	) .
i=1 Ti

Планирование в РВ (диспетчеризация)

Перед началом планирования в РВ предполагается, что запрос aC отсутствует в основной очереди Q .

В момент времени, когда некоторый запрос am становится aC ,

тогда c(tC , aC ) = C(am ) .

1.ЕСЛИ tC = tH , ТО НАЧАЛО

u A (tH , tC ) = 0; u (tH , tC ) = 0;

для всех 1 ≤ v≤ n : uv τ (tH , tC ) = 0;

75

КОНЕЦ

ИНАЧЕ

НАЧАЛО

ЕСЛИ на предыдущем шаге времени выполнялся aC ,

ТО u A (tH , tC ) = u A (tH , tC ) + ε;

ЕСЛИ на предыдущем шаге времени ни один запрос не выполнялся,

ТО u (tH , tC ) = u (tH , tC ) + ε;

ЕСЛИ на предыдущем шаге времени выполнялся запрос задачи Pv ,

ТО uv τ (tH , tC ) = uv τ(tH , tC ) + ε;

КОНЕЦ

2. ЕСЛИ появляется новый ОАЗ am , ТО

НАЧАЛО

ЕСЛИ запрос aC отсутствует в основной очереди Q , ТО

НАЧАЛО

am становится aC (поступая в основную очередь Q );

ПЕРЕЙТИ к шагу 7. КОНЕЦ

ИНАЧЕ am помещается в очередь ОАЗ QA . КОНЕЦ

3. ЕСЛИ выполнение запроса aC завершается (и он удаляется из ос-

новной очереди Q ) и очередь ОАЗ QA не является пустой, ТО НАЧАЛО

Первый запрос в очереди ОАЗ QA становится aC , поступая в основную очередь Q ;

ПЕРЕЙТИ к шагу 7. КОНЕЦ

4.ЕСЛИ выполнение запроса aC прерывается, ТО вычисляется новое значение c(tC , aC ) .

5.ЕСЛИ на предыдущем шаге времени выполнение запроса задачи τi

завершилось (и он был удален из основной очереди Q ) и существует запрос aC , ТО ПЕРЕЙТИ к шагу7.

6.ПЕРЕЙТИ к шагу 8.

76

7. Вычисляются значения Ki ст

для всех 1 ≤ i≤

n согласно (30);

вычисляется K ст согласно (31);

ЕСЛИ K

ст ≥

c(t

C

, a ) , ТО

C

запросу

a

присваивается приоритет πreal (a ) выше,

чем у всех

C

C

задач ЖРВ, то есть πreal (a ) < πreal (после этого запрос a

будет

C

I (1)

C

выполняться досвоегозавершения, расходуя резерв времени).

ИНАЧЕ

находится запрос τi

, j

(см. определение 37),

затем запросу

огр

огр

a

C

присваивается приоритет πreal (a )

ниже, чем у всех задач

C

Γπ (1, iогр) ,

и

выше,

чем

у задач

Γπ (iогр +1, n) ,

то

есть

πreal

< πreal (a ) < πreal

(после этого запрос a

будет выпол-

i

C

I ( π(i )+1)

C

огр

огр

няться только при отсутствии в основной очереди Q запросов задач Γπ (1, iогр) ).

8. КОНЕЦ АЛГОРИТМА

2.6.3.8. Динамический алгоритм захвата резерва

Точная оценка Ki дин точн резерва времени для задачи τi , используе-

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

Алгоритм 5. Алгоритм вычисления Ki дин точн :

Используются вспомогательные переменные w1 , w2 , x .

1.Ki дин точн = 0 ;

w2 = 0

2.ВЫПОЛНЯТЬ ПОКА w2 ≤ (di,Ci − tC ) НАЧАЛО

w1 = w2 ;

w2	= Ki	динточн + ∑				(w1	− (rv,Nv	− tC ))
			c(tC , pv,L		) +		T	0	CvUp
				v
		v I(1,π(i))					v

ЕСЛИ w1 = w2 , ТО

77

НАЧАЛО

	(w1 − (rv,Nv	− tC ))			+ (r	− t
x = min		0	T				C	) − w
v I (1,π(i ))	Tv			v	v,Nv			1

x = min (x, ((di,Ci − tC ) − w1 )0 ) ;

Ki дин точн = Ki дин точн + x ;

w2 = w2 + x + ε2

КОНЕЦ

КОНЕЦ

3.КОНЕЦ АЛГОРИТМА

Врамках описания этого алгоритма используется обозначение вида ( X )0 , которое означает max( X , 0) . Подобное обозначение будет

встречаться и дальше.

Вычисление точного значения Ki дин точн требует значительных за-

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

Рассмотрим приближенную оценку Ki динприбл резерва времени для задачи τi , используемую для динамического алгоритма захвата резерва.

Приближенная оценка Ki динприбл получается именно приближенной потому, что для ее получения используется приближенная оценка значения эффективного крайнего срока diE, jприбл , вычисляемая согласно следующему алгоритму (см. алгоритм 5), а также приближенная оценка значения ui τ(tC , t) .

Алгоритм 6. Алгоритм вычисления diE, jприбл :

Используются вспомогательные переменные v, w, t E .

1.diE, jприбл = di, j ;

w = π (i) −1

2.ВЫПОЛНЯТЬ ПОКА w ≥ 1

НАЧАЛО

78

v = I (w) ;

ЕСЛИ r	< d E прибл			, ТО
v,Nv		i, j
НАЧАЛО		d E прибл
					− r
tE = rv, N v		+	i, j		v, N v	Tv ;
				T
				v

ЕСЛИ tE + CvUp ≥ diE, jприбл, ТО diE, jприбл = tE ;

КОНЕЦ w = w −1

КОНЕЦ 3. КОНЕЦ АЛГОРИТМА

Используется diE, jприбл вместо diE, j потому, что алгоритм вычисления diE, jприбл является простым по временной сложности, его сложность ограничена оценкой O(n) .

Таким образом, приближенная оценка Ki динприбл резерва времени для задачи τi , используемая для динамического алгоритма захвата резерва, вычисляется следующим образом:

u τ прибл (t

, t) = c(t

, p

(t − rv, Nv

)

) +

Tv

0

C Up +

v

C

C

v,L

v

v

(t − rv, Nv )

+ min C

Up ,

−

,

t − r

0

T

(32)

v

v, Nv

Tv

v

0

	(diE,Cприбл − tC ) −	∑ uv τ прибл (tC
Ki динприбл =			, diE,Cприбл ) ,
	i	v I (1,π (i ))	i	0
где uv τ прибл (tC , t) – приближенная оценка значения uv			τ(tC , t) .

79

Алгоритм 7. Описание обобщенного динамического алгоритма захвата резерва:

Предварительное планирование

Вычисление Ki дин точн	(согласно алгоритму 5) или Ki динприбл (согласно
(32)) для всех 1 ≤ i≤	n , предполагая, что tC = 0 .
Планирование в РВ

Перед началом планирования в РВ предполагается, что запрос aC отсутствует в основной очереди Q .

Переменная T дин определяет период пересчета Ki дин при наличии спорадических задач.

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

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

1.ЕСЛИ на предыдущем шаге времени выполнялся запрос задачи Pv ,

ТО для i	I(1, π(v)) :		Ki дин = Ki дин − ε;
ЕСЛИ на предыдущем шаге времени ни один запрос не выполнялся
или выполнялся aC ,
ТО для i |1≤ ≤i		n : Ki дин = Ki дин − ε.
ЕСЛИ на предыдущем шаге времени выполнение запроса задачи τi
завершилось (и он был удален из основной очереди Q ),
ТО вычисление Ki дин точн (согласно алгоритму 5) или Ki динприбл				(со-
гласно (32)) и Ki дин = Ki дин точн или Ki дин = Ki динприбл .
2. ЕСЛИ (tC	mod T дин) = 0 и имеются спорадические задачи,
ТО вычисление		Ki дин точн (согласно алгоритму 5) или Ki динприбл
(согласно	(32))	и	Ki дин = Ki дин точн или Ki дин = Ki динприбл	для
i I(π(v), n) , где v			– это индекс спорадической задачи с наи-

высшим приоритетом.

3.ЕСЛИ появляется новый ОАЗ am , ТО НАЧАЛО

80