Rate monotonic scheduling

Algoritmus RMS je plánovací algoritmus používaný v operačních systémech reálného času (RTOS) se statickým přidělováním priorit.

Úvod

Výběr plánovacího algoritmu záleží na cílech, které chceme sledovat. Představme si, že máme 5 úloh, z nichž každá trvá 100ms. Systém může vykonat jednu po druhé podle pořadí (nejdříve první, pak druhou, atd...). Práce systému zabere 500ms. Ale co když jedna z nich nebo více má deadline? Když například 4. úlohu musíme vykonat do 300ms (například akční zásah do systému v případě řízení). Pokud ji vykonáme jako 4., bude splněna až po 400ms a to je již pozdě. Dále předpokládejme, že výše zmíněné úlohy jsou periodické. Jde například o počítač, který řídí jistý proces (např. průmyslová automatizace) a má za úkol:

• snímat data
• odesílat je po síti
• zobrazovat
• vyhodnocovat akční zásahy
• vykonat akční zásah na V/V zařízení.

V systému tak běží jedna nebo více úloh, které jsou periodické (v nejjednodušším případě měření dat každých 100ms v měřícím systému). Uvažujeme tak úlohy, které vyžadují konstantní čas CPU a musí skončit během své periody (sebrání dat a vyvození akčního zásahu). O systému, který vytváří takové prostředí můžeme mluvit jako o fixed-priority preemptive RTOS (Operační systém reálného času s preempcí a fixní prioritou úloh).

Podmínky za nichž můžeme RMS použít

Algoritmus RMS můžeme použít pokud:

• Procesy nesdílejí zdroje
• Deadlines jsou rovny periodám procesů
• Statické priority s preempcí (úloha s vyšší statickou prioritou, která je připravena, způsobí okamžitě preempci ostatních úloh s nižší prioritou)
• Statické priority jsou stanovovány podle délky periody (úloha s vyšší periodou má nižší prioritu)
• Přepínání kontextů a jiné vláknové operace jsou "zdarma" a nemají dopad na model

Plánovatelnost skupiny úloh

Skupina úloh je plánovatelná, pokud všechny úlohy ze skupiny pokaždé splní svůj deadline (časový okamžik, do kterého musí proběhnout).

Liu, Leylandův limit

V roce 1973, Liu a Layland dokázali že pro skupinu $n$ periodických procesů, existuje plánování, které vždy splní deadline, pokud je využití CPU $U$:

$U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq n({\sqrt[{n}]{2}}-1)$

Kde $C_{i}$ je výpočetní čas potřebný pro proces, $T_{i}$ je perioda procesu.

Pokud roste počet procesů k nekonečnu, je limita výrazu:

$\lim _{n\rightarrow \infty }n({\sqrt[{n}]{2}}-1)=\ln 2\approx 0.693147\ldots$

Cíle a vlastnosti algoritmu

Priorita je úlohám přidělována podle jejich periody: čím kratší perioda úlohy, tím větší priorita. Úlohy jsou periodicky spouštěny za sebou podle přidělené priority. Chceme dodržet deadlines všech úloh a splnit je v rámci jejich periody. Zdůrazněme, že RMA je static-priority algoritmus = priorita je pro danou úlohu statická, nemění se. Algoritmus RMA je optimální static-priority plánovač. Tím chceme říci: Pokud skupina úloh nemůže být úspěšně plánována pomocí algoritmu RMA, neexistuje static-priority algoritmus, který by plánování provedl úspěšně. Jedna z hlavních limitací static-priority plánování je ten, že není vždy možné plně využít kapacity CPU.

Někdy není možné pomoci fixních priorit dosáhnout plánovatelnosti úloh a je třeba zkusit dynamické přidělování priorit. To zatím není v mnoha RTOS standardem.

Závěr

• Analyticky domyšlený algoritmus: analyticky určena podmínka dodržení termínů dokončení: viz Liu, Leylandův limit
• Používáno v mnoha RTOS
• Vypracovány i způsoby spolupráce sdílených systémových prostředků