Анализ производительности проекта параллельной системы

Размещено на http://www.allbest.ru/

Анализ производительности проекта параллельной системы

Введение

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

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

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

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

1. Теория планирования в реальном времени

производительность проект планирование

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

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

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

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

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

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

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

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

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

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

Таблица 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, то есть выше, чем 0,779. Следовательно, теорема о верхней границе не дает гарантии, что задачи смогут удовлетворить временным ограничениям. Далее нужно проверить, так ли это для первых двух задач.

Принимая во внимание устойчивость алгоритма монотонных частот, для подобной проверки допустимо применить теорему о верхней границе коэффициента использования ЦП. Для первых двух задач полный коэффициент равен 0,4, то есть намного ниже значения, полученного из теоремы (0,828). Значит, эти задачи всегда удовлетворяют временным ограничениям. Учитывая, что теорема о верхней границе дает пессимистическую оценку, мы можем проверить, является ли задача t3 планируемой, посредством более точной теоремы о времени завершения.

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

Теорема о времени завершения (теорема 2) гласит:

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

Чтобы убедиться в выполнении условий теоремы, необходимо проверить момент завершения первого периода для данной задачи ti, а также моменты завершения периодов всех задач с более высоким приоритетом. Согласно алгоритму монотонных частот, периоды подобных задач будут меньше, чем для задачи ti. Эти периоды называются точками планирования. Задача t. один раз займет ЦП на время Сi в течение своего периода Тi. Но более приоритетные задачи будут выполняться чаще и могут по крайней мере один раз вытеснить ti. Поэтому нужно учесть также время ЦП, затраченное на более приоритетные задачи.

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

Задача t1: С1 = 20; Т 1= 100; U1= 0,2.

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

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

Их выполнение показано на временной диаграмме на рис.11.1. В методе COMET временная диаграмма - это диаграмма последовательности с временными метками. Заштрихованные участки обозначают интервалы времени, в течение которых реализуется данная задача. Поскольку в приведенном примере есть всего один процессор, то в каждый момент времени выполняется только одна задача.

В худшем случае, когда все три задачи готовы к работе одновременно, первой запускается t1, так как у нее самый короткий период и, значит, самый высокий приоритет. Она завершается по прошествии 20 мс, после чего в течение 30 мс исполняется задача t2 а затем t3 В конце первой точки планирования Т1 = 100, что соответствует сроку завершения t1; t1 уже завершена и, следовательно, удовлетворяет временным ограничениям. Задача t2 также завершила работу задолго до срока, а задача t3 потратила 50 мс из необходимых 90.

В начале второго периода t1 задача t3 вытесняется задачей t3. Проработав 20 мс, t2 завершается и уступает процессор задаче t3. Задача t3 выполняется до конца периода Т2 (150 мс), который соответствует второй точке планирования, определяемой сроком завершения t2. Поскольку t2 завершилась до момента Т1 (меньшего, чем Т2), то она уложилась в отведенный для нее срок. В этот момент t3 использовала 80 мс из необходимых 90.

В начале второго периода задачи t2 она вытесняет задачу t3 Проработав 30 мс, t2 завершается и возвращает процессор задаче t3 Задача t3 исполняется еще 10 мс, И в этот момент заканчиваются ее 90 мс, то есть она успела завершиться до истечения своего срока. На рис.11.1 изображена третья точка планирования, которая расположена в конце второго периода t1 (2T1= 200) и одновременно в конце первого периода t3 (T3 = 200). Из рисунка видно, что каждая задача завершает исполнение до конца своего первого периода, так что все вместе они удовлетворяют временным ограничениям.

На рис.11.1 показано, что ЦП простаивает 10 мс перед началом третьего периода t1 (этот момент совпадает с началом второго периода t3). Отметим, что на протяжении интервала длительностью 200 мс процессор работал 190 мс, то есть задействовался на 95%, хотя полный коэффициент использования равен 0,85. По истечении времени, равного наименьшему общему кратному трех периодов (для данного примера 600 мс) средний коэффициент использования оказывается равным 0,85.

Рис. 1. Временная диаграмма (диаграмма последовательности с временными метками)

Строгая формулировки теоремы о времени завершения.

Теорему о времени завершения можно строго сформулировать следующим образом [24] (теорема 3):

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



,

где Сi и Тi - время выполнения и период задачи tj соответственно, а

Ri = {(k,p): l?k?i, p=l,...,[Ti/Tk]}.

В этой формуле ti - это проверяемая задача, a tk - любая из более приоритетных задач, влияющих на время выполнения ti. Для данной пары задач ti и tk каждое значение р представляет некоторую точку планирования задачи tk. В каждой точке планирования необходимо рассмотреть один раз время ЦП Сi, потраченное на задачу ti, а также время, израсходованное на более приоритетные задачи. Это позволит определить, успеет ли ti завершить выполнение к данной точке планирования.

Рассмотрим применение теоремы 3 к трем задачам, показанным на рис.11.1. Временная диаграмма - это графическое представление вычислений, выполняемых в теореме 3. Снова обратимся к худшему случаю, когда все три задачи одновременно готовы к выполнению. Из теоремы 3 вытекает неравенство для первой точки планирования Т1 = 100:

С1 + C2+ С3 < Т1;

20 + 30 + 90 > 100;

p=l, k=l.

Чтобы это неравенство удовлетворялось, все три задачи должны завершиться на протяжении первого периода Т1 задачи t1. Это не так: прежде чем задача t3 успевает завершиться, ее вытесняет задача t1 в начале своего второго периода.

Теорема 3 дает также неравенство для второй точки планирования Т2 = 150:

2С1 + С2 + С3 ? Т2;

40 + 30 + 90 > 150;

p=l, k=2.

Чтобы полученное неравенство удовлетворялось, задача t1 должна завершиться дважды, а задачи t2 и t3 - по одному разу на протяжении периода Т2 задачи t2. И это не так, поскольку задача t3 вытесняется задачей t2 в начале второго периода t2.

Неравенство для третьей точки планирования, которая находится в конце второго периода t1 (2Т1 = 200) и одновременно в конце первого периода t3 (T3 = 200), выглядит следующим образом:

2С1 + 2С2 + C3 ? 2Т1 = Т3;

40 + 60 + 90 < 200;

р = 2, k = 1 или р = 1, k = 3.

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

11.1.5. Планирование периодических и апериодических задач. Если имеются как периодические, так и апериодические (асинхронные) задачи, то алгоритм монотонных частот необходимо обобщить. Предполагается, что апериодическая задача активизируется в случайный момент времени и выполняется один раз в течение некоторого промежутка времени Тa, который обозначает минимальное время между последовательными возникновениями события, активизирующего эту задачу. Время ЦП Сa, необходимое апериодической задаче для обработки события, резервируется на каждом периоде Тa как своего рода квота. Когда поступает событие, апериодическая задача активизируется, запрашивает квоту и потребляет до Сa единиц процессорного времени. Если в течение периода Тa задача так и не была активизирована, квота на этот период аннулируется. В данных предположениях коэффициент использования ЦП апериодической задачей равен Сa/Тa. Однако здесь приведена оценка для худшего случая, так как, вообще говоря, квоты требуются не всегда.

Если в приложении имеется много апериодических задач, разрешается воспользоваться алгоритмом спорадического сервера [25]. С точки зрения анализа планируемости апериодическая задача (называемая спорадическим сервером) эквивалентна периодической задаче с периодом, равным минимальному времени между возникновениями событий, которые активизируют апериодическую задачу. Поэтому Тa удобно считать периодом эквивалентной периодической задачи. Каждой апериодической задаче выделяется бюджет, равный Сa единиц времени процессора, который может быть использован в любой момент на протяжении периода Тa. Таким образом, апериодическим задачам допустимо назначить различные уровни приоритета в соответствии с эквивалентными периодами и рассматривать их как периодические.

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

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

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

Чтобы предотвратить задержку высокоприоритетных задач низкоприоритетными на долгое время, применяется коррекция приоритетов. Когда низкоприоритетная задача t1 оказывается в критической области, она в состоянии блокировать высокоприоритетные задачи, которым нужен тот же ресурс. Если это происходит, то приоритет t1 повышается до максимального из приоритетов блокируемых задач. Цель состоит в том, чтобы ускорить выполнение низкоприоритетной задачи и сократить время ожидания для высокоприоритетных.

Предельный приоритет Р двоичного семафора S - максимум из приоритетов всех задач, которые могут занять данный семафор. Таким образом, низкоприоритетная задача, захватившая S, способна повысить свой приоритет до Р в зависимости от того, какие задачи она блокирует.

Еще одна возможная проблема - это тупиковая ситуация (deadlock), которая возникает, когда двум задачам нужно захватить по два ресурса. Если каждая задача захватит по одному ресурсу, то ни одна не сможет завершиться, поскольку будет ждать, пока другая освободит ресурс. Протокол предельного приоритета справляется и с такой трудностью [24].

Теоремы о планировании методом монотонных частот необходимо обобщить на задачу об инверсии приоритетов. В следующем разделе мы покажем, как это сделать.

2. Развитие теории планирования в реальном времени

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

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

Инверсия приоритетов. Термин «инверсия приоритетов» применяется к любой ситуации, когда некоторая задача не может продолжить выполнение, поскольку блокирована другой задачей с более низким приоритетом. В случае алгоритма монотонных частот под приоритетом понимается частотно-монотонный приоритет, назначенный задаче исключительно на основе длины ее периода, без учета относительной важности. В реальности задаче допустимо назначить приоритет, отличный от частотно-монотонного. Когда говорят об инверсии частотно-монотонных приоритетов, то имеют в виду, что задача А вытеснена задачей В хотя частотно-монотонный приоритет задачи В меньше, чем задачи А (то есть период В длиннее периода А).

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

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

Рассмотрим задачу ti с периодом Тi, в течение которого она потребляет С единиц времени процессора. Если мы хотим обобщить теоремы 1-3, то необходимо явно рассмотреть каждую задачу ti, чтобы определить, успевает ли она завершиться до своего первого срока. Для любой задачи нужно принять во внимание четыре фактора:

- время вытеснения более приоритетными задачами с периодами меньшими, чем у ti. Такие задачи способны вытеснять ti многократно. Обозначим множество таких задач Нn и предположим, что оно состоит из j задач. Пусть Сj - процессорное время, потребляемое задачей j, а Тj - период этой задачи, причем Тj < Тi. Коэффициент использования процессора задачей j из множества Нn равен Сj / Тj;

- время выполнения задачи ti. Задача ti выполняется один раз в течение своего периода Тi и потребляет Сi единиц времени процессора;

- вытеснение более приоритетными задачами с большими периодами. Это задачи, приоритеты которых отличны от частотно-монотонных. Они могут вытеснять ti только один раз, так как их периоды длиннее, чем у ti. Назовем множество таких задач Н1 и предположим, что оно состоит из k задач. Пусть время, потребляемое k-ой задачей из этого множества, равно Сk. Коэффициент использования ЦП для k-ой задачи в худшем случае равен Сk / Тi, так как при этом задача k вытесняет t и использует все свое время С, на периоде Тi;

- время блокировки задачами с более низким приоритетом (см. предыдущий раздел). Эти задачи могут выполняться только один раз, поскольку имеют более длинные периоды. Задержки из-за блокировки нужно анализировать отдельно для каждой задачи, чтобы определить ситуацию в худшем случае, описываемую протоколом предельного приоритета. Если Вi - время блокировки для задачи ti в худшем случае, то коэффициент использования ЦП (тоже в худшем случае) для периода Тi составляет Вi / Тi.

Обобщенная теорема о верхней границе коэффициента использования ЦП. Поскольку для любой задачи ti факторы 1 и 2 из предыдущего раздела уже учитываются теоремами 1-3, то при обобщении данных теорем надо принять во внимание только факторы 3 и 4. С учетом всех четырех факторов обобщенная теорема о верхней границе коэффициента использования формулируется следующим образом.

Обобщенная теорема о верхней границе коэффициента использования (теорема 4):

Здесь Ui - верхняя граница коэффициента использования ЦП за период Тi для задачи ti. Первый член в полученной формуле - суммарное использование за счет вытеснения высокоприоритетными задачами с периодом меньшим, чем у ti. Второй член соответствует использованию процессора задачей ti Третий член учитывает время блокировки задачи ti в худшем случае, а четвертый - суммарное время вытеснения этой задачи более приоритетными, но с периодами меньшими, чем у ti.

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

Обобщенная теорема о времени завершения. Как и раньше, если обобщенная теорема о верхней границе коэффициента использования не дает результата, допустимо применить более точный тест, позволяющий проверить, сможет ли задача завершиться в течение своего периода. Это обобщенная теорема о времени завершения. Она определяет, закончит ли задача ti выполнение к концу своего периода в условиях вытеснения задачами с более высокими приоритетами и блокировки задачами с более низкими приоритетами. В данной теореме предполагается худший случай, когда все задачи готовы к работе в начале периода ti. Графически обобщенную теорему о времени завершения можно представить, нарисовав временную диаграмму для всех задач вплоть до момента завершения периода Тi задачи ti.

Планирование в реальном времени и проектирование. Теорию планирования в реальном времени можно применить к множеству параллельных задач либо на этапе проектирования, либо уже после реализации всех задач. Поскольку во время проектирования для времени ЦП существуют только приблизительные оценки, нужно быть осторожнее и при разработке задач реального времени с жесткими временными ограничениями полагаться на пессимистическую теорему о верхней границе коэффициента использования. Эта теорема дает верхнюю границу 0,69 в худшем случае, хотя теория планирования в реальном времени часто указывает более высокие значения. Если верхняя граница в худшем случае не может быть достигнута, придется изучить альтернативные решения. С точки зрения проектировщика-пессимиста, оценка верхней границы коэффициента выше 0,69 приемлема при условии, что использование сверх 0,69 целиком обусловлено низкоприоритетными задачами с мягкими временными ограничениями или задачами, которые могут исполняться не в реальном масштабе времени. Для таких задач эпизодический пропуск срока выполнения не столь важен.

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

Пример применения обобщенной теории планирования в реальном времени. В качестве примера рассмотрим следующий случай. Есть четыре задачи: две периодические и две апериодические. Апериодическая задача ta управляется прерываниями и должна успеть выполниться в течение 200 мс после прерывания, иначе данные будут потеряны. Для другой апериодической задачи время между событиями в худшем случае равно Т2 и оно принимается равным периоду эквивалентной периодической задачи. Ниже приведены детальные характеристики задач, причем время указано в миллисекундах, а коэффициент использования Ui=Ci/Ti.

Периодическая задача t1: С1 = 20; Т1 = 100; U1 = 0,2.

Апериодическая задача t2: С2 = 15; Т2 = 150; U2 = 0,1.

Управляемая прерываниями задача ta: Сa = 4; Тa = 200; Ua = 0,02.

Периодическая задача t3: C3 = 30; T3 = 300; U3 = 0,1.

Кроме того, известно, что задачи t1, t2 и t3 обращаются к одному и тому же хранилищу данных, защищенному семафором S. Предполагается, что затраты на контекстное переключение, один раз в начале и один раз в конце выполнения задачи, входят в потребляемое процессорное время.

Задачам назначены приоритеты в строгом соответствии с алгоритмом монотонных частот, то есть t1 имеет наивысший приоритет, а за ней следуют t2, ta и t3 Но, поскольку для ta время реакции жестко ограничено, ей присвоен наивысший приоритет, а уже потом идут t1, t2 и t3

Полный коэффициент использования ЦП равен 0,42, то есть ниже верхней границы в худшем случае (она равна 0,69). Однако необходимо исследовать каждую задачу отдельно, поскольку приоритеты отличаются от частотно-монотонных.

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

Далее разберем задачу t1, которая исполняется 20 мс на протяжении своего периода Т1, равного 100 мс. Для применения обобщенной теоремы о верхней границе коэффициента использования надо принять во внимание четыре фактора:

- время вытеснения более приоритетными задачами с периодами меньшими, чем Т1. Таких задач нет;

- время выполнения С1 задачи t1 равно 20. Коэффициент использования U1 = 0,2;

- вытеснение более приоритетными задачами с большими периодами. В эту категорию попадает задача ta. Коэффициент использования за счет вытеснения на периоде Т1 равен Сa/Т1 = 4/100 = 0,04;

- время блокировки задачами с более низким приоритетом. Потенциально заблокировать t1 могут задачи t2 и t3. Учитывая алгоритм предельного приоритета, мы заключаем, что на самом деле блокировать t1 может только одна низкоприоритетная задача. В худшем случае это будет t3, поскольку она потребляет больше всего процессорного времени - 30 мс. Коэффициент использования за счет блокировки на периоде Т1 составляет B3/Т1 = 30/100 = 0,3.

Коэффициент использования в худшем случае равен сумме всех полученных коэффициентов, то есть 0,04 + 0,2 + 0,3 = 0,54, что меньше верхней границы 0,69. Следовательно, t1 удовлетворяет временным ограничениям.

Далее рассмотрим задачу t2 которая выполняется 15 мс в течение своего периода Т2 длительностью 150 мс. Как и выше, обратим внимание на четыре фактора:

- время вытеснения более приоритетными задачами с периодами меньшими, чем Т2. Только одна задача t1 имеет такой период. Ее коэффициент использования за счет вытеснения равен U1=0,2;

- время выполнения С2 задачи t2 равно 15. Коэффициент использования U2 = 0,1;

- вытеснение более приоритетными задачами с большими периодами. В эту категорию попадает управляемая прерываниями задача ta. Коэффициент использования за счет вытеснения на периоде Т2 равен Сa/Т2 = 4 / 150 = 0,03. Полный коэффициент использования за счет вытеснения задачами t1 и ta составляет 0,2 + 0,03 = 0,23;

- время блокировки задачами с более низким приоритетом. Задача t3 может блокировать t2. В худшем случае время блокировки составит 30 мс. Коэффициент использования за счет блокировки на периоде Т2 равен B3 / Т2 = 30 / 150 = 0,2.

Коэффициент использования в худшем случае составит 0,23+0,1+0,2 = 0,53, то есть меньше 0,69. Следовательно, и t2 удовлетворяет временным ограничениям.

Осталось рассмотреть задачу t3 которая выполняется 30 мс на протяжении своего периода T3 продолжительностью 300 мс. Снова применим обобщенную теорему о верхней границе:

- время вытеснения более приоритетными задачами с периодами меньшими, чем Т3. Все три высокоприоритетные задачи попадают в эту категорию, так что полный коэффициент использования за счет вытеснения равен U1 + U2 + Ua = 0,2 +0,1 + 0,02 = 0,32;

- время выполнения C3 задачи t3 равно 30. Коэффициент использования U3 = 0,1;

- вытеснение более приоритетными задачами с большими периодами. Таких задач нет;

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

Коэффициент использования в худшем случае составит 0,32 + 0,1 = 0,42, то есть меньше 0,69. Значит, t3 также удовлетворяет временным ограничениям. Итак, все четыре задачи успевают выполниться в срок.

3. Анализ производительности с помощью анализа последовательности событий

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

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

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

4. Анализ производительности с помощью теории планирования в реальном времени и анализа последовательности событий

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

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

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

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

5. Пример анализа производительности с помощью анализа последовательности событий

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

Вначале проанализируем случай, когда водитель переводит ручку круиз-контроля в положение «Разгон», инициируя тем самым автоматическое ускорение машины. В требованиях к системе записано, что система должна отреагировать на это действие в течение 250 мс. Последовательность внутренних событий, вызванных действием водителя, показана на диаграмме параллельной кооперации (рис.11.2).

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

С1: От внешнего устройства Ручка Круиз-Контроля поступает прерывание Круиз-Контроля.

С2: Интерфейс Ручки Круиз-Контроля получает входную информацию «Разгон» от Ручки Круиз-Контроля.

С3: Интерфейс Ручки Круиз-Контроля отправляет сообщение, содержащее запрос объекту Круиз-Контроль.

С4: Объект Круиз-Контроль принимает сообщение, исполняет свою диаграмму состояний и изменяет состояние с Начальное на Разгон.

С5: Объект Круиз-Контроль посылает команду на увеличение скорости объекту Корректировка Скорости.

С6: Объект Корректировка Скорости выполняет команду и вычисляет значение дросселя.

С7: Объект Корректировка Скорости передает сообщение, содержащее значение дросселя, задаче Интерфейс Дросселя.

С8: Интерфейс Дросселя вычисляет новое положение дроссельной заслонки.

С9: Интерфейс Дросселя посылает информацию о положении дроссельной заслонки физическому дросселю. (С9 - это операция вывода, на которую ЦП время не тратит.)

На диаграмме последовательности событий (см. рис.11.2) показано, что для обработки внешнего события «Разгон» требуется четыре задачи (Интерфейс Ручки Круиз-Контроля, Круиз-Контроль, Корректировка Скорости и Интерфейс Дросселя). Поэтому имеется как минимум четыре контекстных переключения, на которые тратится время 4Сx , где Сx - время, необходимое для одного переключения.

Полное время, которое ЦП расходует на эти четыре задачи (Сe ), равно сумме времен выполнения каждой задачи и времени, необходимого для межзадачных коммуникаций, плюс затраты на контекстное переключение:

Сe = С1 + C2 + С3 + С4 + С5 + С6 + С7 + С8 + 4Сx .



Рис. 2. Последовательность событий в системе круиз-контроля после действия водителя

Предположим, что затраты на межзадачные коммуникации Сm постоянны. Тогда С3, С5 и С7 равны Сm, так что полное время выполнения составит

Сe = С1 + C2 + С4 + С6 + С8 + 3Сm + 4Сx . (уравнение 1)

Чтобы определить время реакции системы, необходимо также принять во внимание другие задачи, которые способны выполняться, пока система обрабатывает внешнее событие. Посмотрим, какие еще задачи представлены на рис.11.2. Предположим, что задача Автодатчики (С10) активизируется каждые 100 мс, поэтому в течение 250 мс она может отработать три раза. Задача Интерфейс Вала (С11) выполняется при каждом обороте вала и потому в течение того же временного промежутка может быть активизирована до 25 раз (то есть каждые 10 мс) в предположении, что максимальная скорость вращения вала составляет 6000 об/мин. Наконец, задача Путь и Скорость (С12) активизируется четыре раза в секунду и, следовательно, будет запущена только единожды. Каждый раз, как управление получает новая задача, происходит два контекстных переключения, если предположить, что текущая задача вытесняется и продолжает работу после завершения прервавшей ее задачи. Таким образом, эти три задачи могут привести к 58 дополнительным переключениям.

Итак, общее время Сa, затраченное системой на три дополнительные задачи, с учетом накладных расходов составит

Сa = 3(С10 + 2Сx) + 25(С11 + 2Сx) + (С12 + 4Сx) (уравнение 2)

Полное время ЦП не должно превышать предельное время реакции, указанное в требованиях к системе. Это полное время равно

Сt = Сe + Сa (уравнение 3)

Прежде чем решать приведенные уравнения, нужно оценить каждый из временных параметров (табл.11.2). Так как ЦП рассчитан на работу в реальном времени, допустимо предположить, что время контекстного переключения составляет 0,5 мс.

Таблица 2

Затраты процессорного времени в подсистеме Круиз-Контроль

Задача	С, (мс)	Периодические задачи(Ci + 2Cx) мс	Задачи, участвующие в обработке последо-вательности событий(Ci + Cx + Сm) мс
1	2	3	4
Прерывание Круиз-Контроля (С1)	1
Интерфейс Ручки Круиз-Контроля (С2)	4
Всего на Ввод от Круиз-Контроля (С1 + С2)	5		6
Круиз-Контроль(С4)	6		7
Корректировка Скорости (C6)	14	15	16
Интерфейс Дросселя (С8)	5	6	6
Затраты на Межзадачные Коммуникации (Сm)	1
Затраты на Контекстное Переключение (Сx)	0,5
Автодатчики (С10)	5	6
Интерфейс Вала (С11)	1	2
Путь и Скорость (С12)	10	11

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

Подстановка данных из табл.11.2 в уравнение 1 дает оценку Сe = 35 мс. Подстановка в уравнение 2 дает Сa = 79 мс. Следовательно, из уравнения 3 получаем оценку полного времени ЦП: Сt == 114 мс. Это намного меньше, чем 250 мс.

Можно поэкспериментировать с другими значениями параметров, чтобы проверить, насколько оценка времени реакции чувствительна к ошибкам. Например, если окажется, что на контекстное переключение уходит 1 мс, а не 0,5 мс, то Сe возрастет до 37 мс, а Сa - до 108 мс. В результате полное время ЦП составит 145 мс, что на 31 мс больше первоначальной оценки, но все же далеко до предельных 250 мс.

6. Пример анализа производительности с применением теории планирования в реальном времени

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

Проанализируем худший случай, когда от ЦП требуется больше всего времени: машина движется в режиме автоматического управления с максимальной скоростью вращения вала. Пусть период j-ой периодической задачи равен Тj, время ее выполнения Сj, а коэффициент использования ЦП Uj = Сj / Тj. Во время, потребляемое каждой периодической задачей, включены затраты на два контекстных переключения. В табл.11.3 приведены характеристики всех периодических задач.

Таблица 3

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

Задача	Время ЦП Сi	Период Тi	Коэффициент использования Ui	Приоритет
Интерфейс Вала	2	10	0,20	1
Автодатчики	6	100	0,06	2
Путь и Скорость	11	250	0,04	4
Калибровка	5	500	0,01	6
Корректировка Скорости	15	250	0,60	5
Интерфейс Дросселя	6	100	0,06	3
Интерфейс Кнопки Сброса	4	500	0,01	7
Таймер Средних Показателей	20	1000	0,02	9
Интерфейс Кнопки Сброса Обслуживания	6	1000	0,01	8
Таймер Обслуживания	15	2000	0,01	10

Полный коэффициент использования Un равен 0,48.

Рассмотрим названные периодические задачи:

- Интерфейс Вала. Предполагается, что эта задача периодическая. На самом деле она апериодическая, так как активизируется прерыванием от вала. Однако прерывания поступают регулярно, при каждом обороте вала, так что задача ведет себя как периодическая. Планируется худший случай, когда вал вращается со скоростью 6000 об/мин, то есть прерывания возникают каждые 10 мс, что составляет минимальный период эквивалентной периодической задачи. Поскольку период данной задачи самый короткий, то ей назначен наивысший приоритет. Время выполнения составляет 2 мс с учетом затрат на два контекстных переключения по 0,5 мс каждое;

- Автодатчики. Период данной задачи равен 100 мс, а время выполнения с учетом контекстных переключений составляет 6 мс;

- Путь и Скорость. Период этой задачи 250 мс, а время выполнения - 11 мс;

- Калибровка. Период равен 500 мс, время выполнения - 5 мс;

- Корректировка Скорости. При активизации в режиме автоматического управления задача выполняется каждые 250 мс и вычисляет значение дросселя, на что уходит 15 мс;

- Интерфейс Дросселя. При активизации в режиме автоматического управления задача выполняется каждые 1000 мс и выводит новое положение дроссельной заслонки, на что уходит 6 мс;

- Интерфейс Кнопок Сброса Средних Показателей. Период равен 500 мс, время выполнения - 4 мс;

- Таймер Средних Показателей. Эта задача выполняется сравнительно редко, ее период составляет 1 с, а время ЦП - 20 мс. Она некритична по времени;

- Интерфейс Кнопки Сброса Обслуживания. Период равен 1с, время выполнения - 6 мс;

- Таймер Обслуживания. Эта задача выполняется еще реже, период равен 2 с, а время выполнения - 15 мс. Она также некритична по времени.

Частотно-монотонные приоритеты присваиваются задачам так, что более приоритетными оказываются задачи с меньшим периодом. Значит, самый высокий приоритет будет иметь задача Интерфейс Вала с периодом 10 мс. У двух задач - Интерфейс Дросселя и Автодатчики - период равен 100 мс. Задача Автодатчики активна всегда, а задача Интерфейс Дросселя - только в режиме автоматического управления. Задаче Автодатчики назначен более высокий приоритет, поскольку от полученной ею входной информации (например, о нажатии тормоза) может зависеть воздействие на дроссель. Две задачи имеют период 250 мс, больший приоритет назначен задаче Путь и Скорость, поскольку она вычисляет значение текущей скорости, используемой задачей Корректировка Скорости, если последняя активна. Самый низкий приоритет у задачи Таймер Обслуживания, которая имеет максимальный период.

Из табл. 17.3 видно, что полный коэффициент использования ЦП, рассчитанный для 10 задач, равен 0,48, что намного ниже теоретически предельного значения 0,69, которое дает теорема о верхней границе коэффициента использования. Следовательно, если приоритеты назначать согласно алгоритму монотонных частот, то все задачи успеют завершиться в срок.

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

7. Анализ производительности по теории планирования в реальном времени и анализа последовательности событий

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

Эквивалентная апериодическая задача. Необходимо учесть влияние, которое оказывает дополнительная нагрузка, вызванная действиями водителя, на стационарную нагрузку, обусловленную периодическими задачами. Худший случай возникает, когда автомобиль уже движется в автоматическом режиме, иначе задачи Корректировка Скорости и Интерфейс Дросселя не работают, и нагрузка на процессор меньше.

Рассмотрим, что происходит, когда водитель переводит ручку круиз-контроля в новое положение. При анализе последовательности событий и на соответствующей диаграмме показано, что в обработке события участвуют задачи Интерфейс Ручки Круиз-Контроля, Круиз-Контроль, Корректировка Скорости и Интерфейс Дросселя. Время ЦП, необходимое для обработки, задано уравнением 1 (см. раздел 11.5). Хотя в цепочку событий вовлечены четыре задачи, они должны выполняться в строго определенной последовательности, так как каждая следующая активизируется сообщением от предыдущей. Поэтому в первом приближении можно считать, что перечисленные задачи эквивалентны одной апериодической задаче, на выполнение которой уходит время Ce. Ce - это сумма времен выполнения четырех отдельных задач плюс затраты на межзадачные коммуникации и контекстное переключение. Эквивалентная апериодическая задача называется задачей последовательности событий.

Из теории планирования в реальном времени следует, что апериодическую задачу можно рассматривать как периодическую с периодом, равным минимальному интервалу между событиями. Пусть период эквивалентной апериодической задачи равен Тe. Предположим, что Тe - это еще и максимальное время реакции на действия водителя. Например, если Тe составляет 250 мс, то система должна отреагировать на нажатие тормоза или отключение круиз-контроля в течение 250 мс. Для эквивалентной периодической задачи последовательности событий будем считать, что водитель способен инициировать не более четырех внешних событий в секунду, это худший и крайне маловероятный случай. Тем не менее, если удастся доказать, что система может справиться и с такой ситуацией, уверенность в ее работоспособности многократно возрастет.

...