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

Имеется множество апериодических задач A ; подмножество обяза-

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

ческих запросов и в общем случае также неизвестны заранее. Длительность выполнения запроса C(am ) , а также относительный крайний срок

запроса D(am ) становятся известными только в момент времени r(am ) .

D(am ) = C(am ), если am Ω(A) .

Для каждого НАЗ aˆm после его появления в ходе последующего

процесса планирования проверяется выполнение его ограничения РВ, которое определяется условием

Если оказывается, что условие (9) не выполняется, то есть не выполняется ограничение РВ для появившегося запроса aˆm , то тогда про-

61

исходит отказ от выполнения запроса aˆm , при этом b(aˆm ) – это время отказа от выполнения запроса aˆm .

2.6.2.Особенности планирования апериодических запросов

2.6.2.1.Планирование до поступления в основную очередь

Первоначально (при своем появлении) запрос am помещается в оче-

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

Но кроме этого для каждого запроса aˆm , оказавшегося на первом месте в очереди, необходимо проверить тест принятия, успешный результат которого гарантирует соблюдение ограничения РВ для aˆm и раз-

решает поступление этого запроса в основную очередь.

Главная проблема при разработке алгоритма планировании запроса am до поступления его в основную очередь – это разработка теста принятия. Тест принятия должен соответствовать двум условиям:

–успешный результат теста принятия для aˆm должен гарантировать соблюдение ограничения РВ для aˆm ;

–сложность алгоритма теста принятия должна позволять его практическую применимость (тест принятия должен быть хотя бы линейной временной сложности)

2.6.2.2. Планирование в основной очереди

При планировании апериодических запросов в основной очереди должна достигаться оптимизация по критерию обязательного МРВ (см. п. 2.3) при условии, что запросам ЖРВ гарантируется соблюдение их ограничений РВ. Таким образом, при планировании запросов Ω(A) необходимо соблюдать следующие два условия:

–обязательное соблюдение ограничений РВ всех запросов периодическихиспорадическихзадач(этомножествозапросовобозначается Ω(Γ) );

–минимизация среднего времени при выполнении ОАЗ.

62

В дальнейшем будем рассматривать планирование апериодических запросов на примере концепции планирования с фиксированными приоритетами и соответствующей базовой модели планирования (см. п. 2.5).

2.6.2.3. Резерв времени

Сначала приведем некоторые базовые определения.

Определение 4. Наблюдаемый интервал функционирования СРВ

[0, tmax ] – это интервал времени, в течение которого наблюдаются и оце-

ниваются характеристики функционирующей СРВ, в том числе характеристики планирования.

Таким образом, отчет времени ведется от начала наблюдаемого интервала функционирования СРВ.

Также необходимо отметить, что при имитационном моделировании процесса планирования моделируется именно интервал [0, tmax ].

Определение 5. Текущий момент времени обозначается tC и опре-

деляет на интервале [0, tmax ] такой момент времени, в который любое отслеженное событие на интервале [0, tC ] может быть учтено при выполнении того или иного алгоритма, а информация о событиях на интервале (tC , tmax ] в общем случае не известна.

Определение 6. Номер ближайшего появившегося запроса задачи

τi обозначается Li и определяет номер запроса задачи τi , время появления которого является ближайшим относительно tC среди всех уже появившихся к моменту tC запросов задачи τi .

Определение 7. Ближайший появившийся запрос задачи τi обозна-

чается и определяется как τi,Li .

Определение 8. Номер ближайшего следующего запроса задачи τi

обозначается Ni и определяет номер запроса задачи τi , время появления которого является ближайшим относительно tC среди всех еще не появившихся к моменту tC запросов задачи τi .

Определение 9. Ближайший следующий запрос задачи τi обознача-

ется и определяется как τi,Ni .

Определение 10. Номер текущего запроса задачи τi обозначается

Ci и определяет номер ближайшего появившегося запроса задачи τi ,

63

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

Определение 11. Текущий запрос задачи τi определяется как τi,Ci .

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

Определение 12. Резерв времени на интервале K (t1 , t2 ) – это мак-

симальное количество времени, которое может быть использовано для выполнения запросов Ω(A) на интервале [t1 , t2 ] при условии, что будут соблюдены ограничения РВ всех запросов Ω(Γ) .

Определение 13. Резерв времени на текущем интервале K (∆ t) –

это максимальное количество времени, которое может быть использовано для выполнения запросов Ω(A) на интервале [tC , tC + ∆ t] (где tC –

текущий момент времени, ∆ t – длина интервала) при условии, что будут соблюдены ограничения РВ всех запросов Ω(Γ) .

Определение 14. Резерв времени K – это максимальное количество времени, которое может быть использовано для непрерывного выполнения запросов Ω(A) от текущего момента времени при условии, что будут соблюдены ограничения РВ всех запросов Ω(Γ) . Следовательно, значение резерва времени – это максимальное значение ∆ t , удовлетворяющее условию ∆ t= S ∆( t) , то есть

чает никогда не достижимый самый высокий приоритет, например, можно считать, что π0real = −∞ .

Определение15. Резерв времени для задачи τi (обозначаемый Ki ) –

это максимальное количество времени, которое может быть использовано

запроса τi,Ci не будет нарушено ограничение РВ. При этом di,Ci – это крайний срок запроса τi,Ci .

Очевидна справедливость следующего утверждения.

64

Утверждение 5. Резерв времени определяется следующим образом:

делить только при условии, что нет спорадических задач и заранее известны значения Ci, j , например, Ci, j = CiUp для всех запросов всех пе-

риодических задач. В остальных случаях возможны только некоторые оценки значений K (∆ t) и K для крайних случаев.

Если есть спорадические задачи, то при определении K (∆ t) и K

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

Если значения Ci, j заранее не известны, то при определении K (∆ t) и K предполагается такой крайний случай, что Ci, j = CiUp для всех запросов всех периодических и спорадических задач.

2.6.3. Основные концепции планирования апериодических запросов

2.6.3.1.Фоновое выполнение

Вслучае фонового выполнения при поступлении апериодического запроса am в основную очередь Q этому запросу назначается приори-

тет πreal (am ) > πireal , i , то есть am имеет самый низкий приоритет среди

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

только если в очереди нет запросов ЖРВ. Следовательно, ограничения РВ всех запросов Ω(Γ) не нарушаются.

Однако при фоновом выполнении планирование является наименее эффективным по критерию обязательного МРВ (см. п. 2.3). Поэтому данная концепция планирования используется часто для целей сравнительного анализа эффективности других концепций планирования.

2.6.3.2. Алгоритмы захвата резерва

При поступлениизапроса am восновную очередь Q ему назначается приоритет πreal (am ) . И собственно планирование am в очереди Q осуществляется аналогично планированию запроса τi, j .

65

Были разработаны различные алгоритмы захвата резерва, при выполнении которых приоритет πreal (am ) может меняться в процессе

планирования.

Главная проблема разработки алгоритмов захвата резерва – это проблема определения значения πreal (am ) при поступлении am в Q и по-

следующего изменения этого значения.

Алгоритмы захвата резерва основаны на более или менее точном определении оценки резерва времени. При наличии am в очереди Q

проверяется, можно ли отложить, сдвинуть по времени выполнение запросов Ω(Γ) , не нарушая их ограничений РВ, то есть существует ли в данный момент резерв времени, что и определяется с помощью соответствующей оценки. Если необходимый резерв времени существует, то запросу am назначается приоритет πreal (am ) , который выше приоритетов всех или некоторых запросов из множества Ω(Γ) . Естественно, что выполнение запроса τi, j откладывается, то есть его выполнение сдвигается

по времени, если его приоритет ниже, чем πreal (am ) .

Было разработано несколько различных типов алгоритмов захвата резерва (табл. 3).

Так, можно выделить статический алгоритм захвата резерва [91], отличительной особенностью которого являются расчет составляющих резерва времени на этапе предварительного планирования (до старта системы) и сохранение вычисленных значений в памяти в виде массива. Недостаток алгоритма состоит в том, что этот алгоритм применим только для случая, когда отсутствуют спорадические задачи. Кроме того, необходимы значительные объемы памяти, чтобы хранить предварительно рассчитанную информацию о составляющих резерва времени.

Для устранения недостатков статического алгоритма захвата резерва может использоваться динамический алгоритм захвата резерва [35]. Согласно этому алгоритму расчет доступного резерва времени осуществляется в ходе планирования апериодических запросов в РВ, то есть во время функционирования СРВ. Этот алгоритм можно использовать для случаев, когда имеются спорадические задачи, но точный расчет резерва требует значительных вычислений, и во многих случаях данный алгоритм может быть неприменимым из-за слишком больших затрат процессорного времени на вычисления самого алгоритма.

66

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

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

ресурса.

2.6.3.3. Гиперпериод

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

где НОК – наименьшее общее кратное; Γ – множество периодических задач ЖРВ.

67

2.6.3.4. Выполненное время запроса и оставшееся время запроса

Определение 16. Выполненное время запроса ЖРВ λ(t, τi, j ) – это функция от времени, определяемая для любого запроса τi, j следующим образом:

λ(t, am ) – это функция от времени, определяемая для любого запроса ak следующим образом:

функция от времени, определяемая для любого запроса τi, j следующим образом:

c(t, am ) – это функция от времени, определяемая для любого запроса am следующим образом:

68

Очевидно, что если c(t, pi, j ) = 0 , то тогда и только тогда запрос τi, j

к моменту времени t уже завершил свое выполнение, а также если c(t, am ) = 0 , то тогда и только тогда запрос am к моменту времени t уже завершил свое выполнение.

2.6.3.5. Интервал выполнения запроса, множество запросов данного интервала времени

Определение 20. Интервал выполнения запроса – это интервал времени от времени старта этого запроса до времени завершения этого же запроса.

Интервал выполнения запроса τi, j – это интервал [si, j , fi, j ]. Интервал выполнения запроса am – это интервал [s(am ), f (am )] .

Определение 21. Пусть [s, f ] – это интервал выполнения некоторого запроса. Пусть [t1 , t2 ] – заданный интервал времени. Тогда, если выполняется хотя бы одно из следующих условий: t1 ≤ s≤ t2 , t1 ≤ f ≤ t2 ,

s < t1 ≤ t2< f , то [s, f ] пересекается с [t1 , t2 ] .

Определение 22. Множество запросов данного интервала времени

[t1 , t2 ] – это множество запросов, интервалы выполнения которых пересекаются с данным интервалом [t1 , t2 ] , это множество будет обозна-

чаться Ω(t1 , t2 ) .

Тогда, например, Ω(t1 , t2 ) ∩ Ω(τ i ) – это множество запросов, формируемых задачей τi и относящихся к множеству запросов данного интервала времени [t1 , t2 ] , а также Ω(t1 , t2 ) ∩ Ω(A) – это множество

ОАЗ и НАЗ, относящихся к множеству запросов данного интервала времени [t1 , t2 ] .

Определение 23. Пусть ΩSF(t1 , t2 ) обозначает множество всех запросов, для каждого из которых выполняется условие t1 ≤ s≤ f≤ t2 , где [s, f ] – интервал выполнения запроса, [t1 , t2 ] – некоторый интервал времени.

Определение 24. Пусть ΩCF(t1 , t2 ) обозначает множество всех запросов, для каждого из которых выполняется условие s < t1 ≤ f ≤ t2 , где [s, f ] – интервал выполнения запроса, [t1 , t2 ] – некоторый интервал времени.

69

Определение 25. Пусть ΩSC(t1 , t2 ) обозначает множество всех за-

вал времени.

Символ S в обозначении этих множеств означает, что время старта s каждого запроса находится в интервале времени [t1 , t2 ] . Символ F вобозначении этих множеств означает, что время завершения f каждого запроса находится в интервале времени [t1 , t2 ] . Символ C в обозначении

2.6.3.6. Интервальная загрузка, абсолютная интервальная загрузка

Определение 27. Интервальная загрузка U (t1 , t2 ) показывает процент занятого времени на некотором интервале времени [t1 , t2 ] и может

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

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

70