文/马腾
01 前言
阿里云基础软件/达摩操作系统实验室的论文 "Efficient Scheduler Live Update for Linux Kernel with Modularization" 被系统领域著名会议 28th Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'2（3) 录用为长论文（Full Paper）。
ASPLOS 会议在体系结构领域被认为是顶会之一，同时也是系统领域最重要的会议，被中国计算机协会 CCF 认证为 A 类会议，同时在阿里内部会议列表中也被选为 1 类会议。目前已经举办至 28 届，吸引了来自学术及产业界的大量投稿。该会议的参会人员不乏来自国外顶级高校如 MIT、UC Berkeley、University of Chicago、普林斯顿以及国内清北交大等知名院校。
该会议均为学术相关论文，没有专门的 Industry track，在 2022 年设置了三次投稿机会，分别是 spring cycle、summer cycle 和 fall summer。这篇论文投稿了summer cycle，并获得了三位评委 accept 的评价，因此给了一次进行 revision 的机会。在 revision 阶段，Plugsched 实现了评委提出的意见，获得了一致肯定，最终被接收在 ASPLOS 23 会议上，论文所在的 session 是 OS/Virtualization。
文章主要介绍了专门针对调度器的热升级系统 Plugsched，该项目已经开源。调度器是操作系统的一个重要组成部分，与 Linux 内核紧密耦合。生产环境下的云经常承载各种工作负载，这些工作负载需要不同的调度器来实现高性能。因此，在不重启操作系统的情况下在线地升级调度器的能力对生产环境至关重要。然而，目前已有的在线热升级技术只适用于细粒度的功能级升级或需要额外的约束，如限定在微内核中。当前的技术并不能够支持对内核调度子系统的热升级。
因此，我们提出了 Plugsched 来实现调度器的实时更新，其中有两个关键的创新点。首先，利用模块化的思想，Plugsched 将调度器与 Linux 内核解耦，成为一个独立的模块；其次，Plugsched 使用数据重建技术将状态从旧的调度器迁移到新的调度器。这个方案可以直接应用于生产环境中的 Linux 内核调度器，而无需修改内核代码。与目前的函数级实时更新方案不同，Plugsched 允许开发者通过重建技术更新整个调度器子系统并修改内部调度器数据。此外，还引入了优化的堆栈检测方法，以进一步有效减少因更新而导致的停机时间。我们使用三个新的调度器进行升级，来评估 Plugsched 的性能。实验结果表明，Plugsched 能够有效地更新内核调度器，并且停机时间（halting time）小于几十毫秒。
详细论文内容参见或者会议官网议程。下面将对论文进行详细的解析：
02 背景
Linux 调度器
Linux 调度器通过决定一个旧的进程何时停止以及一个新的进程何时运行，来提供抢占式的多任务。调度器是内核中最基础和最复杂的子系统之一。调度器子系统包含超过 27K LOC 和 63 个文件，而且还有许多复杂的子系统与调度器交互，因此它与内核的结构和功能是紧密耦合的。虽然默认的 Linux 调度器很强大，但应用程序往往需要不同的调度器来实现最佳性能。例如，微秒级的工作负载，如memcached、silo，对调度器的开销极为敏感。即使是单一的应用类型，不同的工作负载在不同的调度策略下表现往往有很大差异性。云计算和数据中心的工作负载更多的是混部应用，因此调度器的效率更加重要。随着工作负载的混部化，对延迟敏感的任务和长期运行的批处理任务在同一个节点上共存，为满足各种应用的 SLO，需要考虑到新的调度器策略。为了实现高性能并适应不同的场景，应该允许用户将定制的调度策略整合到生产环境中，例如，使用上游的"core scheduling"patch（将近 4KLOC 的代码修改）来修复潜在的性能问题。实际生产环境的经验还表明，在无服务器（Serverless）计算场景中，当容器部署密度较高时，通过应用新的负载平衡机制，CPU 调度开销可以从 6% 降低到 1.5%。相反，如果部署密度低，该机制会对 CPU 开销产生负面影响。
在生产环境中实现调度器的热升级是有利于整体性能的，但直接的方法是给操作系统（OS）打补丁，重新启动操作系统，重新初始化硬件，并重新启动上层应用。传统的内核升级技术，如虚拟机迁移，是通过 checkpoint-and-restore（C/R）的方法，内核的停机时间随着进程/线程的数量线性增加。虽然在目前的云原生时代，服务器上有超过 10,000 个线程是很常见的场景，但根据我们的测量，超过 10,000 个线程带来的停机时间仍然达到数分钟。对于延迟敏感的应用（如金融交易应用）和长期运行的应用来说，漫长的停机时间是不可接受的。虽然对延迟敏感的应用只能承受较短的停机时间，因此生产环境上需要有一种调度器的热升级方法能够将停机时间减少到几十毫秒的水平。
State-of-the-art 热升级工具的缺陷
学术界和工业界都提出了一些内核热升级的解决方案，以保证内核代码更新到最新的安全版本，而不破坏服务器的现有状态（如重新启动）。图 1 显示了现有内核热升级技术的特点。X 轴的 "表现力 "是指开发人员可以升级内容的范围，而 Y 轴的 "通用性 "是指新的功能在没有额外约束的情况下在现有 Linux 内核上实用性。为了设计一个合适的调度器热升级方案，我们应该考虑三个主要的约束：
1）不应该带来内核代码的额外修改。
2）必须能够部署在商业化 Linux 服务器中。
3）不应该只局限在虚拟化环境中使用。
如图 1 所示，大多数实时补丁工具都是功能级的解决方案（例如，livepatch、kpatch、Ksplice），这些工具主要解决要升级的代码变化很少（少于 100 LOC）的小型安全补丁，并且缺乏对数据状态迁移的考虑。尽管这些工具对大多数情况都是通用的，但它们的表达能力很差，不能支持集成可能修改许多函数和数据结构的新调度器功能。例如，集成上文提到的 "core scheduling "功能需要修改内核中的 19 个文件（超过 4000 行的代码）。
一些先前的工作也支持组件级的实时热升级。PROTEOS 在很大程度上依赖于微内核操作系统的特点，这意味着它不能够被用于商业化 Linux 服务器。针对 KVM 而言，由于 KVM 是一个独立的内核模块，Orthus 通过双 KVM 和 VM 之间迁移实现了 KVM 的热升级。ghOSt 将调度策略迁移到了用户空间进程，它提供了状态封装、通信和行动机制，使用户空间进程可以表达复杂的调度策略。相应地，在用户空间切换到一个新的调度器也很容易。然而，热升级的范围仅限于调度器类（如CFS），而且用户空间和内核空间之间的额外通信开销（上下文切换等），增加了端到端的延迟（原始论文中报告的延迟是正常调度器延迟的 2 倍左右）。另外需要注意的是，运行中的服务器的内核也应该被修改以适应 ghOSt。而操作系统级的实时更新解决方案，比如 VM-PHU，依赖于虚拟机管理器（VMM），它只适用于更新虚拟机中的客户内核。我们可以总结出 State-of-the-art 的热升级解决方案不能满足调度器热升级的需求。
（图 1 / Plugsched 和其他热升级工具的比较）
03 系统设计原则
基于以上的讨论，Plugsched 的定位也如图 1 所示。Plugsched 是一个调度器的实时更新系统，支持组件级的实时更新（即充分的表达能力）。Plugsched 适用于多种场景，包括几乎所有的商用 Linux 服务器和灵活的生产环境（即高通用性）。除了表达性和通用性之外，这样的解决方案还必须满足短停机时间和安全性的要求，即要求该解决方案不应损害应用程序或带来潜在的安全问题。最后，在开发和部署阶段，它应该是用户友好的。
充分的表达能力：Plugsched 支持组件级的实时热升级。具体来说，它可以用一个新的调度器代替旧的调度器，必须能够支持修改大量的函数和数据结构。同时，数据状态能够从旧的调度器自动迁移到新的调度器上。
高通用性：Plugsched可用于大部分的商用 Linux 服务器，而且没有额外的约束条件。其他一些实时更新解决方案需要内核在虚拟机中运行或被限制在微内核中，因此它们的使用场景是有限的，而 Plugsched 可以在各种包括物理机和虚拟机的生产环境中使用。另外一点需要注意的是，要直接将 Plugsched 部署到运行旧内核的服务器上，应避免修改内核代码。
同时实现短停机时间和安全性：停机时间是衡量效率的主要标准。在调度器升级期间，应用程序不应该有明显的服务中断。为了确保安全性，调度器应该被视为一个有明确边界的完整模块，因此它可以以 "全有或全无（all-or-nothing）"的方式被更新（也就是原子性）。此外，还需要一个有效的检查机制来决定内核是否可以安全地更新，并且该机制不应该带来大量的开销。
易于使用：Plugsched 简化了调度器的开发和部署流程，因此开发者可以专注于调度策略的开发。在热升级中，Plugsched 提供常见的热升级辅助技术，如堆栈检查、数据更新、内存池等等，开发者可以直接使用它们，而不需要任何调整。在Plugsched 中，调度器的升级和回滚可以通过安装和卸载调度器 RPM 包轻松完成，所以非常方便开发者在生产环境中快速验证他们的调度策略。
04 设计总览
图 2 给出了 Plugsched 的整体架构。整个架构包括三个部分：调度器模块化的预处理阶段；调度器开发者的开发阶段；以及应用新调度器的部署阶段。
在预处理阶段，使用根据内核版本手工生成的配置，Plugsched 在编译阶段自动收集调度器的相关信息，如函数和数据结构的符号（1）。然后运行边界分析算法，确定调度器和内核之间的清晰边界，并将函数进一步细分为内部函数、接口函数和外部函数（2）。在代码提取阶段，Plugsched 通过代码生成技术将调度器相关的代码（如内部函数和接口函数）重新组织到一个单独的目录中，调度器被解耦到一个新的模块中（3）。在开发阶段，开发者可以像往常一样在该目录下自由开发调度器或集成新的功能（4），然后编译新的调度器，生成一个 RPM 包（5）。在部署阶段，Plugsched 需要找到一个能够安全更新的机会（即 state quiescence），用新的调度器替换原来的调度器。因此，Plugsched 需要首先调用 stop_machine 来停止所有线程。然后，Plugsched 使用堆栈检测来检查所有的内核堆栈，并检查是否有不安全的线程( 6 )。在堆栈检查完成后，Plugsched 将原函数的 prologue （即第一条指令）替换为重定向到新函数的跳转指令（函数重定向，7）。同时，Plugsched将数据从旧的调度器迁移到新的调度器，通过基于重建的方法保证数据是最新的（数据更新，8）。从 stop_machine 返回后，原调度器被旁路。需要注意的是，回滚阶段与安装新调度器的部署阶段基本相同。Plugsched 还提供了一些机制（例如 sidecar）来适应生产环境中的实际部署（详情见论文）。
（图 2 / Plugsched 的工作流程图）
Plugsched 有两个关键的创新点，即调度器模块化和数据重建。具体来说，模块化允许将调度器与内核解耦，这是实现热升级的先决条件。另外我们进一步利用数据重建将数据状态从旧调度器迁移到新调度器。这使得热升级前后的调度器之间能够协作，并确保调度状态的正确性。有了这样一个通用的解决方案，调度器可以针对具体场景进行定制，并支持任何功能的整合，甚至是更换一个全新的调度器。实现调度器模块化并非易事，因为一些热点路径如调度器中的 try_to_wake_up()、schedule()、cpu_set()、scheduler_tick() 和 scheduler_ipi() 等函数被许多其他内核子系统如 time、cgroup 和 IPI 直接调用。如果不进行详尽的代码分析，调度器的模块化可能会导致内核故障。因此，我们提出一种边界分析方法，通过静态分析来分析模块的依赖关系。因此，模块化使开发者能够根据调度器和内核之间清晰的边界自由开发自定义的调度器。在之前的工作中，数据状态在更新内核的时候没有被维护。一些工作使用 object 或 Shadow data structure 来避免数据状态迁移。然而，由于不同的数据结构（上百规模场景下）会涉及大量不同的状态，这些解决方案并不具有足够的通用性。我们观察到调度器中的数据结构状态可以通过操作 running queue 和 task_struct 的两个稳定的 API 进行重构。基于这一观察，Plugsched 在调度器更新后安全地重建了数据结构。我们在 Plugsched 中引入了以下四种设计范式，以支持组件级调度器的热升级，而不会产生安全问题，并避免额外的开销：
1）Plugsched 在预处理阶段使用函数调用依赖图来确定调度器和其余内核之间的明确边界。它利用 GCC 插件将调度器的相关代码提取到子目录中，作为新调度器的 Codebase。
2）为了减少停机时间，Plugsched 从两个维度充分挖掘多核计算的性能，优化了堆栈检测方法。
3）Plugsched 替换了原函数的 prologue，重定向到新函数。这个有一个特例，为了处理不能直接替换的上下文切换逻辑（即__schedule()函数），Plugsched 对__schedule() 函数的分割使用了栈迁移和 ROP 等技术。
4) Plugsched 提出了一种基于重建的方法来处理数据状态迁移 。
05 实验效果
如图 3 所示，我们总结了潜在的解决方案，并将 Plugsched 和它们进行了比较。Plugsched 安全地支持组件级的热升级，而不需要内核修改代码以及额外的开销，与此同时它也有很好的表达能力和通用性，开发者可以自由地开发新的调度器并部署到商用的 Linux 服务器上。
（图 3 / Plugsched和其他工具的详细对比）
Plugsched 已经部署在生产环境的 4000 台服务器上，为这些机器提供安全和高效的组件级别热升级能力，并且仅仅带来很短的停机时间。在我们的实验中，选择了几个 Linux 社区中的新功能和一个全新的 Tiny Scheduler 来取代原生的内核调度器，实验结果表明热升级带来的停机时间只有 2.1∼2.6𝑚𝑠，回滚的停机时间为1.8∼2.5𝑚𝑠。即使在工作负荷很重的情况下，停机时间的增量也不超过 61%。与 kpatch（一个常用的内核补丁工具）相比，Plugsched 在提供组件级热升级能力支持的同时，将升级和回滚的停机时间分别减少了约 24% 和 26%。另外一方面，Plugsched 的整套解决方案也可以扩展到其他 Linux 子系统之中用来做热升级，比如 eBPF、内存管理、网络等子系统。
06 特别感谢
特别感谢阿里云基础软件，达摩院操作系统实验室的同事以及上海交通大学老师在整体方案设计和实现上的帮助和指导，文章的最早一版曾经投稿过 OSDI' 22，经过修改历时一年半，最终被系统领域顶会 ASPLOS 认可！同时也特别感谢所有贡献作者的建议和指导！这是阿里集团的原创性工作，并且项目已经开源在 Github、Gitee以及龙蜥社区。感兴趣的同学多多交流，多多关注。
—— 完 ——
