RMS

定义

RMS 是一种面向周期任务的固定优先级调度策略。系统为每个任务预先指定一个优先级,分配依据只有任务周期一项:周期越短,任务被赋予的优先级越高;周期越长,优先级越低,优先级在运行过程中不再改变^[2][6]。这一规则也可以理解为把优先级写成任务释放速率的单调递增函数,速率高即周期短的任务先执行,算法名称由此而来^[7]。

在经典任务模型中,每个任务用一个三元组描述:周期 $T_i$、最坏执行时间 $C_i$ 与截止期 $D_i$,通常假定截止期等于周期,任务在每个周期开始时释放,并允许高优先级任务抢占正在运行的低优先级任务^[1]。任务之间相互独立、无共享资源,任务切换开销忽略不计,所有任务都是周期性的,这些假设是 RMS 可调度性分析成立的前提^[8][5]。

原理

RMS 的调度过程本身非常简单:调度器在就绪队列中总选择优先级最高的任务运行,由于优先级事先算好,运行时不需要额外运算,只做一次比较即可^[2]。任务的时间特征用处理器利用率衡量,即各任务执行时间与周期之比的总和 $U=\sum_{i=1}^{n} C_i/T_i$,它表示处理器被占用的比例^[9]。

判断任务集是否可调度有两类方法。第一类是利用率上界测试:Liu 与 Layland 证明,对 n 个截止期等于周期的独立周期任务,只要 $U \le n(2^{1/n}-1)$,所有任务必定满足时限^[4]。该上界随任务数增加而下降,n=1 时为 1,n=2 时约为 0.828,n=3 时约为 0.780,当 n 趋于无穷时收敛于 $\ln 2 \approx 0.693$^[8][3]。这一测试是充分的而非必要的,利用率高于上界的任务集仍可能被成功调度,因此结果偏保守^[10]。

第二类是精确测试,其出发点是临界时刻概念:当某任务与所有优先级高于它的任务在同一时刻同时释放时,该任务承受最大的干扰,响应时间最长;只要在这种最坏情况下各任务都能赶上第一次截止期,之后的每个周期也都能满足^[11][1]。最坏响应时间 $R_i$ 可由下面的不动点迭代求出,初值取 $R_i^{(0)}=C_i$,反复代入直至收敛^[12]:

其中 $hp(i)$ 表示优先级高于任务 i 的任务集合。若迭代收敛且最终值不超过该任务的截止期,则任务可调度;若迭代过程中数值超过截止期,则判定不可调度^[13]。这一方法由 Joseph 与 Pandya 提出,是固定优先级调度的精确判据^[14]。

flowchart TD

A[任务集: 周期 Ti、执行时间 Ci] --> B[按周期从小到大排列]

B --> C[周期短者优先级高]

C --> D[计算总利用率 U]

D --> E{U ≤ n(2^(1/n)-1) ?}

E -- 是 --> F[判定可调度]

E -- 否 --> G[计算各任务最坏响应时间 Ri]

G --> H{Ri ≤ Di ?}

H -- 是 --> F

H -- 否 --> I[判定不可调度]

发展历程

1973 年,Liu 与 Layland 在《ACM 杂志》第 20 卷发表论文,首次把速率单调优先级分配与固定优先级调度的最优性问题联系起来,并给出利用率上界公式,这篇论文奠定了实时调度理论的基础^[3][4]。同期 Serlin 也独立得到了类似的上界结果^[4]。

此后研究集中在如何降低利用率测试的保守性。Joseph 与 Pandya 在 1986 年提出基于响应时间的精确判据;1989 年 Lehoczky、Shai 与 Ding 给出了速率单调调度的精确刻画与平均情况行为;1990 年前后 Lehoczky 进一步把分析扩展到截止期不等于周期的情形^[12][14]。同期还出现了双曲线上界与谐波任务集上界等更紧的判定条件,后者在周期呈倍数关系时能把可调度上限提高到 0.828 左右^[3]。

2000 年前后,研究方向扩展到多处理器与容错场景。有研究把周期性任务划分为若干子集分别分配到多个处理器,按 First Fit 分配推导出对应的利用率上界;也有工作分析单个故障发生时的最坏情况,得出在利用率不超过 0.5 时可保证故障恢复后仍无任务错过截止期的结论^[15][16]。近年来还出现了用形式化方法(如实时 Maude)对 RMS 实现进行建模与验证的研究^[17]。

应用

RMS 主要用于具有严格时间约束的周期性多任务系统。嵌入式实时操作系统常采用这类固定优先级策略,在任务周期已知、负载稳定的控制软件中保证可预测性^[5]。工程实践中常用的速率单调分析(RMA)方法,就是把利用率测试与响应时间计算组合成一套离线可调度性检验流程^[18]。

由于 RMS 已被证明是单处理器固定优先级调度的最优算法,且实现开销小,它在安全关键的实时领域使用较广,车辆电子、航空电子等系统都有采用^[17]。在飞行器控制软件中,定时器任务、通信任务、系统布局任务等周期任务可按周期长短依次确定优先级,再对整个任务集做可调度性验证^[19]。在消费电子与图形处理芯片的存储仲裁中,也有实现借鉴 RMS 思路为高优先级请求设定阻塞计时器^[20]。

局限

利用率上界测试偏保守,是其最常被提及的缺点。大量总利用率高于 $n(2^{1/n}-1)$ 但仍可调度的任务集会被判为不可调度,需要改用计算量更大的精确测试才能确认^[10]。在任务数较大时,最坏情况下的可调度上限只有约 69.3%,与最早截止期优先(EDF)等动态优先级算法在理论上可接近 100% 的利用率相比存在明显差距^[8][21]。

RMS 的最优性依赖一组较强的假设。当任务截止期小于周期时,速率单调分配不再最优,应以截止期单调(DM)顺序替代;当任务之间存在共享资源、需要互斥访问时,低优先级任务持锁会造成高优先级任务的阻塞,分析中必须引入阻塞项,否则结论失效^[22][23]。若任务有非零释放偏移、采用非抢占调度,或存在执行时间超出预算的情况,RMS 的最优性同样不成立^[24]。

算法只按周期排优先级,不考虑任务的重要程度。一个周期长但业务上关键的偶发任务会被赋予很低的优先级,可能长期得不到调度,这也是后续研究者提出综合任务重要度、截止期等多项指标改进算法的原因^[5]。传统 RMS 也只适用于周期任务,非周期任务需要借助轮询服务器、偶发服务器等机制转换处理,才能纳入分析框架^[25][19]。在多处理器系统中,任务到处理器的分配相当于装箱问题,分配不当会使整套 RMS 分析失效^[9]。

参见

• 最早截止期优先 —— 按截止期远近动态分配优先级的实时调度算法,常与 RMS 对比。

• 截止期单调调度 —— 以相对截止期取代周期分配优先级的固定优先级算法,适用于截止期小于周期的任务。

• 实时操作系统 —— RMS 的主要运行环境,负责任务调度与时限管理。

• 优先级反转 —— 共享资源互斥访问时高优先级任务被低优先级任务阻塞的现象,会影响 RMS 分析的有效性。

• 响应时间分析 —— 计算任务最坏响应时间、判定固定优先级任务集可调度性的精确方法。

• 速率单调分析 —— 以 RMS 为基础发展出的可调度性分析工程方法体系。