D-OS-Ch05hd-Rate-Monotonic_Scheduling

Rate-Monotonic Scheduling (RMS)

Intuition

period $p$ 越短代表 deadline 會越快到達所以要先做

Implementation

此法使用 preemptive scheduling 並且有 periodic task model 的假設

我們使用 priority scheduling 並且將 priority 設定為 period $p$ 的倒數，也就是 period 越短 priority 越高

當 ready queue 中出現高 priority 的 task 就會直接搶佔 CPU

Guarantee

根據計算，只要 CPU utilization 不超過 $n\cdot (2^{1/n}-1)$ 的話 RMS 就必定不會發生 deadline miss，而超過這個數字的話就需要額外的分析了

當 $n\to \infty$ 這個數字是 $69.3\%$