任務按單調速率優先權分配（RMPA）的調度算法，稱為單調速率調度（RMS）。RMPA是指任務的優先權按任務周期T來分配。它根據任務的執行周期的長短來決定調度優先權，那些具有小的執行周期的任務具有較高的優先權，周期長的任務優先權低。
基本介紹
- 中文名：單調速率調度
- 外文名：RMS
- 特點：周期長
- 性質：單處理器下的最優靜態調度算法
- 全稱：Rate-Monotonic Scheduling
RMS,簡介,RMS算法,定理1,定理2,調度,RMS代表的其它釋義,均方根,有效值,
RMS
RMS（Rate-Monotonic Scheduling）調度算法
簡介
RMS是單處理器下的最優靜態調度算法。1973年Liu和Layland首次提出了RMS調度算法在靜態調度中的最優性。它的一個特點是可通過對系統資源利用率的計算來進行任務可調度性分析，算法簡單、有效，便於實現。不僅如此，他們還把系統的利用係數（utilization factor）和系統可調度性聯繫起來，推導出用RM調度所能達到的最小系統利用率公式。 同時，這篇論文中透露出來的證明思想和方法也被人們所效仿。下面就讓我們來看看這篇文章中關於RM調度算法的重要結論。
任何一個結論都有一個模型假設，讓我們先列出這裡的假設：
（A1) 所有的任務請求都是周期性的，必須在限定的時限內完成；
（A2) 任務的作業必須在該任務的下一個作業發生之前完成，這樣避免了考慮佇列問題； 在這裡，我們對任務和作業不作特別的區分，因為一個任務請求就是一個作業。
（A3) 任務之間都是獨立的，每個任務的請求不依賴於其他任務請求的開始或完成；
（A4) 每個任務的運行時間是不變的，這裡任務的運行時間是指處理器在無中斷情況下用於處理該任務的時間；
（A5) 所有的非周期性任務都在特殊的情況下運行，比如系統初始化或系統非正常緊急處理程式。
（A6) 其它一些假設，比如，單處理器，可搶占調度，任務切換的時間忽略不計等等。
RMS算法
⑴ 任務T i (P i,Ci,D i) 模型： 周期為P i，計算時間為Ci，時限D i 為周期終點。任務在周期起點釋放，高優先權任務可搶占低優先權任務的執行。
⑵ 優先權分配方法： 靜態固定分配。優先權與周期成反比，周期越短優先權越高。
⑶ 可調度性分析： 如果任務集滿足下式，則該任務集可調度。
定理1
n個獨立的周期任務可以被RMPA調度，如果U<=n(2^(1/n)-1）。
一個任務的回響時間（response time）是指一個任務請求，這個任務實際完成的時間跨度。在靜態調度中，任務的臨界時刻（critical instant）這個概念被首先提出來，它被定義為一個特定的時刻，如果在這個時刻有這個任務的請求，那么這個任務就會需要最大的回響時間，由此得出
定理1：一個任務的臨界時間就是比這個任務優先權高的所有任務同時發出請求的時刻。
證明： 由於一個任務的回響時間，是它自己的負載時間，加上被其它優先權高的任務所打斷的時間。由於自己的負載時間是固定的，我們考慮在什麼時候任一高優先權的任務會有最長的打斷時間。顯然，只有當這一高優先權的任務與該任務同時請求處理時，才能可能產生最大的打斷時間。
定理1的價值在於它找到了一個證明、一個調度算法，能否調度任一任務集充分必要條件，那就是所有任務同時請求執行的時的情況下，每個任務仍能滿足各自的期限，那么這個任務集就可以被這個調度算法調度。
有了這個推論，我們就可以證明RM調度的最優性了。
定理2
如果一個任務集能夠被靜態調度，那么RMS算法就能夠調度這個任務集。從這個意義上說，RMS是最優的靜態調度算法。
這個定理的證明方法就是有名的交換法。
證明思路如下：
假設一個任務集S採用其他靜態優先權算法可以調度，那么總有這樣兩個優先權相鄰的任務i和j，有Ti>Tj，而Pi≤Pj。把Ti和Tj的優先權Pi和Pj互換，明顯可以看出這時S仍然可以調度，因為在所有任務同時請求的情況下，交換這兩個任務不會影響其它任務的完成時間，同時這兩個任務都可以在各自期限內完成，按照這樣的方法，其他任何靜態優先權調度最終都可以轉換成RM調度。
RMS已被證明是靜態最優調度算法，開銷小，靈活性好，是實時調度的基礎性理論。即使系統瞬時過載，也完全可預測哪些任務丟失時限。缺點是處理機利用率較低，最壞的情況下，當n→∞時，不超過ln2（≈ 70%）。另外，RMS是充分但非必要條件。而在一般情況下，對於隨機的任務集大約只有88%。70%或者88%的處理器利用率，對於許多實時套用來說是一個嚴重的限制，動態調度算法如最早截止期、最先（earliest deadlinefirst，EDF）或者最少空閒時間最先（least laxity first，LLF）已經被證明是最優的，並且能夠實現100%的處理器利用率。
調度
具有資源同步約束的RMS調度
當實時任務間共享資源時，可能出現低優先權任務不可預測地阻塞高優先權任務執行的情況，叫優先權倒置。這時RMS 算法不能保證任務集的調度，必須使用有關協定控制優先權的倒置時間。常用的協定有優先權頂級協定和堆資源協定，使用這些協定可使優先權的倒置時間最多為一個資源臨界段的執行時間，並且不會發生死鎖。
基於RMS 的非周期任務的調度
實時系統中的非周期任務可採用延遲伺服器算法或隨機伺服器算法進行調度。它們的最大特點是可在周期任務的實時調度環境下處理隨機請求。兩者的基本思想是將非周期任務轉化成周期任務，再利用RMS算法進行調度。前者用一個或幾個專用的周期任務執行所有非周期任務，這種周期任務叫非周期任務伺服器。根據周期大小，伺服器有固定優先權，伺服器的執行時間被稱為預算，它在每個伺服器周期Ts的起點補充。只要伺服器有充足的預算，就可在其周期內為非周期任務服務。該算法實現簡單，但可調度性分析較難，有時會出現抖動，可能發生一個非周期任務在相鄰兩個伺服器周期中連續執行2倍預算的現象，與RMS理論不符，需要適當修改RMS算法。隨機伺服器算法與延遲伺服器算法相似，但預算不是在每個周期起點補充，而是在預算消耗Ts時間之後再補充。該算法與RMS分析算法一致，但實現複雜。
RMS代表的其它釋義
均方根
RMS（Root Mean Square）就是均方根，實際就是有效值，是一組統計數據的平方和的平均值的平方根。
RMS=sqrt[(x1^2+x2^2+......+xn^2)/n]
英語寫為：Root Mean Square（RMS）.
美國傳統詞典的定義為：The square root of the average of squares of a set of numbers.
即：將N個項的平方和除以N後開平方的結果，即均方根的結果。
均方根套用：
在直流（DC）電路中，電壓或電流的定義很簡單，但在交流（AC）電路中，其定義就較為複雜，有多種定義方式。均方根（rms）指的是定義AC波的有效電壓或電流的一種最普遍的數學方法。
要得出rms值需要對表示AC波形的函式執行三個數學操作：
⑴計算波形函式（一般是正弦波）的平方值。
⑵對第一步得到的函式求時間平均值。
⑶求第二步得到的函式的平方根。
有效值
在一個阻抗由純電阻組成的電路中，AC波的rms值通常稱作有效值或DC等價值。比如，一個100V rms的AC源連線著一個電阻器，並且其電流產生50W熱量，那么對於100V連線著這個電阻器的電源來說也將產生50W的熱量。
對正弦波來說，rms值是峰值的0.707倍，或者是峰-峰值的0.354倍。家用電壓是以rms來表示的。所謂的“117V”的交流電，其峰值（pk）約為165V，峰-峰值（pk-pk）約為330V。
