# 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任务进行调度。首先来看最简单的情况：系统只有一个任务，那么调度器在每次任务激活的时候直接调用即可，如下图所示：

![](https://640510796-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Me-3_JXLYv-4hrEXyDb%2Fuploads%2F6fHwPRTSTtFTCdGhDUqN%2Flinux_sched_dl_single.png?alt=media\&token=32da681c-e6e0-494f-94f6-310a1de3f0ee)

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

![](https://640510796-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Me-3_JXLYv-4hrEXyDb%2Fuploads%2F41xpCJhSfqx131mYYskj%2Flinux_sched_dl_three.png?alt=media\&token=76e4c4a8-9544-4334-9da0-3bee577f544e)

图中三个任务的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时间，而如果有任务“不老实”，那么它也只会影响它自己。这样就完成了对任务的隔离，保证了系统的稳定性。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://s3.shizhz.me/linux-sched/dl-sched/algorithm.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.