OS 调度

针对现代计算系统的更优调度策略

Kostis Kaffes，Peter Alvaro 引言

研究应用于实践专栏结合了数字图书馆（世界上最大的计算机科学研究库）的资源和会员的专业知识。研究应用于实践专栏的共同目标是在学术界和工业界的同行之间分享阅读计算机科学研究的乐趣和实用性。

在任何资源多路复用的系统中，调度计算在何处以及何时运行的问题可能是最根本的。然而，像计算机科学中的许多其他基本问题（例如，数据库中的查询优化）一样，调度方面的学术研究像钟摆一样摆动，经历了活跃期，然后是休眠期，在休眠期它被认为是“已解决”的问题。

很高兴见证这个钟摆再次摆动，我们非常幸运能够邀请到 Kostis Kaffes 来策划最近精选的优秀调度研究。他的选择突出了与性能、可扩展性和策略选择相关的突破。第一篇论文挑战了低延迟（通常通过配置专用核心来实现）和高利用率（需要核心重新分配）之间的假定权衡，通过在微秒级粒度上进行分配决策来实现。第二篇论文通过将策略的创建和操作（可以完全由用户空间代理处理）与固定的内核机制（将事件传递给代理并应用调度决策）分离，从而能够创建任意调度策略。最后，有了在微秒级粒度上基于灵活策略执行负载均衡和分配决策的能力，最终的选择解决了在每个应用程序基础上选择策略的问题。

Kostis 汇集了一个精彩且连贯的选择，并附有一篇引言，让首次考虑调度研究的读者感到舒适。请尽情享受。

—Peter Alvaro

研究应用于实践：OS 调度

Kostis Kaffes

长期以来，调度一直是系统和网络中最基本的操作之一。它涉及将任务分配给 CPU 并在它们之间切换——这些决策对于应用程序性能和系统效率都至关重要。长期以来，操作系统 (OS) 调度侧重于公平性。然而，最近的两项发展导致了 OS 调度研究的复兴。首先，云计算的兴起使尾部延迟和时间尺度（即微秒 (μs) 级）等不同的、难以优化的指标变得重要，而传统调度程序并未考虑这些指标。其次，摩尔定律的终结使得系统堆栈（包括调度）的专业化变得必要，以继续提高性能。

本期“研究应用于实践”介绍了三篇论文，探讨了将 OS 调度引入现代时代的方法。第一篇论文侧重于构建最快的调度程序，而第二篇论文旨在使实现与现有应用程序和操作系统兼容的新策略变得容易。第三篇论文探讨了不同类型应用程序的最佳调度策略。最终，所有三篇论文都为持续开发针对现代计算系统的更优调度策略的努力做出了宝贵贡献。

微秒级核心重新分配

Amy Ousterhout、Joshua Fried、Jonathan Behrens、Adam Belay 和 Hari Balakrishnan（MIT CSAIL）。 Shenango：为延迟敏感型数据中心工作负载实现高 CPU 效率。《第 16 届 Usenix 网络系统设计与实现研讨会论文集》，2019 年。

https://dl.acm.org/doi/10.5555/3323234.3323265

Ousterhout 等人的第一篇论文回答了操作系统中核心分配可以多快进行以及这种重新分配是否有益于应用程序性能的基本问题。论文中提出的系统 Shenango 挑战了长期以来的普遍看法，即在微秒级时间尺度上跨应用程序分配核心是不可行的，因为开销高且可能导致缓存污染。作者表明，快速核心重新分配确实是可能的，并且可以产生显着的性能优势。

Shenango 操作系统中实现微秒级核心重新分配的关键是使用专用调度核心，该核心可以每 5 微秒做出分配决策。为了确定何时从应用程序分配或回收核心，Shenango 监视每个应用程序的线程运行队列和网络数据包队列的长度，并将它们长度的导数用作拥塞信号。该算法完全在专用核心上运行，该核心还管理将传入网络数据包引导至其各自目标应用程序核心。

作者通过展示细粒度核心重新分配如何提高位于同一系统上的延迟敏感型和批处理应用程序的性能，证明了这种方法的有效性。通过根据瞬时输入数据包速率分配核心，与 100 微秒间隔相比，Shenango 将前者的延迟降低，并将后者的吞吐量提高了六倍以上（使用 5 微秒核心重新分配间隔时）。

随后的工作表明，Shenango 的微秒级调度程序还可以帮助缓解其他系统资源（例如，末级缓存和内存带宽）的干扰，并为网络提供细粒度反馈以防止过载。

用于将 OS 调度部署到 Linux 的框架

Jack Tigar Humphries（谷歌）、Neel Natu（谷歌）、Ashwin Chaugule（谷歌）、Ofir Weisse（谷歌）、Barret Rhoden（谷歌）、Josh Don（谷歌）、Luigi Rizzo（谷歌）、Oleg Rombakh（谷歌）、Paul Turner（谷歌）和 Christos Kozyrakis（斯坦福大学和谷歌）。 ghOSt：Linux 调度的快速且灵活的用户空间委托。《第 28 届操作系统原理研讨会论文集》，2021 年。

https://dl.acm.org/doi/10.1145/3477132.3483542

构建像 Shenango 这样高效的调度程序是一项有趣的学术实践，但它不能立即应用于生产环境，因为生产环境受到与现有应用程序和 Linux 等操作系统向后兼容性等约束。这就是为什么谷歌工程师团队构建了一个名为 ghOSt 的框架，该框架可以轻松实现不同的调度策略并将它们部署到 Linux 内核。

ghOSt 设计背后的关键观察是调度不需要在内核中进行。ghOSt 从微内核中汲取灵感，将 OS 调度委托给用户空间代理，可以是全局的或每个 CPU 的。它由一个精简的内核调度类组成，该类仅将调度事件（例如，线程变为可运行状态）通信给这些代理，这些代理做出关于在何处运行什么的调度决策，然后将其传回内核。因此，开发人员可以享受用户空间开发的敏捷性，而不会受到内核代码和漫长部署周期的限制。此外，ghOSt 允许应用程序通过共享内存与调度代理共享提示，从而使后者能够做出更明智的调度决策。

ghOSt 必须克服的最大挑战是内核组件和用户空间代理之间的通信延迟，这可能长达 5 微秒。这可能导致 (1) 竞争条件（例如，用户空间代理将线程调度到已从线程的 CPU 掩码中删除的 CPU）和 (2) 利用率不足，因为 CPU 保持空闲状态，等待代理的调度决策。

ghOSt 通过在共享内存上实现事务 API 来避免竞争条件，该 API 允许代理原子地提交调度决策。为了缓解第二个问题，作者建议使用自定义 eBPF 程序，这些程序在每个核心上本地运行并临时调度任务，直到收到代理的决策。相同的技术也适用于将其他操作系统功能卸载到用户空间（例如，内存管理）。

选择最佳调度策略选项

Sarah McClure（加州大学伯克利分校）、Amy Ousterhout（加州大学伯克利分校）、Scott Shenker（加州大学伯克利分校和 ICSI）、Sylvia Ratnasamy（加州大学伯克利分校）。微秒级任务的高效调度策略。《第 19 届 Usenix 网络系统设计与实现研讨会论文集》，2022 年。

https://www.usenix.org/conference/nsdi22/presentation/mcclure

在引入 ghOSt（允许轻松开发和部署自定义调度策略）之后，出现了一个问题，即每个应用程序应使用哪种策略。为了回答这个问题，McClure 等人对可用选项进行了全面分析。

作者将调度过程分为两个不同的决策：跨应用程序分配核心和在每个应用程序内的 CPU 之间进行负载均衡任务。令人惊讶的是，他们发现第二个决策相对简单；无论任务服务时间分布、核心数量、核心分配策略和负载均衡开销如何，工作窃取都是延迟和效率方面最佳的负载均衡策略。

相比之下，核心分配决策要细致得多。例如，与过去的工作相反，作者发现，对于小任务，基于平均延迟或利用率主动从应用程序回收核心比等待 CPU 变为空闲状态效果更好。他们还发现，在服务小任务时，最好为每个应用程序分配固定数量的 CPU，而不是动态分配 CPU。

该分析开辟了新的研究领域，例如开发实现可扩展全局队列的新硬件，仿真表明，该硬件的性能甚至优于工作窃取。此外，这项研究没有考虑抢占的存在，这表明需要进一步检查抢占如何影响调度决策。

结论

这三篇论文为持续开发针对现代计算系统的更优调度策略的努力做出了重大贡献。这些论文突出了对更好、更高效和更灵活的 OS 调度程序的需求；开辟了新的研究领域；并证明了 OS 调度策略持续开发和创新的重要性。

Peter Alvaro 是加州大学圣克鲁兹分校计算机科学副教授，他在那里领导 Disorderly Labs 研究小组 (disorderlylabs.github.io)。他的研究重点是使用以数据为中心的语言和分析技术来构建和推理数据密集型分布式系统，以便使它们可扩展、可预测且对大规模分布特有的故障和不确定性具有鲁棒性。他在加州大学伯克利分校获得博士学位，师从 Joseph M. Hellerstein。他是国家科学基金会职业奖、Facebook 研究奖、Usenix ATC 2020 最佳演示奖、SIGMOD 2021 杰出 PC 奖和 UCSC 卓越教学奖的获得者。

Kostis Kaffes 是哥伦比亚大学即将上任的助理教授，也是 SystemsResearch@Google 的软件工程师。他在斯坦福大学获得电气工程博士学位，导师是 Christos Kozyrakis。他的研究兴趣包括计算机系统、云计算和调度。

最初发表于 Queue vol. 21, no. 2—
在数字图书馆中评论本文

更多相关文章

David Chisnall - 如何设计 ISA
在过去的十年中，我参与了多个项目，这些项目设计了 ISA（指令集架构）扩展或针对各种处理器的全新 ISA（您甚至可以在 RISC-V 规范的致谢中找到我的名字，一直追溯到第一个公共版本）。当我开始时，我对是什么构成好的 ISA 知之甚少，而且，据我所知，这在任何地方都没有正式教授。

Gabriel Falcao, João Dinis Ferreira - PiM 还是非 PiM
随着人工智能成为数十亿边缘 IoT（物联网）设备的普遍工具，数据移动瓶颈对这些系统的性能和自主性施加了严格的限制。PiM（内存内处理）正在兴起，成为一种缓解数据移动瓶颈的方法，同时满足依赖 CNN（卷积神经网络）的边缘成像应用程序的严格性能、能效和准确性要求。

Mohamed Zahran - 异构计算：将继续存在
在过去的几年中，对流行语异构计算的提及一直在增加，并且在未来几年将继续被听到，因为异构计算将继续存在。什么是异构计算，为什么它正在成为常态？我们如何从软件方面和硬件方面来处理它？本文提供了对其中一些问题的解答，并提出了对其他问题的不同观点。

David Chisnall - 没有所谓的通用处理器
计算机架构中存在一种日益增长的趋势，即将处理器和加速器归类为“通用”。在今年国际计算机体系结构研讨会 (ISCA 2014) 上发表的论文中，45 篇论文中有 9 篇明确提到了通用处理器；另一篇还提到了通用 FPGA（现场可编程门阵列），另一篇提到了通用 MIMD（多指令多数据）超级计算机，将定义扩展到了崩溃点。本文提出了一个论点，即没有真正意义上的通用处理器，并且对这种设备的信念是有害的。