Differences

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

--- statnice:bakalar:b4b35psr [2026/05/24 10:46] – [Rozvrhnutelnost a analýza doby odezvy] mates1n
+++ 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 nejzazší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 nejzazší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 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.
+== 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 nejzazší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, nejzazší 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 108: / Line 136: @@
 ===== Bezpečnostně kritický software =====
-Popište proces vývoje bezpečnostně kritického software:
+=== Proces vývoje bezpečnostně kritického SW ===
-**fáze vývoje**-
+== Fáze vývoje ==
 (Dle MIL-STD-882E)
   - Zdokumentujte jakým způsobem je dosažena bezpečnost
@@ Line 122: / Line 149: @@
-**způsoby zmírňování nepřiměřeného rizika**
+== Způsoby zmírňování nepřiměřeného rizika ==
 Snížení rizik lze docílit následujícími kroky:
@@ Line 138: / Line 165: @@
-** Co je to ”safety integrity level”(SIL)? **
+=== 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í.
-Obecně jde o relativní úroveň snížení rizikovosti uplatněním bezpečnostních nároků.
+Úrovně:
-Standard IEC 61508 upravuje úrovně vyžadovaného ochrany proti systematickému selhání v "safety-related" systémech.
+  * SIL 1 - selhání jednou za 10 let
-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 )
+  * SIL 2
+  * SIL 3
+  * SIL 4 - selhání jednou za 10 000 let
-** Jak a kdy se určí? **
+Určení SIL testováním nemožné (protože nemáme času), místo toho se používají nepřímé metody.
-Jak:
+Vyšší SIL obecně znamená přísnější požadavky na:
-  - Identifikace hazardů - (např HAZOP)
+  * 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
@@ Line 158: / Line 199: @@
 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:
+**Kdy:**
-SIL se obecně určuje již při plánování - je to jeden z podstatných kroků analýzy bezpečnosti.
+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 ==
-** 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.
@@ Line 231: / 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 295: / 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: • b4b36zui • b4b35psr

Differences

Search

Navigation

Print/export

Tools

QR Code