Table of Contents

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 Vypracované otázky

Rozvrhovací algoritmy pro systémy reálného času

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

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í.

Off-line rozvrhování

Lze použít, pokud dopředu známe všechny úlohy, které bude systém vykonávat.

Uvažujeme úlohy (task) s fixní prioritou a periodické podúlohy (job) se zděděnou prioritou, danou periodou, dobou vykonávání a nejzazším termínem vykonání (deadline).

Off-line rozvrhování se také nazývá clock driven - 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.

Implementace pomocí tabulky

Nejprve se vytvoří celá schedule v rámci hyperperiody (perioda opakování celého rozvrhu), která se pak opakuje. Tento přístup je paměťově náročný a přeprogramování časovače může být pomalé.

Frame-based rozvrhování

Rozdělení výpočetního času do kusů konstantní délky - frames ($f$ ~ frame size).

Do jednoho frame lze implementovat více podúloh, pokud splní podmínky:

  1. Každá podúloha se musí vejít do jednoho frame, aby nedocházelo k preempci: $$f>max(C_i)$$
  2. $f$ dělí hyperperiodu 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 co nejkratší frame size - zajištění dostatečného času mezi release a deadline (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 (task splitting):

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

Tyto volby nelze udělat nezávisle, ovšem k jejich učinění lze použít například max-flow grafový algoritmus.

Cyklická exekutiva (Scheduler 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:

Odezva aperiodických podúloh

Při statickém rozvrhování se aperiodické úlohy vykonávají při volné kapacitě. Ta je buď statickým rozvrhem dána implicitně (tj. pevné časové sloty), nebo ji můžeme optimalizovat pomocí kradení rezervy (Slack Stealing) tak, aby byly aperiodické úlohy splněny co nejdříve, ale periodické úlohy se vykonaly v rámci svého přiděleného frame.

Slack Stealingem obecně docílíme lepší odezvy aperiodických úloh.

On-line rozvrhování

Fixed Priority rozvrhování

Přidělení výpočetního času té úloze, která má nejvyšší prioritu.

Rate-Monotonic (RM) - priorita je určena podle periody. Platí - čím nižší perioda, tím vyšší priorita.

Deadline-Monotonic (DM) - priorita je určena podle blízkosti deadline. 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í (Dynamic Priority rozhodování)

Nejjednodušší příklad - EDF (Earliest deadline first) - vždy se vykonává podúloha s nejbližším deadlinem. 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í real-time a best-effort ú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ší.

Background scheduling

Periodické úlohy rozvrhovány pomocí zvoleného algoritmu řízeného prioritou. 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 - implementace tohoto kroku je výpočetně náročná.

Simple Periodic Server

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 deadlinu určujeme tzv. “execution budget” (tj. maximální časová dotace, kterou může server využít během jedné periody).

Nevýhoda - k obnově budgetu dochází pouze pokud je aperiodická úloha připravena na začátku obnovovací periody → 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.

Bandwith-preserving Server

Řeší problém se zpožděním aperiodických úloh → po dokončení úlohy nemusí být ve stavu idle budget nulový.

Total-Bandwidth Server (TBS).

Je dán maximální procentuální poměr výpočetního času pro aperiodické podúlohy ($U$). Při příchodu nové aperiodické úlohy je určen virtuální deadline $d$. Obnova budgetu se řídí třemi pravidly:

  1. Na počátku $(t=0)$ je budget nulový a deadline je $d=0$.
  2. Při příchodu nové aperiodické úlohy, pokud je server ve stavu idle, určí se deadline $d=max(d,t)+\frac{e}{U}$, kde $e$ je čas vykonávání ú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í další podúlohy. Pokud je server ve stavu idle, neděje se nic.

příklad:

Constant Utilization Server (CUS)

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 budgetu:

  1. Na počátku $(t=0)$ je budget $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 budget
  3. Při dosažení deadline (a) pokud je připravena další úloha $d = t + \frac{e}{U}$ a dochází k obnově budgetu, (b) pokud je server ve stavu idle, neděje se nic

příklad:

Bezpečnostně kritický software

Proces vývoje bezpečnostně kritického SW

Fáze vývoje

(Dle MIL-STD-882E)

  1. Zdokumentujte jakým způsobem je dosažena bezpečnost
  2. Identifikujte a zdokumentujte hazardy
  3. Zhodnoťe a zdokumentujte rizika
  4. Identifikujte a zdokumentujte způsoby jak snížit jejich závažnost
  5. Snižte rizika
  6. Prověřte, validujte a zdokumentujte dosažená snížení rizik
  7. Akceptujte setrvávající rizika a zdokumentujte je
  8. “Manage life-cycle risk”
Způsoby zmírňování nepřiměřeného rizika

Snížení rizik lze docílit následujícími kroky:

(MIL-STD-882E, Clause 4.3.4)

  1. Eliminujte hazardy skrze design
  2. Redukujte rizika skrze design
  3. Zapracujte “engineered features or devices”
  4. Doplňte varovná zařízení
  5. Zapracujte podpisy, školení, procedury, osobní ochranné pomůcky

safety standardy MIL-STD-882E, IEC 61508

Safety Integrity Level (SIL)

Požadovaná relativní úroveň zabezpečení pro snížení rizika selhání bezpečnostní funkce uplatněním bezpečnostních nároků → určuje, jak nízká musí být pravděpodobnost nebezpečného selhání.

Úrovně:

Určení SIL testováním nemožné (protože nemáme času), místo toho se používají nepřímé metody.

Vyšší SIL obecně znamená přísnější požadavky na:

Určení SIL

Jak:

  1. Identifikace hazardů - (např. HAZOP)
  2. Přiřazení pravděpodobnosti jednotlivých hazardů
  3. Identifikace mechanismů jim zabraňujícím
  4. Identifikace dopadů hazardů
  5. Identifikace vážnosti dopadů
  6. Výpočet třídy rizika (1-nepřípustné až 4-zanedbatelné)
  7. Identifikace třídy SIL

Obecně chceme docílit třídy rizika 4. Systémy se třídou SIL1 mohou snížit rizika o jednu třídu, Systémy se třídou SIL4 mohou snížit rizika o tři úrovně.

Kdy:

Při plánování - je to jeden z podstatných kroků analýzy bezpečnosti.

Vliv SIL na vývoj a testování systému

Různé úrovně SIL mají různé nároky - například je třeba pro různé úrovně je vyžadována různá úroveň kontroly korektního fungování a to od formy důkazu korektnosti až po množství lidí, kteří systém zkontrolují. Dále je podstatná míra jejich nezávislosti. Stejně tak jsou doporučené praktiky pro různé úrovně SIL.

Rozvrhnutelnost a analýza doby odezvy

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 nejzazší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 nejzazší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 nejzazší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

Sdílené zdroje v systémech reálného času

Sdílení zdrojů v systémech reálného času může představovat potenciálně velký problém ve zpoždění vykonání úlohy a tak i nedodržení limitu pro vykonání. Tento problém může být způsoben hlavně dvěma důvody – Inverze priority a inverze deadlinu.

Inverze priorit je stav, kdy úloha s vyšší prioritou je blokován úlohou s nižší prioritou. K tomuto standarndě dochází díky sdílenému zámku.

Deadline Inversion je stav, kdy je úloha blokována úlohou s pozdějším časovým limitem splnění.

Jako řešení můžeme uvažovat několik protokolů (concurrency-control protocols). Pro systémy s fixní prioritou úloh uvažujeme protokoly

Priority Inheritance Protocol

Obecně - protokol dědění priorit, jak nasvědčuje název, pracuje na principu při kterém kdy dochází k blokaci inverzí priority, blokující podúloha zdědí prioritu blokované po dobu vykonávání kritické sekce.

a Priority Ceiling Protocol

Tento protokol zajišťuje, že chod úlohy může být blokován úlohou s nižší prioritou nejvýše jednou. Zabraňuje vzájemnému uváznutí atd. Pracuje na principu stanovení horních mezí, která vytváří pravidla pro možnost vstupu do kritické sekce. U tohoto protokolu rozdělujeme dvě jeho formy:

Original PCP

pravidla:

  1. Každá úloha má svou statickou prioritu
  2. Každá úloha má dynamickou prioritu, která je maximem vlastní statické a zděděné statické priority.
  3. Každá kritická sekce/zdroj má stanovenou maximální prioritu úloh, které do ní vstupují
  4. Úloha může vstoupit do kritické sekce pouze pokud je jeho dynamická priorita vyšší než systémové maximum. To je stanoveno jako maximální hodnota z priorit aktuálně uzavřených kritických sekcí.

příklad:

Immediate PCP pravidla:

  1. Každá úloha má svou statickou prioritu
  2. Každá kritická sekce/zdroj má stanovenou maximální prioritu úloh, které do ní vstupují
  3. Každá úloha má dynamickou prioritu, která je maximem vlastní statické a kritické sekce, do které vstoupila

Díky tomu, pokud je úloha blokována, je to pouze na začátku. V moment, kdy je již vykonáván, všechny potřebné zdroje musí být volné.

příklad:

Obecně - IPCP je jednodušší na implementaci, vede k méně změnám kontextu, ale vyžaduje více změn priorit. IPCP mění prioritu pouze v případě blokace. PCP obecně poroti dědění priority vede k rychlejší odězvě u úloh s vyšší prioritou.

(Pozn. na tohle se mě docela detailně ptal Sojka na ústní když jsem chtěl Ačko, takže tady to asi nebude tak žhavé…)

Pro systémy s dynamickými prioritami existuje protokol Stack Resource Policy , což je zobecnění PCP. Zajímavost je, že umožňuje stack sharing.

Čím se liší RTOS od obecného operačního systému

Nad rámec normálního operačního systému, kde vyžadujeme zvláště logickou determinističnost, je u Real Time operačních systémů vyžadována tzv. časová korektnost (Temporal correctness) → “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 u RT aplikací není důležitá průměrná výkonnost, ale právě dodržení limitů → časová náročnost nejhoršího možného scénáře (worst case scenario).

Příklady RTOS