> For the complete documentation index, see [llms.txt](https://s3.shizhz.me/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://s3.shizhz.me/linux-sched/dl-sched/algorithm.md).

# 2.4.1 DL调度器 - 调度算法

Deadline调度器的核心思想是EDF(Earliest Deadline First)与CBS(Constant Bandwidth Server), 我们将在本节详细讨论。

Deadline任务有三个重要的属性：runtime, period, deadline, 调度器需要确保任务在每个period时间窗口内得到runtime这么多的CPU时间，并且必须在deadline这个时间点之前得到。我们可以将一个Deadline任务看着是一个连续的子任务流，而period实质上代表着子任务的激活模式。例如一个视频处理引擎每秒需要处理60帧数据，每个数据帧的处理时间最长为10ms，并且新的数据帧每16ms就会到达，因此该进程的period是16ms, runtime是10ms, 由于这里没有显示的指定每帧数据处理的deadline, 因此默认与period相同。

这三个属性在用户启动Deadline任务时就需要指定，例如：

```
chrt -d --sched-runtime 5000000 --sched-deadline 10000000 \
    --sched-period 16666666 0 video_processing_tool
```

在该命令中，三个参数的单位都是纳秒，其中参数 `0` 用来表示进程优先级，由于Deadline 任务的优先级是固定的-1, 所以该值在这里没有实际意义，仅用来充当占位符的作用。

接下来我们讨论一下系统如何对Deadline任务进行调度。首先来看最简单的情况：系统只有一个任务，那么调度器在每次任务激活的时候直接调用即可，如下图所示：

![](/files/6GQH1NLxdkOvP2ZrsJIe)

但如果有多个任务的话，调度器就需要合理地安排每个任务的执行时间，确保每个任务在每个period内都按时完成。Linux采用的调度算法叫EDF(Earliest Deadline First), 即在任意时刻，调度器都挑选Deadline最近的任务执行。下图展现了三个任务的调度示例：

![](/files/uVncdrpzPam9AQ8tSeNr)

图中三个任务的runtime与period都不一样，此时将产生一个问题：当有多个任务同时存在时，如何确保所有任务在理论上确实是能够按时完成的呢？系统通过CPU带宽（Bandwidth）来进行判断，一个任务需要的CPU带宽的计算方式如下：B = runtime/period, 如果系统中所有Deadline任务的带宽之和不超过1, 那么理论上调度器就可以按时完成所有的任务。直白一点说，就是如果在时间窗口T内，所有任务对时间的需求总量小于T, 那么这些任务就可以按时完成，这是很自然的逻辑。例如上图中，各个任务的参数为：

| Task | Runtime | Period |
| ---- | ------- | ------ |
| T1   | 1       | 4      |
| T2   | 2       | 6      |
| T3   | 3       | 8      |

三个任务消耗的CPU带宽为：U = 1/4 + 2/6 + 3/8 = 23/24, 因此系统在理论上可以完成调度。

为了保证所有的Deadline任务能够按时完成，系统有一个准入机制，前面提到系统在启动Deadline任务时必须指定runtime, deadline与period, 系统会根据这些参数对任务的带宽需求进行校验，如果已经没有足够的剩余带宽来负担新任务，那么该任务就会被拒绝。

到此为止，调度器能够正确地工作还基于一个隐式的假设：即在每个period内，每个任务的运行时间都不会超过自己的runtime时长。如果某个任务的执行时间超出了自己的runtime的话，就可能会对其他任务造成影响，甚至造成雪崩效应，导致所有任务的执行时间都超过deadline, 无法按时完成。 这是调度器必须解决的问题，runtime的设置取决于用户对每个子任务耗时的预估，最大值可以设置为子任务的WCET(Worst-case Execution Time)，但这样仍然存在两个问题：

1. 造成带宽浪费，降低调度器的吞吐量 \
   因为只有在少数情况下，子任务的处理时间才会达到WCET, 其他绝大多数情况下都不需要这么多时间，所以如果所有任务都按照WCET设置runtime的话，事实上是给每个任务预留了过多的CPU带宽，这会导致系统的准入机制拒绝更多的任务进入系统。
2. WCET也不可靠 \
   即使将每个任务的runtime都设置为WCET, 系统也有可能在某些极端情况下导致某个任务在某次处理中超出了runtime. runtime不够实际上并不是这个问题的核心，问题的核心是我们需要某种机制来对任务的行为进行隔离：如果一个任务的runtime设置过小，那么它应该只影响自己，其它“守信”的任务不应该受到影响。

Linux采用CBS来解决这个问题，CBS 实际上是一种带宽预留机制，其原理如下：

1. 每个任务通过 `scheduling deadline` 与 `remaining runtime` 来描述当前状态，前者表示当前子任务的deadline, 后者表示任务在 `scheduling deadline` 之前还剩多少runtime可以用
2. 当任务被唤醒时，系统会对该任务做如下两方面的校验：

   1. `scheduling deadline < now`, 即查看该任务是否已经错过了当前deadline
   2. `remaining runtime / (scheduling deadline - now) > runtime / period`, 校验带宽是否溢出，即在当前period中，CPU是否已经无法满足该任务的带宽要求

   如果二者都不成立，则说明该任务状态良好，否则则说明该任务已经无法在当前period内按时完成了，需要将其往后顺移，调度器会对其状态做如下修改： `scheduling deadline = now + deadline` `remaining runtime = runtime`
3. 任务的运行时间会从 `remaining runtime` 中及时减去
4. 当 `remaining runtime <= 0` 时，说明该任务已经没法在deadline前交差了，此时该任务的状态会被设置为throttled, 调度器将暂停对其进行调度。调度器会在任务的 `scheduling deadline` 这个时间点重新为其设置状态，这个动作叫着replenishment, 该时间点被称为 replenishment time
5. 当时间运行到throttled任务的replenishment time时，调度器会通过如下方式更新任务的状态： `scheduling deadline = scheduling deadline + period` `remaining runtime = remaining runtime + runtime`

上述的规则细看起来比较绕，其实核心思想就是为给每个任务预留固定的runtime，如果有任务在自己的runtime内无法交差，那么就在下一个period中再为其分配时间。这样只要任务“老老实实”地遵守自己的参数设定去运行，调度器就能够确保为其分配足够的CPU时间，而如果有任务“不老实”，那么它也只会影响它自己。这样就完成了对任务的隔离，保证了系统的稳定性。