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 periodických procesů, existuje plánování, které vždy splní deadline, pokud je využití CPU :

Kde je výpočetní čas potřebný pro proces, je perioda procesu.

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

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ů