RMS

单调速率调度

RMS（单调速率调度算法）是一种静态优先级调度算法，是经典的周期性任务调度算法。RMS的基本思路是任务的优先级与它的周期表现为单调函数的关系，任务的周期越短，优先级越高；任务的周期越长，优先级越低。如果存在一种基于静态优先级的调度顺序，使得每个任务都能在其期限时间内完成，那么RMS算法总能找到这样的一种可行的统调度方案。

RMS

RMS（Rate-Monotonic Scheduling）调度算法

简介

RMS是单处理器下的最优静态调度算法。1973年Liu和Layland首次提出了RMS调度算法在静态调度中的最优性。它的一个特点是可通过对系统资源利用率的计算来进行任务可调度性分析，算法简单、有效，便于实现。不仅如此，他们还把系统的利用系数（utilization factor）和系统可调度性联系起来，推导出用RM调度所能达到的最小系统利用率公式。同时，这篇论文中透露出来的证明思想和方法也被人们所效仿。下面就让我们来看看这篇文章中关于RM调度算法的重要结论。

任何一个结论都有一个模型假设，让我们先列出这里的假设：

（A1）所有的任务请求都是周期性的，必须在限定的时限内完成；

（A2）任务的作业必须在该任务的下一个作业发生之前完成，这样避免了考虑队列问题；在这里，我们对任务和作业不作特别的区分，因为一个任务请求就是一个作业。

（A3）任务之间都是独立的，每个任务的请求不依赖于其他任务请求的开始或完成；

（A4）每个任务的运行时间是不变的，这里任务的运行时间是指处理器在无中断情况下用于处理该任务的时间；

（A5）所有的非周期性任务都在特殊的情况下运行，比如系统初始化或系统非正常紧急处理程序。

（A6）其它一些假设，比如，单处理器，可抢占调度，任务切换的时间忽略不计等等。

RMS算法

⑴ 任务T i (P i,Ci,D i) 模型：周期为P i，计算时间为Ci，时限D i 为周期终点。任务在周期起点释放，高优先级任务可抢占低优先级任务的执行。

⑵ 优先级分配方法：静态固定分配。优先级与周期成反比，周期越短优先级越高。

⑶ 可调度性分析：如果任务集满足下式，则该任务集可调度。

定理1

n个独立的周期任务可以被RMPA调度，如果U<=n(2^(1/n)-1）。

一个任务的响应时间（response time）是指一个任务请求，这个任务实际完成的时间跨度。在静态调度中，任务的临界时刻（critical instant）这个概念被首先提出来，它被定义为一个特定的时刻，如果在这个时刻有这个任务的请求，那么这个任务就会需要最大的响应时间，由此得出：

定理1：一个任务的临界时间就是比这个任务优先级高的所有任务同时发出请求的时刻。

证明：由于一个任务的响应时间，是它自己的负载时间，加上被其它优先级高的任务所打断的时间。由于自己的负载时间是固定的，我们考虑在什么时候任一高优先级的任务会有最长的打断时间。显然，只有当这一高优先级的任务与该任务同时请求处理时，才能可能产生最大的打断时间。

定理1的价值在于它找到了一个证明、一个调度算法，能否调度任一任务集充分必要条件，那就是所有任务同时请求执行的时的情况下，每个任务仍能满足各自的期限，那么这个任务集就可以被这个调度算法调度。

有了这个推论，我们就可以证明RM调度的最优性了。

定理2

如果一个任务集能够被静态调度，那么RMS算法就能够调度这个任务集。从这个意义上说，RMS是最优的静态调度算法。

这个定理的证明方法就是有名的交换法。

证明思路如下：

假设一个任务集S采用其他静态优先级算法可以调度，那么总有这样两个优先级相邻的任务i和j，有Ti>Tj，而Pi≤Pj。把Ti和Tj的优先级Pi和Pj互换，明显可以看出这时S仍然可以调度，因为在所有任务同时请求的情况下，交换这两个任务不会影响其它任务的完成时间，同时这两个任务都可以在各自期限内完成，按照这样的方法，其他任何静态优先级调度最终都可以转换成RM调度。

RMS已被证明是静态最优调度算法，开销小，灵活性好，是实时调度的基础性理论。即使系统瞬时过载，也完全可预测哪些任务丢失时限。缺点是处理机利用率较低，最坏的情况下，当n→∞时，不超过ln2（≈ 70%）。另外，RMS是充分但非必要条件。而在一般情况下，对于随机的任务集大约只有88%。70%或者88%的处理器利用率，对于许多实时应用来说是一个严重的限制，动态调度算法如最早截止期、最先（earliest deadlinefirst，EDF）或者最少空闲时间最先（least laxity first，LLF）已经被证明是最优的，并且能够实现100%的处理器利用率。

调度

具有资源同步约束的RMS调度

当实时任务间共享资源时，可能出现低优先级任务不可预测地阻塞高优先级任务执行的情况，叫优先级倒置。这时RMS 算法不能保证任务集的调度，必须使用有关协议控制优先级的倒置时间。常用的协议有优先级顶级协议和堆资源协议，使用这些协议可使优先级的倒置时间最多为一个资源临界段的执行时间，并且不会发生死锁。

基于RMS 的非周期任务的调度

实时系统中的非周期任务可采用延迟服务器算法或随机服务器算法进行调度。它们的最大特点是可在周期任务的实时调度环境下处理随机请求。两者的基本思想是将非周期任务转化成周期任务，再利用RMS算法进行调度。前者用一个或几个专用的周期任务执行所有非周期任务，这种周期任务叫非周期任务服务器。根据周期大小，服务器有固定优先级，服务器的执行时间被称为预算，它在每个服务器周期Ts的起点补充。只要服务器有充足的预算，就可在其周期内为非周期任务服务。该算法实现简单，但可调度性分析较难，有时会出现抖动，可能发生一个非周期任务在相邻两个服务器周期中连续执行2倍预算的现象，与RMS理论不符，需要适当修改RMS算法。随机服务器算法与延迟服务器算法相似，但预算不是在每个周期起点补充，而是在预算消耗Ts时间之后再补充。该算法与RMS分析算法一致，但实现复杂。

RMS代表的其它释义

均方根

RMS（Root Mean Square）就是均方根，实际就是有效值，是一组统计数据的平方和的平均值的平方根。

RMS=sqrt[(x1^2+x2^2+......+xn^2)/n]

英语写为：Root Mean Square（RMS）.

美国传统词典的定义为：The square root of the average of squares of a set of numbers.

即：将N个项的平方和除以N后开平方的结果，即均方根的结果。

均方根应用：

在直流（DC）电路中，电压或电流的定义很简单，但在交流（AC）电路中，其定义就较为复杂，有多种定义方式。均方根（rms）指的是定义AC波的有效电压或电流的一种最普遍的数学方法。

要得出rms值需要对表示AC波形的函数执行三个数学操作：

⑴计算波形函数（一般是正弦波）的平方值。

⑵对第一步得到的函数求时间平均值。