苹果 XNU：Clutch 调度器
Hacker News 摘要原标题：Apple XNU: Clutch Scheduler
苹果的 XNU 内核在设计上需要兼顾多种动态且高效的运行需求。从对延迟极度敏感的用户界面交互、多媒体录制与回放，到对饥饿规避有要求的低优先级后台批处理任务，如照片同步或源码编译，内核必须做出最优的资源分配。传统的 Mach 调度器依靠线程的优先级数字进行管理，将高优先级视为交互式，低优先级视为批处理。这种方式使用基于优先级衰减的时间分片模型来确保公平和防止饥饿。
然而，传统方法存在缺陷。它丢失了线程与更高级别用户工作负载之间的联系，导致调度器无法从全局视角看待用户关心的完整任务。这往往会导致不相关的线程在同一优先级上竞争，甚至引发各子系统为了避免饥饿而盲目提高优先级的现象。此外，传统的线程级调度存在核算不准确和隔离性差的问题。
Clutch 调度器设计
为了解决上述问题，Clutch 调度器不再调度单个线程，而是调度线程组。它实现了一个三层的层级调度模型：
1. 调度桶层：这是最高级别，决定执行哪一类线程。内核根据线程的基础优先级定义调度桶，这些桶大致对应操作系统的服务质量（QoS）等级。这一层使用 最早截止时间优先 (EDF) 算法。每个桶都有一个预定义的 最坏情况执行延迟 (WCEL) 值。当一个桶变为可运行状态时，会根据当前时间加上 WCEL 计算截止时间。为了防止高优先级任务在重负载下被低优先级任务阻塞，该层引入了 Warp (跳跃) 机制，允许高优先级桶在特定窗口内获得执行优势。同时，它还具备 饥饿规避窗口，确保低优先级任务在极端竞争下也能获得执行机会。
2. 线程组层：这一层决定在同一个 QoS 调度桶中，哪一个线程组应该优先执行。线程组代表了为特定工作负载服务的一组线程。该层借鉴了 FreeBSD ULE 调度器 的变体。它会计算一个 交互性评分，该评分基于线程组的自愿阻塞时间与 CPU 使用时间的比例。这种机制使调度器能够偏好交互式应用，而非计算密集型的批处理任务。
3. 线程层：在最低层级，调度器在具体的线程组内选择具体的线程。这一层沿用了传统的 Mach 调度算法，利用负载和 CPU 使用率来使线程优先级衰减。由于负载计算仅限于同一线程组内，因此它能为组内的延迟敏感线程提供快速的 CPU 访问，而不影响系统中的其他无关线程。
优先级计算逻辑
• 根优先级：基于当前层级中最高优先级的线程计算，用于抢占决策。对于 AboveUI 等极高优先级任务，会有特殊的处理逻辑以确保极低延迟。
• 根桶优先级：即截止时间，计算方式为 当前时间 + 桶的 WCEL。
• Clutch 桶优先级：由该桶内最高优先级的线程值加上交互性评分组成。
• 线程优先级：基于 Mach 时间分片算法，每隔一个调度滴答根据负载更新，计算公式为 基础优先级 - (线程 CPU 使用量 >> 优先级偏移)。
Edge 调度器设计
Edge 调度器是针对多集群非对称平台（如大核加小核架构）设计的扩展。它将机器表示为一个图，其中节点是计算集群，有向边表示线程迁移的可能性。其核心目标包括：
• 紧凑性：尽量将小规模工作负载限制在单个集群内，以提高缓存利用率并允许关闭闲置核心以省电。
• 快速开启集群：当工作负载需要并行处理时，迅速启用更多集群。
• 低延迟访问：确保高 QoS 任务在重负载下仍能快速获得响应。
• 单向迁移：线程通常只向执行效率不会显著降低的集群迁移。
• 管理乘客效应：当不同性能需求的任务共享集群导致性能受损时，主动拆分负载。
线程放置与迁移策略
Edge 调度器结合了性能控制器的建议和每集群运行队列。
• 集群建议：性能控制器可以为每个线程组的每个 QoS 级别指定首选集群。当线程变为可运行时，调度器会首先评估首选集群。如果首选集群空闲或运行着更低 QoS 的任务，则直接放入；否则，将根据 迁移矩阵 寻找其他合适的集群。
• 调度延迟指标：调度器为每个集群维护一个动态指标，计算公式为 累计高优先级负载 * 平均执行延迟。通过计算集群间的延迟差值，决定是否需要迁移。
• 线程窃取与平衡：当某个处理器空闲时，它会尝试从其他集群中窃取任务。它会优先处理 国外 (Foreign) 线程，即那些当前运行在非首选集群类型上的线程。
特殊管理机制
• 共享资源线程管理：为了减少对集群共享资源的竞争，调度器提供了 轮询 (RR) 和 本地优先 两种策略。前者将任务均匀分散到所有集群，后者则优先填满首选集群及其同类集群。
• 搅拌锅 (Stir-the-pot) 机制：针对长时间运行的并行任务，调度器会在量子时间片结束时，在不同类型的核心之间交换线程。这可以确保所有线程的整体进度大致相同，防止慢速核心上的线程成为性能瓶颈，从而最大化利用系统的并行能力。
原文：https://github.com/apple-oss-distributions/xnu/blob/main/doc/scheduler/sched_clutch_edge.md