速率单调

简单单调速率分析假设线程具有以下属性:

·没有资源共享（进程不共享资源，例如硬件资源、队列或任何类型的信号量阻塞或非阻塞(忙-等待)）

·决定性的截止日期正好等于周期

·静态优先级(具有最高静态优先级且可立即运行的任务优先于所有其他任务)

·根据单调速率约定分配的静态优先级(周期/期限较短的任务被赋予更高的优先级)

·上下文切换时间和其他线程操作是免费的，对模型没有影响

它是一个数学模型，包含封闭系统中周期的计算模拟，在封闭系统中，循环调度器和分时调度器不能满足调度需求。单调速率调度着眼于系统中所有线程的运行建模，并确定满足相关线程集的保证所需的时间。

Liu & Layland刘&蕾兰(1973)证明，对于一组具有唯一周期的n个周期任务，如果CPU利用率低于特定的界限(取决于任务的数量)，就存在一个总是满足截止日期的可行调度。RMS可调度性测试是:

其中Ci是计算时间，Ti是发布周期(截止日期在一个周期之后)，n是要计划的进程数。例如，两个过程的U ≤ 0.8284。当过程的数量趋向于无穷大时，这个表达式将趋向于:

因此，粗略估计，如果中央处理器利用率低于69.32%，RMS可以满足所有期限。另外30.7%的中央处理器可以专用于较低优先级的非实时任务。众所周知，当利用率为85%或更低时，随机生成的周期性任务系统将满足所有的截止日期，^[3]但是这一事实取决于对确切的任务统计数据(周期、截止日期)的了解，而这些数据并不能保证适用于所有的任务集。

双曲线界限^[4]是比Liu & Layland提出的可调度性更严格的充分条件:

 ,

其中Ui是每个任务的CPU利用率。

单调速率优先级分配是最优的，这意味着如果任何静态优先级调度算法都可以满足所有的截止日期，那么单调速率算法也可以。期限单调调度算法在相同的周期和期限下也是最优的，事实上在这种情况下算法是相同的；此外，当截止时间小于周期时，截止时间单调调度是最佳的。对于期限大于周期的任务模型，奥德斯利（Audsley）算法通过对该模型进行精确的可调度性测试，找到了最优的优先级分配。^[5]

在许多实际应用中，资源是共享的，未修改的RMS会受到优先级反转和死锁的危害。实际上，这可以通过禁用抢占或优先级继承来解决。替代方法是使用无锁算法或避免互斥体/信号量在不同优先级的线程之间共享。这样一来，资源冲突就不会首先产生。

2.1 禁止抢占

■在实时内核中锁定CPU中断的操作系统输入关键()和操作系统输出关键()原语（OS_ENTER_CRITICAL() and OS_EXIT_CRITICAL() ），例如微处理器/操作系统（MicroC/OS-II）

■splx()原语家族嵌套了设备中断的锁定(FreeBSD 5.x/6.x)。

2.2 优先继承

• 基本优先级继承协议^[6]将持有资源任务的优先级，提升为在发出请求时请求该资源的任务的优先级。释放资源后，升级恢复之前的原始优先级。这种方法不能防止死锁，并且容易遭受链式阻塞。也就是说，如果高优先级任务顺序访问多个共享资源，它可能必须为每个资源等待(阻塞)较低优先级的任务。^[7]Linux内核的实时补丁就包括该协议的实现。^[8]

• 优先级上限协议^[9]通过为每个信号量分配上限优先级来增强基本优先级继承协议，上限优先级是访问该信号量的最高作业的优先级。如果某个作业的优先级低于某个优先级较低的关键区段的最高优先级，则该作业不能抢占该区段。这种方法可以防止死锁，并将阻塞时间限制在一个较低优先级关键部分的最大长度。这种方法可能是次优的，因为它会导致不必要的阻塞。优先级上限协议在VxWorks实时内核中可用。它也被称为最高锁的优先级 (HLP)。 ^[10]

优先级继承算法可以用两个参数来表征。首先，继承是懒惰的(仅在必要时)还是直接的(在冲突发生前提高优先级)。其次是继承乐观(增加最小数量)或悲观(增加超过最小数量):

在实践中，惰性算法和即时算法之间没有数学上的区别(就Liu & Layland系统的使用范围而言)，即时算法的实现效率更高，因此它们是大多数实际系统使用的算法。

使用基本优先级继承的一个例子与“火星探路者重置错误（Mars Pathfinder reset bug）”有关， ^[11][12]该错误是通过改变信号量的创建标志以启用优先级继承而在Mars上修复的。

利用率将为:

对于3个进程，我们可以得出系统是可调度的充分条件为:

因为   该系统肯定是可调度的。

需要注意的是，这个条件不是必须的。因此，我们不能说高利用率的系统不能用这种调度算法来调度。