Från Rilpedia

Rate-monotonic Scheduling (RMS) är en schemaläggningsalgoritm som kan översättas till ungefär "period-monoton schemaläggning" och används inom datalogi, speciellt inom kategorin realtidssystem.

För att använda sig av RMS, börjar man med att ta reda på vilken period varje process ska ha, det vill säga hur ofta processen körs. Därefter tilldela varje process en prioritet. Denna prioritet baseras på hur lång period processen ska köras. Den process som har längst period får lägst prioritet.

När sedan schemaläggningen startas så körs alltid den process som har högst prioritet tills den är färdig, och sedan väljer man nästa process i kön.

Följande formel bevisades 1973 av Liu och Leyland ^[1] att gälla om alla processer ska klara sina tidsgränser och alltså ska vara schemaläggningsbara:

Där n är antalet processer som ska schemaläggas, och U är den totala utnyttjandegraden för alla processer i systemet.

Förutsättningarna är att:

• Alla processer måste vara periodiska.
• Alla tidsgränser är satta till slutet av processens period.
• Alla processer måste vara oberoende och får alltså inte dela enheter eller andra resurser.

Utnyttjandegraden får man fram genom följande ekvation:

Där C_i är exekveringstid (den tid det tar att köra en process) och T_i är periodtid (tidslängden från att en process körs, tills att den vill köra igen).

Genom att låta n gå mot oändligheten kan man visa att U går mot 0,69. Så länge man maximalt utnyttjar datorn till 69% så är processerna alltså schemaläggningsbara med rate monotonic, men om man överskrider detta så är det inte säkert att så är fallet (även om det kan gå att schemalägga mer i vissa fall).

Källor

1. ↑ C. L. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment, Journal of the ACM, 20(1), 1973, pp. 46-61.