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₁ удовлетворяет временным ограничениям.

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