Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| statnice:bakalar:b4b35psr [2025/06/10 11:24] – [Sdílené zdroje v systémech reálného času] dudactom | 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. | 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// | + | === Off-line rozvrhování |
| + | Lze použít, pokud dopředu známe | ||
| - | - Délka nesmí být kratší než maximální nutná doba ke zpracování libovolné podúlohy, aby nedocházelo k preempci: $$f> | + | Uvažujeme **úlohy** (task) s **fixní prioritou** a **periodické podúlohy** (job) se **zděděnou prioritou**, |
| - | - $f$ by též měla dělit tzv. hyperperiodu | + | |
| - | - Stejně tak je třeba | + | 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> | ||
| + | - $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 | ||
| příklad: | příklad: | ||
| Line 37: | Line 48: | ||
| {{: | {{: | ||
| - | + | Pokud nemůže být splněna některá z podmínek, je možné řešit problém například | |
| - | 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: | + | |
| {{: | {{: | ||
| - | Obecně je třeba pro rozvržení splnit tři kroky | + | Obecně je třeba |
| * volba velikosti časového okna (frame size) | * volba velikosti časového okna (frame size) | ||
| * rozdělení podúloh na do dílů | * rozdělení podúloh na do dílů | ||
| * přiřazení dílů do časových oken | * 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 |
| - | Jde respektive o fancy název pro rozvrhovač | + | |
| - | V případě, že kombinujeme cyklickou exekutivu s OS, jde o úlohu/ | + | V případě, že kombinujeme cyklickou exekutivu s OS, jde o **úlohu/ |
| - | Problémy cyklické exekutivy | + | Problémy cyklické exekutivy: |
| + | * není schopna zabránit přetečení časové dotace podúlohy | ||
| + | * nelze docílit preempce aperiodických podúloh | ||
| ** Odezva 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). | ||
| - | {{: | + | 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í ** - | + | {{: |
| - | ** 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í. | + | **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í | + | == Deadline driven |
| - | ** Kombinování RT a obyčejných úloh ** - | + | Nejjednodušší příklad - **EDF** (Earliest deadline first) |
| + | == 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ší. | 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é | + | == Background scheduling |
| + | Periodické | ||
| - | Druhou variantou je tzv. **Simple Periodic Server**, kde periodické úlohy rozvrhujeme znovu zvoleným algoritmem pracujícím s prioritou | + | Stejně jako u kradení rezervy, můžeme odložit spuštění periodických úloh a nejprve |
| - | Nevýhoodu tohoto " | + | == Simple Periodic Server == |
| + | Periodické úlohy rozvrhujeme znovu zvoleným algoritmem pracujícím s prioritou a **aperiodické úlohy spouští** tzv. // | ||
| - | Konkrétním | + | * Aperiodické úlohy jsou vykonávány, |
| + | - 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. |
| - | - Vždy když dojde k vzniku | + | |
| - | - 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: | ||
| + | |||
| + | | ||
| + | - Při příchodu | ||
| + | - 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í | ||
| příklad: | příklad: | ||
| Line 95: | Line 122: | ||
| {{: | {{: | ||
| + | **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 |
| - | + | - Na počátku $(t=0)$ je budget | |
| - | Pravidla pro konzumaci | + | - 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 | + | - Při dosažení deadline (a) pokud je připravena další úloha $d = t + \frac{e}{U}$ a dochází k obnově |
| - | - 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ě | + | |
| | | ||
| příklad: | příklad: | ||
| Line 107: | Line 135: | ||
| {{: | {{: | ||
| ===== Bezpečnostně kritický software ===== | ===== 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 | ||
| + | - " | ||
| + | |||
| + | |||
| + | == 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, | ||
| + | |||
| + | - Eliminujte hazardy skrze design | ||
| + | - Redukujte rizika skrze design | ||
| + | - Zapracujte " | ||
| + | - Doplňte varovná zařízení | ||
| + | - Zapracujte podpisy, školení, procedury, osobní ochranné pomůcky | ||
| + | |||
| + | ** safety standardy ** | ||
| + | MIL-STD-882E, | ||
| + | |||
| + | |||
| + | === 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 (" | ||
| + | * 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 | ||
| + | |||
| + | **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 ===== | ===== 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? | + | 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? |
| {{: | {{: | ||
| Line 126: | Line 228: | ||
| ** Time demand analysis ** | ** 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. | 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ý, | Tento test lze pro některé modely a rozvrhovací algoritmy považovat nejen za dostatečný, | ||
| Line 147: | Line 249: | ||
| ** Response time analysis ** | ** Response time analysis ** | ||
| - | Výpočet doby odezvy je konkrétním, | + | Výpočet doby odezvy je konkrétním, |
| Dobu odezvy lze vypočítat jako | Dobu odezvy lze vypočítat jako | ||
| Line 170: | Line 272: | ||
| {{: | {{: | ||
| + | * Je rozvrhovatelné pokud $$R_{i} \le D_{i}$$ | ||
| ** Vliv sdílených zdrojů ** | ** Vliv sdílených zdrojů ** | ||
| Line 226: | Line 329: | ||
| - | Obecně - IPCP je jednodušší na implementaci, | + | Obecně - IPCP je jednodušší na implementaci, |
| (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é...) | (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é...) | ||
| Line 233: | Line 336: | ||
| ===== Čím se liší RTOS od obecného operačního systému ===== | ===== Čí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, | + | Nad rámec normálního operačního systému, kde vyžadujeme zvláště logickou determinističnost, |
| - | Pro RTOS je důležité, | + | Pro RTOS je důležité, |
| ===== Příklady RTOS ===== | ===== Příklady RTOS ===== | ||