statnice:bakalar:b4b35psr

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Rozvrhování v systémech reálného času; časová analýza těchto systémů; správa sdílených zdrojů; bezpečnostně kritické aplikace. ======
 

[[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))?
  * 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.

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

{{:statnice:bakalar:pasted:20250604-090409.png?400}}

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

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

  - **Každá podúloha** se musí vejít do **jednoho frame**, aby nedocházelo k preempci: $$f>max(C_i)$$
  - $f$ **dělí hyperperiodu** a tedy i** alespoň jednu z period**: $$ \Big\lfloor \frac{T_i}{f} \Big\rfloor = \frac{T_i}{f} $$
  - 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:

{{: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** (task splitting):

{{: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.

** Cyklická exekutiva **
(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:
  * není schopna zabránit přetečení časové dotace podúlohy (předpokládá správný rozvrh)
  * nelze docílit preempce aperiodických podúloh

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

{{:statnice:bakalar:pasted:20250608-101026.png?400}}


=== 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 nejzazšího 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 termínem nejzazší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í 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). 

  * Aperiodické úlohy jsou vykonávány, když:
     - není připravena **žádná periodická úloha**
     - je **nenulový budget**
  * Po uplynutí periody dochází k obnovení budgetu. Pokud ovšem server dokončil vykonávání úlohy, a je ve stavu //idle//, má automaticky nulový budget.

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: 

  - Na počátku $(t=0)$ je budget nulový a deadline je $d=0$.
  - 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
  - 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:

{{:statnice:bakalar:pasted:20250608-194627.png?400}}

**Constant Utilization Server** (CUS) 
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:
  - Na počátku $(t=0)$ je budget $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 budget
  - 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:

{{:statnice:bakalar:pasted:20250608-194545.png?400}}
===== Bezpečnostně kritický software =====

=== Proces vývoje bezpečnostně kritického SW ===
== 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


=== 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ě:
  * SIL 1 - selhání jednou za 10 let
  * SIL 2
  * SIL 3
  * SIL 4 - selhání jednou za 10 000 let

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:

  * návrh systému
  * dokumentaci 
  * traceabilitu ("proč je na tomhle místě právě tenhle kus kódu")
  * verifikaci a validaci
  * nezávislé kontroly a review
  * testovací pokrytí
  * používání formálních metod a doporučených postupů

== Určení SIL ==

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

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

{{:statnice:bakalar:pasted:20250604-130552.png?400}}

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

{{: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 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)

{{:statnice:bakalar:pasted:20250605-085713.png?400}}
{{:statnice:bakalar:pasted:20250605-085731.png?200}}

  * Je rozvrhovatelné pokud $$R_{i} \le D_{i}$$

** 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í 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 =====

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 =====

  * **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
Trace: • b0b01lag • b4b01dma • b4b36zui • b4b36pdv • b0b01ma2 • b6b36ts1 • b4b17eam • b0b35lsp • b4b33rpz • exams
Search

Navigation

Print/export

Tools

QR Code
