速率单调调度

---

速率单调调度用于实时操作系统，它是一种优先级分配，提供优先级调度类。该算法将为具有最小周期的任务分配更高的优先级。因此，该算法被称为固定优先级算法，分配给任务的时间不会改变，这反过来也不会改变优先级。所有这些优先级在执行过程开始之前就已经确定，因此不会随着时间的推移而改变。它是一个抢占式算法，当另一个具有更高优先级的进程到达时，当前进程会被抢占。这种抢占是基于分配给每个进程组的优先级级别进行的。

速率单调进程

此调度具有一个分析过程，其中包含一些线程假设，其属性如下：

• 优先级被设置为静态的，以便更高优先级的任务立即执行，抢占其他剩余的任务。

• 这些优先级是根据速率单调约定分配的。

• 不允许共享资源，例如信号量的阻塞或解除阻塞、任何硬件资源等。

• 线程函数和上下文切换周期没有限制，并且不会受到为执行而设计的模型的影响。

如果该算法满足给定的截止期限，则认为它是最佳的，这适用于任何静态优先级算法。如果给定的截止期限小于周期，则截止期限单调算法也被认为是最佳的。

下面给出的公式应该由分配的调度满足，并且应该满足其截止期限。CPU 利用率低于给定下限由用于可调度性测试的最小上限公式给出：

$$\mathrm{U\:=\:\displaystyle\sum\limits_{i=1}^n\:(\frac{Ci}{Ti})\:\leq\:n\:(2^{\frac{1}{n}}\:−\:1)}$$

在上式中：

Ci - 进程计算时间

Ti - 进程执行周期（释放周期）

N - 进程数

U - 处理器利用率。

当 n>=10 时，进行粗略的数值计算，则速率单调算法将在 CPU 利用率 <70% 的情况下满足所有给定的截止期限，剩余的 30% 可用于较低优先级的任务。

已经为较短周期的倍数任务推导出上限，并且刘和莱兰设计了这个谐波任务。它可以表示为 k 个谐波任务或链，上述公式可以改写为：

$$\mathrm{U\:=\:\displaystyle\sum\limits_{i=1}^n\:(\frac{Ci}{Ti})\:\leq\:n\:(2^{\frac{1}{k}}\:−\:1)}$$

当 k=1 时，上限达到 1.0，这得出了 CPU 的完全利用率。

刘和莱兰处理了另一个界限以获得更严格的可调度条件，这被称为双曲线界限，其公式如下：

$$\mathrm{U\:=\:\prod_{i=1}^{n}\:(Ui\:+\:1)\:\leq\:2}$$

其中 Ui 是处理器利用率。

例如

考虑三个进程及其在下面表格中给出的执行时间和周期，在这里我们计算满足计划截止期限的最小上限。

进程列表	执行率	时间
P1	2	5
P2	1	7
P3	2	10

在给定的表中，P1 与其他进程 P2 和 P3 相比具有最短的周期 5。因此，P1 将首先执行，然后是 P2，最后是 P3。

最小上限是根据所有给定进程的周期/执行率计算的，并将它们全部加在一起以获得利用率值。

$$\mathrm{U\:=\:\frac{2}{5}\:+\:\frac{1}{7}\:+\:\frac{2}{10}\:=\:0.742}$$

对于给定的三个进程，我们使用以下公式推导出计划系统：

$\mathrm{U\:=\:3\:(2^{\frac{1}{3}}\:−\:1)\:=\:0.7796\:\gt\:0.742}$ 由于满足此条件，系统可以使用最小上限值进行调度。

由于 P1 和 P3 被认为是谐波子集（因为 P3 是 P1 的 2 倍），因此可以对上述任务进行谐波分析。

$\mathrm{U_{harmonic}\:=\:K\:(2^{(\frac{1}{K})}\:−\:1)}$, k =2，所以 U 值将为 0.82

根据计算的总利用率 U，将其与 U 谐波 0.742 < 0.82 进行比较，因为导出的谐波值越高，任务可以使用谐波子集值进行调度。

结论

如上所述，如果静态优先级算法满足目标截止期限，则速率单调算法也执行相同的操作，并且它被称为最佳的。尽管速率单调调度在满足截止期限时被认为是最佳的，但它并没有满足 CPU 资源的最大利用率。当计划任务周期和截止期限彼此不同时，它可能不是最佳的。优先级旨在保持静态，并且在执行期间不能更改，因为它们是预先定义的，这可能会导致另一个进程等待更长时间。