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

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

Другой случай возникает, когда есть апериодические задачи. В разделе 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 также удовлетворяет временным ограничениям. Итак, все четыре задачи успевают выполниться в срок.