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

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

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

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

Периодическая задача характеризуется периодом Т (частота запуска) и временем выполнения С (время ЦП, необходимое для завершения одного запуска). Коэффициент использования ЦП для нее равен 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.

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

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

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

Задача 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].

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