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

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

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

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

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

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

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

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

,

где С_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 завершить выполнение к данной точке планирования.

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

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

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

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

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

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