Лекции - Системы реального времени
Подождите немного. Документ загружается.
взаимодействуют друг с другом и, следовательно, не нуждаются в
синхронизации.
Периодическая задача характеризуется периодом Т (частота запуска) и
временем выполнения С (время ЦП, необходимое для завершения одного
запуска). Коэффициент использования ЦП для нее равен U = С/Т. Задача
называется планируемой, если она удовлетворяет всем временным
ограничениям, то есть ее исполнение завершается до истечения периода.
Группа задач именуется планируемой, когда планируемой является каждая
входящая в нее задача.
Пользуясь теорией планирования, можно показать, что группа
независимых периодических задач всегда удовлетворяет временным
ограничениям при условии, что сумма отношений С/Т по всем задачам меньше
некоторого граничного значения.
Теорема о верхней границе коэффициента использования ЦП гласит:
множество из n независимых периодических задач, планируемых согласно
алгоритму монотонных частот, всегда удовлетворяет временным ограничениям,
если
C
1
/T
1
+ ... + C
n
/T
n
≤ n(2
1/n
- 1) = U(n),
где С
i
и Т
i
– время выполнения и период задачи t
i
соответ ственно.
Другими словами, подмножество всего множества задач, состоящее из
задач с наивысшими приоритетами (то есть наименьшими периодами), все еще
бу дет у довлетворять временным ограничениям, если система в течение
короткого промежутка времени подвергается сверхрасчетной нагрузке. Задачи с
ни зким и приоритетами по ме ре повышения загрузки процессора могут
эпизодически выполняться дольше положенного времени.
Если для некоторого множества задач полный коэффициент
использования больше, чем требует теорема о верхней границе, то можно
прибегнуть к помощи теоремы о времени завершения, которая дает более
достоверный критерий. Она позволяет точно определить, является ли данное
множество независимых периодических задач планируемым. В этой теореме
предполагается худший случай, когда все периодические задачи готовы к
41
исполнению одновременно. Если в указанных условиях выполнение задачи
завершается до истечения ее первого периода, то она всегда будет
удовлетворять временным ограничениям. Таким образом, теорема о времени
завершения проверяет, способна ли каждая задача завершиться до истечения
своего первого периода.
Теорема о времени завершения гласит: если имеется такое множество
независимых периодиче ских задач, в котором каждая задача успевает
завершиться вовремя в случае, когда все задачи запускаются одновременно, то
все задачи смогут завершиться вовремя при любой комбинации моментов
запуска.
Планирование периодических и апериодических задач. Если имеются
как периодические, так и апериодические (асинхронные) задачи, то алгоритм
монотонных частот необходимо обобщить.
Предполагается, что апериодическая задача активизируется в случайный
момент времени и выполняется один раз в течение некоторого промежутка
в р е м е н и Т a , ко т о р ы й о б о з н ач а е т м и н и м а л ь н о е в р е м я м е ж д у
последовательными возникновениями события, активизирующего эту задачу.
Время ЦП С
a
, необходимое апериодической задаче для обработки события,
резервируется на каждом периоде Т
a
как своего рода квота. Когда поступает
событие, апериодиче ская задача активизируется, запрашивает квоту и
потребляет до С
a
единиц процессорного времени. Если в течение периода Т
a
задача так и не была активизирована, квота на этот период аннулируется. В
данных предположениях коэффициент использования ЦП апериодической
задачей равен С
a
/Т
a
.
Планирование с синхронизацией задач. Теория планирования в
реальном времени распространяется и на синхронизацию задач. Проблема здесь
в том, что задача, входящая в критическую область, может блокировать другие
более приоритетные задачи, которые хотят войти в ту же область. Ситуация,
когда низкоприоритетная задача не дает выполняться высокоприоритетной,
называется инверсией приоритетов. Обычно это связано с тем, что первая
задача захватывает ресурс, который нужен второй.
42
Неограниченная инверсия приоритетов возникает, когда
низкоприоритетная задача, находящаяся в критиче ской области, с ама
заблокирована другими более приоритетными задачами. Одно из решений
данно й проблемы состоит в т ом, чт обы запре тить выт еснение задач,
находящихся в критической секции. Но это приемлемо, если время пребывания
в критической секции очень мало. В противном случае низкоприоритетная
задача способна заблокировать высокоприоритетные задачи, которым нужен
разделяемый ресурс.
Протокол предельного приоритета позволяет избежать тупиковой
ситуации и гарантирует ограниченную инверсию приоритетов за счет того, что
высокоприоритетная задача может блокироваться самое большее одной
низкоприоритетной.
Чтоб ы пред от вратит ь задержку выс окоп рио рит етн ых задач
низкоприоритетными на долгое время, применяется коррекция приоритетов.
Когда низкоприоритетная задача t
1
оказывает ся в критической области, она в
состоянии блокировать высокоприоритетные задачи, которым нужен тот же
ресурс. Если это происходит, то приоритет t
1
повышается до максимального из
приоритетов блокируемых задач.
43
22 АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ ПРОЕКТА
ПАРАЛЛЕЛЬНЫХ СИСТЕМ
На этапе определения требований задает ся время реакции системы на
внешние события. После разбиения на задачи можно предпринять первую
попытку выделен ия временных бюджет ов параллельным задачам. Для
выявления задач, которые необходимо в ыполнить при обслуживании данного
внешнего события, используется анализ последовательности событий.
Чтобы показать последовательность событий и задач, активизируемых
приходом внешнего события, применяется диаграмма последовательности
событий, основанная на диаграмме параллельной кооперации.
Следует рассмотреть внешнее событие, определить, какая задача ввода/
вывода активизируется таким событием и какая ожидается цепочка внутренних
событий. Для этого необходимо знать, какие задачи активизируются и какие
задачи ввода/вывода генерируют отклик системы на внешнее событие. Далее
нужно оценить время ЦП, потребляемое каждой задачей, и накладные расходы,
состоящие из затрат на контекстное переключение, обработку прерывания и
межзадачные коммуникации и синхронизацию. Надо проанализировать также
другие задачи, выполняемые в тот же период времени. Суммарное время ЦП,
потребляемое всеми задачами, которые участвуют в цепочке событий, и всеми
дополнительными задачами, которые исполнялись в то же время, плюс
накладные расходы – все вместе не должно превысить заданное время реакции
системы. Если точное время ЦП, потребляемого каждой задачей, неизвестно, то
следует принимать оценку для худшего случая.
Для анализа полного коэффициента и с п ользования ЦП необходимо
рассчитать время, потребляемо е каждой задачей на данном интервале. Если
существует несколько путей выполнения задачи, то нужно получить оценку
времени для каждого из них. Затем следует оценить частоту активизации задач.
Анализ последовательности событий сочетается с теорией планирования
в реальном времени. Вместо того чтобы рассматривать задачи по отдельности,
необходимо изучить все задачи, участвующие в н екоторой последовательности
44
событий. Сначала исполняется задача, активизируемая внешним событием,
которая инициирует цепочку внутренних событий, а они, в свою очередь,
активизируют другие задачи. Необходимо убедиться, что все задачи, вошедшие
в цепочку, способны завершить исполнение вовремя.
Для этого сначала вс ем задачам в цепочке назначаются одинаковые
приоритеты. С точки зрения теории планирования в реальном времени вместо
них можно рассмотреть одну эквивалентную задачу. Она потребляет время,
которое равно сумме времен, потребляемых всеми задачами в группе, плюс
затраты на контекстное переключение, меж задачные коммуникации и
синхронизацию. В качестве периода эквивалентной задачи устанавливает ся
время в худ ш е м случае между последовательными приходами внешнего
события, активизирующего цепочку.
Чтобы определить, удовлетворяет ли эквивалентная задача временным
ограничениям, нужно применить теоремы из теории планирования в реальном
времени.
Иногда задачи, участвующие в обработке последовательности событий,
нельзя заменить одной эквивалентной задачей. Например, это невозможно, если
одна из задач встречается в нескольких последовательных задачах или если
исполнение эквивалентной задачи с тем же приоритетом будет препятствовать
своевременному завершению других задач. В таких случаях задачи следует
анализировать по отдельности и назначать им различные приоритеты. При
решении вопро са о том, смогут ли задачи в цепочке событий удовлетворить
временным ограничениям, необходимо учитывать в ытеснение и блокировку для
каждой задачи в отдельности, но не менее важно рассчитать, завершатся ли в
срок все задачи в последовательности.
45