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/04 14:39] – [Rozvrhovací algoritmy pro systémy reálného času] 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 14: Line 14:
  
 {{:statnice:bakalar:pasted:20250604-090409.png?400}} {{:statnice:bakalar:pasted:20250604-090409.png?400}}
- 
-(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)) 
  
 Pro aplikování a analýzu korektnosti je třeba vytvořit model. Ten se skládá ze tří prvků: Pro aplikování a analýzu korektnosti je třeba vytvořit model. Ten se skládá ze tří prvků:
Line 25: Line 23:
  
 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í**.  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). S těmito informacemi jsme schopni aplikovat tyto algoritmy – například rozvrhování Rate-Monotonic či Deadline-Monotonic.+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:
 +
 +  - 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 $$
 +
 +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}}
 +
 +
 +** 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. **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.
  
Line 33: Line 70:
 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} $ 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: 
 +
 +  - 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 45: Line 179:
 $$\mathrm{Taks\ utilization:}\quad  u_i = \frac{C_i}{T_i} $$ $$\mathrm{Taks\ utilization:}\quad  u_i = \frac{C_i}{T_i} $$
 $$\mathrm{System\ utilization:}\quad  U = \sum_i u_i$$ $$\mathrm{System\ utilization:}\quad  U = \sum_i u_i$$
 +
 +kde $T_i$ odpovídá periodě.
  
 Pro rozvrhnutelné systémy platí Pro rozvrhnutelné systémy platí
Line 50: Line 186:
 $$ U \le n\big(2^{\frac{1}{n} - 1} \big)$$ $$ U \le n\big(2^{\frac{1}{n} - 1} \big)$$
  
-(work in progress...)+** 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).  
 + 
 +{{:statnice:bakalar:pasted:20250605-080331.png?600}} 
 + 
 +(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) 
 + 
 +{{:statnice:bakalar:pasted:20250605-085713.png?400}} 
 +{{:statnice:bakalar:pasted:20250605-085731.png?200}} 
 + 
 +  * Je rozvrhovatelné pokud Ri <= Di 
 + 
 +** 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 [[statnice:bakalar:b4b35psr#sdilene_zdroje_v_systemech_realneho_casu|části o sdílených zdrojích]] 
 ===== 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)