率單調排程(rate-monotonic scheduling)
/ RM /
假設你有好幾件各自照自己時鐘重複的家事——每小時澆花、每天收信、每月付房租。一個合理的規則是把最頻繁的家事給最高優先權,因為它在下次必須完成前的餘裕最少。率單調排程把這個規則正好套用到週期性即時任務上:一個任務的週期越短(重複越頻繁),它固定的優先權就越高。
它的運作方式:每個任務是週期性的,每隔 P 個時間單位抵達、每次需要 C 個單位的 CPU,截止期限在它週期的結尾。率單調依速率一次性、靜態地指派優先權——每 20 毫秒重複的任務勝過每 50 毫秒重複的——然後以先佔式固定優先權排程執行它們。它是最佳的靜態優先權方案:若任何固定優先權的指派能趕上所有截止期限,率單調的也能。它甚至有個簡單的充分檢驗:n 個任務的集合若它們的總 CPU 使用率保持低於 n 乘以 (2^(1/n) - 1),就可排程,這個界限在任務很多時趨近約 0.69(2 的自然對數)。
為什麼重要與它的限制:率單調是針對有週期性任務的硬即時系統的經典、被充分理解的選擇,其靜態優先權讓它易於分析、可預測。誠實的提醒:它可能無法把 CPU 用滿——它保證的使用率界限只有約 69%,所以超過此值的任務集即使 CPU 沒滿,仍可能錯過截止期限。它也假設任務獨立、週期性、且截止期限等於週期;現實(共享資源、零星任務)需要像優先權繼承這類的延伸。
任務 A:週期 50 毫秒、需 25 毫秒(使用率 0.5)。任務 B:週期 80 毫秒、需 35 毫秒(使用率 0.4375)。A 重複較頻繁,所以得到較高優先權。總使用率約 0.94——高於兩任務的界限約 0.83——所以簡單檢驗無法保證可排程,你必須直接檢查時間軸。
率單調把最頻繁的任務給最高優先權;它的使用率界限是充分但非必要條件。
這個使用率界限是充分而非必要條件:超過界限的任務集「可能」仍可排程(要檢查時間軸),但低於界限的就保證可排程。沒通過檢驗並不證明會失敗。