The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

--- statnice:bakalar:b4b35psr [2025/06/05 10:49] – [Rozvrhovací algoritmy pro systémy reálného času] offline partial dudactom
+++ statnice:bakalar:b4b35psr [2025/06/10 18:59] (current) – [Bezpečnostně kritický software] added dudactom
@@ Line 3: / Line 3: @@
 [[https://intranet.fel.cvut.cz/cz/education/bk/predmety/47/26/p4726106.html|B4B35PSR]] [[https://psr.pages.fel.cvut.cz/psr/prednasky/|Webové stránky předmětu]]
+[[https://docs.google.com/document/d/18P7Tj1d6qu43yE8bbGnrcd_nBuf1k_xTfG4n634u3Jw/edit?tab=t.0#heading=h.pdzqg1fe35o6|Vypracované otázky]]
   * 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))?
@@ Line 27: / Line 27: @@
 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. Do této délky můžeme kombinovat více podúloh, ovšem délka nesmí být kratší než maximální nutná doba ke zpracování libovolné podúlohy (1) ($f>max(C_i)$), aby nedocházelo k preempci. Stejně tak je třeba držet tuto délku co nejkratší (3) a tato délka by měla dělit tzv. hyperperiodu(2) (perioda opakování celého rozvrhu).
+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:
+  - 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)$$
+  - $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} $$
+  - 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 $$
-(TODO)
+příklad:
+{{:statnice:bakalar:pasted:20250606-093531.png?400}}
+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:
+{{:statnice:bakalar:pasted:20250606-095947.png?400}}
+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).
+{{:statnice:bakalar:pasted:20250608-101026.png?400}}
@@ Line 44: / Line 71: @@
+** 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:
+  - Na počátku $(t=0)$ je rozpočet $e$ nulový a deadline je na $d=0$.
+  - 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.
+  - 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:
+{{:statnice:bakalar:pasted:20250608-194627.png?400}}
+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!"...
-** Deadline driven rozvrhování ** - EDF (TODO)
+Pravidla pro konzumaci rozpočtu:
+  - Na počátku $(t=0)$ je rozpočet $e$ nulový a deadline je na $d=0$.
+  - 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
+  - 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:
-** Kombinování RT a obyčejných úloh ** - background scheduling, total-bandwidth server (TBS), constant utilization server (CUS) (TODO)
+{{:statnice:bakalar:pasted:20250608-194545.png?400}}
 ===== Bezpečnostně kritický software =====
+Popište proces vývoje bezpečnostně kritického software:
+**fáze vývoje**-
+(Dle MIL-STD-882E)
+  - Zdokumentujte jakým způsobem je dosažena bezpečnost
+  - Identifikujte a zdokumentujte hazardy
+  - Zhodnoťe a zdokumentujte rizika
+  - Identifikujte a zdokumentujte způsoby jak snížit jejich závažnost
+  - Snižte rizika
+  - Prověřte, validujte a zdokumentujte dosažená snížení rizik
+  - Akceptujte setrvávající rizika a zdokumentujte je
+  - "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)
+  - Eliminujte hazardy skrze design
+  - Redukujte rizika skrze design
+  - Zapracujte "engineered features or devices"
+  - Doplňte varovná zařízení
+  - Zapracujte podpisy, školení, procedury, osobní ochranné pomůcky
+** safety standardy **
+MIL-STD-882E, IEC 61508
+** Co je to ”safety integrity level”(SIL)? **
+Obecně jde o relativní úroveň snížení rizikovosti uplatněním bezpečnostních nároků.
+Standard IEC 61508 upravuje úrovně vyžadovaného ochrany proti systematickému selhání v "safety-related" systémech.
+Obecně - čím vyšší vyžadovaná úroveň SIL, tím nižší je tolerance na "nebezpečná selhání" (dangerous failure). SIL 1 - cca 1 za 10 let, SIL 4 - cca 1 za 10000 let. Toho nelze dosáhnout testováním, využíváme nepřímé způsoby. Vznikají konkrétní nároky na způsob provedení. (nebudu sem dávat screeny, úplně není legální šířit obashy placených standardů :D )
+** Jak a kdy se určí? **
+Jak:
+  - Identifikace hazardů - (např HAZOP)
+  - Přiřazení pravděpodobnosti jednotlivých hazardů
+  - Identifikace mechanismů jim zabraňujícím
+  - Identifikace dopadů hazardů
+  - Identifikace vážnosti dopadů
+  - Výpočet třídy rizika (1-nepřípustné až 4-zanedbatelné)
+  - 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:
+SIL se obecně určuje již při plánování - je to jeden z podstatných kroků analýzy bezpečnosti.
+** Jak se různý SIL projeví při vývoji 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 =====
@@ Line 112: / Line 231: @@
 {{:statnice:bakalar:pasted:20250605-085731.png?200}}
+  * Je rozvrhovatelné pokud Ri <= Di
 ** Vliv sdílených zdrojů **
@@ Line 119: / Line 239: @@
 ===== 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.
+{{:statnice:bakalar:pasted:20250610-105359.png?400}}
+** 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**
+{{:statnice:bakalar:pasted:20250610-105513.png?400}}
+{{:statnice:bakalar:pasted:20250610-105417.png?400}}
+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:
+  - Každá úloha má svou statickou prioritu
+  - Každá úloha má dynamickou prioritu, která je maximem vlastní statické a zděděné statické priority.
+  - Každá kritická sekce/zdroj má stanovenou maximální prioritu úloh, které do ní vstupují
+  - Ú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:
+{{:statnice:bakalar:pasted:20250610-111142.png?400}}
+** Immediate PCP**
+pravidla:
+  - Každá úloha má svou statickou prioritu
+  - Každá kritická sekce/zdroj má stanovenou maximální prioritu úloh, které do ní vstupují
+  - 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:
+{{:statnice:bakalar:pasted:20250610-111217.png?400}}
+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 =====

Trace:

Differences

Search

Navigation

Print/export

Tools

QR Code