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

Лекции - Часть 11
скачать (1838.1 kb.)
Доступные файлы (1):
n1.doc2070kb.01.09.2004 21:02скачать
Победи орков

Доступно в Google Play

n1.doc

  1   2   3   4   5   6   7   8   9   10
11. Анализ производительности проекта параллельной системы
Анализ производительности проекта особенно важен для систем реального вре­мени. Если такая система не справляется со своими задачами в течение отведен­ного интервала, последствия могут быть катастрофическими.

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

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

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

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

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

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

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

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

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

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

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

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

Верхняя граница 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



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

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

Задача t2: C2 = 30; Т2 = 150; U2= 0,2.

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

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

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

Задача t3: C3 = 90; Т3 = 200; U3= 0,45.

Теперь полный коэффициент использования ЦП равен 0,85,
  1   2   3   4   5   6   7   8   9   10


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации