BVT 1999 — 让一份调度器同时照顾"急性子"和"老黄牛"

是什么

BVT（Borrowed-Virtual-Time，借式虚拟时间）是一套让操作系统同时招待两类完全相反的任务的调度算法。

两类任务长什么样：

急性子（延迟敏感）：视频通话、游戏、UI、音频。要求”事件一来，毫秒级上 CPU”，但每次只占 CPU 一小会儿
老黄牛（吞吐型）：编译代码、跑数据分析、备份。要求”长期把 CPU 总量按比例分给我”，但不在乎多等 50 毫秒

日常类比：医院急诊。急诊病人不能排队（延迟敏感），但门诊病人也不能因为急诊一直来就永远排不到（吞吐公平）。BVT 的解法就是给急诊一张”借号牌”——可以插队，但事后从他自己的额度里扣掉。

为什么重要

不理解 BVT，下面这些事都说不清：

Linux 内核里那个 vruntime 字段是怎么来的——CFS（Completely Fair Scheduler）的虚拟时间核心思想就是 BVT
早期 Xen 虚拟机为什么能给一台机器跑 30 个 VM 还不卡——Xen 第一版 CPU 调度器叫 “BVT scheduler”，直接抄
为什么现代 OS 不再像 Windows 95 那样用”优先级数字”调度，改用虚拟时间——优先级会饿死低优先级任务，BVT 不会
1999 年这篇 6 页论文影响了之后 25 年所有通用 OS 的调度器

核心要点

BVT 把每个线程贴两个数：

AVT（Actual Virtual Time，实际虚拟时间）：这个线程实际烧了多少 CPU。日常类比：你在自助餐取了多少饭。每个线程取饭速度还按”权重”调（权重大的取得慢，相当于饭菜便宜）。
EVT（Effective Virtual Time，有效虚拟时间）= AVT − warp：调度器只看 EVT，永远把 CPU 给 EVT 最小那个。warp（“扭曲”）就是借号牌的额度。

延迟敏感线程一被事件唤醒（比如收到网络包），瞬间 EVT 减去 warp，立刻冲到队列最前。跑完短任务回去睡觉，AVT 已经多记了一笔。长期来看，他借的时间最终都还了——CPU 总量仍然按权重公平分。

护栏两条：

L（warp time limit）：最多能借多久不还，防止他赖着不走
U（unwarp time requirement）：还完后多久才能再借，防止他来回横跳

实践案例

案例 1：视频通话和编译同时跑

你一边开视频会议，一边后台 cargo build。

编译进程：warp = 0（老黄牛），AVT 一直涨
视频解码进程：warp = 50ms（急性子）；平时它睡眠 AVT 不涨；新视频帧到达，OS 唤醒它，瞬间 EVT 比编译进程小 50ms 的虚拟时间，立刻抢到 CPU

解码完一帧（比如 5ms）就睡。下次唤醒再借。编译没饿死，视频不卡——一个 warp 参数搞定。

具体数字：假设编译 AVT = 1000ms，视频被唤醒时 AVT = 950ms。

没有 warp：视频 EVT = 950，编译 EVT = 1000，视频本就该跑——但实际刚醒来时调度器要等当前时间片用完
加 warp = 50ms：视频 EVT = 950 − 50 = 900，立刻抢占编译，无需等当前时间片用完

案例 2：BVT 和优先级调度的本质区别

传统优先级调度：
  视频 = 优先级 10  →  编译 = 优先级 5
  视频要是 bug 死循环了 → 编译永远拿不到 CPU（饿死）

BVT：
  视频 warp=50ms，编译 warp=0
  视频死循环 → AVT 涨到比编译大 → EVT 自己变大 → 让位给编译

BVT 的关键：借的总要还。优先级是单向的，BVT 是闭环的。

案例 3：Linux CFS 里的 BVT 影子

打开 /proc/<pid>/sched，能看到 se.vruntime 字段。这就是 AVT。CFS 用红黑树把所有线程按 vruntime 排序，永远跑最小那个。nice 值改的是 vruntime 增长速度（相当于权重）。

CFS 没用显式 warp，但有两个”精神继承”的机制：

wakeup preemption 阈值（sched_wakeup_granularity_ns）：刚醒的线程可以”少算一点 vruntime”立刻抢占
min_vruntime 同步：新进程或长睡的进程不会”vruntime 严重落后”霸占 CPU——相当于 BVT 的 L 护栏

案例 4：Xen 用 BVT 调度 VM

Xen 是开源 hypervisor。一台物理机跑多个 VM，每个 VM 是一个被调度的实体。Xen 第一版（2003）直接照搬 BVT：

dom0（特权域，处理所有物理 IO）warp 大 → 网络/磁盘中断响应快
普通 VM warp = 0 → 按 CPU 分配权重公平共享

后续 Xen 改成 credit scheduler（2006），用”周期补 credit”代替 warp，但虚拟时间记账没变。这是 BVT 思想从 OS 进程级扩展到 hypervisor 级的最早实证。

踩过的坑（论文 + 后续工程）

warp 参数靠手调：到底设 5ms 还是 50ms？论文给经验值（音频 50ms），但跨设备/场景没通用解。这是 BVT 没解决的痛点。后来 Xen credit 调度器用”周期补充 credit”绕过手调，但又引入新的边角行为
多核扩展难：单核下 EVT 全局排序简单。32 核每核一个就绪队列时，全局最小 EVT 要跨核找，开销大。Linux CFS 通过”每核红黑树 + 周期 load balance”绕过
不是硬实时：BVT 提供”低延迟”但不保证”最坏情况延迟 < X 毫秒”。航天/汽车/医疗仪器这些硬实时场景仍要 EDF（最早截止优先）类算法
IO vs CPU 密集判断仍靠经验：哪些线程该给 warp？默认所有交互线程，但”交互”的判定还是要 OS 启发式（最近是否在阻塞 IO 之类）
新线程 AVT 设多少：直接给 0 会让新线程一直被优先（AVT 远小于已跑很久的老线程）。论文要求 “AVT 至少要追上系统最小 AVT”——CFS 也用 min_vruntime 解决相同问题

适用 vs 不适用场景

适用：

通用桌面/服务器 OS（要同时跑交互 + 后台批处理）
虚拟机 hypervisor 给 VM 分 CPU（Xen credit/BVT、KVM）
容器编排里的 CPU 共享（cgroup cpu.shares 本质就是权重）
移动设备（前台 app 高 warp，后台同步任务 warp = 0）

不适用：

硬实时系统（飞控、医疗）→ 用 EDF 或 RM
单一负载（只跑批处理）→ FIFO 都够
极端低延迟交易系统 → 直接 spin 占核，不用通用调度器
GPU 调度 → GPU 上下文切换代价不同，要专门的 token bucket 类算法

历史小故事（可跳过）

1989-1995：Waldspurger 的 Lottery Scheduling（彩票调度）和 Stride Scheduling（步幅调度）把”概率公平”变成”确定性公平”，引入虚拟时间雏形
1996：Waldspurger 博士论文系统化”proportional share”调度
1999 年 12 月：Duda 和 Cheriton 在 SOSP 1999 发表 BVT 论文，把 warp 加到虚拟时间上，6 页搞定。Cheriton 是 Stanford V Kernel 作者，也是 Google 早期天使
2003：Xen 第一版 hypervisor 直接采用 BVT 作为 VM CPU 调度器
2007：Linux 2.6.23 把 CFS 进主线，vruntime + 红黑树成为之后 18 年事实标准
2024：EEVDF（Earliest Eligible Virtual Deadline First）替换 CFS，但虚拟时间核心思想没变

borrow（借）这个名字的灵感就是金融借贷——延迟敏感线程从未来”借”CPU 时间，事后还。论文作者明说这是设计美感所在：把不公平限制在可量化范围内。

学到什么

调度的本质是给”时间”建模：不是排队列，而是记账。BVT 把”已用 CPU”变成”可比较的数”，调度变排序题
闭环 vs 开环：优先级是开环（高就一直高），虚拟时间是闭环（用得多就排后面）。闭环系统天然抗饿死
借号牌设计：用一个标量参数 warp 同时编码”我多急”和”我愿意还”，比加一堆类别字段优雅
理论 → 算法 → 工程 → 标准：1989 概率 → 1995 确定 → 1999 加 warp → 2007 Linux 主线，每跳一步隔 5-10 年
简单的护栏 > 复杂的策略：BVT 的 L 和 U 两个参数就把所有”借了不还”的边角情况堵住，没引入分类讨论

关联

lottery-1994 —— Lottery Scheduling，BVT 的概率版前辈，引入”虚拟时间”思想
afs-1988 —— AFS 同时代分布式系统，体现 SOSP 1980-90 年代关注的 fair share 主题
amdahl-law-1967 —— 调度器优化最终被 Amdahl 律限制，并行部分越多收益越大

反向链接

afs-1988 —— AFS 1988 — 客户端缓存 + 回调失效让分布式文件系统真正能扩展
amdahl-law-1967 —— Amdahl 定律 — 串行比例决定并行加速比的上界
lottery-1994 —— 彩票调度 — 用抽奖代替优先级的资源分配