单调速率调度（RMS）算法（详解版）

单调速率（RMS）调度算法采用抢占的、静态优先级的策略，调度周期性任务。

当较低优先级的进程正在运行并且较高优先级的进程可以运行时，较高优先级进程将会抢占低优先级。在进入系统时，每个周期性任务会分配一个优先级，它与其周期成反比，即周期越短，优先级越高；周期越长，优先级越低。

这种策略背后的理由是：更频繁地需要 CPU 的任务应分配更高的优先级。此外，单调速率调度假定：对于每次 CPU 执行，周期性进程的处理时间是相同的。也就是说，在每次进程获取 CPU 时，它的 CPU 执行长度是相同的。

举一个例子，我们有两个进程 P₁ 和 P₂。P₁ 和 P₂ 的周期分别为 50 和 100，即 ρ₁ = 50 和 ρ₂= 100。P₁ 和 P₂ 的处理时间分别为 t₁ = 20 和 t₂ = 35。每个进程的截止期限要求，它在下一个周期开始之前完成 CPU 执行。

首先，我们应问自己是否可能调度这些任务以便每个进程都能满足截止期限。如果我们按执行与周期的比率 t_i/ρ_i 测量一个进程的 CPU 利用率，那么 P₁ 的 CPU 利用率 20/50 = 0.40，P₂ 的是 35/100 = 0.35，总的 CPU 利用率为 75%。因此，我们似乎可以调度这些任务以便满足它们的截止期限，并且仍让 CPU 有多余可用的时间。

假设为 P₂ 分配比 P₁ 更高的优先级。P₁ 和 P₂ 的执行情况如图 1 所示。

图 1 当 P₂ 的优先级高于 P₁ 时的任务调度

我们可以看到，P₂ 首先开始执行并在时间 35 完成。这时，P₁ 开始，它完成 CPU 执行时间 55。然而，P₁ 的第一个截止期限是在时间 50，所以调度程序让 P₁ 错过其截止期限。

现在假设使用单调速率调度，这里 P₁ 分配的优先级要高于 P₂ 的，因为 P₁ 的周期比 P₂ 的更短。在这种情况下，这些进程执行如图 2 所示。

图 2 单调速率调度

首先，P₁ 开始，并在时间 20 完成 CPU 执行，从而满足第一个截止期限。P₂ 在这点开始运行，并运行直到时间 50。此时，它被 P₁ 抢占，尽管它的 CPU 执行仍有 5ms 的时间。P₁ 在时间 70 完成 CPU 执行，在这点调度器恢复 P₂。P₁ 在时间 75 完成 CPU 执行，也满足第一个截止期限。然后，系统一直空闲直到时间 100，这时，P₁ 再次被调度。

单调速率调度可认为是最优的，因为如果一组进程不能由此算法调度，它不能由任何其他分配静态优先级的算法来调度。我们接下来分析一组进程，它们不能使用单调速率算法来调度。

假设进程 P₁ 具有周期 ρ1=50 和 CPU 执行 t₁ = 25。进程 P₂ 的对应值是 ρ₂=80 和 t₂ = 35。单调速率调度将为进程 P₁ 分配较高的优先级，因为它具有较短的周期。两个进程的总 CPU 利用率为 (25/50)+(35/80)=0.94，因此似乎合乎逻辑的结论是：这两个进程可以被调度，并且仍让 CPU 有 6% 的可用时间。

图 2 错过截止期限的单调速率调度

图 3 显示了进程 P₁ 和 P₂ 的调度。最初，P₁ 运行，直到在时间 25 完成 CPU 执行。进程 P₁ 然后开始运行，并运行直到时间 0，这时它被 P₁ 抢占；这时，P₂ 在 CPU 执行中仍有 10ms 的剩余。进程 P₁ 运行直到时间 75，导致 P₂ 在时间 85 结束，因而超过了在时间 80 完成 CPU 执行的截止期限。

尽管是最优的，然而单调速率调度有一个限制，CPU 的利用率是有限的，并不总是可能完全最大化 CPU 资源。调度 N 个进程的最坏情况下的 CPU 利用率为

对于具有一个进程的系统，CPU 利用率是 100%；但是当进程数量接近无穷时，它大约接近 69%。对于具有两个进程的系统，CPU 利用率是 83%。图 1 和图 2 调度的两个进程的组合利用率为 75%，因此单调速率调度算法保证能够调度它们。图 3 所示的两个进程的组合利用率为 94%，因此，单调速率调度不能保证它们可以调度以便满足它们的截止期限。