系统与数据库2016ece.ubc.ca
Linux 调度器：浪费核心的十年
The Linux Scheduler: A Decade of Wasted Cores
进阶 · 约 75 分钟读完前置知识：操作系统基础、多核 CPU 调度、Linux CFS
导读
这篇 EuroSys 2016 论文系统分析了 Linux CFS 调度器十余年来与负载均衡相关的缺陷，发现多个会导致 CPU 核心被浪费（空闲核心未被利用、任务无法被迁移）的 bug，并给出了修复补丁。核心问题是调度器在跨 CPU 迁移任务和负载均衡上的实现错误长期存在，造成性能损失。
HN 关注点：是因为它揭示了操作系统最核心的调度器里长期潜伏的 bug，并引发对软件正确性、调度复杂度和测量方法的讨论。
后来怎么样
论文揭示了 Linux CFS 负载均衡中的多个真实缺陷，相关修复进入 Linux 内核，并成为调度器正确性与可观测性讨论中的典型案例。
HN 评论精选
这几条评论里：支持 1 补充 2 亲历 1
亲历用运行队列延迟直方图（如 runqlat）来检测调度问题。
我以前也在其他内核里处理过调度 bug（Linux 并非特例）。我们关注的关键指标是运行队列延迟，用来检测线程等待时间是否超出预期。测量方法有很多；我最近用的是 bcc/BPF 工具里的 runqlat，它以直方图形式展示运行队列延迟，例如输出会显示不同微秒区间的计数分布。
brendangregg查看英文原文
I've worked scheduling bugs in other kernels before (Linux is not an outlier here). The key metric we keep an eye on is run queue latency, to detect when threads are waiting longer than one would expect. And there's many ways to measure it; my most recent is runqlat from bcc/BPF tools, which shows it as a histogram. eg: # ./runqlat Tracing run queue latency... Hit Ctrl-C to end. ^C usecs : count distribution 0 -> 1 : 233 |*********** | 2 -> 3 : 742 |************************************ | 4 -> 7 : 203 |********** | 8 -> 15 : 173 |******** | 16 -> 31 : 24 |* | 32 -> 63 : 0 | | 64 -> 127 : 30 |* | 128 -> 255 : 6 | | 256 -> 511 : 3 | | 512 -> 1023 : 5 | | 1024 -> 2047 : 27 |* | 2048 -> 4095 : 30 |* | 4096 -> 8191 : 20 | | 8192 -> 16383 : 29 |* | 16384 -> 32767 : 809 |****************************************| 32768 -> 65535 : 64 |*** | I'll also use metrics that sum it by thread to estimate speed up (which helps quantify the issue), and do sanity tests. Note that this isolates one issue -- wait time in the scheduler -- whereas NUMA and scheduling also effects memory placement, so the runtime of applications can become slower with longer latency memory I/O from accessing remote memory. I like to measure and isolate that separately (PMCs). So I haven't generally seen such severe scheduling issues on our 1 or 2 node Linux systems. Although they are testing on 8 node, which may exacerbate the issue. Whatever the bugs are, though, I'll be happy to see them fixed, and may help encourage people to upgrade to newer Linux kernels (which come with other benefits, like BPF).
支持论文引文显示调度器 bug 众多且易被忽视，软件正确性很难。
论文里的引文很有意思：“没人能第一次就写出完美代码，除了我。但世上只有一个我。”——Linus Torvalds，2007。另一段引文则说明为何可能还有更多 bug 未被发现且容易被忽视：“我怀疑让调度器使用 per-CPU 队列加上一些跨 CPU 负载均衡逻辑大概很简单。补丁已经有了，我不觉得人们能把那几百行搞砸。”从更大视角看，这再次表明让软件正确并不容易。时不时还会听到最核心的操作系统代码里冒出 bug，我记得一个十年前的 TCP bug 去年被 Google 修复了。
jor-el查看英文原文
The quotes in the paper are interesting: "Nobody actually creates perfect code the first time around, except me. But there’s only one of me.” Linus Torvalds, 2007 And another, which highlights why there might be many more unearthed bugs, and would probably go unnoticed. "I suspect that making the scheduler use per-CPU queues together with some inter-CPU load balancing logic is probably trivial . Patches already exist, and I don’t feel that people can screw up the few hundred lines too badly" Looking at the bigger picture in general, this again shows that getting software right is not easy. Now and then you still hear about the bugs popping up in the code which is very core to an OS. One I can recall is a decade old TCP bug which Google fixed last year[1]. [1] http://bitsup.blogspot.sg/2015/09/thanks-google-tcp-team-for-open-source.html
补充调度是涉及缓存、功耗、锁开销的复杂成本优化问题。
调度已经变成一个困难问题。把任务从一个 CPU 移到另一个有缓存未命中开销。CPU 可以进入省电状态，但退出需要时间。跨 CPU 共享运行队列有锁开销。所以现在这是一个成本优化问题，却要在亚毫秒级决策层面完成。
Animats查看英文原文
Scheduling has become a hard problem. There's cache miss cost in moving a task from one CPU to another. CPUs can be put into power-saving states, but take time to come out of them. Sharing the run queue across CPUs has a locking cost. So it's now a cost optimization problem. That's a lot of work to be doing at the sub-millisecond decision level.
补充提供论文中修复补丁的链接（针对内核 4.1）。
如论文所述，补丁（目前针对内核 4.1）在这里：https://github.com/jplozi/wastedcores
j1vms查看英文原文
As indicated in the paper, patches (currently for kernel 4.1) are here: https://github.com/jplozi/wastedcores
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2016Hacker News 讨论帖467 分 · 142 评
同领域还值得读
I/O 比 CPU 更快——让我们划分资源并消除操作系统抽象
I/O Is Faster Than CPU – Let’s Partition Resources and Eliminate OS Abstractions
指出在现代服务器硬件上 I/O 速度已接近甚至超过 CPU，传统操作系统抽象反而成为瓶颈。
系统与数据库2019 · 817 分 · 277 评进阶 · 约 30 分钟编辑精选使用 io_uring 的高效 I/O
Efficient IO with io_uring
由 Linux 内核开发者 Jens Axboe 撰写，介绍 Linux 新的异步 I/O 接口 io_uring。
系统与数据库2019 · 426 分 · 96 评进阶 · 约 45 分钟编辑精选线程对大多数用途而言是个坏主意（1995）
Threads Are a Bad Idea for Most Purposes (1995)
这篇 1995 年的文章由 John Ousterhout 撰写，讨论为什么线程对大多数用途而言是坏主意，并主张事件驱动编程通常更简单、更高效。
系统与数据库2017 · 423 分 · 382 评进阶 · 约 25 分钟编辑精选学习型索引结构之论证
The Case for Learned Index Structures
提出把索引看作一种"模型"：既然 B-tree 等结构本质上是在学习数据的分布，就可以用机器学习模型（如回归模型、神经网络）来近似键到位置的映射，从而替代 B-tree、哈希索引…
系统与数据库2017 · 398 分 · 66 评 · 引用 25进阶 · 约 60 分钟编辑精选FoundationDB：一个分布式、解耦的事务型键值存储
FoundationDB: A distributed, unbundled, transactional key value store
介绍 FoundationDB：一个分布式、解耦设计的事务性键值存储。
系统与数据库2021 · 283 分 · 99 评进阶 · 约 90 分钟编辑精选