Visa källa för 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 [[Tidsperiod|period]] varje [[process (datorteknik)|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 <ref>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.</ref> att gälla om alla processer ska klara sina tidsgränser och alltså ska vara schemaläggningsbara:
:<math>U \leq n(2^{\frac{1}{n}} - 1)</math>
Där <math>n</math> är antalet processer som ska schemaläggas, och <math>U</math> ä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:
:<math>U = \sum_{i=1}^{n} \frac{C_i}{T_i}</math>
Där <math>C_i</math> är exekveringstid (den tid det tar att köra en process) och <math>T_i</math> ä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 <math>U</math> går mot 0,69:

:<math>\lim_{n \rightarrow \infty} n(\sqrt[n]{2} - 1) = \ln 2 \approx 0.693147\ldots</math>

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<ref>Enrico Bini, Giorgio C. Buttazzo and Giuseppe M. Buttazzo. Rate Monotonic Analysis: the Hyperbolic Bound. IEEE Transactions on Computers, 2003, volym 52, s. 933-942</ref>, som är tajtare än Liu och Laylands:

:<math>\prod_{i=1}^n (U_i +1) \leq 2</math>

==Källor==
<references/>

[[Kategori:Schemaläggningsalgoritmer]]
[[Kategori:Datavetenskap]]