简介
作为整体调度器开发工作的一部分，Zircon 即将改用新的公平调度器作为系统的主要调度器。本文档介绍了调度器的属性以及如何启用调度器在发布之前进行测试。
启用公平调度程序
公平调度程序默认处于停用状态。通过将 GN build 参数 enable_fair_scheduler 设置为 true，可在编译时启用新的调度器。
您可以按如下方式在 GN 调用中设置此变量：
gn gen build-zircon --args='enable_fair_scheduler=true'
详细的调度程序跟踪
新的调度器包含详细的跟踪插桩，用于分析调度器的行为及其与系统中竞争工作负载的交互以及对系统内竞争工作负载的影响。通过将 GN build 参数 detailed_scheduler_tracing 设置为 true，可以在编译时启用详细跟踪。
您可以按如下方式在 GN 调用中设置此变量：
gn gen build-zircon --args='enable_fair_scheduler=true detailed_scheduler_tracing=true'
您可以使用 kernel:sched 跟踪类别在跟踪会话中添加详细的调度器信息。此外，最好也包含 kernel:irq 类别，因为中断可能会导致调度器 activity 看起来与其他事件未连接。
ffx trace start --categories kernel:sched,kernel:irq,<other categories> --duration 4 --buffer-size 64
调度器事件摘要
详细的调度器事件主要是时长事件和数据流事件。这些事件会显示在 Chromium Trace Viewer 的时间轴上，其标签为 cpu-0 到 cpu-N，其中 N 是系统中的 CPU 数量。这些时间轴表示内核中按 CPU 进行的活动，包括中断和线程调度。
公平调度程序发出持续时间事件，包括以下内容：
- sched_block：活动线程会在 Zircon 对象、futex、内核内部锁上阻塞。
- sched_unblock：活动线程因与 Zircon 对象、futex 或内核内部锁进行互动而取消屏蔽另一个线程。
- sched_unblock_list：当活跃线程的操作可以一次唤醒一个或多个线程时，sched_block 的一个变体（例如
wait_queue_wake_all）。 - sched_yield：名为
zx_thread_yield的活动线程。 - sched_preempt：中断请求重新评估运行队列。这可能是因为时间片计时器过期、另一个 CPU 在修改 CPU 的运行队列后请求重新调度，或者硬件中断处理程序唤醒了 CPU 上的线程。
- sched_reschedule：内核操作更改了当前 CPU 的运行队列，其他线程可能需要运行。
公平调度程序发出数据流事件，包括：
- sched_latency：将线程进入运行队列后的时间点连接到紧接在目标 CPU 上下文（可能不同的）切换到线程之前的时间点的流程。此数据流事件对于直观呈现跨 CPU 调度活动，以及观察线程在任何时间点可运行到正在运行的调度器的延迟时间非常有用。
关于流程事件的注意事项：有时，Chromium Trace Viewer 中会默认停用显示流程事件的功能。使用页面右上角的 View Options 菜单，并确保选中 Flow events 复选框。
如果流事件过多且渲染速度过慢，您也可以停用流事件的显示。在启用数据流事件显示功能之前，请尝试放大较小的区域，以便在超大轨迹中获得更好的性能。
公平调度概览
公平调度是在竞争线程之间分配 CPU 带宽，使每个线程在一段时间内都获得一定比例的 CPU 占用。在这个规则中，系统会为每个线程分配一个权重，这有点类似于其他调度规则中的优先级。线程接收 CPU 时间与其权重成比例（相对于其他竞争线程的权重）。这种比例的带宽分配具有一些有用的特性，使公平调度成为通用操作系统中的主要调度规则。
简而言之，这些属性包括：
- 直观的带宽分配机制：随着时间的推移，相对于另一个线程，权重是另一个线程的两倍的线程将获得大约两倍的 CPU 时间。然而，随着时间的推移，相对于另一个线程，与另一个线程具有相同权重的线程将获得大致相同的 CPU 时间。
- 所有线程无饥饿：比例带宽分配可确保所有参与竞争的线程都能及时收到 CPU 时间，无论线程权重相对于其他线程有多低。值得注意的是，此属性可以防止无界限的优先级倒置。
- 对系统过载的公平响应：当系统过载时，所有线程会在减速过程中按比例共享。解决过载条件通常比管理其他调度学科中所需的复杂优先级交互更简单。
- 在不断变化的需求下保持稳定性：与其他调度学科相比，以最少的干预措施可很好地适应各种各样的工作负载。
关于截止日期的说明：虽然公平调度适用于绝大多数工作负载，但也有一些任务需要非常具体的时间安排和/或不能很好地适应过载情况。例如，这些工作负载包括低延迟音频 / 图形、高频传感器和高速率/低延迟网络。最好使用截止时间调度程序（计划在 Zircon 调度器开发周期的后期推出）来处理这些特殊任务。
Zircon 的公平调度
Zircon 公平调度程序主要基于加权公平队列 (WFQ) 规则，并结合来自其他类似队列和调度规则的数据分析。我们计划采用最差情况公平加权公平队列 (WF2Q) 规则的各个方面（WFQ 的修改），以改善对延迟与吞吐量的调整。
以下小节概述了在 Zircon 中实现的算法。从现在开始，“Fair Scheduler”和“Zircon fair scheduler”可互换使用。
对线程执行进行排序
调度程序的一项主要作业是决定以何种顺序在 CPU 上执行竞争线程。公平调度程序会在每个 CPU 上单独做出这些决定。从本质上讲，每个 CPU 都运行一个单独的调度器实例，并管理自己的运行队列。
在此方法中，一个线程一次只能在一个 CPU 上竞争。线程可以处于以下三种状态之一：ready、running 或 blocked（其他状态与本文所述无关。）对于每个 CPU，无论何时，最多只有一个线程处于 running 状态：此线程在 CPU 上执行，所有其他竞争线程在 ready 状态下等待执行，而被屏蔽的线程不参与竞争。处于 ready 状态的线程会被列入 CPU 的运行队列；运行队列中的线程顺序决定了接下来要运行哪个线程。
公平调度程序与优先级轮循(RR) 等O (1) 调度规则不同，它使用排序标准来比较运行队列中的线程并对其进行排序。这是使用平衡二元树实现的，这意味着调度决策通常需要花费 O(log n) 才能执行。虽然这比 O(1) 调度器的开销更高，但结果是所有竞争线程都接近最优的最糟糕情况延迟边界（排队时间）。
排序标准
使用两个概念对运行队列中的线程进行排序：虚拟时间轴和每个线程的标准化速率。虚拟时间轴会跟踪运行队列中的每个线程在完成归一化时间片时何时完成。归一化时间片与线程的归一化率成正比，而归一化率与线程的权重成反比。运行队列中的线程会按照虚拟时间轴中的结束时间以升序进行排序。
与权重成反比关系会导致权重较高的线程插入更靠近运行队列前端的线程，而不是具有相似到达时间的低权重线程。不过，这个时间是有界限的：线程在运行队列中等待的时间越长，新到达的线程（无论其权重越高）被插入该线程的可能性就越小。此属性对于调度程序的公平性至关重要。
以下部分以更精确的术语定义调度器。
按线程的调度状态
对于每个线程 P[i]，我们定义了以下状态：
- 权重 w[i]：表示线程相对权重的实数。
- 开始时间 s[i]：CPU 的虚拟时间轴中线程的开始时间。
- 完成时间 f[i]：CPU 的虚拟时间轴中的线程结束时间。
- 时间片 t[i]：当前时间段的时间片大小。
按 CPU 的调度状态
对于每个 CPU C[j]，我们定义以下状态：
- 线程数 n[j]：在 CPU 上竞争的可运行线程数。
- 调度期 p[j]：CPU 上的所有竞争线程大约执行一次的时间段。
- 总权重 W[j]：在 CPU 上竞争的线程的权重总和。
当线程参与对 CPU 的竞争时，其权重就会添加到 CPU 的总权重中。同样，当一个线程阻塞或迁移到另一个 CPU 时，该线程的权重会从该 CPU 的总权重中减去。总计值包括就绪线程和当前正在运行的线程的权重。
可调状态
我们定义了以下可调状态，它可能是全局状态，也可能是基于 CPU 的状态：
- 最小粒度 M：分配给任何线程的最小时间片。
- 目标延迟时间 L：CPU 的目标调度时间段，除非线程过多，无法为每个线程提供至少一个最小粒度时间片。
定义
我们为关键调度程序变量定义了以下关系：
调度期
调度时段用于控制时间片的大小。当竞争的线程很少时，调度期默认为目标延迟。这会导致更长的时间片和更少的抢占，从而提高吞吐量并降低潜在的功耗。如果线程数量过大，则调度周期将会延长，以便每个任务至少接收最小粒度时间片。
将 N 设为经期拉伸之前的最大竞争线程数。
N = floor(L / M)
p[j] = n[j] > N --> M * n[j], L
虚拟时间轴
当线程进入运行队列（无论是通过新加入竞争 CPU 还是完成时间片）时，都会计算线程的虚拟开始和结束时间。由于当前的公平调度程序基于 WFQ，因此结束时间用于选择线程在运行队列中相对于其他线程的位置。之后，在实现 WF2Q 时，系统会同时考虑开始时间和结束时间。
某些 WFQ 实现会使用线程的实际时间片来计算时间轴的归一化时间片。但是，实际的时间片取决于 CPU 的总权重（见下文），该值会随着线程进入竞争而变化。而 Zircon fair 调度器会将调度周期用作虚拟时间轴的理想统一时间片，因为它的值的变化幅度较小。对所有线程使用统一值可避免不公平地使虚拟时间轴出现偏差，从而有利于提前联接的线程。
将 T 设为线程 P[i] 进入运行队列时 CPU C[j] 的系统时间。
s[i] = T
f[i] = s[i] + p[j] / w[i]
时间片段
选择某个线程运行时，系统会根据其相对速率和调度周期计算其时间片。
让 g 是 CPU C[j] 的当前调度期 p[j] 内最小粒度单位 M 的整数值。
将 R 设为线程 P[i] 的相对速率。
g = floor(p[j] / M)
R = w[i] / W[j]
t[i] = ceil(g * R) * M
此定义可确保 t[i] 是最小粒度 M 的整数倍，同时与线程的相对速率大致成比例。
产品
让出会立即使线程的时间片过期，并返回运行队列。此行为与 O(1) 调度中的退让类似：挂起的线程一定会排在具有相同或更高权重的线程后面。但是，产生线程的线程不一定会先跳到权重较低的线程，具体取决于其他线程等待运行的时长。