在 Linux 内核调度器的演进中可扩展调度器类sched_ext和代理执行Proxy Execution是当前技术前沿的两个核心热点。下面将首先解析“代理执行”的技术概念再结合内核最新动态包括sched_ext的子调度器架构及其与代理执行的融合进展进行完整的梳理与介绍。一、 什么是“代理执行”Proxy Execution代理执行Proxy Execution是操作系统内核中用于解决优先级反转Priority Inversion与死锁/延迟阻塞问题的一种高度通用的调度机制。1. 背景问题优先级反转与经典限制当低优先级任务 L 持有某个互斥锁而高优先级任务 H 也在请求该锁时任务 H 必须等待 L 释放锁。若此时出现无需该锁的中优先级任务 MCPU 会优先运行 M导致低优先级的 L 无法获得 CPU 运行进而使高优先级的 H 无期限等待——这就是典型的优先级反转。传统解决方案是优先级继承Priority Inheritance, PI即临时将 L 的数值优先级提升至与 H 相同。然而优先级继承存在致命局限不兼容非数值优先级算法对于截止时间调度如SCHED_DEADLINE任务根本没有数值形式的优先级仅有截止时间Deadline和配额RuntimePI 机制无法生效。算账不公L 继承高优先级后消耗的是自己的 CPU 额度资源核算容易失真。2. 代理执行的核心逻辑“借出调度上下文”代理执行不再尝试修改持锁者的属性而是引入了“出借调度身份”的概念[高优先级/截止时间任务 H] --------(持有 CPU 时间片与调度资格)--------┐ │ │ 借出执行权 ▼ (申请锁失败被阻塞) ▼ [持锁任务 L] (内核以 H 的身份代为执行 L 的代码) ┘留在队列当任务 H 因互斥锁阻塞时它不会被移出调度器的运行队列。选中与追踪当调度器按照正常规则如截止时间到了选中 H 运行 CPU 时内核发现 H 被锁阻塞于是顺着锁链追踪到持有该锁的任务 L。透明代运行内核直接在 CPU 上运行 L 的代码但消耗 H 的 CPU 配额与调度上下文。归还上下文一旦 L 运行完临界区并释放锁代理关系解除H 正式恢复自身的代码执行。这种方式完美解决了非优先级调度器的锁阻塞问题同时也让资源消耗的核算更加精准公平。二、 深度解析Linux 内核sched_ext的演进与代理执行融合下文整理自内核社区最新技术前沿介绍了sched_ext基于 BPF 的可扩展调度器在子调度器层级化Sub-schedulers和代理执行兼容性Proxy Execution Integration方面的重大更新。1. 前言与背景可扩展调度器类sched_ext允许将自定义 CPU 调度器作为一组 BPF 程序安装到内核中。尽管sched_ext以其当前形式已经引发了大量有趣的调度器开发工作但该子系统本身仍处于快速演进之中。在众多工作中设置子调度器层级结构的功能已接近完成而长期以来与“代理执行”的不兼容问题也即将划上句点。2. 子调度器入队路径The Sub-scheduler Enqueue Pathsched_ext在最初实现时只允许在任意给定系统上安装单个自定义调度器。然而没过多久多租户系统的用户就提出希望能够为不同的进程组设置不同的调度器。其成果便是引入了“子调度器”sub-schedulers将一个sched_ext调度器与一个控制组cgroup关联起来该组内的所有进程都将由挂载的调度器进行管理。与控制组的通用机制类似sched_ext调度器被组织成树状层级结构较高层级的调度器可以决定较低层级的调度器何时能够将进程放置到 CPU 上。最初的子调度器工作已合并入 7.1 版本内核但该功能尚不完整。具体而言子调度器当时只能处理派发路径dispatch path——即选择接下来在给定 CPU 上运行哪个进程。派发处理是按层级进行的父组调度器决定何时为其挂载的每个子组调度器运行派发处理程序。派发操作可以从派发队列中取出进程但它并没有解决进程最初是如何被放入该队列的问题。Tejun Heo 提交的这一系列补丁解决了入队路径enqueue path的问题事实证明这本身就具有相当的复杂性。派发端的逻辑相对简单控制权沿着调度器层级向下传递每个层级决定其下方的哪个子调度器被允许在任意给定时间将任务放入特定 CPU 的队列中。然而当某个受控任务变为可运行状态runnable时内核调度器核心随时都可以直接调用子调度器的enqueue()回调。在当前的内核中该回调可以将任务放入任意 CPU 的派发队列中并且能够抢占该 CPU 上正在运行的任务——无论被抢占的任务是否受同一个调度器控制。控制组旨在提供进程组之间的隔离性而入队路径也需要维护这种隔离性。由于调度是一项对性能极其敏感的活动入队路径应尽可能避免沿着调度器层级向上发起调用来判断某个特定的子调度器是否有权做出特定的放置决策。解决该问题的方法是一种“能力/权限capability”机制它允许调度器将其拥有的部分访问权限共享给其下方的子调度器。当子调度器挂载到层级结构中时它最初对系统中的任何 CPU 都没有访问权限。随后其父调度器可以通过调用scx_bpf_sub_grant()给予新调度器访问特定 CPU 集的能力。这种访问权限分为三个等级将任务放置到空闲 CPU 上的能力将任务放入 CPU 派发队列以待后续执行的能力抢占由其他调度器控制的任务的能力。根调度器root scheduler在所有 CPU 上拥有全部能力它可以将这些能力的部分或全部向下传递给挂载到它的子调度器。调度器只能将其自身拥有的能力授予子调度器。如果子调度器尝试将任务入队到其缺乏所需能力的 CPU 上该任务将被重定向到一个特殊的拒绝队列reject queue随后带有一个特殊的标志SCX_TASK_REENQ_CAP被重新交还给该子调度器的enqueue()回调提示调度器重试。如果父调度器撤销了先前授予子调度器的能力也会发生类似的情况在受影响 CPU 上调度的所有任务都将被移除然后交还给子调度器重新进行放置。随着这些修改的引入子调度器的相关工作已接近尾声不过 Heo 在封面信中还列出了几个剩余的细节问题将进程从一个控制组移动到另一个控制组时不会改变控制它的子调度器。可以通过限制手段例如使用sched_setaffinity()将进程绑定到其子调度器无法运行进程的 CPU 集上在这种情况下该进程最终将无法在任何地方运行。这种状态固然提高了隔离性但受影响进程的所有者恐怕不会欣赏这种“改进”。这些问题将留待后续工作解决。与此同时针对入队路径的补丁集已经历了多轮迭代并正稳步推进合并入 7.3 版本内核的计划。3. 与代理执行协同工作Getting Along with Proxy Execution正如前文所述在代理执行出现前sched_ext与代理执行是完全互斥的。当sched_ext调度器认为自己已经决定了由哪个进程运行后可能会惊讶地发现内核实际运行的是另一个不同的进程该进程甚至可能完全不在其控制范围内。出于这个原因代理执行和sched_ext在内核配置系统中被设置为互斥状态内核编译时只能二选一。这种局面给 Linux 发行版厂商带来了困扰因为他们不想被迫在两个重要特性之间做单选题。解决该问题的一个方案来自于 Andrea Righi 和 John Stultz 提交的补丁集。该补丁对sched_ext与代理执行的交互方式做了两项根本性改变1透明隐藏重定向细节当调度器选中一个被阻塞的进程运行时持锁者将被透明地代为运行但sched_ext调度器完全不会察觉到这种重定向因此不会因看到未经自己调度甚至不受自己控制的进程在运行而产生异常。此时使用的是等待进程的调度上下文持锁者消耗的 CPU 时间也将记在等待进程账上。在代理执行期间等待进程的调度上下文会被移动到持锁者所在的 CPU 上。一旦锁被释放调度上下文会被移回并调用调度器将现已可运行的进程重新入队。2显式声明Opt-in与标志回调在上述逻辑生效之前调度器必须向sched_ext核心表明其愿意参与代理执行这是通过在注册时提供新的SCX_OPS_ENQ_BLOCKED标志来实现的。当调度器以这种方式完成注册后因互斥锁而被阻塞的进程在传给调度器的enqueue()回调时会带有SCX_ENQ_BLOCKED标志。调度器随后可以决定是否要对阻塞任务的调度进行特殊处理。该补丁集包含对示例调度器scx_qmap的微小修改使其立即调度阻塞任务抢占当时正在运行的任何任务。这种“故意不公”的策略旨在使代理执行过程易于观察同时也展示了在底层基础设施就绪后让sched_ext调度器支持代理执行所需的修改是多么微小。3多调度器混合下的复杂性不过代理执行的效果如何还将取决于系统中运行的进程组合。如果sched_ext只负责一部分运行中的进程它将无法抢占在sched_ext之外运行且具有更高优先级的进程。该补丁的变更日志中包含一张表格根据等待进程、持锁者以及 CPU 上无关竞争进程的调度状态详细描述了 8 种不同场景下的实际行为。针对代理执行的补丁集也已进行了多轮修订并目标合并入 7.3 版本内核。总结Linux 内核调度子系统正在经历一场重塑子调度器机制通过能力授权解决了多租户 cgroup 隔离下的任务入队难题而代理执行与sched_ext的打通则消除了用户态/BPF 调度器与内核锁机制之间的鸿沟。这两项技术的合流意味着未来的 Linux 内核不仅能实现高度定制化、动态可编程的调度策略同时还能保持极致的响应速度与强隔离保障。
在 Linux 内核调度器的演进中可扩展调度器类sched_ext和代理执行Proxy Execution是当前技术前沿的两个核心热点。下面将首先解析“代理执行”的技术概念再结合内核最新动态包括sched_ext的子调度器架构及其与代理执行的融合进展进行完整的梳理与介绍。一、 什么是“代理执行”Proxy Execution代理执行Proxy Execution是操作系统内核中用于解决优先级反转Priority Inversion与死锁/延迟阻塞问题的一种高度通用的调度机制。1. 背景问题优先级反转与经典限制当低优先级任务 L 持有某个互斥锁而高优先级任务 H 也在请求该锁时任务 H 必须等待 L 释放锁。若此时出现无需该锁的中优先级任务 MCPU 会优先运行 M导致低优先级的 L 无法获得 CPU 运行进而使高优先级的 H 无期限等待——这就是典型的优先级反转。传统解决方案是优先级继承Priority Inheritance, PI即临时将 L 的数值优先级提升至与 H 相同。然而优先级继承存在致命局限不兼容非数值优先级算法对于截止时间调度如SCHED_DEADLINE任务根本没有数值形式的优先级仅有截止时间Deadline和配额RuntimePI 机制无法生效。算账不公L 继承高优先级后消耗的是自己的 CPU 额度资源核算容易失真。2. 代理执行的核心逻辑“借出调度上下文”代理执行不再尝试修改持锁者的属性而是引入了“出借调度身份”的概念[高优先级/截止时间任务 H] --------(持有 CPU 时间片与调度资格)--------┐ │ │ 借出执行权 ▼ (申请锁失败被阻塞) ▼ [持锁任务 L] (内核以 H 的身份代为执行 L 的代码) ┘留在队列当任务 H 因互斥锁阻塞时它不会被移出调度器的运行队列。选中与追踪当调度器按照正常规则如截止时间到了选中 H 运行 CPU 时内核发现 H 被锁阻塞于是顺着锁链追踪到持有该锁的任务 L。透明代运行内核直接在 CPU 上运行 L 的代码但消耗 H 的 CPU 配额与调度上下文。归还上下文一旦 L 运行完临界区并释放锁代理关系解除H 正式恢复自身的代码执行。这种方式完美解决了非优先级调度器的锁阻塞问题同时也让资源消耗的核算更加精准公平。二、 深度解析Linux 内核sched_ext的演进与代理执行融合下文整理自内核社区最新技术前沿介绍了sched_ext基于 BPF 的可扩展调度器在子调度器层级化Sub-schedulers和代理执行兼容性Proxy Execution Integration方面的重大更新。1. 前言与背景可扩展调度器类sched_ext允许将自定义 CPU 调度器作为一组 BPF 程序安装到内核中。尽管sched_ext以其当前形式已经引发了大量有趣的调度器开发工作但该子系统本身仍处于快速演进之中。在众多工作中设置子调度器层级结构的功能已接近完成而长期以来与“代理执行”的不兼容问题也即将划上句点。2. 子调度器入队路径The Sub-scheduler Enqueue Pathsched_ext在最初实现时只允许在任意给定系统上安装单个自定义调度器。然而没过多久多租户系统的用户就提出希望能够为不同的进程组设置不同的调度器。其成果便是引入了“子调度器”sub-schedulers将一个sched_ext调度器与一个控制组cgroup关联起来该组内的所有进程都将由挂载的调度器进行管理。与控制组的通用机制类似sched_ext调度器被组织成树状层级结构较高层级的调度器可以决定较低层级的调度器何时能够将进程放置到 CPU 上。最初的子调度器工作已合并入 7.1 版本内核但该功能尚不完整。具体而言子调度器当时只能处理派发路径dispatch path——即选择接下来在给定 CPU 上运行哪个进程。派发处理是按层级进行的父组调度器决定何时为其挂载的每个子组调度器运行派发处理程序。派发操作可以从派发队列中取出进程但它并没有解决进程最初是如何被放入该队列的问题。Tejun Heo 提交的这一系列补丁解决了入队路径enqueue path的问题事实证明这本身就具有相当的复杂性。派发端的逻辑相对简单控制权沿着调度器层级向下传递每个层级决定其下方的哪个子调度器被允许在任意给定时间将任务放入特定 CPU 的队列中。然而当某个受控任务变为可运行状态runnable时内核调度器核心随时都可以直接调用子调度器的enqueue()回调。在当前的内核中该回调可以将任务放入任意 CPU 的派发队列中并且能够抢占该 CPU 上正在运行的任务——无论被抢占的任务是否受同一个调度器控制。控制组旨在提供进程组之间的隔离性而入队路径也需要维护这种隔离性。由于调度是一项对性能极其敏感的活动入队路径应尽可能避免沿着调度器层级向上发起调用来判断某个特定的子调度器是否有权做出特定的放置决策。解决该问题的方法是一种“能力/权限capability”机制它允许调度器将其拥有的部分访问权限共享给其下方的子调度器。当子调度器挂载到层级结构中时它最初对系统中的任何 CPU 都没有访问权限。随后其父调度器可以通过调用scx_bpf_sub_grant()给予新调度器访问特定 CPU 集的能力。这种访问权限分为三个等级将任务放置到空闲 CPU 上的能力将任务放入 CPU 派发队列以待后续执行的能力抢占由其他调度器控制的任务的能力。根调度器root scheduler在所有 CPU 上拥有全部能力它可以将这些能力的部分或全部向下传递给挂载到它的子调度器。调度器只能将其自身拥有的能力授予子调度器。如果子调度器尝试将任务入队到其缺乏所需能力的 CPU 上该任务将被重定向到一个特殊的拒绝队列reject queue随后带有一个特殊的标志SCX_TASK_REENQ_CAP被重新交还给该子调度器的enqueue()回调提示调度器重试。如果父调度器撤销了先前授予子调度器的能力也会发生类似的情况在受影响 CPU 上调度的所有任务都将被移除然后交还给子调度器重新进行放置。随着这些修改的引入子调度器的相关工作已接近尾声不过 Heo 在封面信中还列出了几个剩余的细节问题将进程从一个控制组移动到另一个控制组时不会改变控制它的子调度器。可以通过限制手段例如使用sched_setaffinity()将进程绑定到其子调度器无法运行进程的 CPU 集上在这种情况下该进程最终将无法在任何地方运行。这种状态固然提高了隔离性但受影响进程的所有者恐怕不会欣赏这种“改进”。这些问题将留待后续工作解决。与此同时针对入队路径的补丁集已经历了多轮迭代并正稳步推进合并入 7.3 版本内核的计划。3. 与代理执行协同工作Getting Along with Proxy Execution正如前文所述在代理执行出现前sched_ext与代理执行是完全互斥的。当sched_ext调度器认为自己已经决定了由哪个进程运行后可能会惊讶地发现内核实际运行的是另一个不同的进程该进程甚至可能完全不在其控制范围内。出于这个原因代理执行和sched_ext在内核配置系统中被设置为互斥状态内核编译时只能二选一。这种局面给 Linux 发行版厂商带来了困扰因为他们不想被迫在两个重要特性之间做单选题。解决该问题的一个方案来自于 Andrea Righi 和 John Stultz 提交的补丁集。该补丁对sched_ext与代理执行的交互方式做了两项根本性改变1透明隐藏重定向细节当调度器选中一个被阻塞的进程运行时持锁者将被透明地代为运行但sched_ext调度器完全不会察觉到这种重定向因此不会因看到未经自己调度甚至不受自己控制的进程在运行而产生异常。此时使用的是等待进程的调度上下文持锁者消耗的 CPU 时间也将记在等待进程账上。在代理执行期间等待进程的调度上下文会被移动到持锁者所在的 CPU 上。一旦锁被释放调度上下文会被移回并调用调度器将现已可运行的进程重新入队。2显式声明Opt-in与标志回调在上述逻辑生效之前调度器必须向sched_ext核心表明其愿意参与代理执行这是通过在注册时提供新的SCX_OPS_ENQ_BLOCKED标志来实现的。当调度器以这种方式完成注册后因互斥锁而被阻塞的进程在传给调度器的enqueue()回调时会带有SCX_ENQ_BLOCKED标志。调度器随后可以决定是否要对阻塞任务的调度进行特殊处理。该补丁集包含对示例调度器scx_qmap的微小修改使其立即调度阻塞任务抢占当时正在运行的任何任务。这种“故意不公”的策略旨在使代理执行过程易于观察同时也展示了在底层基础设施就绪后让sched_ext调度器支持代理执行所需的修改是多么微小。3多调度器混合下的复杂性不过代理执行的效果如何还将取决于系统中运行的进程组合。如果sched_ext只负责一部分运行中的进程它将无法抢占在sched_ext之外运行且具有更高优先级的进程。该补丁的变更日志中包含一张表格根据等待进程、持锁者以及 CPU 上无关竞争进程的调度状态详细描述了 8 种不同场景下的实际行为。针对代理执行的补丁集也已进行了多轮修订并目标合并入 7.3 版本内核。总结Linux 内核调度子系统正在经历一场重塑子调度器机制通过能力授权解决了多租户 cgroup 隔离下的任务入队难题而代理执行与sched_ext的打通则消除了用户态/BPF 调度器与内核锁机制之间的鸿沟。这两项技术的合流意味着未来的 Linux 内核不仅能实现高度定制化、动态可编程的调度策略同时还能保持极致的响应速度与强隔离保障。
