The wiki page is under active construction, expect bugs.

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b35psr [2025/06/08 10:47] – [Rozvrhovací algoritmy pro systémy reálného času] edf dudactomstatnice: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://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))?   * 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 72: Line 72:
  
 ** Deadline driven rozvrhování ** -  ** 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 ** - background scheduling, total-bandwidth server (TBS), constant utilization server (CUS) (TODO)+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!"...  
 + 
 +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: 
 + 
 +{{:statnice:bakalar:pasted:20250608-194545.png?400}}
 ===== Bezpečnostně kritický software ===== ===== 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 ===== ===== Rozvrhnutelnost a analýza doby odezvy =====
Line 139: Line 231:
 {{:statnice:bakalar:pasted:20250605-085731.png?200}} {{:statnice:bakalar:pasted:20250605-085731.png?200}}
  
 +  * Je rozvrhovatelné pokud Ri <= Di
  
 ** Vliv sdílených zdrojů ** ** Vliv sdílených zdrojů **
Line 146: Line 239:
 ===== Sdílené zdroje v systémech reálného času ===== ===== 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 ===== ===== Čím se liší RTOS od obecného operačního systému =====
  

Trace:

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b35psr (generated for current page)