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

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

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

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

где С_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.

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