每个程序员都应该知道的关于RMA的三件事情

原文：

http://www.embedded.com/electronics-blogs/barr-code/4206206/Three-Things-Every-Programmer-Should-Know-About-RMA

翻译：Cory Xie <cory.xie@gmail.com>

实时系统的设计和RMA（速率单调算法，rate monotonic algorithms），就像花生酱和果冻一样常被搭配在一起（此系美国俚语）。那么，为什么在嵌入式社区里，无论我走到哪里，工程师们正在开发的实时系统几乎都没有应用RMA呢？这是一个很危险的境地，但是很容易补救，只要确保每个程序员都知道关于RMA的三件事情就行。

如果你对RMA是完全陌生的，这里有一个对该技术的专题介绍的链接。我写这篇专栏的方式，试图让你可以选择在阅读这些细节之前或之后看这篇专栏。在本文末尾，我还加入了一个关于实时的术语词汇表。

＃1：RMA不只是学术
您可能听说过RMA。甚至也许你都能扩展该首字母缩写（如果你不能，参考在此专栏末尾的参考词汇表）。也许你也知道，RMA的理论基础主要是在卡内基·梅隆大学的软件工程研究所开发的，且该技术已经为人们知道大约有三十年了。

但是，如果你是像我作为一个专栏作家/编辑，顾问和培训师多年来所沟通过的成千上万的固件工程师中的绝大多数一样，你可能会认为RMA只是为搞学术的人准备的。我几年前也曾这样想，但这里是一些直接的兴奋剂：

1）所有流行的商业实时 *** 作系统，如 VxWorks，ThreadX，和MicroC / OS都建立于固定优先级的抢占式调度。

动态调整任务优先级的调度程序，如桌面 *** 作系统Windows和Linux，可能会不分青红皂白地在瞬时过载期间错过死线，因此，他们不应该被用于安全关键的实时系统的设计中。

2） RMA是固定优先级分配RTOS任务的最佳方法。也就是说，如果一组任务不能被使用RMA调度，它就不能被使用任何其它固定优先级算法调度。

3） RMA提供了方便的经验法则，用于获得您可以放心使用的CPU百分比，同时还能满足所有的死线。如果你不使用RMA为你的任务分配优先级，就没有其它经验法则可以确保所有死线都能得到满足。

例如，有广泛的传言说系统小于50％的负载将始终能满足其死线。不幸的是，是没有这样的正确经验法则的。与此相反，如果你的确使用RMA，那么的确有一个基于简单规则的范围，从最高的2个任务的82.8％，至最低的N个任务的69.2％。

RMA的一个重要特点是能够先验证明一组给定的任务一定能满足其死线，甚至在瞬时过载期间。动态优先级的 *** 作系统不能保证这一点。固定优先级的RTOS使用其它任务优先级分配方案时也不行。

现今太多的RTOS实时系统能够工作是靠运气。过剩的处理能力可能会掩盖设计和分析的罪行，亦或者最坏的情况只是还没有发生而已。

底线：如果你不使用RMA为关键任务分配优先级的话，那么你是在玩火；在你产品的用户引火烧身之前，它可能只是一个时间问题。

也许你没有使用RMA来指定任务优先级并证明其能满足死线，正好说明了你的客户一直在抱怨的一个或多个这类"毛刺"？

＃2：RMA不必对每个任务都采用

正如任何已经把RMA付之实践的程序员会告诉你的，分析阶段最困难的部分在于为每个任务的最坏情况下的执行时间建立一个上限。每个任务的CPU利用率的计算是最坏情况执行时间与最坏情况下的周期的比值。（建立一个任务的最坏情况下的周期，要更容易且更稳定些。）

 

有三种方式可以得出执行时间的上限：（1）通过测量在被测的最坏情况下的实际执行时间;（2）通过与一个周期计数器(cycle-counter)结合，对代码执行自顶向下的分析; 或（3）在大O表示法基础上作出猜测。

我把这些可选方式分别叫做测量(measuring)，分析(analyzing)和预算(budgeting)，请注意，决定使用其中哪一个要涉及对精度与工作量水平的权衡。

测量(measuring)可以非常精确，但需要有对实际的工作代码进行分析和测试的能力，并且必须在每次代码更改后重新测量。预算(budgeting)是最简单的，甚至可以在项目开始的时候就进行，但它一定是不准确的（在保守的方向上，可能要求比实际需要更多的CPU带宽）。

但至少在分析(analyzing)方面还是有一些好消息的。RMA不必对系统中的整个任务组来执行。它可以定义一个较小的（相对要少得多，以我的经验）需要执行RMA的关键任务组，对剩下的非关键任务可以简单地分配较低的优先级。

这个关键的任务组应包含所有不能错过死线的任务。此外，它应该包含与该组任务要么共享互斥体，要么需要他们及时发射信号或消息队列的任何其他的任务。所有其他任务被认为是非关键的。

RMA可以有意地仅仅应用于关键任务组，只要我们确保所有的非关键任务的优先级低于整个关键组的优先级。这样我们只需要为关键组确定最坏情况下的周期和最坏情况下的执行时间。此外，我们只需要按照速率单调算法对关键组进行优先级分配就可以了。

底线：当没有死线时，任何任务都可以在较低的优先级。

＃3：RMA也适用于中断服务程序

除了少数例外，当书籍，文章和论文中提到RMA时，都将它描述为一种在抢占式固定优先级的 *** 作系统中指定任务优先级的技术。但该技术对于正确指定中断处理程序的优先级也是必不可少的。

事实上，即使你已经设计了一个实时系统，只包含中断服务例程（加上一个什么都不做的后台主循环），你也应该使用速率单调算法，基于他们最坏情况下的发生频率来考虑他们的优先级。然后，你可以使用速率单调分析来证明，他们都将满足他们的实时死线，即使在瞬时过载的情况下也如此。

图1 RMA适合的Real-Time层次

此外，如果你有一组重要的任务，除了在上面的图1所示的中断服务例程，与RMA相关的优先级分配和分析需要在这些实体整体上执行。

（请注意，即使有一个或多个中断自己不具有实时死线，这仍然是必要的；这是因为中断可能会在瞬态过载时发生，从而阻止一个或多个关键任务组满足其真正死线） 。

这可能比较复杂，因为有一个CPU硬件所规定的任意的"优先级边界"：即使是最低优先级的ISR也被认为是比最高优先级的任务更重要。

例如，考虑下面的表1中ISR和任务组的冲突。 RMA决定了任务A的优先级应高于ISR的优先级，因为任务可能会发生得更频繁。

但硬件的要求与此却不同，这限制了我们将中断服务程序的优先级降低的能力。如果我们任由如此，我们不能简单地将这组实体的CPU使用率相加，来看他们是否低于四个实体的可调度边界。

表1 优先级设置有误的中断处理程序

那么，在这样一个冲突的情况下，我们应该怎样做呢？有两种选择。要么我们改变程序的结构，移动ISR代码到一个优先级为2的轮询循环周期为10 ms的任务中，在这种情况下，总利用率为51％。

或者我们把ISR假设认为它实际上最坏情况下的周期为3 ms，毕竟这里只是为了通过速率单调分析得出证据。对于后一个选项，ISR 按照RMA来说具有大致的最高优先级，但专用于该ISR的CPU带宽从5％增加至16.7％ - 带来新的总量高达62.7％。

无论哪种方式，整组都被证明是可调度的。但是，将代码切换成使用轮询，实际上消耗了另一个解决方案中保留用于最坏情况的时间。这可能意味着在平均情况下没有用以低优先级非关键任务的CPU时间。

底线： 中断处理程序必须被作为关键组的一部分来考虑，使用RMA相对于他们可能会从中偷走CPU时间的任务优先级，来分配他们的优先级，。

结论：每个程序员都应该知道有关RMA的三个关键事情。 首先， RMA技术应该被用来分析具有死线的任何抢占式系统，毕竟它不只是为学术而生。 第二，在RMA分析中所涉及的工作量可以被减少，只要通过忽略关键组之外的任务，且非关键任务可以使用任意方案被分配到较低的优先级，从而不必分析。 第三，如果中断可以抢占关键组任务，或者甚至只是他们彼此之间抢占，RMA也应该被用来分析这些中断。图1通过把RMA的作用正确地定位，强调了所有三个点。

名词解释：实时术语

死线(deadline )：名词，一个特定的作业必须给出其结果的(最晚)时间。

作业(job)：名词，组成一个特定的决定，运算，数据传输，或它们的组合的软件，内存和其他 *** 作的集合。

互斥量(mutex)： 名词，由RTOS提供的用于安全保护共享资源的多任务感知的二进制标志。是相互排斥(MUTual EXclusion)的简称。术语互斥量(mutex)，只应用于当 *** 作系统包含有防止无界优先级反转(unbounded priority inversion)的实现的情形。

周期(period) : 名词，任务或ISR调用的连续运行时间之间的最小长度。可以被认为是作业的最小间隔时间。

抢占式调度(preemptive scheduling)，名词，多任务的一种方式，支持当另一任务就绪时就中断正在运行的任务，以便可以立即使用处理器。在任何时候，保证在运行的是就绪的优先级最高的任务。

优先级(priority): 名词，一个任务或中断相比于另一个的相对排名。对于任务的情况，优先级是由程序员分配的一个整数，抢占式调度器用其跟所有就绪任务的优先级进行比较，选择一个来使用处理器。请注意，每个中断都比即使是高优先级的任务具有更高的优先级，这是为处理器设计的"特性"。

优先级倒置 (priority inversion)：名词，实时系统的失误，其中一个高优先级的任务，被中等优先级的任务阻止其使用CPU。关键的第一步是高优先级任务阻塞，等待一个低优先级任务，与它通过一个互斥体共享一些全局资源。RMA只有在完全防止优先级倒置时能提供证据，通常是通过修改互斥量系统调用的方式。

实时系统(real-time system): 名词，具有死线的计算机系统。如果错过死线就像得到错误结果那么糟糕，那么该系统就是一个实时系统。如果错过了死线的后果是死亡或任务失败，系统会进一步归类为"硬实时系统"。在硬实时系统和没有死线的系统两者之间的一切系统，称为 "软实时系统"。

结果 (result): 名词，作业的成果。

RMA: 简称，Rate Monotonic Algorithm或者Rate Monotonic Analysis的短称，每一个都在这篇文章里有解释。

RTOS:名词，基于优先级的抢占式调度的 *** 作系统。Real-Time Operating System，即实时 *** 作系统的简称。

可调度约束(schedulable bound): 名词，总的CPU利用率的上限，用于建立一组使用RMA分配优先级的任务一定能满足其死线的最简单的证据。调度约束是基于你分析的任务数量，范围从2个任务的82.8％到69.2％。在对单个任务的最坏情况利用率分析时，RTOS开销，如上下文切换时间和系统调用都被计算在内。

共享资源 (shared resource): 名词，两个或多个任务或任务和ISR访问的数据结构或外设。每一个共享的资源应该由互斥锁保护。

任务(task)，名词，包含一个无限循环，开始等待RTOS的信号，另一个任务或ISR的函数，然后在再次等待前运行作业。

瞬时过载 (transient overload): 名词，一段时间，在此期间，立刻诸事不顺(everything goes wrong at once)，使每个任务和ISR需要同时运行。在这段时间内，CPU可能会不足以满足对其提出的所有的要求。