操作系统驱动开发【免费下载链接】darwin-xnuLegacy mirror of Darwin Kernel. Replaced by https://github.com/apple-oss-distributions/xnu项目地址https://gitcode.com/gh_mirrors/da/darwin-xnu点击查看免费下载本文基于开源 darwin-xnu 仓库中 osfmk/kern/sched_clutch.md 设计文档结合 osfmk/kern/sched_clutch.c 与 osfmk/kern/sched_clutch.h 的源码实现系统讲解 Clutch Scheduler 的三层层次化调度架构、根桶 EDF 选择与 warp 机制、线程组优先级计算以及线程级 Mach timesharing 衰减模型。读完本文你将理解 XNU 如何通过调度桶 → 线程组 → 线程三层结构同时保证高 QoS 工作负载的低延迟与低 QoS 批量任务的防饿死并能在源码中精准定位每个机制的实现位置。背景为什么传统 Mach 调度器难以满足现代负载XNU 内核运行在多种平台上需要在两类截然不同的需求之间取得平衡延迟敏感型工作负载UI 交互、多媒体录制/播放等需要快速获得 CPU批量型低优先级工作负载照片同步、源码编译等需要防饿死保证但不能抢占关键任务。传统 Mach 调度器通过给系统中每个线程打一个优先级数字来近似这两类需求高优先级视为交互型、低优先级视为批量型并使用基于优先级衰减的 timesharing 模型——线程消耗 CPU 越多、优先级衰减越多从而实现 fairshare 与防饿死。这种线程中心的调度方式存在两个根本性缺陷不精确的记账Inaccurate accounting线程级 CPU 记账会激励系统创建更多线程在 GCD 与 workqueue 时代线程被快速创建与销毁线程级记账既不精确还容易导致过度 CPU 消耗。糟糕的隔离性Poor isolationtimesharing 通过按全局系统负载衰减线程优先级实现这会导致同级别或更低级别出现突发活动时App/UI 线程也被衰减造成性能与响应性下降。调度器几乎无法在延迟敏感的 UI 工作负载与大批量非敏感操作之间提供隔离。更深层的问题在于线程级调度丢失了线程与更高层用户工作负载之间的关联关系调度器无法把工作负载当作一个整体来推理——而这恰恰是最终用户真正关心的。线程级 timesharing 的另一个产物是同一优先级下的线程无论服务于哪个用户工作负载都被一视同仁常常导致非最优决策各子系统为了防饿死与避免同其他无关线程 timesharing还会不断抬升自身优先级最终造成平台范围内的优先级通胀priority inflation。Clutch Scheduler 总体设计三层层次化调度为了解决上述问题Clutch Scheduler 不再调度单个线程而是调度线程组thread group。它打破传统的单层调度模型实现了一个层次化调度器在多个线程聚合层级上做出最优决策。当前实现包含 3 个层级Scheduling Bucket Level调度桶层——最顶层决定选择哪一类线程执行Thread Group Level线程组层——决定一个桶内选择哪个线程组Thread Level线程层——最底层决定线程组内选择哪个线程。调度桶由线程的 base/scheduling 优先级决定粗略映射到 OS runtime 使用的 QoS 类用于定义各类工作的性能预期。同一调度桶内的所有可运行线程在顶层由单个条目代表该条目在实现中称为root bucket根桶。第一层Scheduling Bucket Level调度桶层调度桶层的目标为高 QoS 类提供低延迟的 CPU 访问同时为低 QoS 类保证防饿死。EDF 根桶选择算法调度桶层使用Earliest Deadline FirstEDF算法决定下一个执行哪个根桶。每个有可运行线程的根桶作为条目进入一个按 deadline截止时间排序的优先队列选择算法直接选出 deadline 最早的根桶。根桶的 deadline 基于其 first-runnable 时间戳与该桶预定义的Worst Case Execution LatencyWCEL最坏执行延迟计算。WCEL 的取值参考了 Mach timesharing 算法的衰减曲线使得新调度器在更高层面看与旧调度器行为接近。其定义见 osfmk/kern/sched_clutch.cstatic uint32_t sched_clutch_root_bucket_wcel_us[TH_BUCKET_SCHED_MAX] { SCHED_CLUTCH_INVALID_TIME_32, /* FIXPRI */ 0, /* FG */ 37500, /* IN (37.5ms) */ 75000, /* DF (75ms) */ 150000, /* UT (150ms) */ 250000 /* BG (250ms) */ };各调度桶的含义见 osfmk/kern/sched.h 的sched_bucket_t枚举TH_BUCKET_FIXPRI固定优先级、TH_BUCKET_SHARE_FG高于BASEPRI_DEFAULT的 timeshare 线程、TH_BUCKET_SHARE_INBASEPRI_USER_INITIATED与BASEPRI_DEFAULT之间、TH_BUCKET_SHARE_DF、TH_BUCKET_SHARE_UT、TH_BUCKET_SHARE_BG最底层的 throttled/后台区间。关键行为当根桶从 non-runnable 变为 runnable 时其 deadline 被设置为(now WCEL[bucket])保证即使在重度负载系统中该桶也会在WCEL[bucket]时间内被调度到一旦根桶被选中执行其 deadline 被向后推迟WCEL[bucket]。注意TH_BUCKET_FIXPRI的 WCEL 是SCHED_CLUTCH_INVALID_TIME_32~0表示无效时间因为 FIXPRI 桶被特例处理见下文 AboveUI 特例。实现中微秒单位通过sched_clutch_us_to_abstime()osfmk/kern/sched_clutch.c在启动时统一转换为绝对时间单位无效值映射为SCHED_CLUTCH_INVALID_TIME_64其余通过clock_interval_to_absolutetime_interval(us_vals[i], NSEC_PER_USEC, ...)转换最终存入sched_clutch_root_bucket_wcel[]。根桶 warp 机制应对突发负载基本 EDF 实现有一个重大问题在重度负载系统中高桶近期可能已消耗了足够多的 CPU导致其 deadline 落在低桶之后。此时若出现一小波用户关键工作负载高桶必须等低桶跑完才能获得 CPU可能引发性能问题。为此调度桶层实现了根桶 warp扭曲/前跳机制每个桶被赋予一个 warp 值每当桶因 deadline 到期而被选中时刷新。定义见 osfmk/kern/sched_clutch.cstatic uint32_t sched_clutch_root_bucket_warp_us[TH_BUCKET_SCHED_MAX] { SCHED_CLUTCH_INVALID_TIME_32, /* FIXPRI */ 8000, /* FG (8ms)*/ 4000, /* IN (4ms) */ 2000, /* DF (2ms) */ 1000, /* UT (1ms) */ 0 /* BG (0ms) */ };根桶选择逻辑sched_clutch_root_highest_root_bucket()找到 deadline 最早的桶EDF 桶检查是否有自然优先级顺序更高的桶还有 warp 剩余通过scr_unbound_warp_available/scr_bound_warp_available位图查找若有则选择该桶并打开一个 warp 窗口——warp 窗口期间调度器持续选择这个 warp 桶而忽略更低的桶scrb_warped_deadline timestamp scrb_warp_remaining当 warp 桶被耗尽drain或 warp 窗口到期后scrb_warped_deadline timestamp调度器回到按 deadline 顺序调度此时将该桶的scrb_warp_remaining置 0 并从 warp 可用位图中清除。该机制给高层桶提供有界的优势使它们在突发负载下保持响应性。warp 只在同类型bound/unbound根桶之间生效因为 warp 本质上是相对低 QoS 根桶的调度优势。AboveUIFIXPRI桶特例FIXPRI 桶包含对延迟极其敏感的线程被特殊处理源码注释见 osfmk/kern/sched_clutch.c实现见sched_clutch_root_unbound_select_aboveui()与sched_clutch_root_bound_select_aboveui()由于 AboveUI 与 FG timeshare 桶的优先级范围重叠必须在这两个桶之间维持某种原生优先级顺序策略比较两个桶的最高 clutch bucketunbound 情形若 AboveUI 桶更高则立即调度它否则回落到基于 deadline 的调度bound 情形则直接比较两个桶中最高可运行线程的highq。这一设计允许 AboveUI 线程获得极低延迟的 CPU 访问同时支持高优先级 timeshare 线程与低优先级固定优先级线程竞争的场景某些媒体工作负载中可观察到。由于 timeshare 桶消费 CPU 后优先级会自然下降该模型为 UI 之上的 timeshare 线程提供了期望行为。位图与空层次检查调度桶层还维护一个可运行根桶的位图scr_unbound_runnable_bitmap/scr_bound_runnable_bitmap用于快速检查层次是否为空以及根级优先级计算。相关数据结构定义于 osfmk/kern/sched_clutch.h 的struct sched_clutch_root它维护所有可运行根桶的优先队列scr_unbound_root_buckets/scr_bound_root_buckets均为 deadline 最小堆、根级优先级scr_priority、根级 urgencyscr_urgency、可运行线程总数scr_thr_count以及绑定/未绑定根桶的存储数组。为什么这一层选 EDF文档给出的理由非常明确可直接用于理解设计取舍基于 deadline 的调度允许调度器为所有调度桶定义严格的最坏执行延迟上界EDF 算法基于桶的可运行性与选择是动态的由于所有 deadline 更新计算开销都很低算法可以在无明显开销的情况下维持最新信息高效实现高桶低调度延迟 低桶防饿死的双重目标桶层调度器最坏情况下只面对固定且数量很小的可运行桶定义 deadline、warp 等参数非常容易配置。第二层Thread Group Level线程组层线程组层决定一个桶内选择哪个线程组执行。线程组thread group是随 AMP 调度器引入的机制代表为一个特定工作负载服务的线程集合。每个桶内具有可运行线程的线程组在本层由条目代表实现中称为clutch bucket离合桶。本层目标在各种用户工作负载之间共享 CPU且偏好交互式应用而非计算密集型批量负载。ULE 变体clutch bucket 优先级队列线程组层实现的是 FreeBSD ULE 调度器的一种变体每个有可运行线程的 clutch bucket 作为条目进入一个按 clutch bucket 优先级排序的 runqueue选择算法直接取最高优先级的 clutch bucket。优先级计算基于三个因素clutch bucket 内最高可运行线程clutch bucket 维护一个优先队列scb_clutchpri_prioq按线程的 promoted提升后或 base 优先级排序——哪个属性使线程有资格进入该 clutch bucket 就用哪个。使用 base 与 sched 两种优先级让调度器能够尊重来自用户空间的 SPI 优先级指定、turnstile 等优先级继承机制带来的优先级提升以及其他核心调度器之外的优先级影响机制交互性得分Interactivity score基于 clutch bucket 整体自愿阻塞时间 / CPU 使用时间的比值计算让调度器偏好高度交互的线程组而非批量计算型线程组线程组类型Thread Group Type为改善 AMP 设备电池续航OS 将守护进程线程组标记为 Efficient。这些线程组通常代表与用户请求工作负载无直接关系的任务。调度器将其因素计入优先级计算从而使其排在别的工作之后。优先级计算细节见下文Clutch Bucket 优先级计算一节。数据结构上struct sched_clutch_bucketosfmk/kern/sched_clutch.h保存线程组的 runqueuescb_thread_runq、clutchpri 优先队列、桶编号scb_bucket、桶优先级scb_priority与线程数scb_thr_count等struct sched_clutch_bucket_group同文件 #L301-L338则维护该线程组在该调度桶上的 timesharing 属性优先级 shift、CPU 使用/阻塞数据、interactivity 数据并内嵌每个 pset 一个的scbg_clutch_buckets[MAX_PSETS]。runqueue 的两点精细设计插入队首当 clutch bucket 中的线程被抢占preempt时该 clutch bucket 被插入 runqueue 的队首使被抢占的线程保持其在队列中的顺序轮转rotate当从 clutch bucket 选出一个线程执行时runqueue 会把该 clutch bucket 轮转到同优先级层的队尾从而在同一优先级的多个 clutch bucket 之间高效 round robin——特别是在高度争用、CPU 数量少的系统上。为什么这一层适合交互性得分算法基于近期行为它允许线程组之间公平共享 CPU由于只看近期 CPU 使用历史能快速适应变化的行为优先级计算相当廉价调度器能维护所有线程组的最新信息从而做出更优决策线程组为共同服务于一个用户工作负载的线程提供了方便的抽象基于该抽象做调度决策系统可以做出有趣的选择例如优先 App 而非 daemon——这通常更有利于系统响应性。第三层Thread Level线程层最底层决定一个 clutch bucket 内选择哪个线程执行。clutch bucket 内每个可运行线程作为条目进入按schedpri组织的 runqueuescb_thread_runq一个 stable max 优先队列线程选择算法直接取队列中最高优先级线程。schedpri基于传统 Mach 调度算法计算用负载与 CPU 使用量衰减线程优先级。线程衰减模型在这层比在全局调度器更合适因为负载计算只统计同一 clutch bucket 内的线程。由于同一 clutch bucket 内所有线程属于同一线程组和调度桶该算法能为 clutch bucket 内延迟敏感的线程提供快速 CPU 访问而不影响系统中其他无关线程。实现Mach timesharing 每桶 quantum线程层实现 Mach timesharing 算法clutch bucket 内所有可运行线程按 schedpri 插入 runqueue调度器根据 clutch bucket 内可运行线程数与单个线程的 CPU 使用量计算 schedpri。负载信息每个 scheduler tick 更新线程随 CPU 消耗用其做优先级衰减计算。衰减算法奖励突发型交互线程、惩罚 CPU 密集型线程。线程被选中运行后获得一个基于其调度桶的 quantum时间片静态定义如下非 OSX 目标见 osfmk/kern/sched_clutch.cOSX 目标下 IN/DF 也是 10msstatic uint32_t sched_clutch_thread_quantum_us[TH_BUCKET_SCHED_MAX] { 10000, /* FIXPRI (10ms) */ 10000, /* FG (10ms) */ 8000, /* IN (8ms) */ 6000, /* DF (6ms) */ 4000, /* UT (4ms) */ 2000 /* BG (2ms) */ };每桶 quantum 使调度器能够为被高优先级线程饿死的低优先级线程界定最坏执行延迟。此外struct sched_clutch_rootosfmk/kern/sched_clutch.h的注释还提到根级维护上次调度的 root bucket信息以实现桶级 quantum桶级 quantum 允许低优先级桶即使包含一堆短执行线程也有公平机会使用 CPU。调度器优先级计算根优先级Root Priority计算调度器为层次维护一个根级优先级用于做抢占pre-emption与线程选择决策线程插入/移出层次时更新。根级同时维护 urgency 位辅助抢占决策。伪代码Root Priority Calculation: * If AboveUI bucket is runnable, * Compare priority of AboveUI highest clutch bucket (CBUI) with Timeshare FG highest clutch bucket (CBFG) * If pri(CBUI) pri(CBFG), select CBUI * Otherwise find the (non-AboveUI) highest priority root bucket that is runnable and select its highest clutch bucket * Find the highest priority (promoted or base pri) thread within that clutch bucket and assign that as root priority Root Urgency Calculation: * On thread insertion into the hierarchy, increment the root level urgency based on threads sched_pri * On thread removal from the hierarchy, decrement the root level urgency based on threads sched_pri源码中对应sched_clutch_root_priority()与sched_clutch_root_urgency()声明见 osfmk/kern/sched_clutch.c根结构scr_priority与scr_urgency均在sched_clutch_root_init()中初始化为NOPRI/ 0osfmk/kern/sched_clutch.c。根桶优先级计算根桶优先级就是根桶的 deadlineroot-bucket priority now WCEL[bucket]即把桶的 WCEL 加到桶变为 runnable 的时间戳上对应sched_clutch_root_bucket_deadline_calculate()osfmk/kern/sched_clutch.c。Clutch Bucket 优先级计算如前所述clutch bucket 优先级由最高可运行线程、交互性得分与线程组类型三个因素决定伪代码* Find the highest runnable thread (promoted or basepri) in the clutch bucket (maxpri) * Check if the thread group for this clutch bucket is marked Efficient. * If not, assign a positive boost value (clutch_boost) * Calculate the ratio of CPU blocked and CPU used for the clutch bucket. * If blocked used, assign a score (interactivity_score) in the higher range. * Else, assign a score (interactivity_score) in the lower range. * clutch-bucket priority maxpri clutch_boost interactivity_score线程组 boost 的基础在 osfmk/kern/sched_clutch.hSCHED_CLUTCH_TG_PRI_LOW/MED/HIGH枚举当前实现给 HIGH 与 MED 线程组小幅 boost实际效果就是在 AMP 系统上把标记为 Efficient 的守护进程线程组降权。交互性得分的实现为sched_clutch_bucket_group_interactivity_score_calculate()osfmk/kern/sched_clutch.c对 FIXPRI 桶强制标记为交互2 * sched_clutch_bucket_group_interactive_pri因为 AboveUI 根桶选择依赖 clutch bucket 优先级对其他桶先按 pending 时间与桶负载做 CPU 统计老化sched_clutch_bucket_group_pending_ageout()再用 CPU used/blocked 数据算出得分sched_clutch_interactivity_from_cpu_data()。CPU 使用/阻塞数据由sched_clutch_bucket_cpu_data_t联合体osfmk/kern/sched_clutch.h统一原子维护64 位平台用unsigned __int128打包scbcd_cpu_used与scbcd_cpu_blocked32 位平台则用 64 位打包保证并发更新的一致性。线程优先级计算线程优先级基于 Mach timesharing 算法* Every scheduler tick, snapshot the load for the clutch bucket * Use the load value to calculate the priority shift values for all threads in the clutch bucket * thread priority base priority - (thread CPU usage priority shift)每个 scheduler tick 对 clutch bucket 负载做快照用负载值计算桶内所有线程的 priority shift存储在sched_clutch_bucket_group的scbg_pri_shift见 osfmk/kern/sched_clutch.h线程优先级为 base priority 减去其 CPU 使用量右移 shift 位的结果——这正是 Mach 衰减曲线在该层的内化体现且负载只统计同一 clutch bucket隔离性由此而来。关键数据结构与并发模型速览理解 Clutch Scheduler 还需要了解三个核心对象及其关联全部定义在 osfmk/kern/sched_clutch.h结构含义与上层的关系struct sched_clutch_root层次根一个 pset 一个管理所有可运行根桶的 EDF 优先队列与位图struct sched_clutch_root_bucket根桶所有同一调度桶的 unbound 线程跨线程组或 bound 线程含 clutch bucket runqueue / bound runq、warp 状态与防饿死窗口struct sched_clutch一个线程组 1:1 的调度对象内嵌全部sched_clutch_bucket_group[TH_BUCKET_SCHED_MAX]struct sched_clutch_bucket_group线程组在某调度桶上的聚合维护 timesharing 属性与每 pset 的 clutch bucketstruct sched_clutch_bucketclutch bucket线程组 × 调度桶 × cluster线程 runqueue clutchpri 队列 CPU 统计层次结构挂在 pset 上因此受pset lock保护sched_clutch_hierarchy_locked_assert()断言pset_assert_locked(root_clutch-scr_pset)osfmk/kern/sched_clutch.c头文件中用(P)标注 pset lock 保护、(A)标注原子更新、(I)标注仅初始化后不变。跨 cluster 迁移相关的计数如sched_clutch.sc_thr_count用原子类型支持。此外SCHED_CLUTCH_THREAD_ELIGIBLE(thread)宏osfmk/kern/sched_clutch.h规定绑定到特定处理器bound_processor ! PROCESSOR_NULL的线程不进入 clutch 层次在CONFIG_SCHED_EDGE下cluster bound 线程ECORE/PCORE only会走独立的 bound 根桶路径这也是实现中反复出现 bound/unbound 两套根桶与位图的原因。从源码验证设计关键实现位置索引三层架构总述与背景设计文档 osfmk/kern/sched_clutch.md根桶 WCEL / warp / 线程 quantum 配置数组osfmk/kern/sched_clutch.cEDF warp AboveUI 特例的根桶选择主流程sched_clutch_root_highest_root_bucket()osfmk/kern/sched_clutch.c根桶 deadline 计算sched_clutch_root_bucket_deadline_calculate()osfmk/kern/sched_clutch.c交互性得分计算sched_clutch_bucket_group_interactivity_score_calculate()osfmk/kern/sched_clutch.c调度桶枚举与含义osfmk/kern/sched.h全部核心数据结构与锁协议标注osfmk/kern/sched_clutch.h。小结Clutch Scheduler 用调度桶 → 线程组 → 线程三层层次化模型把调度决策从孤立线程提升到用户工作负载的粒度顶层 EDF warp 保证高 QoS 桶的低延迟与低 QoS 桶的防饿死中间层基于最高线程优先级、交互性得分与线程组类型Efficient 标记在应用与守护进程之间公平分配 CPU底层则沿用 Mach timesharing 衰减模型但负载计算被隔离在同一 clutch bucket 内从而同时获得交互响应性与工作负载隔离。这一设计从根本上缓解了传统 Mach 调度器的记账失真、隔离缺失与优先级通胀问题也解释了现代 Apple 平台上前台 App 流畅、后台守护不抢 CPU体验背后的调度层原理。赞分享操作系统驱动开发【免费下载链接】darwin-xnuLegacy mirror of Darwin Kernel. Replaced by https://github.com/apple-oss-distributions/xnu项目地址https://gitcode.com/gh_mirrors/da/darwin-xnu点击查看免费下载相关推荐Nomad 调度器深度解析从评估Evaluation到分配计划Plan的完整调度流水线Nomad 调度器深度解析从评估Evaluation到分配计划Plan的完整调度流水线 本篇技术指南以 scheduler/README.md htt任务调度云原生运维后端Linux 内核初始化第八部分调度器Scheduler初始化深度解析Linux 内核初始化第八部分调度器Scheduler初始化深度解析 导读 本文基于 linux insides 项目 Initialization 章节文档教程操作系统mistral.rs 架构解析三层分层、引擎线程与连续批处理调度机制mistral.rs 架构解析三层分层、引擎线程与连续批处理调度机制 本篇技术指南以 mistral.rs 开发者文档中的 架构说明 https://link推理引擎模型推理服务AI Agent多模态创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考