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. +more 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. +more 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ů

Kategorie:Algoritmy plánování procesů