Návrh časově kritických systémů II: úlohy reálného času

 

 

Každou z úloh RT (dále jen „úloh“) si lze představit jako výpočetní jednotku provádějící specifickou funkci – např. čekání nan vstupní podnět, vzorkování či transformaci veličin, odměřování času, interakci s okolím nebo generování odezev. Jinými slovy – úloha je zodpovědná za správné provedení konkrétní dílčí části algoritmu řízení v reálném čase. Podle toho, jak je možné charakterizovat intervaly mezi příchody požadavků na zahájení úloh, lze každou z úloh zařadit do jedné z těchto kategorií:

 

Převodem specifikace systému na množinu úloh RT se sice přiblížíme cílové realizaci systému RT, avšak nesmíme zapomenout, že reprezentace systému na úrovni úloh stále abstrahuje jak od prostředků cílového operačního systému reálného času (Real-Time Operating System – RTOS), tak od vlastností cílové platformy. Nicméně, některé (z pohledu systému RT) významné parametry zanedbat nelze, a naopak je nutné je zahrnout do tzv. modelu úlohy RT. K základním takovým parametrům patří např. r – absolutní čas příchodu požadavku na provedení úlohy (čas vyvolání úlohy), T – perioda mezi příchody požadavků na provedení úlohy (pouze pro periodické úlohy), C – nejdelší z možných dob běhu úlohy, D – relativní časová mez odezvy úlohy, d – absolutní časová mez odezvy úlohy či P – priorita úlohy.

 

Pro úplnost dodejme, že úloha RT je obvykle označována písmenem řecké abecedy t, množina úloh RT písmenem G. Parametry jsou úloze obvykle přiřazeny formou uspořádané n-tice uvedené v závorce u symbolu t, tj. např. t₁(r, C, D, T) = t₁(0, 2, 100, 35) pro periodickou úlohu či t₄(r, C, D) = t₄(4, 5, 7) pro neperiodickou úlohu.

 

Vedle již uvedených základních statických (v čase neměnných) parametrů úloh je možné zpřesnit model úloh zahrnutím dalších statických či dynamických (v čase proměnných) parametrů. Jistě platí, že čím větší počet parametrů model úloh zahrnuje, tím více se blíží chování navrhovaného systému RT v reálných podmínkách. Naproti tomu je však nutné si uvědomit, že s počtem parametrů rostou také požadavky kladené nejen na konstrukci plánovače, ale i na analýzu vlastností systému RT. Přehled často používaných parametrů úloh je v tab. 1.

 

Uspořádání provádění úloh v čase se nazývá plán (lze použít i označení rozvrh, v tomto a souvisejících článcích se však přidržíme označení „plán“ – pozn. aut.) a obvykle je zobrazováno v podobě časového diagramu, jak ilustruje obr. 1. Časy r, popř. d, bývají v diagramu zvýrazněny použitím symbolů ↑, popř. ↓. V souvislosti s plány uveďme alespoň tyto pojmy:

 

Plán je generován tzv. plánovačem, který rozhoduje o tom, které z úloh bude v daném čase přidělen čas procesorové jednotky. Hlavní funkcí plánovače je volit pořadí provádění úloh tak, aby každá z úloh byla dokončena nejpozději do uplynutí její časové meze, tj. času odpovídajícího hodnotě parametru d dané úlohy. Téměř všechny moderní plánovače jsou prioritní; tj. o tom, které úloze bude přidělen čas procesoru, rozhodují na základě priorit přiřazených jednotlivým úlohám, přičemž v ideálním případě plánovač garantuje, že v daném časovém okamžiku vždy běží ta z úloh připravených k běhu, jejíž priorita je nejvýznamnější. Při vykonávání tohoto rozhodnutí je důležité, zda je plánovač preemptivní či nepreemptivní – zatímco preemptivní plánovač zajistí přepnutí na nejvýznamnější úlohu přerušením provádění momentálně běžící úlohy, nepreemptivní plánovač přepnutí odloží až do okamžiku jejího ukončení. Jelikož doba odezvy preemptivních systémů je kratší než u nepreemptivních systémů, jsou plánovače používané v RTOS téměř výhradně preemptivní. Avšak mnohé RTOS obsahují i prostředky umožňující dočasně využívat vlastnosti nepreemptivního plánovače, většinou při použití služeb typu zamknutí/odemknutí plánovače, a oba mechanismy tak kombinovat. K hlavním nedostatkům preemptivního plánovače patří režie spojené s přepínáním kontextu úloh a s ukládáním kontextu každé z úloh. Tato režie roste úměrně s počtem úloh a s počtem přepnutí úloh v rámci daného časového intervalu. Podstatnou část této režie tvoří složky zpoždění přerušení, odezva přerušení a zotavení se z přerušení, které, spolu s dobou provádění příslušných obsluh přerušení, hrají důležitou roli při určování nejdelší doby odezvy úloh. Navíc může být v rámci obsluhy přerušení do systému zařazena úloha s významnější prioritou, než jakou měla úloha přerušená touto obsluhou. V takovém případě je doba odezvy přerušené úlohy ještě delší.

 

K názorné ilustraci rozdílu mezi preemptivním a nepreemptivním způsobem plánování úloh RT předpokládejme množinu G tvořenou podle obr. 2 úlohami t₁, t₂, t₃ s parametry t₁(r₁, C₁, D₁, T₁) = t₁(0, 3, 11, 11), t₂(r₂, C₂, D₂, T₂) = t₂(0, 2, 5, 5) a t₃(r₃, C₃, D₃, T₃) = t₃(0, 2, 10, 10). Pro jednoduchost předpokládejme, že nejvyšší priorita je přiřazena úloze t₂, střední úloze t₃ a nejnižší úloze t₁. Pro úplnost poznamenejme, že plán systému s několika úlohami bývá zobrazován po tzv. hladinách (úrovních) priorit, tj. od nejvyšší prioritní úrovně (v našem případě spodní časový průběh pro t₂) po nejnižší (v našem případě horní časový průběh pro t₁).

 

I z uvedených jednoduchých plánů lze vyvodit tyto závěry:

 

Následující článek bude zaměřen na základní mechanismy přiřazování priorit v preemptivních systémech RT. Budou představeni typičtí zástupci statických a dynamických mechanismů, jejich přednosti a nedostatky a s nimi související testy plánovatelnosti množin úloh RT.

Článek vznikl za podpory výzkumného záměru MSM0021630528 – Výzkum informačních technologií z hlediska bezpečnosti (agentura CEZ MŠMT) a projektu specifického výzkumu FIT-S-10-1 (VUT v Brně).

[1] CHENG, A. M. K.: Real-Time Systems: Scheduling, Analysis, and Verification. Wiley, 2002, 552 s., ISBN 0-471-18406-3.

[2] COTTET, F. – DELACROIX, J. – KAISER, C. – MAMMERI, Z.: Scheduling in Real-Time Systems. John Wiley & Sons, 2002, 266 s., ISBN 0-470-84766-2.

[3] JOSEPH, M.: Real-Time Systems Specification, Verification and Analysis. Prentice Hall, 1996, 278 s., ISBN 0-13-455297-0.

[4] STRNADEL, J.: Návrh časově kritických systémů I: specifikace a verifikace. Automa, 2010, roč. 16, č. 10, s. 42–44, ISSN 1210-9592.