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

⇐ ПредыдущаяСтр 8 из 9Следующая ⇒

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

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

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

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

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

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

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

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

Теорема о времени завершения.

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

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

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

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

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

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

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

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

R_i = {(k, p): l≤ k≤ i, p=l,..., [T_i/T_k]}.

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

Планирование периодических и апериодических задач. Планирование с синхронизацией задач

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

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

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

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

Теоремы о планировании методом монотонных частот необходимо обобщить на задачу об инверсии приоритетов.

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

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

100. Планирование в реальном времени и проектирование. Пример применения обобщенной теории планирования в реальном времени

В качестве примера рассмотрим следующий случай. Есть четыре задачи: две периодические и две апериодические. Ниже приведены детальные характеристики задач, причем время указано в миллисекундах, а коэффициент использования U_i=C_i/T_i.

Периодическая задача t₁: С₁ = 20; Т₁ = 100; U₁ = 0, 2.

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

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

Периодическая задача t₃: C₃ = 30; T₃ = 300; U₃ = 0, 1.

Кроме того, известно, что задачи t₁, t₂и t₃ обращаются к одному и тому же хранилищу данных, защищенному семафором S.

Задачам назначены приоритеты в строгом соответствии с алгоритмом монотонных частот, то есть t₁ имеет наивысший приоритет, а за ней следуют t₂, t_a и t₃ Но, поскольку для t_a время реакции жестко ограничено, ей присвоен наивысший приоритет, а уже потом идут t₁, t₂ и t₃

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

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

– время выполнения С₁ задачи t₁ равно 20. Коэффициент использования U₁ = 0, 2;

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

– время блокировки задачами с более низким приоритетом. Потенциально заблокировать t₁ могут задачи t₂ и t₃. Коэффициент использования за счет блокировки на периоде Т₁ составляет B₃/Т₁ = 30/100 = 0, 3.

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

Далее таким же образом рассматриваем остальные задачи

⇐ Предыдущая 1 2 3 4 5 6 789 Следующая ⇒