操作系统中的速率单调调度

引言

速率单调调度 (Rate-Monotonic Scheduling, RMS) 是操作系统中现有的实时调度器之一，用于管理任务和进程。RMS 根据任务的执行速率来确定优先级，因此执行速度更快的任务具有更高的优先级。这使其非常适合以截止日期为重要考量的实时系统。

速率单调调度根据任务执行周期的倒数来确定任务的优先级。这种优先级的数学表示非常直接：优先级 = 1 / 周期。

任务的调度方式是高优先级活动会抢占低优先级活动。这种主动特性确保了最重要的任务能够获得优先权，从而降低了在面向时间的应用程序中错过截止日期的可能性。

历史背景和发展

实时系统在20世纪60年代被认识到。速率单调调度可以追溯到它们的起源。这个概念最初由Liu和Layland在1973年提出，是调度算法的一个里程碑事件。速率单调调度的正式化被认为是开发实时系统有效任务管理方案努力中的重要一步。

RMS 是早期航空电子、航空航天和工业控制系统中的一个重要组成部分，这些系统专注于精确计时和截止日期合规性。随着技术的发展，RMS 被应用于电信、医疗、汽车系统等各种行业。

RMS 的出现与实时操作系统 (RTOS) 的发展密切相关。这种算法的完成方式成为构建 RTOS 的支柱之一。多年来，RMS 不断改进并适应各种计算环境，在实际应用中变得相当知名。

速率单调调度的特点

速率单调调度具有几个鲜明的特点，有助于其在管理实时任务方面的有效性。

• 基于周期的优先级分配： 如前所述，RMS 的优先级与任务周期成反比。这个特性使得短暂但更频繁的任务具有优先权，并与实际需求相吻合。
• 抢占式调度： RMS 是抢占式的，因此，高优先级任务可能会中断低优先级任务的执行。抢占在实时系统中被广泛使用，因为上述高优先级任务可以立即执行，而无需等待低优先级任务完成。
• 确定性行为： RMS 的一个优势在于其确定性。对于给定的任务集及其属性，RMS 将始终产生相同的结果。
• 高效的资源利用： 速率单调调度通常能实现最高的系统资源利用率，因为它优先处理频率更高的任务。它能够最大化 CPU 时间并尽快处理关键任务。

优先级反转问题

优先级反转是实时系统的一个特性，当某个低优先级任务持有某个高优先级任务所需的资源时，就会发生这种情况。结果是，第一个关键任务无法继续，优先级被暂时反转。这种行为可能会严重挑战整个系统，并影响重要任务的及时实现。

为了理解优先级反转，我们考虑一个包含三个任务的场景：高优先级任务 A、中优先级任务 B 和低优先级任务 C。任务 B 持有任务 A 所需的资源。在非抢占式系统中，如果进程 C 获得了所有必需的资源并且 CPU 被分配给它，我们就无法切换到另一个进程，除非进程 C 完成其执行。这个问题被称为优先级反转，即低优先级任务直接影响了高优先级任务的运行。

实时系统要求任务必须按时完成，而这种现象可能会导致关键操作的延迟。随着系统复杂性和任务交互性的增加，优先级反转会变得更加复杂。

对实时系统的影响

优先级反转对实时系统的影响可能是灾难性的，因为这类系统旨在在规定的时间范围内对外部刺激做出反应。以下是优先级反转的一些主要后果：

• 错过截止日期： 优先级反转也可能意味着高优先级任务会错过截止日期，从而导致系统整体性能下降。然而，未能满足截止日期可能在需要及时响应的应用程序中产生深远的影响，例如航空航天应用或医疗保健系统。
• 不可预测的行为： 优先级反转使系统变得不可预测。系统的计时行为可能难以保证，因为预期中的任务会出现意外延迟。
• 系统吞吐量降低： 系统整体吞吐量可能会受到影响，因为高优先级任务可能会由于低优先级特权任务持有关键资源而不得不等待，从而导致延迟。
• 调试困难： 解决优先级反转问题并不容易。问题的间歇性和任务之间的交互性使得调试成为一个耗时的过程。

速率单调调度如何解决优先级反转问题？

RMS 通过其抢占性以及基于任务周期的优先级分配来解决优先级反转问题。

• 抢占：RMS 中的高优先级任务可以接管低优先级任务。当高优先级任务需要访问低优先级任务持有的资源时，它可以抢占该操作并继续执行。这确保了不重要的任务不会不必要地拖延对时间敏感的操作。
• 优先级继承： 优先级继承是另一种可以与 RMS 一起使用来解决优先级反转问题的方法。在此方案中，任务在资源上的优先级会暂时提升到等待同一资源的所有任务中的最高优先级。这确保了低优先级任务不会长时间占用高优先级任务所需的资源。
• 任务优先级分配： RMS 的优先级分配方式自然而然地降低了优先级反转的概率。由于优先级是基于任务周期的，周期较短（频率较高）的任务会获得更高的优先级。这最大限度地降低了被低优先级任务阻塞高优先级任务的可能性，因为高优先级任务通常会很快完成。

虽然速率单调调度可以有效地解决优先级反转问题，但值得一提的是，这种方法可能无法在所有情况下完全解决该问题。涉及复杂且频繁的进程间通信的系统容易发生优先级反转。

速率单调调度的数学原理

• 计算任务的优先级公式

速率单调调度 (RMS) 的核心在于一个简单的公式，用于计算任务的优先级。优先级越高，执行时间越短。

优先级(i) = 1 / 周期(i)

其中

• 优先级(i) 是分配给任务 i 的优先级。
• 周期(i) 是任务 i 的执行周期。

这意味着执行时间较短的任务被分配较高的优先级，而执行时间较长的任务被分配较低的优先级。

优先级较高的任务会更频繁地出现并获得 CPU 时间。

例如，让我们考虑两个任务，任务 A 和任务 B，它们的执行时间分别为 10 毫秒和 20 毫秒。应用公式后，我们得到：

优先级(A) = 1 / 10 = 0.1

优先级(B) = 1 / 20 = 0.05

• 如此一来，任务 A 将获得比任务 B 更高的优先级（0.1），而任务 B 的优先级为（0.05），这是因为任务 A 的操作持续时间较短。这种方法将活动分为需要短时间处理的任务和不需要如此严格调度的任务。

周期与优先级的关系

在速率单调调度中，执行周期对优先级的依赖性对于理解算法如何确定其调度方式至关重要。随着任务执行周期的增加，其优先级根据其反比性质成比例地降低。

这反映了 RMS 的基本原则，即实时系统需要较短的周期。短周期代表必须反复执行的活动，并且将这些短周期作业安排在较高的优先级级别将确保它们在较长周期任务之前被调度。

考虑一组执行周期分别为 10ms、20ms 和 40ms 的任务。相应的优先级计算如下：

• 优先级(5ms) = 1 / 5 = 0.2
• 优先级(10ms) = 1 / 10 = 0.1
• 优先级(20 ms) = 1 / 20 = 0.05
• 优先级(40 ms) = 1 / 40 = 0.025

• 然而，这种关系表明，应该了解此系统中每个进程的紧急程度，确保所有需要立即关注的任务都得到优先处理。
• 如果不存在资源竞争，调度器将分配优先级最高且需要最多 CPU 时间的任务。

速率单调调度与其他调度算法的比较

调度算法是操作系统中任务调度的一个关键部分。实时系统使用多种算法，RMS（速率单调调度）是其中之一。

与循环调度 (Round Robin) 的比较

循环调度是一种最流行的分时调度算法，它在连续的间隔内依次为每个任务应用固定的时间片。当时间片结束时，任务会放弃 CPU，等待支付，然后开始下一个周期。

优先级分配

• 循环调度平等对待队列中的所有任务。
• 在 RMS 中，使用任务周期的倒数来设置优先级。

抢占

• 循环调度是一种非抢占算法，其中不存在优先级抢占。
• RMS 会被高优先级任务抢占低优先级任务。

响应时间

• 系统的性能在于公平分配，但它缺乏实时应用所需的实时可用性，因为它们有时间限制。
• 在较短的周期内，RMS 得到优先处理，以确保重要任务及时完成。

效率

• 不同的任务可能有不同的持续时间；因此，循环调度的 CPU 时间可能会被低效利用。
• 值得一提的是，RMS 的效率意味着对具有短周期的任务给予高度重视，因为这些任务通常只需要很少的 CPU 时间。

与最早截止日期优先 (EDF) 的比较

任务截止日期被用作 EDF 中设置优先级的标准。具有最早截止日期的任务首先获得优先权。以下是它与速率单调调度的比较：

优先级分配

• EDF 会考虑截止日期来分配优先级。
• RMS 根据时间框架来确定优先级。

抢占

• EDF 和RMS 都是抢占式的；高优先级进程可以替换低优先级进程。

响应时间

• 这种技术将 CPU 分配给具有最早截止日期的进程。
• RMS 通过管理短期框架内的活动来实现及时交付。

确定性

• EDF 的优先级分配也是适应性的，根据实时进程指定的截止日期进行调整。
• RMS 允许回溯确定性，因为在系统启动时就为不同的时间设置了优先级。

速率单调调度的优点

速率单调调度在操作系统中有许多优点。速率单调调度在操作系统中的一些主要优点如下：

• 确定性行为： RMS 的优点之一是其确定性。在相同条件下，RMS 将始终产生相同的调度结果。这种确定性对于实时系统很重要。
• 高效的资源利用： RMS 通过首先执行频率较高的任务来尝试利用系统上的所有可用资源。这可以节省 CPU 时间。
• 实现简单： RMS 由于其简单的优先级分配公式(优先级 = 1 / 周期)，也很容易实现。在这种算法的简单性的帮助下，调度在资源受限的环境中变得更加简单。
• 非常适合周期性任务： 在执行间隔固定的系统中，RMS 非常高效。它优先处理耗时较短的任务，从而响应实时需求的即时关键性。

速率单调调度的缺点

速率单调调度在操作系统中有一些缺点。速率单调调度在操作系统中的一些主要缺点如下：

• 同质任务的假设： 在计算中，RMS 假设所有任务在计算负载方面是相等的，并且它们的截止日期与其周期一致。在实际场景中，截止日期的数量可能会有所不同，并且可能与周期不一致。
• 灵活性有限： RMS 在满足截止日期和实现确定性行为方面表现出色，但对于需要不同计算能力的任务来说，它的灵活性较低。然而，仅根据周期分配的优先级的不灵活性可能导致不理想的调度。
• 优先级反转的风险： 尽管 RMS 的设计是为了对抗优先级反转，但如果一个系统具有复杂的结构和任务之间的相互依赖性，这个问题仍然存在。也可以应用其他方法，如优先级继承，来完全解决这个问题。
• 不适合非周期性任务： RMS 主要针对具有恒定执行周期的固定周期性任务类别。零星任务的管理可能需要额外的机制或与其他调度算法的组合。

实现速率单调调度

RMS 算法是实时系统中处理任务时最常用的算法之一。RMS 的编码要求是根据集成的 RTOS 和遵循最佳实践来实现的。

1. 编码注意事项

在开发 RMS 时，任务优先级和抢占应该正确处理，因为任务的优先级由其执行周期决定。

• 确保优先级值被存储并在必要时进行更新。

抢占机制

• 建立一种抢占式调度策略，以便高优先级任务可以接管低优先级任务。
• 实现适当的同步方法来控制关键区域并防止竞争条件。

任务结构

• 编写由任务 ID、周期、优先级、执行时间和状态等属性组成的数据结构任务的描述。
• 使用适当的参数初始化任务结构。

调度器实现

• 规划一个调度器，该调度器在特定间隔内选择就绪队列中优先级最高的任务。
• 引入任务切换和上下文存储/恢复，以确保抢占。

任务执行监控

• 通过任务计时来监控和跟踪系统生产力的评估。
• 建立处理错过截止程序的程序。

错误处理

• 整合程序来处理异常，例如错误的任务参数或调度干扰。