Linux DEADLINE调度算法详解

介绍

在实时系统中，调度算法的选择对于任务的及时执行至关重要。为了满足实时性需求，Linux内核引入了不同的调度算法，其中 DEADLINE 调度算法是为硬实时任务而设计的。DEADLINE 调度算法的目标是在多任务的情况下确保任务在其指定的最后期限（deadline）之前被执行，从而最大限度地减少错过最后期限的情况。本文将详细介绍Linux的DEADLINE调度算法的原理、工作机制、优缺点以及其适用场景。

Linux调度算法

Linux系统在调度时，会按照下图的顺序依次从调度策略子模块选取进程，作为下一个在处理器运行的候选者。如果优先级高的调度策略子模块没有候选进程，则从后继的子模块选取进程。从下图可见，Linux DEADLINE子模块的优先级是要高于RT调度子模块，以及CFS子模块的。

图1、Linux的调度顺序

为了处理那些对时间非常敏感的任务，Linux 引入了 DEADLINE 调度类，它基于 Earliest Deadline First (EDF) 和 Constant Bandwidth Server (CBS) 算法。这种调度策略能够确保在一个处理上运行了多个硬实时任务的情况下，只要满足一定条件，每个任务在其规定的时间内得到处理。

DEADLINE调度算法的参数

DEADLINE 调度算法依赖于三个重要的参数，它们被用于定义任务的时间约束：

运行时（Runtime，runtime）: 指每个调度周期内任务需要运行的时间量。
周期（Period，period）: 指任务可以再次运行的时间间隔，即调度任务的频率。

3)最后期限（Deadline，deadline）: 指任务的最后执行时间点，任务必须在这个时间点之前完成。

每个任务在创建时都会被分配这些参数。调度器会根据每个任务的最后期限来决定优先级：最后期限越早，优先级越高。这与传统的优先级调度不同，它完全基于任务的时间要求来进行调度。

DEADLINE调度算法的工作机制

Linux 中的 DEADLINE 调度算法是通过两个主要子算法实现的：

最早截止时间优先（Earliest Deadline First, EDF）：这是 DEADLINE 调度的核心部分。调度器根据任务的截止时间对其进行排序，并优先调度最早到期的任务。每次有新任务需要调度时，调度器都会重新检查所有任务的最后期限，并选择那个最先到期的任务。

恒定带宽服务器（Constant Bandwidth Server, CBS）：DEADLINE 调度器还需要确保每个任务不会超出其分配的 CPU 时间，这就是 CBS 的作用。它通过管理任务的运行时间来控制任务的CPU占用，使得即使在过载的情况下，也能够限制任务的 CPU 使用量，避免系统资源被某些任务过度占用。

DEADLINE 调度器中的每个任务会分配一个虚拟的截止时间（virtual deadline），这个时间用于决定其调度顺序。每次任务被调度时，其截止时间会被更新，从而确保系统中不同任务的公平性。

理论证明[1]，在满足下面公式的前提下，调度算法能保证在同一处理器上运行的周期性任务都不超时:

以上公式的符号说明：Ci表示任务i的运算时间，Ti表示任务i的运行周期。

[1]给出了例子，说明，面对同样的任务，RM算法（先到达优先）不能保证所有任务都能满足运行期限需求。而EDF算法可以满足这些需求。

图2、RM调度算法和DEADLINE调度算法的比较

为了比较Linux RT调度策略和DEADLINE算法，国科环宇用相同的一组任务分别针对Linux RT下的RR算法、FIFO算法，以及DEADLINE算法做了比较实验，RR算法和FIFO算法都出现了超时的情况，而DEADLINE调度算法没有超时。实验数据如下：

在同一个CPU核心上运行三个实时进程，周期分别为4ms、4ms、2ms，实际占用CPU时间为1ms、2ms、0.4ms，是否能在周期内完成运行：

FIFO调度超时概率：95%，94%，95%

RR调度超时概率：92%，96%，92%

Deadline调度：0%，0%，0%

DEADLINE调度算法的应用

DEADLINE算法目前在媒体播放器，以及工业控制上进行了实验和测试。同时RT-TESTS测试套件[2]中的deadline_test测试程序给出了对Linux DEADLINE算法的使用样例。

deadline_test[2]的工作原理是，根据输入的总的运行时间/运行周期比例，给多个进程分配相应的运行时间/运行周期（并按照此运行时间/运行周期设置DEADLINE调度参数），使这些进程的运行时间/运行周期的和等于总的运行时间/运行周期。针对每个进程，按照其运行时间进行整数计算。所有进程运行10秒后，统计其运行时间错过率，以及运行周期错过率。

对周期性实时任务有需求的开发者可以参照deadline_test的样例设计和实施DEADLINE调度，也可以与国科环宇合作，打造Linux下的多任务强实时应用案例。