Rozvrhování v systémech reálného času; časová analýza těchto systémů; správa sdílených zdrojů; bezpečnostně kritické aplikace.

B4B35PSR Webové stránky předmětu

• Rozvrhovací algoritmy pro systémy reálného času (online, offline, fixed-priority scheduling, EDF). Co je jejich vstupem a výstupem? Jaké jsou možnost kombinování real-time a obyčejných úloh a co nám různé možnosti garantují a co naopak ne (např. background scheduling, total-bandwidth server (TBS), constant utilization server (CUS))?
• Bezpečnostně kritický software - popište proces vývoje bezpečnostně kritického software (fáze vývoje, způsoby zmírňování nepřiměřeného rizika, safety standardy). Co je to ”safety integrity level”(SIL)? Jak a kdy se určí? Jak se různý SIL projeví při vývoji a testování systému?
• Rozvrhnutelnost a analýza doby odezvy. Popište různé metody analýzy odezvy systému (např. utilization-based, RTA). Jaký vliv mají na analýzu a její výsledky sdílené zdroje (např. mutexy v aplikaci či operačním systému)?
• Sdílené zdroje v systémech reálného času. Definujte problém inverze priorit a uveďte několik způsobů jak jej řešit (concurrency-control protocols = priority inheritance, priority ceiling). Porovnejte tyto způsoby mezi sebou.
• Čím se liší RTOS od obecného operačního systému? Uveďte příklady RTOS.

Pro aplikování a analýzu korektnosti je třeba vytvořit model. Ten se skládá ze tří prvků:

• Workload (zatížení) - jednotlivé aplikace / procesy / úlohy / …
• Resource (zdroje) - dostupné delegovatelné zdroje
• Algorithm (algoritmy) - způsob využití zdrojů

Pro jednotlivé algoritmy lze zbylé dva vstupy modelu považovat za jejich vstup. Výstupem algoritmu je v případě rozvrhnutelnosti rozvrh jednotlivých úloh.

Algoritmy můžeme dělit nejprve podle způsobu rozvrhování. V případě, že známe všechny úlohy, které bude systém vykonávat, předem, lze aplikovat první podskupinu algoritmů – Off-line rozvrhování. V tomto případě uvažujeme úlohy (task) s fixní prioritou a periodické podúlohy (job) se zděděnou prioritou, danou periodou, dobou vykonávání a nejzašším termínem vykonání (deadline). Off-line rozvrhování se také nazývá clock driven, jelikož rozvrh je nejprve vytvořen pomocí některého z algoritmů offline a následně je implementován jako volání jednotlivých úloh v konkrétní čas. V nejjednodušším případě lze tento přístup implementovat pomocí tabulky. Tento přístup je však paměťově náročný a přeprogramování časovače může být pomalé.

Druhý přístup představuje tzv. frame-based rozvrhování. To spočívá v rozdělení výpočetního času do kusů konstantní délky ($f$ ~ frame size). Do této délky můžeme kombinovat více podúloh za určitých podmínek:

1. Délka nesmí být kratší než maximální nutná doba ke zpracování libovolné podúlohy, aby nedocházelo k preempci: $$f>max(C_i)$$
2. $f$ by též měla dělit tzv. hyperperiodu (perioda opakování celého rozvrhu) a tedy i alespoň jednu z period: $$ \Big\lfloor \frac{T_i}{f} \Big\rfloor = \frac{T_i}{f} $$
3. Stejně tak je třeba držet tuto délku co nejkratší se zachováním možnosti kontroly splnění deadlinu (tj. mezi vypuštěním podúlohy a jejím deadlinem musí být minimálně 2 frame) $$ 2f - gcd(T_i,f) \le D_i $$

příklad:

Pokud nemůže být splněna některá z podmínek, je možné řešit problém například rozdělením podúlohy a jejím plnění při volných výpočetních prostředcích:

Obecně je třeba pro rozvržení splnit tři kroky

• volba velikosti časového okna (frame size)
• rozdělení podúloh na do dílů
• přiřazení dílů do časových oken

Tyto volby nelze udělat nezávisle, ovšem k jejich učinění lze použít například max-flow grafový algoritmus. (Vynechávám… kdyžtak v přednášce)

Cyklická exekutiva Jde respektive o fancy název pro rozvrhovač spouštící “frame based” rozvrh. V případě, že kombinujeme cyklickou exekutivu s OS, jde o úlohu/proces s nejvyšší prioritou. Problémy cyklické exekutivy jsou, že není schopna zabránit přetečení časové dotace podúlohy a nelze docílit preempce aperiodických podúloh.

Odezva aperiodických podúloh Obecně, nemá smysl cílit na co nejdřívější splnění hard-RT podúloh, jelikož jejich plněním až po určité části aperiodické podúlohy můžeme doscílit dřívějšího splnění všech podúloh, tedy i lepší doby odezvy aperiodických podúloh. Tomuto způsobu přiřazování výpočetního času přezdíváme tzv. Kradení rezervy (angl. Slack stealing).

On-line rozvrhování -

Fixed priority rozvrhování Rate-Monotonic (RM) rozvrhovač funguje na principu přidělení výpočetního času té úloze, která má nejvyšší prioritu, kde priorita je určena podle periody. Platí - čím nižší perioda, tím vyšší priorita.

Deadline-Monotonic (DM) rozvrhovač funguje na principu přidělení výpočetního času té úloze, která má nejvyšší prioritu, kde priorita je určena podle blízkosti nejzašštího termínu vykonání. Platí - čím bližší deadline, tím vyšší priorita.

Ani jeden z těchto algoritmů není optimální. RM rozvrhovač je optimální pouze pro jednoduše periodické úlohy (tj. úlohy, kde pro každé dvě úlohy $ i,j $ platí, že pokud pro periody platí $ T_i < T_k $, pak platí $ T_k = n \cdot T_i; n \in \mathbb{Z} $

Deadline driven rozvrhování -

Také jinak rozvrhování rozvrhování s dynamickou prioritou. Nejjednodušším příkladem je algoritmus EDF (Earliest deadline first) - vždy se vykonává podúloha s nejbližším termínem nejzaššího vykonání. Tento algoritmus je optimální za podmínek možnosti preempce podúloh a vyloučení zpoždění způsobeného sdíleným přístupem k paměti.

Kombinování RT a obyčejných úloh -

U systémů kombinujících RT a obyčejné úlohy se obecně snažíme dosáhnout jednoho cíle, tím je mechanismus rezervující zdroje na úrovní RT rozvrhovače. Pro systémy s cyklickým rozvrhovačem lze k tomuto kombinování použít zmíněné kradení rezervy. Pro rozvrhovače dynamické (resp. online) je tato úloha složitější.

První způsob jakým lze k úloze přistoupit je tzv. Background scheduling. Při něm jsou periodické úlohy rozvrhovány pomocí zvoleného algoritmu řízeného prioritou a aperiodické úlohy se vykonávají pouze tehdy, pokud v rozvrhu není připravena žádná periodická úloha. Stejně jako u kradení rezervy, můžeme odložit spuštění periodických úloh a nejprve spouštět aperiodické. Problém je, že implementace tohoto kroku je náročná z hlediska nutného výpočetního výkonu.

Druhou variantou je tzv. Simple Periodic Server, kde periodické úlohy rozvrhujeme znovu zvoleným algoritmem pracujícím s prioritou a aperiodické úlohy spouští tzv. periodický server. Jde o úlohu, u níž místo termínu nejzaššího vykonání určujeme tzv. “execution budget” (výpočetní rozpočet - resp. časová dotace). Aperiodické úlohy jsou vykonávány vždy, když není připravena žádná periodická úloha, a je nenulový rozpočet. Po uplynutí periody serveru dochází k obnovení rozpočtu. Pokud ovšem server dokončil vykonávání úlohy, a je ve stavu idle, má automaticky nulový rozpočet.

Nevýhoodu tohoto “serveru” je že k obnově časové dotace/rozpočtu dochází pouze pokud je aperiodická úloha připravena na začátku obnovovací periody. Tedy pokud dojde k uvolnění aperiodické podúlohy před obnovovací periodou, není spuštěna ani pokud není zrovna vykonávána žádná periodická úloha. Toto řeší tzv. Bandwith-preserving Server. Pro ně platí, že i po dokončení úlohy nemusí být ve stavu idle rozpočet nulový.

Konkrétním příkladem bandwidth-preserving serveru je tzv. Total-Bandwidth Server. Ten funguje na principu, kdy je dán maximální procentuální poměr výpočetního času, který může být věnován aperiodickým podúlohám. Obnova rozpočtu se řídí třemi pravidly:

1. Na počátku $(t=0)$ je rozpočet $e$ nulový a deadline je na $d=0$.
2. Vždy když dojde k vzniku nové aperiodické podúlohy s dobou vykonávání e a server je ve stavu idle, nejzašší termín vykonání je $d=max(d,t)+\frac{e}{U}$, kde $U$ je poměr výpočetního času pro aperiodické úlohy.
3. Při dokončení podúlohy, pokud je připravena další úloha $d = d + \frac{e}{U}$ a $e$ je nastaveno na dobu vykonávání podúlohy. Pokud je server ve stavu idle, neděje se nic.

příklad:

Druhým konkrétním příkladem je Constant Utilization Server (CUS). Ten uvedeme pouze okrajově, protože podle materiálů “The value of the CUS is not clear, and Liu does a terrible job arguing for it!”…

Pravidla pro konzumaci rozpočtu:

1. Na počátku $(t=0)$ je rozpočet $e$ nulový a deadline je na $d=0$.
2. V čase $t$ je vypuštěna podúloha a server je ve stavu idle, pak (a) pokud $t<d$, tak nic (b) pokud $t \geq d, tak $d = t + \frac{e}{U}$ a doplní se rozpočet
3. Při dosažení deadline (a) pokud je připravena další úloha $d = t + \frac{e}{U}$ a dochází k obnově rozpočtu, (b) pokud je server ve stavu idle, neděje se nic

příklad:

Pro kontrolu rozvrhnutelnosti zavádíme test rozvrhnutelnosti RM na základě zatížení. Ten nám říká, že pro $n$ nezávislých preemptable (předřaditelných?… kdyžtak doplňte lepší překlad prosím), periodických úloh s nejzašším termínem vykonání rovným jejich periodám, lze pro kontrolu rozvrhnutelnosti na jednom procesoru použít pro RM součet parciálního využití výpočetního času procesoru v periodě (tj. součet Task ulilizations = System utilization).

Matematicky zapsáno

$$\mathrm{Taks\ utilization:}\quad u_i = \frac{C_i}{T_i} $$ $$\mathrm{System\ utilization:}\quad U = \sum_i u_i$$

kde $T_i$ odpovídá periodě.

Pro rozvrhnutelné systémy platí

$$ U \le n\big(2^{\frac{1}{n} - 1} \big)$$

Time demand analysis V tzv. analýze časové poptávky řešíme zda-li celková poptávka na výpočetní čas jednotlivých podúloh vypuštěných v určité časy může být splněna nabídkou našeho systému před nejzašším termínem splnění. TDA může být také použita na vyprodukování testu rozvrhnutelnosti pro libovolný algoritmus se statickou prioritou, který zajistí, splnění podúlohy úlohy, před vypuštěním další podúlohy. Tento test lze pro některé modely a rozvrhovací algoritmy považovat nejen za dostatečný, ale dokonce za nutný.

Pro výpočet TDA zavádíme tzv. time demand function

$$ w_i(t) = C_i + \sum_{k=1}^{i-1} \Big\lceil \frac{t}{T_k} \Big\rceil \cdot C_k \quad \mathrm{pro\ } 0 < t \le T_i $$

Příklad:

Mějme zadané tři úlohy pro kontrolu jejich rozvrhnutelnosti (levý horní roh obrázku).

(Tady je možná chyba v začátku $w_2$, když na to koukám znovu, ale výsledek je správně… kdyžtak to je nahrané v přednášce… + je tohle navíc, ne?)

Podmínka rozvrhnutelnosti je

$$ \forall i : \exists t : w_i(t) \le t; \quad 0 < t \le T_i $$

Response time analysis Výpočet doby odezvy je konkrétním, jednodušším, případem TDA. Pokud známe tzv. critical instant, čas vypuštění podúlohy s nejzašším časem vykonání, můžeme jej vypočítat. Dobu odezvy lze vypočítat jako

$$ R_i = C_i + I_i $$

kde $I_i$ je interference, resp. zpoždění vykonání, podúlohami s vyšší prioritou.

Obecně ke spuštění podúlohy s vyšší prioritou může dojít několikrát. Počet spuštění podúlohy $t_j$ lze určit jako $\Big\lceil\frac{R_i}{T_j}\Big\rceil$

Proto lze uvažovat dosazení

$$ R_i = \sum_{J} \Big\lceil\frac{R_i}{T_j}\Big\rceil C_j \quad \mathrm{kde\ } J = \{j: j\in \mathbb{N}, j < i\} $$

Jak vidíme, pro výpočet je třeba rekurentní rovnice, tu lze zapsat jako

$$ w_{i}^{n+1} = \sum_{J} \Big\lceil\frac{w_{i}^{n}}{T_j}\Big\rceil C_j \quad $$

příklad: (periodu uvažujeme též jako deadline)

Vliv sdílených zdrojů

Sdílené zdroje zpravidla situaci zesložiťují – prakticky přidávají další podmínky naprioritu rozvrhování,či prodlužují čas vykonání podúlohy. Více v části o sdílených zdrojích

Nad rámec normálního operačního systému, kde vyžadujeme zvláště logickou determinističnost, je tu Real Time operačních systémů vyžadována tzv. časová korektnost (angl. Temporal correctness). To lze interpretovat jako “nezáleží pouze na logické korektnosti a determinističnosti výsledku, ale i jeho včasnosti”.

Pro RTOS je důležité, aby dokázal reagovat na nepředvídatelné události deterministickým způsobem. Toto chování je však třeba analyticky dokázat a mluvíme tak o nutnosti dodržení časových limitů pro reakci na tyto události. Narozdíl od standardního softwaru nás u RT aplikací nezajímá průměrná výkonnost, ale právě toto dodržení limitů - mluvíme tak o časové náročnosti nejhoršího možného scénáře (angl. worst case scenario).

• VxWorks - komerční, certifikace pro aerospace, multiprocessor support
• RTEMS - open-source, multiprocessor support,
• Zephyr - open-source, bez memory protection, certifikace jako služba
• Apache NuttX - open-source
• QNX - komerční, mikrojádro
• FreeRTOS - jeden adresní prostor, pro mikrokontroléry, SIL3 (IEC-61508) a další certifikace
• Windows CE - Microsoft…
• Azure RTOS (TheadX) - Microsoft…
• Linux - PREEMPT_RT patch - kernel v6.12