Differences

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

--- statnice:bakalar:b4b35psr [2025/06/10 14:20] – [Sdílené zdroje v systémech reálného času] petrstep
+++ statnice:bakalar:b4b35psr [2026/05/30 20:57] (current) – [On-line rozvrhování] mates1n
@@ Line 22: / Line 22: @@
 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í. 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 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:
+=== Off-line rozvrhování ===
+Lze použít, pokud dopředu známe všechny úlohy, které bude systém vykonávat.
-  - 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)$$
+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**).
-  - $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 $$
+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:
@@ Line 37: / Line 48: @@
 {{: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):
-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
+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.
+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 **
+** Cyklická exekutiva (Scheduler spouštící frame-based rozvrh) **
-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.
+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.
+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 **
-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}}
+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í ** -
+{{:statnice:bakalar:pasted:20250608-101026.png?400}}
-** 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.
-**Deadline-Monotonic (DM)** rozvrhovač funguje na principu přidělení výpočetního času té úloze, která má nejvyšší prioritu, kde priorita je určena podle blízkosti nejzašštího termínu vykonání. Platí - čím bližší deadline, tím vyšší priorita.
+=== On-line rozvrhování===
+== Fixed Priority rozvrhování ==
+Přidělení výpočetního času té úloze, která má nejvyšší prioritu.
-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} $
+**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.
-** Deadline driven rozvrhování ** -
+**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} $
-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.
+== Deadline driven rozvrhování (Dynamic Priority rozhodování) ==
-** Kombinování RT a obyčejných úloh ** -
+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ší.
-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.
+== 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.
-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.
+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á.
-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ý.
+== 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).
-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:
+  * 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.
-  - Na počátku $(t=0)$ je rozpočet $e$ nulový a deadline je na $d=0$.
+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.
-  - 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.
+== 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:
@@ Line 95: / Line 122: @@
 {{:statnice:bakalar:pasted:20250608-194627.png?400}}
+**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!"...
-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 budgetu:
+  - Na počátku $(t=0)$ je budget $e$ nulový a deadline je na $d=0$.
-Pravidla pro konzumaci rozpočtu:
+  - 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
-  - Na počátku $(t=0)$ je rozpočet $e$ nulový a deadline je na $d=0$.
+  - 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
-  - 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:
@@ Line 107: / Line 135: @@
 {{: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 nejzašší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).
+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}}
@@ Line 126: / Line 228: @@
 ** 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í.
+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ý.
@@ Line 147: / Line 249: @@
 ** 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.
+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
@@ Line 170: / Line 272: @@
 {{:statnice:bakalar:pasted:20250605-085731.png?200}}
-  * Je rozvrhovatelné pokud Ri <= Di
+  * Je rozvrhovatelné pokud $$R_{i} \le D_{i}$$
 ** Vliv sdílených zdrojů **
@@ Line 234: / Line 336: @@
 ===== Čí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 tu Real Time operačních systémů vyžadována tzv. //časová korektnost// (//angl. Temporal correctness//). To lze interpretovat jako "nezáleží pouze na logické korektnosti a determinističnosti výsledku, ale i jeho včasnosti".
+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 nás u RT aplikací nezajímá průměrná výkonnost, ale právě toto dodržení limitů - mluvíme tak o časové náročnosti nejhoršího možného scénáře (//angl. worst case scenario//).
+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 =====

Trace: • b4b35psr • b0b01ma2 • b0b39pgr • b0b01ma2 • playground • b0b01lgr • b0b36dbs • b4b33rpz • b4b36zui

Differences

Search

Navigation

Print/export

Tools

QR Code