Rozvrhování v systémech reálného času; časová analýza těchto systémů; správa sdílených zdrojů; bezpečnostně kritické aplikace.

B4B35PSR Webové stránky předmětu

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

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

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.

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} $

On-line rozvrhování - (TODO)

Fixed priority rozvrhování - (TODO)

Deadline driven rozvrhování - EDF (TODO)

Kombinování RT a obyčejných úloh - background scheduling, total-bandwidth server (TBS), constant utilization server (CUS) (TODO)

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

Matematicky zapsáno

$$\mathrm{Taks\ utilization:}\quad u_i = \frac{C_i}{T_i} $$ $$\mathrm{System\ utilization:}\quad U = \sum_i u_i$$

Pro rozvrhnutelné systémy platí

$$ U \le n\big(2^{\frac{1}{n} - 1} \big)$$

Time demand analysis (TODO)

Response time analysis (TODO)

TODO - vliv sdílených zdrojů

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

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

• 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