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 以及龙蜥社区。感兴趣的同学多多交换，多多关注。
文 / 马腾
原文链接
本文为阿里云原创内容，未经容许不得转载。