Лекции - Часть 11 - файл n1.doc

Лекции - Часть 11
скачать (1838.1 kb.)
Доступные файлы (1):

2070kb.

01.09.2004 21:02

n1.doc

1 2 3 4 5 6 7 8 9 10

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

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

Ниже речь пойдет о способе анализа производительности проекта ПО, основанном на теории планирования в реальном времени. Этот метод прекрасно работает для систем реального времени, которые должны выдерживать жесткие временные ограничения [24]. Он позволяет определить, будут ли выполнены наложенные ограничения.

Мы опишем два подхода к анализу производительности. В первом используется теория планирования в реальном времени, а во втором – анализ последовательности событий. Затем мы объединим оба подхода. Каждый из них применим к проектам, состоящим из набора параллельных задач. Следовательно, анализ производительности можно начинать сразу после проектирования архитектуры задач.
11.1. Теория планирования в реальном времени

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

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

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

Периодическая задача характеризуется периодом Т (частота запуска) и временем выполнения С (время ЦП, необходимое для завершения одного запуска). Коэффициент использования ЦП для нее равен U = С/Т. Задача называется планируемой (schedulable), если она удовлетворяет всем временным ограничениям, то есть ее исполнение завершается до истечения периода. Группа задач именуется планируемой, когда планируемой является каждая входящая в нее задача.

Если дано множество независимых периодических задач, то алгоритм монотонных частот назначает каждой задаче фиксированный приоритет, вычисляемый на основе ее периода: чем короче период, тем выше приоритет. Рассмотрим задачи t_a, t_b и t_c с периодами 10, 20 и 30 соответственно. Наивысший приоритет будет назначен задаче t_a с самым коротким периодом, средний приоритет - задаче t_b а самый низкий – задаче t_c, период которой максимален.

11.1.2. Теорема о верхней границе коэффициента использования ЦП. Пользуясь теорией планирования, можно показать, что группа независимых периодических задач всегда удовлетворяет временным ограничениям при условии, что сумма отношений С/Т по всем задачам меньше некоторого граничного значения.

Теорема о верхней границе коэффициента использования ЦП (теорема 1) гласит:

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

где С_i и Т_i – время выполнения и период задачи t_i соответственно.

Верхняя граница U(n) стремится к 69% (ln 2), когда число задач стремится к бесконечности. Значения верхней границы для числа задач от 1 до 9 приведены в табл.11.1. Это оценка для худшего случая, но, как показано в работе [22], для случайно выбранной группы задач вероятная верхняя граница равна 88%. Если периоды задач гармоничны (являются кратными друг другу), то верхняя граница оказывается еще выше.
Таблица 11.1

Теорема о верхней границе коэффициента использования

Число задач n	Верхняя граница коэффициента использования U(n)
1	1,000
2	0,828
3	0,779
4	0,756
5	0,743
6	0,734
7	0,728
8	0,724
9	0,720
Бесконечность	0,690

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

Применим теорему о верхней границе коэффициента использования к трем задачам со следующими характеристиками (время всюду выражено в миллисекундах):
Задача t₁: С₁ ⁼ 20; Т₁ ⁼ 100; U₁= 0,2.

Задача t₂: C₂ = 30; Т₂ = 150; U₂= 0,2.

Задача t₃: С₃ = 60; Т₃ = 200; U₃= 0,3.
Предполагается, что накладные расходы на контекстное переключение, происходящее один раз в начале и один раз в конце выполнения задачи, содержатся в оценке времени ЦП.

Полный коэффициент использования ЦП для всех трех задач равен 0,7, что ниже, чем величина 0,779, которую дает теорема о верхней границе. Таким образом, эти задачи будут удовлетворять временным ограничениям.

Но попробуем изменить характеристики третьей задачи:

Задача t₃: C₃ = 90; Т₃ = 200; U₃= 0,45.

Теперь полный коэффициент использования ЦП равен 0,85,

1 2 3 4 5 6 7 8 9 10