锆石公平调度器

简介

作为整体调度器开发工作的一部分，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 类别，因为中断可能会导致调度器活动 否则看起来与其他事件没有关联。

ffx trace start --categories kernel:sched,kernel:irq,<other categories> --duration 4 --buffer-size 64

调度器事件摘要

详细调度程序事件主要是持续时间和数据流事件。通过 事件会显示在 Chromium 跟踪查看器中标记为“cpu-0”的时间轴中 至 cpu-N，其中 N 是系统中的 CPU 数量。这些时间轴 表示内核中每个 CPU 的活动，其中包括中断和 线程调度。

公平调度程序发出持续时间事件，包括：

  • sched_block：活动线程会在 Zircon 对象、futex、 内核内部锁。
  • sched_unblock：活动线程因以下原因解除了对另一个线程的阻塞 与 Zircon 对象、futex 或内核内部锁交互。
  • sched_unblock_list：当 活动线程可以一次唤醒一个或多个线程（例如， 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 的加权比例。 在这个分类中，系统会为每个线程分配一个权重，这个权重有点相似， 其他调度学科的优先顺序。线程在 它们的权重相对于其他竞争线程的权重的比例。 这种比例的带宽分配具有实用的属性， 一般来说，将好的选择作为主要的时间安排管理方式 用途的操作系统。

简而言之，这些属性包括：

  • 直观的带宽分配机制：权重为两倍的线程 将获得大约 2 倍的 CPU 时间 其他线程。而权重与另一个线程相同的线程 将获得与其他线程大致相同的 CPU 时间 。
  • 所有线程均无可用资源：按比例分配带宽可确保 确保所有竞争线程都能及时获得 CPU 时间，而无论 线程相对于其他线程的低值得注意的是，这个属性 可防止无界限优先级倒置
  • 对系统过载的公平响应：当系统过载时， 线程在运行缓慢期间按比例共享。“解决过载条件”现为 通常比管理其他云平台中所需的复杂优先级交互 调度学科。
  • 在不断变化的需求下保持稳定性：很好地适应各种各样的工作负载 所需的干预最少。

关于截止日期的注意事项：虽然公平的时间安排适用于大量 但对于大部分工作负载，也有一些任务需要非常具体的时间安排 和/或不能很好地适应过载情况。例如，这些工作负载 包括低延迟音频 / 图形、高频传感器和高速率 / 低延迟网络这些专用任务更适合 截止时间调度程序，计划稍后在 Zircon 调度器中 开发周期。

Zircon 中的公平调度机制

Zircon 公平调度程序主要基于加权公平排队 (WFQ) 以及来自其他类似排队和调度学科的数据洞见。 采用了最坏案例的公平性加权公平队列 (WF2Q) 规则的各个方面， 对 WFQ 的修改，计划加强对延迟时间调整的控制 而不是吞吐量

以下小节概述了在 Zircon 中实现的算法。出发地： 继续，“公平调度程序”和“Zircon fair scheduler”可互换使用。

对线程执行进行排序

调度器的主要作业之一是确定要执行的顺序 竞争线程。公平调度程序做出这些决策 分别在各 CPU 上运行从本质上讲，每个 CPU 都运行 调度程序，并管理自己的运行队列。

在此方法中，一个线程一次只能争用一个 CPU。线程可以 处于以下三种状态之一：ready、running 或 blocked（其他状态 的内容。）对于每个 CPU 中最多只允许有一个线程 running 状态：此线程在 CPU 上执行，而所有其他 竞争线程在 ready 状态下等待执行，而阻塞的线程 未参与竞争。处于 ready 状态的线程在队列中加入 CPU 的运行队列；运行队列中的线程顺序决定了 接下来会运行。

公平调度器，与优先级等 O(1) 调度规则不同 轮循机制 (RR)，使用排序标准来比较 运行队列中。这是使用平衡二元树实现的，意味着 制定调度决策通常需要 O(log n)。虽然这更适合 开销比 O(1) 调度程序高，因此是接近最佳最坏情况下的结果 所有竞争线程都有延迟限制（排队时间）。

排序标准

两个概念用于对运行队列中的线程进行排序：虚拟时间轴和 每个线程的标准化率。虚拟时间轴会跟踪每个线程 如果运行队列完整运行，则该运行队列会在标准化时间片中结束运行。 标准化时间片与线程的标准化率成比例， 而后者与线程的重量成反比线程是 按虚拟时间轴中的结束时间升序排列。

与权重的反比例关系会导致线的权重较高 可以插入到比权重较低的线程更靠近运行队列前的位置 且到达时间相近。不过，这也存在一定限制：广告越长， 线程在运行队列中等待，不过新到达的线程可能性越小， 会插入在它前面。此属性对于 调度程序的公平性

以下部分更精确地定义了调度器。

每个线程的调度状态

对于每个线程 P[i]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 的总权重中减去线程的权重总计包括 ready 线程和当前 running 线程的权重。

可调状态

我们定义以下可调状态，可以是全局状态，也可以是每个 CPU 的状态：

  • 最小粒度 M：分配给任何线程的最小时间片。
  • 目标延迟时间 L：CPU 的目标调度周期，除非 线程过多，无法为每个线程提供至少一个最小粒度时间 。

定义

我们为关键调度器变量定义以下关系：

安排时间段

安排时间段控制时间片的大小。如果只有 线程参与竞争，则调度期默认为目标延迟时间。这个 可以扩大时间片并减少抢占，从而提高吞吐量和 潜在功耗如果线程数过多， 调度期延长，以确保每个任务至少获得 粒度时间片。

让 N 作为时间段拉伸之前的最大竞争线程数。

 N = floor(L / M)

p[j] = n[j] > N --> M * n[j], L

虚拟时间轴

当线程进入运行队列（可能因为新加入针对其他线程的竞争） CPU 或完成时间片时，线程的虚拟开始和结束时间 进行计算。由于当前的公平调度程序基于 WFQ，因此结束时间为 用于选择线程在运行队列中相对于其他线程的位置 线程。之后在实施 WF2Q 时，开始时间和结束时间均为 。

某些 WFQ 实现使用线程的实际时间片来计算 时间轴的标准化时间片。然而，实际的时间片 CPU 的总重量（见下文），该值会随着线程数进入 竞争。Zircon 公平调度程序则将调度期用作 用于虚拟时间轴的理想统一时间片，因为它的值 变化不那么明显。对所有线程使用统一的值可避免偏差 虚拟时间轴不公平，偏向于提前加入的线程。

让 T 作为线程 P[i] 进入运行时 CPU C[j] 的系统时间 队列。

s[i] = T

f[i] = s[i] + p[j] / w[i]

时间片

当某个线程被选定为运行时，其时间片将根据其 相对费率和投放时间

让 g 是最小粒度单位 M 的整数， CPU C[j] 的当前调度期 p[j]。

让 R 表示线程 P[i] 的相对速率。

 g = floor(p[j] / M)

 R = w[i] / W[j]

 t[i] = ceil(g * R) * M

此定义可确保 t[i] 是最小尺寸的整数倍 M 同时保持大致成比例 线程速率

收益率

让出会立即使线程的时间片过期，并将其返回到运行时 队列。此行为类似于 O(1) 调度中的让出： 线程必定会排在权重相同或更大的线程后面。 不过，让出的线程不一定会跳过权重较低的线程， 具体取决于其他线程等待运行的时间。