Från Rilpedia

Du har inte behörighet att redigera denna sida, av följande anledning:

Du kan se och kopiera denna sidas källtext:

<noinclude>{{rpsv.from.wpsv}}</noinclude>'''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 (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 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 <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. 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. 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== <references/> [[Kategori:schemaläggningsalgoritmer]] [[Kategori:datavetenskap]] [[cs:Rate monotonic scheduling]] [[de:Rate Monotonic Scheduling]] [[en:Rate-monotonic scheduling]] [[fr:Rate-monotonic scheduling]] [[hu:Rate Monotonic Scheduling]] [[ja:レートモノトニックスケジューリング]] [[ko:비율 단조 스케줄링]]

Tillbaka till Rate-monoton schemaläggning.