Linux Deadline 调度器 - 第一部分：简介与理论背景

原文链接：https://lwn.net/Articles/743740/ 
导语：实时系统是一类必须在精确的时间限制内作出响应事件的系统，在这样的系统中，一个请求的响应正确性，不仅依赖其逻辑结果的正确性，还要求在限定期限 (Deadline) 内完成响应。在多任务操作系统（如 Linux）中，实时调度器负责协调 CPU 访问，以确保系统中所有实时任务都能在限期内完成。 Deadline 调度器便是实时调度器中的一种，本文将介绍实时调度及背后的部分理论，并会着重介绍 Linux 下的 Deadline 调度器。

作者

张金利，马涛，Linux系统工程师，来自阿里云系统组。

本文中若有任何疏漏错误，有任何建议和意见，请回复内核月谈微信公众号，或通过caspar at linux.alibaba.com或者 tao.ma at linux.alibaba.com反馈。

阿里云系统团队，是由原淘宝内核组扩建而成，2013年淘宝内核组响应阿里巴巴集团的号召，整建制转入阿里云，开始为云计算底层系统构建完善的系统支持。 阿里云系统团队是由一群具有高度使命感和自我追求的内核开发人员组成，团队中的大多数人，都是活跃的社区内核开发人员。目前的工作领域主要涉及（但不限于） Linux内核的内存管理、文件系统、网络和内核维护构建，以及和内核相关联的用户态库和工具。如果你对我们的工作很感兴趣，欢迎加入我们，请将简历发送至 tao.ma at linux.alibaba.com或者 boyu.mt at alibaba-inc.com。

Linux中的实时调度器

实时任务与非实时任务的不同之处在于前者在调度时有响应期限的约束。为满足实时任务的此类约束需求，Linux 提供了两种实时调度器：POSIX 实时调度器（下文统称为“实时调度器”），以及 Deadline 调度器。

POSIX 实时调度器可提供 先进先出（First-In-First-Out, FIFO） 和 轮转（Round-Robin, RR） 两种调度策略，根据每个任务固定优先级来进行调度，优先级最高的任务将最先被服务。在实时理论中，该调度器被归类为 固定优先级调度器 。在两个任务有同一优先级的时候，就能看出 FIFO 和 RR 调度器的区别：FIFO 调度器下，先到达的任务将先运行，一直运行到进入睡眠为止；而在 RR 调度器下，同样优先级的任务将共享处理器并以轮转方式交替运行。RR 任务得以开始运行后，将至多运行到一段最大配额时间（即时间片长度），如果该任务在时间片结束前没有阻塞，调度器会将该任务放到同优先级任务的 RR 队列末尾，然后选择下一个任务运行。

对比实时调度器，顾名思义，Deadline 调度器则是根据每个任务自己的期限 (Deadline) 来进行调度的。最短期限的任务将被最先服务。

不同的调度器针对实时任务的设置也不尽相同。在实时调度器中，用户需要提供两个参数： 调度策略 
和 固定优先级 。例如命令：

该命令表示任务 video_processing_tool 由实时调度器调度，调度策略为 FIFO (-f 参数)，优先级为10。

而在 Deadline 调度器下，用户需要设置3个参数：周期 ， 运行时间 和 期限 。

• 周期 指定了实时任务的激活模式。举个特定的例子，如果一个视频处理任务必须每秒处理60帧，新的帧每隔 16ms 会到来，那么周期就是 16ms。

• 运行时间 指应用程序产出结果所需的 CPU 时间。在大多保守情况下，运行时间必须是最坏情况执行时间（the Worst-Case Execution Time，WCET），表示该任务需要处理一个周期内工作的最长时间。例如，一个视频处理工具在最坏情况下处理一张图片可能要花费 5ms，则其运行时间为 5ms。

• 期限 指该任务需要交付结果的最长时间，是相对于周期而言的。例如，如果该任务需要在 10ms 内交付处理的帧，那么期限为 10ms。

我们同样可以使用 chrt 来设置 Deadline 调度的参数。例如，上面提到的工具可通过如下命令设置：

其中：

• --sched-runtime 5000000 表示运行时间，单位为 ns；

• --sched-deadline 10000000 表示相对的期限，单位为 ns；

• --sched-period 16666666 表示周期，单位同样为 ns；

• 0 为优先级占位符，chrt 命令所需。

通过这种方式，该任务将在每 16.6ms 内确保得到 5ms 的 CPU 时间来运行，并且这 5ms 的 CPU 运行时间都可以在 10ms 期限内保证可用。

尽管 Deadline 调度器的配置看上去复杂，实际上并非如此。通过给定应用依赖的正确参数，用户无需了解系统中的其他任务即可保证该应用在期限内交付结果。而使用实时调度器时，用户需要考虑系统中所有的任务才能定义出每个任务正确的固定优先级。

由于 Deadline 调度器知道每个任务需要多少CPU，因此也知道系统何时可以或不可以允许新的任务调度。一定程度上实时调度器允许用户使系统过载，Deadline 调度器会主动拒绝掉多余的任务，以保障 Deadline 任务都能获得足够的 CPU 时间以满足在期限内运行的条件。

实时调度概述

在调度理论中，我们评估一个调度器，是看重其调度的实时任务的运行时间要求是否都得到了满足。为了提供确定的响应时间，实时任务必须有确定性的定时行为。不同的任务模型描述了不同任务的确定性行为。

假设每个实时任务有 N 次周期性激活。激活后的任务被称为 job 。当一个 job 在上一次激活后的一个固定时间偏移后再次激活，那么这个任务就是“ 周期性的（Periodic） ”；任务也可能是“ 偶发的（Sporadic） ”：一个偶发任务将 至少 在前一次激活后一个最小时间间隔（a minimum inter-arrival time）后被再次激活；最后，任务也可能是“ 不定期的（Aperiodic） ”，没有确定的激活模式。

一个任务可以有一个 隐含期限（Implicit Deadline） ，比如期限等于其激活周期；也可以有一个 约束期限（Constrained Deadline） ，比如期限小于或者等于激活周期；当然也可以有 任意期限（Arbitrary Deadline） ，这种情况下，期限和周期不相关。

利用这些模式，通过给定任务集调度能力，实时研究者发明了一些方法来比较各种调度算法。针对单核系统，最早期限优先（Early Deadline First，EDF）调度被证明是最优算法。Deadline 调度器在单核系统上针对期限小于或等于任务周期的周期性和偶发任务是最优算法。事实上，只要一个任务集在任何时候都不会超过 100% 的 CPU 时间，对于带隐含期限的周期性或偶发性任务来说，EDF 调度算法都能成功调度所有任务。Linux 的 Deadline 调度器实现的就是 EDF 算法。

设想一下，系统中有三个周期性任务，其期限等于周期：

Task Runtime 
(WCET) Period T1 1 4 T2 2 6 T3 3 8

任务集的 CPU 使用率（U）小于 100%：

给定这样的一个任务集，EDF 调度算法将呈现出以下行为：

看图说话，每两段带箭头的线段给定的时间间隔标识了任务的周期和期限，所以每个期限里的任务都得到了运行；灰色框标识每个任务的运行时间，可以看到每个周期内的运行时间也得到了完整的保证，可谓皆大欢喜。

然而，我们却无法使用固定优先级的调度器来调度该任务集又同时满足每个任务的期限；不管优先级如何分配，总会有任务将无法按期跑完任务。其结果行为将如下所示：

继续看图，可以推测优先级是T1>T2>T3固定好的，然后一个任务周期性运行，到点了就跑，同时低优先的任务被打断。所以T1跑完T2跑，T2跑完T3跑，可是T3跑了一个单位时间之后就被T1打断了，因为T1的第二个周期开始了；接下来T1跑完了自己的时间片，T2的第二个周期还没开始，T3得以插空继续跑，可是它这次又只跑了一个单位时间之后，T2激活，再次被打断了；之后T2结束，T1继续跑，直到T3第三次跑的时候，刚运行不久就已经超过期限了：T3的周期和期限都是8个时间单位，而运行到第三个时间单位的时候，距离第一次运行已经过了9个时间单位了，超期了（标红的是第10个时间单位）。

从上面的对比可以看出，Deadline 调度器的主要优点在于，一旦知道每个任务的参数，我们无需分析其他任务并可知道所有任务都将满足期限。Deadline 调度往往可以带来更少的上下文切换。并且在单核系统中，相比固定优先级调度，Deadline 调度能够调更多的任务并满足每个任务的期限。不过，Deadline 
调度器同样也存在一些缺点。

Deadline 调度器承诺每个任务在期限内完成，但不能确保每个给定任务的最小响应时间。在固定优先级调度器下，最高优先级任务总是有着最小响应时间，这是 Deadline 调度器不能保证的。EDF 调度算法也比固定优先级算法更复杂。固定优先级的复杂度为 O(1)，相比之下 Deadline 调度器是 O(log(n))。但是，固定优先级需要用户“离线计算”出最佳的优先级集合，这有着O(N!)的复杂度。

另外，前面说的前提都是系统负载不超 100% CPU 时间，如果系统超载了，例如添加了一个新任务，或者计算了错误的 WCET，系统很可能面临多米诺效应（Domino Effect，即连锁反应）：一旦一个任务运行无法满足期限了，所有接下来的其他任务可能也会满足不了期限，如下图红色区域所示：

所有任务的运行时间都是2个时间单位，T1, T2, T3, T4 四个任务的周期和期限分别为5个，6个，7个和8个时间单位，计算 CPU 利用率 U = 2/5 + 2/6 + 2/7 + 2/8 = 533 / 420 > 1，属于超负荷运行，从图上看很容易 T1 任务首先发生了超期的情况，接下来 T2, T3, T4 依次连锁反应发生了超期。

除去优先级问题外，多核系统下还有分配问题。在多核系统中，调度器同样需要决定任务可以运行在哪个核上。通常情况下，调度器可以按如下归类：

• 全局性的(Global)：单个调度器管理所有系统中的 CPU。换句话说，任务可以迁移到所有 CPU；

• 集群性的(Clustered)：单个调度器管理 CPU 的一个不相交子集。换句话说，任务仅可迁移到可用 CPU 的一个子集上；

• 分区性地(Partitioned)：每个调度器管理单个 CPU，因此不允许迁移；

• 任意的(Arbitrary)：每个任务可运行在任意CPU集合上。

在多核系统中，全局性的、集群性的以及任意类型的 Deadline 调度器并不是最佳的。由于存在多种特殊情况，多核调度理论相比单核系统更加复杂。一个 M 核处理器系统可能调度 M 个运行时间等于周期的任务。例如，四核系统可以调度 4 个运行时间和周期都为 1000ms 的“大”任务。该情况下，系统将达到最大的利用率：4 * 1000/1000 = 4。

调度行为结果类似下图：

直觉上我们可能认为系统负载低时，总是可调度的。其实这仅针对单核系统成立。例如，四核系统中，一个由 4 个小任务和一个大任务组成的任务集，其中小任务的运行时间为 1ms，周期为 999ms；大任务的运行时间和周期都为1s。则系统的总负载为：

并不成立。这是因为如果所有任务在同一时间被释放，M个小任务将在 M 个可用处理器上同时被调度。而大任务仅可在小任务之后才能开始，很明显大任务运行完毕后就超期了。如下图所示，这被称为Dhall效应：

将任务合理分布到多个核上最终是一个 NP-hard 问题（其本质上是装箱问题，Bin-Packing Problem），并且还存在其他特殊情形，所以目前不存在一个最优调度算法。

带着这些背景知识，我们可以开始分析 Linux Deadline 调度器的细节，以及尝试寻求在利用其优势的同时又避免潜在问题的最佳实践。敬请期待即将发表的第二部分。