RSoC 2026：Redox OS 中的 EEVDF

# RSoC 2026：Redox 的 EEVDF 调度器 - Redox 来源：https://www.redox-os.org/news/rsoc-eevdf/ ##### 作者：Akshit Gaur，发布于 2026 年 8 月 22 日，星期六 首先，请阅读这篇文章（https://www.redox-os.org/news/rsoc-dwrr/）以了解背景（Redox OS、基础调度、轮询调度与亏损加权轮询调度器）。 ## 摘要 Redox OS 现在使用基于 EEVDF 的调度器。从 DWRR 的转变在几乎所有指标上都带来了显著提升：公平性提升了 782 倍，上下文切换时间减少了 82%，吞吐量增加了 2.6 倍，等等！ 特别感谢 Jacob Lorentzon（4lDO2）和 Wildan Mubarok 在整个过程中提供的帮助和指导，如果没有他们以及 Redox 社区中其他帮助过我的人，我认为这是不可能实现的！ ## 酒吧中的清醒思考 让我们看看上一篇文章中离开我们酒吧时的情景：贵宾们通过我们的交错式 DWRR 方法得到了充分款待（或者说是喝足了？），不幸的是，普通大众却在挨饿（在一个免费畅饮的酒吧里保持清醒可能比挨饿更糟）！尽管我们尚未实现像邻居酒吧“Linoox”多年前那样许多复杂的启发式算法，但如果我们继续使用 DWRR，我们就不得不这样做，因为我们的保安最终需要复杂的“启发式”（猜测游戏）来判断何时该阻止贵宾，以免普通顾客渴死。我们的调酒师需要重新思考了。 :::note 虽然这打断了文章的流畅性，但我想强调我并非在这里批评 Linux，以避免任何误解。Linux 多年来一直使用 CFS，这比简单的 DWRR 要复杂得多（也不同）。它使用复杂的启发式算法来猜测应用程序的性质，这些算法多年来变得臃肿不堪。Linux 用 EEVDF 替换了它，并且正是在他们证明其有效性之后，我们才开始实施它！ ::: 经过多次讨论，调酒师们基于一种新的标签系统提出了一个新系统。在这个系统中，调酒师们会跟踪客户的重要性，以及他们此刻是否真的配得上一杯啤酒。 他们的判断方式是使用“延迟（lag）”：他们精确追踪为你倒了多少酒，以及你实际应得多少！如果你被欠了啤酒，你就有正的延迟；如果你喝得太快，你就有负的延迟！他们将其记录为你的“资格时间（eligible time）”，即你的延迟不再为负的时刻！ 尽管一个穷人会容忍一段时间没有啤酒在手，即使他被欠了一些酒（毕竟他喝的是免费酒！），但客户越重要，他们就越不耐烦。因此，调酒师们会计算你下一杯酒的“截止时间（deadline）”！截止时间等于你的资格时间加上一个基础等待时间除以你的重要性权重（等待时间 / w）。你越重要，截止时间就越紧！ 这样产生的结果是，贵宾们不仅被欠了更多的酒，而且由于他们更紧的截止时间，酒会尽快送到他们手中；而不太重要的客户也不会挨饿，因为截止时间系统的引入确保了他们在清醒之前杯子里就能有酒！ ## 正式介绍 最早资格虚拟截止时间优先（Earliest Eligible Virtual Deadline First）调度器，正如其拗口的名字所示，无疑是“最好”的调度器之一，由 Ion Stoica 和 Hussein Abdel-Wahab 在他们 1995 年的论文《Earliest Eligible Virtual Deadline First : A Flexible and Accurate Mechanism for Proportional Share Resource Allocation》（https://people.eecs.berkeley.edu/~istoica/papers/eevdf-tr-95.pdf）中提出。 我将尝试解释它！ ### 假设 a. 我们只能在一个时间量子 `q` 内将 CPU 分配给一个进程。 b. 一个进程如果在竞争资源则称为活动状态，否则为被动状态。在时间 `t` 处于活动状态的进程属于活动集 `A(t)`。 c. 每个进程都有一个关联的权重 `w`，决定了它的资源份额 `f`。 $$ f_i(t) = \frac{w_i}{\sum_{j \in A(t)} w_j} $$ d. 由于各种原因，客户不可能总是恰好收到其应得的服务时间。因此，我们为这个应得时间与实际接收时间的差值分配一个值，称为 `lag`。 $$ lag_i(t) = \underbrace{S_i(t_0^i, t)}_{\text{理论值}} - \underbrace{s_i(t_0^i, t)}_{\text{实际值}} $$ 其中， $$ \tag{1} S_i(t_1, t_2) = w_i \int_{t_1}^{t_2} \frac{1}{\sum_{j \in A(t)} w_j} d\tau $$ ### 前奏 一个客户/进程发出一个请求，指定了它需要的服务持续时间 `r`。因此，在一个理想的系统中，给定 `r`（服务持续时间）和 `t`（请求发出的时间），我们可以通过解方程来求出请求必须被服务的截止时间 `d`： $$ r = S(t, d) $$ 假设我们的进程份额 `f` 在该时间段内不变， $$ S(t, d) = f \times (d - t) $$ $$ r = f \times (d - t) $$ $$ d = t + \frac{r}{f} $$ EEVDF 不使用时钟时间，而是使用“虚拟时间（Virtual Time）”，定义如下： $$ \tag{2} V(t) = \int_0^t \frac{1}{\sum_{j \in A(t)} w_j} d\tau $$ 这里一个很好的性质是，这个虚拟时间的流逝与当前资源竞争的程度成反比。当竞争激烈时，虚拟时间流速变慢；当竞争较低时，流速变快！ 由公式 1 和 2 可得， $$ S(t_1, t_2) = w_i (V(t_2) - V(t_1)) $$ ### 算法 EEVDF 背后的基本思想非常简单，你为每个请求（或客户）关联两个（或更多）数字： 1. **资格时间（eligible time）`e`**：请求变得有资格被服务的确切时间。 $$ S_i(t_0^i, e) = s_i(t_0^i, t) $$ 2. **截止时间（deadline）`d`**：选择 `d`，使得客户在 `e` 和 `d` 之间获得的服务等于其请求的服务时间 `r`，即： $$ S_i(e, d) = r $$ 换句话说，如果客户恰好从 `e` 开始获得其公平份额，`d` 就是其请求被完全服务的时间点。不过需要记住的是，这是一个调度截止时间，而不是硬实时保证；它决定了合格请求之间的顺序。 在我们使用它们之前，需要将它们转换到虚拟时钟。 $$ V(e) = V(t_0^i) + \frac{s_i(t_0^i, t)}{w_i} $$ $$ V(d) = V(e) + \frac{r}{w_i} $$ 现在我们有了所有值，终于可以定义策略了！引用原始论文： > **EEVDF 算法**：*一个新的时间量子被分配给具有最早虚拟截止时间的合格请求的客户。* 现在让我们定义在第 `k` 个请求时的虚拟资格时间（Virtual Eligible Time）和虚拟截止时间（Virtual Deadline），分别记为 $ve^{(k)}$ 和 $vd^{(k)}$： $$ ve^{(1)} = V(t_0^i), $$ $$ vd^{(k)} = ve^{(k)} + \frac{r^{(k)}}{w_i} $$ $$ ve^{(k + 1)} = vd^{(k)} $$ 如果因为某种原因（例如，提前让出或阻塞），它在第 `k` 个请求期间实际获得的服务时间（$u^{(k)}$）不等于 $r^{(k)}$，我们只需要修改最后一个方程： $$ ve^{(k + 1)} = ve^{(k)} + \frac{u^{(k)}}{w_i} $$ 如果一个客户没有消耗完它的时间片，它的下一个 `ve` 和 `vd` 会被提前，这使得它在与一个完全消耗了时间片的相同进程竞争时具有优先权。 因此，重申我们选择下一个服务客户的策略：我们选择具有正（或零）延迟（即 `Si >= si`）且截止时间最早的客户！ ## 在 Redox 中的实现 我将带您浏览 `select_next_context` 函数，它包含了实际的调度逻辑。需要记住的一点是，我们没有显式计算延迟（有符号变量），而是存储上下文的局部 `V(t)`，它与 $s_i$ 成正比，因此 $$ lag = V_{global} - V_{local} $$ 请记住，这是虚拟/标准化延迟。如果您想要绝对延迟， $$ lag_i = w_i \times (V_{global} - V_{local}) $$ ### 我们还能运行前一个客户吗？ 我们做的第一件事是检查是否可以继续运行前一个上下文/客户。如果没有其他合格的上下文可以运行，这对我们很有帮助。我们也在这里更新它的 `ve`（代码中为 `vtime`）和 `vd`。 如果它提前让出了 CPU，我们会应用一个惩罚（与其权重/优先级成反比），以防止进程反复提前让出来操纵其延迟并垄断 CPU 时间。 我们还判断 `prev_context` 是否仍有资格运行（`vtime` < `V`）。 ### 遍历树 所有可运行/活动的上下文都存储在一个按核（per-core）分布的 BTreeMap 中。BTreeMap 的键是（`vd`，`rem_slice`（剩余服务时间片），`ctxt_id`），这确保了映射首先按 `vd` 排序，并使用剩余时间片（基于 `BASE_SLICE`，即一个客户被分配的 CPU 时间量，以时间片切换为单位）作为平局决胜标准，最后使用它们的 ID 作为最终决胜标准。这确保了在两个具有相同虚拟截止时间的上下文之间，已经开始运行但尚未完成其时间片的那个会被优先考虑！ BTreeMap 的值是（`vtime`，`context_weight` 和 `context_ref`）。虽然锁定 `context_ref` 后可以访问 `vtime` 和 `context_weight`，但显式存储它们可以让我们无需锁定就能快速查看上下文是否有资格运行，这以少量存储开销为代价提高了性能。 我们遍历这个 BTreeMap，一旦找到一个合格的上下文（`vtime` <= `V`），我们就中断遍历并切换到它！ :::note 原始论文为此描述了一棵增强树，我们目前没有使用，因为它增加了实现复杂性。我选择使用标准的 BTreeMap，因为它经过了很好的优化并且是标准组件。如果我选择自己创建一棵增强树，那么在**我**睡觉的时候，bug 偷溜进来的机会就会更多。尽管如此，在大多数情况下，一个简单的 BTreeMap 应该能提供与增强树相似的性能。只有在最坏的情况下（没有/最少合格的上下文），增强树在时间复杂度上（O(logN) vs O(N)）才会获得优势，但考虑到实际使用中树的长度及其缓存友好性，我决定 BTreeMap **目前**足够好了。 ::: 如果树中没有合格的上下文，我们找到具有最小 `vtime` 的上下文，并将其作为目标，快速推进我们按核分布的 `V` 到它的值，从而使其有资格运行，这确保了我们不会闲置地浪费 CPU 周期。 ### 工作窃取（Work Stealing） 随着我们的数据结构转向按核驻留，现在可能出现一个核心的 BTreeMap 中没有上下文，而另一个核心完全满载的情况！为了防止这种情况，我们实现了工作窃取！ 工作窃取在以下情况下触发： 1. 我们当前核心的 BTreeMap 为空。 2. 每隔 `STEAL_INTERVAL` 时间一次，附加条件是我们树中的上下文数量与任何其他核心的数量之差 > `STEAL_THRESHOLD`。 如果触发，我们计算从核心 X 窃取的上下文数量为： `窃取的上下文数量 (N) = min((X.queue.len() - local.queue.len()) / 2, MAX_STEAL)` 然后我们从核心 X 的树中窃取前 `N` 个（间隔窃取，即第 1、3、5... 个）上下文到我们自己的树中，并使用以下公式调整它们的 `vtimes`： $$ offset = context.vtime - X.V $$ $$ context.vtime = max(0, local.V + offset) $$ ### 推进虚拟时钟 当所有这些都尘埃落定后，我们最终推进虚拟时钟！ $$ V_{\text{local}} \mathrel{+}= \frac{\text{elapsed\_ticks}}{\text{total\_weight}} $$ ## 其他优化 除了将调度器从 DWRR 更改为 EEVDF 之外，我还进行了以下重要的优化。 ### 将 `RUN_CONTEXTS` 从全局（GLOBAL）移至按核（PerCPU） 全局运行队列意味着两个核心无法同时进行上下文切换，必须等待先前的核心释放锁。这意味着随着核心数量的增加，锁竞争也随之增加，从而导致上下文切换所需时间增加。这个合并请求（https://gitlab.redox-os.org/redox-os/kernel/-/merge_requests/660）为每个核心提供了自己独立的运行队列。它还实现了这一变更所必需的工作窃取！ ### 将 `RUN_CONTEXTS` 从 VecDeque 移至 BTreeMap EEVDF 的初始实现使用简单的 VecDeque 来存储活动上下文。这个合并请求（https://gitlab.redox-os.org/redox-os/kernel/-/merge_requests/618）将其改为 BTreeMap，将扫描的时间复杂度从 O(N) 降低到 O(logN)。 ### 移除线性扫描 这是我们之前处理阻塞任务的方式： 1. 当一个上下文被阻塞时，它会从 `RUN_CONTEXTS` 中移除，并移动到另一个全局列表 `IDLE_CONTEXTS`。 2. 在每次上下文切换时，我们会扫描 `IDLE_CONTEXTS`，检查是否有上下文变得可运行，然后将它们从 `IDLE_CONTEXTS` 移动到全局 `RUN_CONTEXTS`。 这些阻塞任务分为两种类型：定时器和非定时器，因此分两轮处理。 **定时器**： 我们分离了定时器，现在将它们存储在 BTreeSet 中，这允许我们提取所有将在当前时刻触发的定时器。（相关合并请求：https://gitlab.redox-os.org/redox-os/kernel/-/merge_requests/649）。因此时间复杂度从 O(N) 降低到 O(logN)。 **非定时器**： 以前，解除阻塞的代码只将标志切换为标记上下文为可运行状态（Runnable），现在该代码也负责将上下文实际放入运行队列，将时间复杂度从 O(N) 降低到 O(1)！（相关合并请求：https://gitlab.redox-os.org/redox-os/kernel/-/merge_requests/656）。 ## 有带来改变吗？ 现在，让我们看看数据，以量化这次调度器变更的结果！ ### 公平性 公平性（以及下一节）是我们迁移最明显的胜利。我启动了 16 个相同的、仅增加计数器的 CPU 密集型进程，最后比较这些计数器以估算它们的 CPU 时间。这里的方差是最小/最大偏差—— | 设置 | DWRR 方差 | EEVDF 方差 | | :--- | :--- | :--- | | 16 进程 / 4 核心 | 389 - 617% | 1.09 - 1.37% | | 16 进程 / 1 核心 | 1940.52% | 2.48% | 公平性提升了 782 倍！ ### 上下文切换时间 这并非直接源于转向 EEVDF，而是与运行队列从全局状态移至按核状态相关的变更，使得自愿（`yield_now`）上下文切换所需时间从 2μs 降至 350ns（请注意，这些值也包含一些测试框架的开销，因此实际数字可能小于报告值）！ 对于阻塞上下文切换，请参见下表： | 平均延迟 | Linux，固定在核心 0，原生主机 | 0.552μs | | :--- | :--- | :--- | | Redox EEVDF，单核心，QEMU | 0.923μs | | Redox EEVDF，4 核心，QEMU | 0.931μs | | Linux，未固定，原生主机 | 1.230μs | | Redox DWRR，单核心，QEMU | 1.367μs | | Redox DWRR，4 核心，QEMU | 4.253μs | 与 Linux 的比较并非完全同类，因为 Linux 在原生主机上运行，而 Redox 在 QEMU 下运行。 ### 饥饿现象 如果你还记得 EEVDF 合并时的这个简短公告（https://www.redox-os.org/news/eevdf/），低优先级进程的饥饿现象使得测量优先级是否得到正确遵循变得非常困难，测得的比率仅为 1.4 倍，而理论值是 86.8 倍。使用 EEVDF 后，我们这个比率达到了 76.87 倍，约为理论值的 89%。剩余的差异很小，可能是由于调度噪声和不完美的起始点造成的。 ### 唤醒密集型工作负载 对于有许多休眠线程的工作负载，新调度器表现出显著优势，这更多归功于各种优化而非数学算法本身，但仍然... 我启动了 10,000 个休眠的...