Rate-monoton schemaläggning

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 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 Layland att gälla om alla processer ska klara sina tidsgränser och alltså ska vara schemaläggningsbara:

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

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.
• Det inte tar någon tid att växla från en process till en annan

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

$U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}$

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:

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

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

På senare tid har en ny schemaläggningsgräns hittats av italienska forskare, som är tajtare än Liu och Laylands:

$\prod _{i=1}^{n}(U_{i}+1)\leq 2$