概览
Zircon 调度器是一种混合调度器，同时支持公平 和 Deadline 调度规范。它在每个逻辑 CPU 上独立运行，管理自己的运行队列集，并通过处理器间中断 (IPI) 与其他 CPU 协调。
调度器的主要目标是在竞争线程之间共享 CPU 带宽，同时保证关键工作负载（例如音频、图形和高频传感器）的时序要求。
调度规范
公平调度
公平调度是系统中通用工作负载的主要调度规范。它在竞争线程之间分配 CPU 带宽，使每个线程在一段时间内获得加权比例的 CPU。
- 基于权重的分配：每个线程都被分配一个权重。一个线程的权重是另一个线程的两倍，则前者获得的 CPU 时间大约是后者的两倍。
- 虚拟时间轴：就绪线程根据 虚拟完成时间在平衡二叉树 （WAVL 树）中排序。权重较高的线程排序靠前，但权重较低的线程保证及时执行，以防止饥饿和无界优先级反转。
- 调度周期：调度周期会适应 竞争线程的数量。如果竞争的线程过多，则周期会延长，以确保每个线程至少获得一个最小粒度 片段，从而提高吞吐量。
如需详细了解公平调度算法的数学原理和排序 条件，请参阅公平调度器机制。
Deadline 调度
Deadline 调度支持对延迟时间要求严格的任务，这些任务需要严格的时序保证，并且在过载情况下不得参与比例减速。
- 保证：Deadline 任务指定容量 （CPU 时间）和 Deadline （周期）。如果总体 Deadline 需求可行，调度器会保证任务在其 Deadline 周期内获得其容量。
- 优先级：Deadline 任务始终优先于符合条件的公平 任务。
- 过载响应：为确保所有 Deadline 任务都能在预期周期内调度 ，Deadline 需求的总和不得 超过处理器的容量。如果处理器的总 Deadline 需求超过 100%，则预计会出现随机 Deadline 遗漏，并且系统将表现为某些或所有任务的周期乘以过载系数。
- 关键优先级：Deadline 配置文件可以选择标记为 关键。在 CPU 超额订阅期间，关键 Deadline 任务的优先级绝对高于普通 Deadline 任务，确保基本工作负载不会因失控的标准 Deadline 线程而降级。在正常运行的系统中，关键利用率总和绝不应超过处理器的限制，否则会发出内核 oops。
运行队列和选择
每个 CPU 维护三个主要运行队列，这些队列以增强型 WAVL 树的形式实现，以满足高效的 O(log n) 操作：
- 关键 Deadline 运行队列：包含可运行的关键 Deadline 任务。
- Deadline 运行队列：包含可运行的非关键 Deadline 任务。
- 公平运行队列：包含可运行的公平任务。
线程选择
在选择要运行的下一个线程时，调度器会按以下顺序评估队列：
- 关键 Deadline 任务：选择完成时间最早的符合条件的的关键 Deadline 任务。
- Deadline 任务：选择完成时间最早的符合条件的 Deadline 任务 。
- 公平任务：选择虚拟完成时间最早的符合条件的公平任务。
- 空闲/电源线程：在没有其他符合条件的线程时运行。
抢占和时间片
调度器根据所选线程的时间片或 Deadline 任务的到达时间设置 CPU 本地抢占计时器。当计时器触发时，当前线程的执行会停止，并且调度器会重新评估哪个线程最适合接下来运行。
CPU 放置和迁移
调度器根据多个因素执行负载均衡和任务放置，以优化性能和热效率。
放置条件
当线程唤醒或解除阻塞时，调度器会根据以下条件选择目标 CPU：
- 亲和性：优先考虑线程的用户定义的 CPU 亲和性掩码。
- 上次 CPU：在上次 CPU 上运行有助于保持缓存热度 （集群内亲和性）。
- 空闲状态：如果核心避免了繁忙 CPU 的上下文切换 开销，则优先级很高。
工作窃取
为保持负载均衡，没有符合条件工作的 CPU 会尝试从其他繁忙的 CPU 窃取 工作。
- 集群感知：调度器会感知 CPU 拓扑。CPU 窃取优先考虑本地集群而不是远程集群，以利用更好的共享缓存性能水平并减少迁移惩罚。
电源和能耗感知
调度器使用本地能耗模型和功率级别控制来优化能耗和热性能。
- 性能规模：在预算计算中考虑各个 CPU 性能乘数 。
- 动态电压和频率缩放 (DVFS)：调整处理器工作负载 ，支持用户定义的限制，同时努力满足 Deadline 调度。