前置讲 P3 · 操作系统基础：调度、虚拟内存与分页、缓存与淘汰 · OS Basics for Inference Systems

对应 Maps to：原课没有对应的一次课。CS349D 默认学生学过操作系统；这篇前置讲为没有这类背景的读者补上读第 2、3、9、12–14 讲需要的操作系统概念。PagedAttention 就是”分页”，RadixAttention 是”基数树 + LRU”，抢占与换出是”进程调度 + swap”，Clockwork、LithOS 都自称在做”操作系统”——不懂这些概念，那几讲会很吃力。 依据说明：操作系统部分依据 R. Arpaci-Dusseau 与 A. Arpaci-Dusseau 的公开教材 Operating Systems: Three Easy Pieces（OSTEP）中关于调度、多级反馈队列、分页、换页策略的章节，以及几篇经典论文：L. Belady, A Study of Replacement Algorithms for a Virtual-Storage Computer（1966，最优置换）；L. Belady, R. Nelson, G. Shedler（1969，FIFO 的异常）；N. Megiddo, D. Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache（FAST 2003）；N. Bansal, M. Harchol-Balter, Analysis of SRPT Scheduling: Investigating Unfairness（SIGMETRICS 2001）；D. Morrison 的 PATRICIA（1968，基数树）。与推理系统的对应来自本讲义第 2、3、9–14 讲读过的论文（vLLM、SGLang、Mooncake、Autellix、LithOS、Prism、MemGPT）。 配套代码 Code：code/prereq3/（numpy + 标准库；5 个脚本 + 1 个共享模块；全部几秒内跑完） 预计阅读时间：3–4 小时（含运行代码）

0. 本讲导航 · How to read this lecture

0.1 学习目标 Learning goals

学完这一篇，你应该能够：

1. 区分进程和线程，说出上下文切换做了什么、大约要多久；解释 Python 的 GIL 为什么让推理引擎把分词、调度、反分词拆成几个进程。
2. 比较 FCFS、SJF、SRPT、轮转、多级反馈队列、优先级调度在平均响应时间、尾延迟和公平性上的表现，说清”作业大小的方差”和”知不知道作业有多大”为什么是关键。
3. 解释虚拟内存的地址翻译、外部碎片与内部碎片、分页、写时复制、换出与颠簸，并把它们一一对应到 PagedAttention 和 KV cache 的管理上。
4. 比较 FIFO、LRU、LFU、CLOCK、ARC 和 Belady 最优的命中率，说出每种策略在什么访问模式下崩溃。
5. 描述前缀树和基数树，说明 RadixAttention 为什么要用引用计数、为什么只淘汰叶子。

0.2 先修与本讲范围 Prerequisites & scope

0.3 本讲地图 Map

§1  进程、线程与上下文切换；GIL；为什么推理引擎是多进程的                       ← 代码 01
§2  CPU 调度：FCFS、SJF、SRPT、轮转、多级反馈队列、优先级与老化                 ← 代码 02
§3  虚拟内存：地址翻译、碎片、分页、页大小、写时复制、换出与颠簸               ← 代码 03
§4  缓存与淘汰：局部性、FIFO / LRU / LFU / CLOCK / ARC、Belady 最优与异常       ← 代码 04
§5  前缀树、基数树与引用计数                                                 ← 代码 05
§6  与推理系统的联系（只想快速浏览的读者读这一节）
§7–11  小结、常见误区、练习、延伸阅读、下一篇

0.4 记号与术语 Notation

0.5 关于数字 · About the numbers

代码 02–05 是模拟：调度、内存分配、缓存、基数树都是用 Python 实现的小模型，时间单位是抽象的（调度里是”平均作业大小”），结果说明规律和量级，不是某个操作系统或推理引擎的实测。代码 01 是实测（一台 Apple M4 Pro、12 核、macOS、Python 3.13），你的机器上会不同。

1. 进程、线程与上下文切换 · Processes, threads, and context switches

1.1 进程和线程

一个进程（process）是一个正在运行的程序：它有自己的地址空间（自己的一份内存）、打开的文件、以及一个或多个执行流。一个线程（thread）就是其中的一个执行流：它有自己的寄存器和栈，但和同一进程里的其他线程共享内存。

代码 01 演示 1：线程把一个列表的元素改成 1，主线程马上看到 1；子进程把它改成 2，主进程看到的仍然是 1——子进程改的是它自己的那一份。共享内存让线程之间交换数据很方便（直接读写），也很危险（两个线程同时改同一个数据会互相踩，需要加锁）；进程之间默认隔离，要交换数据得通过管道、套接字、共享内存段等进程间通信（IPC）。

1.2 上下文切换

一个 CPU 核心同一时刻只能执行一个执行流。操作系统让很多进程、线程”轮流”使用 CPU：时间到了、或者当前执行流在等 I/O，就把它的寄存器等状态保存起来，换上另一个的——这叫上下文切换（context switch）。切换本身要花时间（保存、恢复状态；调度器做决定；缓存和 TLB 里的内容被新的执行流冲掉，之后要重新预热）。

代码 01 演示 3 量了一次”发过去、再发回来”（往返）要多久，每次往返至少包含两次唤醒另一个执行流：

跨线程、跨进程比函数调用慢几百倍。推理引擎每一步都要在组件之间传消息（新请求、生成的 token、要反分词的文字）；一步 decode 只有几到几十毫秒，所以引擎会把一批请求的消息打包成一条发送，而不是每个请求发一次。

1.3 GIL：为什么推理引擎是多进程的

CPython（最常用的 Python 解释器）有一个全局解释器锁（GIL）：同一个进程里，同一时刻只有一个线程能执行 Python 字节码。代码 01 演示 2（4 份同样的工作）：

纯 Python 的计算，开再多线程也几乎不会更快；多进程各有自己的解释器和 GIL，才能真正并行。numpy 在做大块运算时会释放 GIL，但它底层的 BLAS 库自己已经用了多个核心，再开线程或进程也快不了多少。

推理引擎在 CPU 上要做的事——接收请求、分词、调度、组批、采样后处理、反分词、流式返回——大多是 Python 代码。放在同一个进程的不同线程里，它们会互相抢 GIL，拖慢每一步的调度。所以 SGLang、vLLM 都把它们拆成几个进程：例如 SGLang 有 tokenizer manager、scheduler、detokenizer manager 三个进程，用 ZeroMQ 传消息（第 16 讲）。Python 3.13 起有可选的”无 GIL”版本，这个设计今后可能改变。

GPU 也有”上下文”：每个使用 GPU 的进程有自己的 GPU 上下文（地址空间、内核、显存）。多个进程共享一块 GPU 时，时间片轮转要在上下文之间切换，代价比 CPU 上大得多——这是第 12 讲 MPS、MIG、LithOS 要解决的问题之一。

2. CPU 调度 · CPU scheduling

2.1 问题

有一个服务器（一个 CPU 核心、一块 GPU、一个推理引擎的批），作业陆续到达，每个作业需要一定的服务时间。调度器要决定：下一个运行谁？运行多久？新作业到达时，要不要打断正在运行的？

衡量的指标：

• 平均响应时间：大家平均等多久。
• 尾延迟：P99 响应时间、最长的等待——最倒霉的那些人等多久。
• 公平性：大作业和小作业的 slowdown 是否差不多；有没有人永远等不到（饥饿，starvation）。

2.2 FCFS 与护航效应

最简单的策略是先到先服务（FCFS，first come first served）。代码 02 演示 1：A 需要 10 个单位，B、C 各需要 1 个，同时到达。

FCFS 让两个只要 1 个单位的作业在 A 后面等了 10 个单位——一辆慢车后面跟着一串快车，这叫护航效应（convoy effect）。先跑短的，平均响应时间降到一半以下，A 只多等了 2 个单位。

2.3 SJF 与 SRPT：短作业优先

• SJF（shortest job first）：每次选最短的作业，运行到结束，不抢占。
• SRPT（shortest remaining processing time）：每次选剩余时间最短的；新作业到达时，如果它比当前作业的剩余时间还短，就抢占。

SRPT 是单服务器上平均响应时间最优的策略（这是一个经典定理）。直觉是：先完成一个短作业，后面所有人都少等了一小段；先完成一个长作业，后面所有人都多等了一大段。

代码 02 演示 2 在负载 0.8 下比较三种作业大小分布（平均都是 1）：

（表里是平均响应时间。）几个要点：

• 方差决定排队：同样的平均大小、同样的负载，FCFS 的平均响应从指数分布的 4.6 涨到长尾分布的 31.3。偶尔一个超大作业，后面的人全部要等。前置讲 P4 的 Pollaczek–Khinchine 公式会把这一点写成精确的式子：排队时间和作业大小的二阶矩成正比。
• 抢占很重要：不抢占的 SJF 好不少，但还是会被已经开始运行的大作业挡住；SRPT 在长尾时是 FCFS 的 1/19。
• SRPT 并不怎么”欺负”大作业：长尾时，最大的 1% 作业在 SRPT 下的 slowdown 是 2.11，比 FCFS（2.45）和轮转（3.38）都低。原因是长尾分布里大部分工作量都在少数大作业上，小作业插队花不了多少时间（Bansal 与 Harchol-Balter 2001 年证明了重尾分布下的这个结论）。SRPT 的代价在”首次等待”：有的大作业要等 88 个单位才第一次被运行。

2.4 轮转与时间片

SRPT 要知道每个作业还要运行多久。不知道的时候，最朴素的公平做法是轮转（RR，round robin）：每个作业每次最多运行一个时间片（quantum），没做完就排到队尾。它让短作业很快完成，对大小作业一视同仁（双峰分布时小、大作业的 slowdown 几乎一样）。

时间片多大合适？代码 02 演示 3（长尾作业，负载 0.8，每次切换花 0.005 个单位）：

时间片太小，17% 的时间花在切换上，有效负载从 0.8 涨到接近 1，排队急剧变长——开销本身把系统推向过载。时间片太大，轮转退化成 FCFS。原则是：时间片要远大于切换开销，又要比大多数作业短。

还有一个有意思的现象：指数分布下，轮转的平均响应（4.58）和 FCFS（4.62）几乎相等。这是排队论里的一个经典结论（M/M/1 下，FCFS 和”处理器共享”的平均响应时间相同），P4 会再遇到它。

2.5 多级反馈队列：不知道大小，就看已经运行了多久

多级反馈队列（MLFQ，multi-level feedback queue）是操作系统里最常用的调度思想之一（OSTEP 用一整章讲它）。规则：

1. 有多级队列，优先级从高到低；总是运行最高的非空级。
2. 新作业进最高级。
3. 一个作业在某一级用完了这一级的时间配额，就降一级（我们的实现里，第 $i$ 级的配额是首级时间片 × $2^i$）。
4. 同一级里先到先服务（OSTEP 的版本是同级轮转，并且每隔一段时间把所有作业提回最高级，防止饥饿；我们的模拟器省略了这一条）。

MLFQ 不需要知道作业有多大：短作业在最高级就跑完了，长作业逐级下沉。它用”已经运行了多久”来估计”还要运行多久”。演示 2 里，长尾和双峰分布下 MLFQ 接近 SRPT（2.49、2.48）。

但在指数分布下，MLFQ（4.61）和 FCFS（4.62）几乎一样。指数分布是无记忆的：一个作业已经运行了多久，完全不说明它还要运行多久，MLFQ 赖以判断的信息不存在。MLFQ 的好处来自”作业大小有长尾”这个事实——而现实中的作业（进程、网络流、LLM 请求的输出长度）恰恰大多是长尾的。

2.6 预测有误差时

另一条路是预测作业大小，再用 SRPT。代码 02 演示 4（长尾，负载 0.8；预测值 = 真实大小 × $e^{N(0, \sigma^2)}$）：

预测越不准，SRPT 越差，但都远好于 FCFS。按平均响应，MLFQ 介于 σ = 1 和 σ = 2 之间；按平均 slowdown，MLFQ 远好于任何有误差的 SRPT——预测一出错，一个短作业被当成长作业，就会排到很后面，它的 slowdown 就很难看。（这一组用了另一个随机种子，FCFS 的平均响应是演示 2 的 3 倍：长尾分布下，少数几个超大作业落在哪里，对结果影响很大。）

这正是 LLM 推理调度的处境：输出长度事先未知。第 2 讲讨论了”预测输出长度、再按预测排序”；第 13 讲的 Autellix 则对 agent 程序用”程序已经消耗的服务”做多级反馈队列（PLAS）——两条路都在这里。

2.7 优先级、饥饿与老化

有时候作业本身有轻重：交互式请求要快，批处理可以等。严格优先级：总是先运行高优先级的（同级先到先服务），高优先级到达时抢占。代码 02 演示 5（交互式负载 0.6 + 批处理负载 0.3）：

严格优先级让交互式作业几乎不用等，代价全部转嫁给批处理。如果高优先级的负载接近 1，低优先级会几乎永远等不到——这就是饥饿。老化（aging）让等得越久的作业优先级越高，给低优先级一个上界；老化越快，批处理越好、交互式越差。多租户的推理服务（第 12 讲）、按 SLO 分级的调度都面对同样的权衡。

2.8 推理系统里的调度

把操作系统的调度对应到推理引擎：

一个重要的不同：推理引擎是批处理的服务器，一步可以同时服务很多请求，“谁先跑”变成了”谁进这一批”，而批的大小又受显存（KV cache）限制——这就把调度和内存管理（§3）绑在了一起。

3. 虚拟内存与分页 · Virtual memory and paging

3.1 为什么要虚拟内存

如果每个程序直接使用物理内存的地址，会有三个麻烦：程序之间可以互相改写对方的内存（没有隔离）；程序必须知道自己被加载到哪里（不能都从地址 0 开始）；内存必须是一大块连续的空间，用一阵子之后就被切得七零八落。虚拟内存给每个进程一个从 0 开始的、连续的、私有的虚拟地址空间，由操作系统和硬件把虚拟地址翻译成物理地址。

3.2 地址翻译与页表

分页（paging）把虚拟地址空间和物理内存都切成固定大小的块：虚拟的叫页（page），物理的叫页框（frame），常见大小 4 KB。页表（page table）记录每个虚拟页在哪个物理页框里。翻译一个地址：

代码 03 演示 1：页大小 4096，页表 {0 → 7, 1 → 3, 2 → 12, 3 → 5}。虚拟地址 5000 在第 1 页、偏移 904，翻译成 3 × 4096 + 904 = 13192；虚拟地址 20000 在第 4 页，页表里没有它——缺页（page fault），由操作系统处理（把这一页从磁盘调进来，或者报错）。

页与页在物理上可以完全不连续。真实的页表是多级的（一个 64 位地址空间的一级页表太大），硬件还用一个叫 TLB 的小缓存记住最近的翻译结果，避免每次访存都查页表。

PagedAttention 的块表就是页表。第 3 讲的 vLLM 把 KV cache 切成固定大小的块（默认每块 16 个 token）：一个序列的 token 在逻辑上连续，物理上存在任意的块里。演示 1 的例子：块表 {0 → 9, 1 → 2, 2 → 31}，第 37 个 token 在逻辑块 37 // 16 = 2 的第 5 个位置，也就是物理块 31 的第 5 个槽位。注意力内核每读一个 token 的 K、V，就做一次这样的”地址翻译”——块就是页，token 就是字节。

3.3 碎片

外部碎片（external fragmentation）：如果每个请求必须分到一段连续的空间，内存用一阵子之后会被切成很多小空闲段；空闲的总量够，却没有一段连续的够大，请求还是失败。连续分配器选空闲段的常见策略：首次适应（第一个够大的）、最佳适应（够大的里面最小的）、最差适应（最大的）。

内部碎片（internal fragmentation）：分页时，一个请求占整数个页，最后一页可能填不满，这部分浪费在”已分配的空间内部”。

代码 03 演示 2（容量 20,000 单位，请求大小对数正态、平均 50，大小在分配时已知）：

这张表有两个和”分页处处更好”的直觉不太一样的地方：

• 大小事先已知、请求又不大时，外部碎片的危害有限：首次适应只有 1.2% 的请求因为碎片被拒绝。最差适应反而最差，因为它总把大段切碎。
• 分页消灭了外部碎片，但页大小 16 时内部碎片（约 14%）反而让它比首次适应拒绝得更多；页大小 1 时两种碎片都没有，才全面更好。

推理里真正要命的是最后一行：不知道一个请求最终有多大。KV cache 随生成一个 token 一个 token地增长，输出长度事先未知；连续分配只能按上限预留，按 400 预留时 86% 的请求被拒绝，真正存了数据的只有 12%。分页按需一页一页地分，这才是 PagedAttention 的主要收益：第 3 讲里，它让同一块显存同时服务的请求数提高了好几倍。

3.4 页多大合适

代码 03 演示 3（同一串请求）：

页越大，最后一页浪费得越多；页越小，页表项越多（页表占内存、翻译更慢、要读的元数据更多）。操作系统的页通常是 4 KB，再配上 2 MB、1 GB 的”大页”给大块连续的数据用。推理引擎里也是同样的取舍：vLLM 默认每块 16 个 token；SGLang 的基数树缓存可以做到每页 1 个 token（前缀共享的粒度最细）；注意力内核则希望块大一些，好让每次读取连续、合并（P1 §3.3）。

3.5 写时复制

Unix 的 fork 创建一个子进程，子进程的内存最初和父进程一模一样。朴素的做法是把全部内存复制一份；写时复制（copy-on-write，COW）只复制页表，让父子进程共享所有页框（引用计数 +1），并把这些页标成只读；谁要写一个被共享的页，才为它复制一份私有的。

代码 03 演示 4：并行采样 8 个回答，共享一段 1,024 个 token 的提示（每页 16 个 token，共 64 页），每个回答再生成 200 个 token。朴素做法每个回答复制一整份提示，一共 672 页；写时复制只复制被写的最后一页（每个回答 1 页），一共 168 页，差 4 倍。PagedAttention 正是用这个办法实现并行采样和束搜索（第 3 讲）；前缀缓存则让不同的请求共享同一段系统提示的 KV。

3.6 换出、按需调页与颠簸

物理内存不够时，操作系统把暂时不用的页换出（swap out）到磁盘，用到时再换入；更进一步，程序启动时一页都不加载，用到哪页才调哪页（按需调页，demand paging）。只要程序正在用的那部分（工作集，working set）放得下，这就很有效。

放不下会怎样？代码 03 演示 5：工作集 200 页、LRU 置换，内存访问 100 ns，缺页时从 SSD 调页 100 µs（假设值）：

物理内存比工作集小时，几乎每次访问都缺页，系统忙着换页、几乎不做正事——这叫颠簸（thrashing）。缺页率在工作集附近有一个陡峭的拐点。即使内存足够，阶段切换和零星的随机访问仍然造成约 5% 的缺页，而每次缺页的代价是访存的 1000 倍，所以平均访问时间仍然慢几十倍：缺页的代价和命中的代价差得越多，越需要把缺页率压得非常低（练习 7）。

推理系统里的对应物：

• KV cache 放不下时，把被抢占的请求的 KV 换出到 CPU 内存，稍后换回（第 3 讲比较了换出和重算）；
• 分层的 KV 存储：GPU 显存 → CPU 内存 → SSD → 远端（第 9 讲的 Mooncake、Strata）；
• MemGPT 把 LLM 的上下文窗口当”内存”、外部存储当”磁盘”，让模型自己换页（第 14 讲）；
• 多个模型共享一块 GPU 时，按需加载权重和 KV、像”内存气球”一样伸缩显存（第 12 讲的 Prism）。

它们都要避免颠簸：放进 GPU 的必须是正在用的那部分。

4. 缓存与淘汰 · Caching and eviction

4.1 局部性与命中率

缓存之所以有用，是因为程序的访问有局部性：

• 时间局部性：刚访问过的东西，很可能马上又被访问（循环里的变量、热门的网页、所有请求共用的系统提示）。
• 空间局部性：访问了一个地址，很可能马上访问它旁边的地址（数组、连续存放的 KV）。

缓存的效果用命中率衡量。平均访问代价 = 命中率 × 命中代价 + (1 − 命中率) × 不命中代价。不命中的代价往往是命中的几十到几千倍，所以平均代价几乎完全由不命中率决定：代码 04 演示 1 里，命中代价 1、不命中代价 100 时，缓存 100 的 LRU（命中 37.9%）平均代价 62.5，ARC（45.8%）54.7，最优（62.7%）38.0。

缓存满了，新来的东西要放进去，就得扔掉一个——扔谁，就是淘汰策略（eviction / replacement policy）。

4.2 几种淘汰策略

代码 04 演示 1（Zipf 访问：第 $r$ 热门的 key 被访问的概率 ∝ $r^{-0.8}$，1,000 个 key，3 万次访问）：

Zipf 访问下热门程度稳定，LFU 和 ARC 最好；所有策略离 Belady 最优都还有一段距离。Belady 最优（1966）的价值在于告诉我们上限在哪里：如果某个策略已经很接近它，再换策略也没多大用，要么加缓存，要么改变访问模式。

4.3 每种策略都有崩溃的时候

代码 04 演示 2（缓存 100）：

• 循环访问一个比缓存稍大的集合：LRU 每次淘汰的恰好是马上要用的那个，命中率 0；其他几种在线策略也都是 0。（反复扫描一个比缓存稍大的数据集就是这样。）
• 一次性扫描会把热点挤出缓存：LRU 让只用一次的 key 挤掉热点；LFU 和 ARC 记得”谁被用过多次”。推理里的对应物：一批只会用一次的长文档请求，把大家共用的系统提示从前缀缓存里挤出去。
• 热点漂移时，LFU 抱着过时的计数不放（30.9%）；LRU 跟得上变化；ARC 自适应，在扫描和漂移两种模式下都接近或超过最好的那个。

没有一种策略处处最好。选策略之前要先看访问模式；推理系统里不同的缓存（前缀缓存、模型权重的缓存、多层 KV 存储）访问模式也各不相同。

4.4 Belady 异常

直觉上，缓存越大，命中率越高。代码 04 演示 3 用一个经典的访问序列 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 说明 FIFO 不满足这一点：

FIFO 用 4 个位置反而比 3 个多不命中一次（Belady、Nelson、Shedler 1969 年发现）。LRU 和 OPT 不会这样：它们是栈算法——大缓存里的内容永远包含小缓存里的内容，所以命中率随缓存大小单调不降。这个性质让”命中率 vs 缓存大小”的曲线可以一次模拟全部算出来，也让我们可以放心地说”加缓存不会变差”。

4.5 推理系统里的缓存

• 前缀缓存（第 3 讲）：缓存的是 KV，key 是 token 前缀。SGLang 用 LRU 淘汰基数树的叶子（§5）；第 3 讲还讨论了”最长前缀优先”的调度怎样提高命中率。
• 分层 KV 存储（第 9 讲）：GPU 显存 → CPU 内存 → SSD，每一层都是下一层的缓存；淘汰策略要考虑”重算一段 KV 要多少 FLOPs”和”从下一层读回来要多久”。
• 混合模型的状态缓存（第 10 讲的 Marconi）：不同条目的大小和重算代价差别很大，淘汰时要按”每字节省下多少 FLOPs”来权衡，而不是只看最近。
• 集群级的缓存感知路由（第 11 讲）：把请求送到已经缓存了它的前缀的那台机器——在多个缓存之间提高整体的命中率。
• 模型权重的缓存（第 12 讲）：多模型服务里，哪些模型常驻显存、哪些按需加载，本质也是缓存淘汰。

5. 前缀树、基数树与引用计数 · Tries, radix trees, and reference counting

5.1 前缀树

很多推理请求的开头是一样的：同一个应用的系统提示、同一组 few-shot 例子、多轮对话里前面的全部历史。要找出”这个新请求的开头，有多长已经算过了”，最自然的数据结构是前缀树（trie）：每个节点代表一个 token，从根到某个节点的路径就是一个前缀；共享前缀的序列共享路径。

5.2 基数树：把单链压成一个节点

前缀树里有很多”只有一个孩子”的长链（一段系统提示就是一条几百个节点的链）。基数树（radix tree，也叫压缩前缀树、PATRICIA 树）把这样的链压成一个节点，每个节点存一段 token。

插入一个序列时，从根往下匹配；如果在某个节点的中间分叉，就把这个节点分裂成两段。代码 05 演示 1 用单词当 token 插入四句话：

└ [you are a]  长度 3
  └ [careful reviewer . check this code .]  长度 7
  └ [helpful assistant .]  长度 3
    └ [explain lru caching .]  长度 4
    └ [what is]  长度 2
      └ [a radix tree ?]  长度 4
      └ [paging ?]  长度 2

第 2 句和第 1 句共享”you are a helpful assistant . what is”，插入时原来的节点从分叉处分裂；第 4 句只共享”you are a”，又在更前面分裂了一次。四句话一共 42 个 token，去重后 25 个，基数树只用 7 个节点。查询”you are a helpful assistant . what is caching ?”时从根往下走，能走 8 个 token——这 8 个 token 的 KV 已经在缓存里，prefill 可以跳过它们。

代码 05 演示 2 用一批合成的多轮对话（所有请求共享一段系统提示，4 个应用各有一段 few-shot 例子，每段对话 1–3 轮）：402 个请求如果各存一份要 53,632 个 token；共享前缀后只要 13,088 个（差 4.1 倍）；基数树只用 407 个节点，平均每个节点 32 个 token。节点少，意味着匹配时走的步数少、要管理的元数据少。

5.3 引用计数：正在用的不能删

缓存的空间有限，要淘汰。但有两条规则：

1. 正在运行的请求用到的节点不能删：它每一步 decode 都要读全部历史的 KV。所以每个运行中的请求给它路径上的每个节点引用计数 +1，结束时 −1；引用计数不为 0 的节点不能删。这和操作系统里”有进程映射着的页框不能释放”、写时复制的引用计数是一回事。
2. 只能从叶子删起：内部节点是它所有后代的前缀，删掉它，后代就再也匹配不上了（它们的 KV 也就白存了）。

代码 05 演示 3：缓存里 2,080 个 token；5 个请求正在运行，锁住它们的路径后，最多只能腾出 1,584 个；要求”尽可能多地腾”，实际腾出 1,584 个，5 个运行中的请求的前缀都还完整地在缓存里；它们结束、解锁以后，剩下的 496 个也可以淘汰了。

SGLang 的 RadixAttention（第 3 讲）就是这样做的：基数树的每个节点对应一段 KV cache，正在运行的请求锁住自己的路径，空间不够时用 LRU 递归地淘汰没人用的叶子。“最久没被匹配到的叶子先走”：被所有请求反复访问的系统提示总是位于内部、总在被访问，不会被淘汰；一次性的长问题、早就结束的对话最先被淘汰。

5.4 前缀缓存 vs 整段匹配

代码 05 演示 4（400 段多轮对话，808 个请求）：

（token 命中率。）整段匹配的缓存一次都不命中：多轮对话的每一轮提示都比上一轮长，和任何旧提示都不完全相同。前缀缓存只要求开头相同；容量只有 500 个 token 时也能命中 63%，因为被所有请求反复访问的系统提示和 few-shot 例子一直留在缓存里。容量够大时命中率到 89%，剩下的几乎全是每一轮新问的问题，本来就不可能命中。这就是第 3 讲 RadixAttention、第 9 讲 Mooncake 的分层 KV 缓存、第 11 讲按前缀路由的出发点。

6. 与推理系统的联系 · Connections to inference systems

有系统背景的读者可以只读这一节。

7. 小结 · Summary

1. 进程有自己的地址空间，线程共享进程的内存；上下文切换要花几微秒到几十微秒。Python 的 GIL 让纯 Python 的计算无法用多线程并行，所以推理引擎把 CPU 上的工作拆成多个进程，用 IPC 传打包的消息。
2. 调度：FCFS 有护航效应；SRPT 让平均响应时间最短，在长尾分布下也不怎么欺负大作业；不知道作业大小时，MLFQ 用”已经运行了多久”代替”还要运行多久”，只在作业大小有长尾时有效；严格优先级会饿死低优先级，老化给出上界。作业大小的方差决定排队。
3. 虚拟内存：页表把连续的虚拟地址映射到不连续的物理页框；PagedAttention 的块表就是页表。连续分配有外部碎片，分页有内部碎片；推理里分页的主要收益是按需分配——不知道请求最终多大时，按上限预留会浪费大部分显存。写时复制让多个序列共享 KV；工作集放不下时会颠簸。
4. 缓存：平均代价几乎完全由不命中率决定；LRU、LFU、ARC 各有擅长和崩溃的访问模式；Belady 最优给出上限；FIFO 有 Belady 异常，LRU 这类栈算法没有。
5. 基数树 + 引用计数 + LRU 叶子淘汰就是 RadixAttention：共享前缀只存一份；正在用的不能删；只从叶子删起。

8. 常见误区 · Common pitfalls

• “多开几个线程就能让 Python 代码更快”。纯 Python 的计算受 GIL 限制；要并行得用多进程（或者把计算交给会释放 GIL 的库）。
• “轮转最公平，所以最好”。轮转对大小作业一视同仁，但平均响应时间比 SRPT 差得多；时间片太小时切换开销还会把系统推向过载。
• “SRPT 会饿死大作业”。在长尾分布下，大作业在 SRPT 下的 slowdown 甚至比 FCFS 和轮转还低；它的代价主要是部分大作业的首次等待变长。
• “MLFQ 总能逼近 SRPT”。只有作业大小有长尾、“运行得越久的还要运行越久”时才成立；指数分布下它和 FCFS 一样。
• “分页的好处是消灭外部碎片”。对推理来说，更大的好处是按需分配：KV 随生成增长，不知道最终多大；按上限预留才是浪费的大头。
• “页越小越好”。页小，内部碎片少，但页表项多、元数据多、访存不连续；页大则相反。
• “LRU 总是不错”。循环访问比缓存稍大的集合时 LRU 一次都不命中；一次性的扫描会把热点挤出去。
• “缓存越大，命中率一定越高”。对 FIFO 不一定（Belady 异常）；对 LRU 这类栈算法才成立。
• “前缀缓存可以随便淘汰任何节点”。正在用的不能删，内部节点不能先于它的后代删。

9. 练习 · Exercises

练习 1（手算调度）。四个作业同时到达，大小分别是 8、4、2、1（按这个顺序排队）。分别用 FCFS、SJF、轮转（时间片 1）调度，平均响应时间各是多少？

FCFS：完成时刻 8、12、14、15，平均 12.25。SJF：1、3、7、15，平均 6.5。轮转（时间片 1，按 8、4、2、1 的顺序轮）：大小为 1 的作业在第 4 个单位结束，2 在第 7 个，4 在第 11 个，8 在第 15 个，平均 9.25（可以用 simulate 验证）。

练习 2（为什么 MLFQ 需要”定期提升”）。OSTEP 的 MLFQ 有一条规则：每隔一段时间，把所有作业都提回最高级。如果没有这条规则，会发生什么？我们的模拟器没有实现它，演示 2 里哪一列能看出后果？

长作业一旦沉到最低级，只要高级别一直有新作业到达，它就一直得不到运行——饥饿。另外，一个作业的行为可能变化（例如先算很久、后来变成交互式的），没有提升它就回不到高优先级。演示 2 里 MLFQ 的”大作业 slowdown”（长尾时 5.41）比 SRPT（2.11）和轮转（3.38）都高，就是大作业被压在低级别的后果。

练习 3（块表有多大）。一个 128K token 的序列，块大小 16 时块表有多少项？每项 4 字节，批 256 时一共多少？块大小 1 时呢？为什么注意力内核关心这个数？

块大小 16：131,072 / 16 = 8,192 项，32 KB；批 256 时 8 MB。块大小 1：131,072 项、512 KB，批 256 时 128 MB。注意力内核每一步都要读块表来找每个 token 的 KV 在哪里；块越小，要读的元数据越多、访存越不连续（P1 §3.3 的合并访存）。这就是页大小的取舍在推理里的样子。

练习 4（束搜索的写时复制）。束宽 4，提示 1,000 个 token，每块 16 个 token。每一步，4 个候选各生成 1 个 token。如果每次分叉都整份复制 KV，和用写时复制相比，一步大约多复制多少块？

提示占 ⌈1000/16⌉ = 63 块。整份复制时，每个新候选（除了直接接手父候选的那个）都要复制约 63 块，一步最多 3 × 63 ≈ 189 块（随着生成变长还会更多）；写时复制只需要在写入时复制被共享的最后一块，一步最多 3 块。前置讲 P2 代码 04 演示 5 的束搜索统计了朴素复制的字节数。

练习 5（Belady 异常与栈算法）。用 os_lab 验证：访问序列 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，缓存 3 个位置时，OPT 不命中几次？为什么 LRU 不会出现 Belady 异常？

len(seq) - cache_opt(seq, 3) = 7 次。LRU 是栈算法：大小为 $k$ 的 LRU 缓存里的内容，永远是大小为 $k+1$ 的 LRU 缓存内容的子集（都是”最近访问过的 $k$ 个”和”最近访问过的 $k+1$ 个”），所以在小缓存里命中的访问，在大缓存里一定也命中。FIFO 的内容取决于进入的先后，没有这种包含关系。

练习 6（前缀匹配）。基数树里已经有”you are a helpful assistant . what is paging ?”和”you are a careful reviewer .”。新请求”you are a helpful assistant . explain paging .”能跳过多少个 token 的 prefill？插入它以后树会怎样变化？

共享”you are a helpful assistant .”，命中 6 个 token。插入时，原来的”helpful assistant . what is paging ?”节点在”.”之后分裂成”helpful assistant .”和”what is paging ?”，新的”explain paging .”作为”helpful assistant .”的第二个孩子。

练习 7（缺页率要多低）。内存访问 100 ns，缺页的代价 100 µs。要让平均访问时间不超过全在内存时的 2 倍，缺页率最多多少？如果”缺页”的代价是从 CPU 内存经 PCIe 把一块 KV 读回 GPU（假设 10 µs），呢？

$(1 - f) \times 100\ \text{ns} + f \times 100\ \mu\text{s} \le 200\ \text{ns}$，得 $f \le 100 / 99{,}900 \approx 0.1\%$。代价 10 µs 时 $f \le 100 / 9{,}900 \approx 1\%$。缺页代价越大，对命中率的要求越苛刻——这就是分层 KV 存储（第 9 讲）要么让慢层的读取和计算重叠、要么只把”肯定不会马上用”的数据放下去的原因。

10. 延伸阅读 · Further reading

• R. Arpaci-Dusseau, A. Arpaci-Dusseau. Operating Systems: Three Easy Pieces（免费在线）。推荐章节：Scheduling: Introduction、Multi-Level Feedback Queue、Paging: Introduction、TLBs、Swapping: Policies。
• M. Harchol-Balter. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press, 2013。调度与排队论（P4 的主要参考书）。
• N. Bansal, M. Harchol-Balter. Analysis of SRPT Scheduling: Investigating Unfairness. SIGMETRICS 2001。
• L. Belady. A Study of Replacement Algorithms for a Virtual-Storage Computer. IBM Systems Journal, 1966。
• N. Megiddo, D. Modha. ARC: A Self-Tuning, Low Overhead Replacement Cache. FAST 2003。
• W. Kwon et al. Efficient Memory Management for Large Language Model Serving with PagedAttention. SOSP 2023（第 3 讲）：§4 明确地把设计对应到操作系统的分页。
• L. Zheng et al. SGLang: Efficient Execution of Structured Language Model Programs. 2024（第 3 讲）：RadixAttention 的基数树、引用计数与 LRU 淘汰。

11. 下一篇 · Next

前置讲 P4：排队论与性能评估。§2 反复看到”方差决定排队""负载接近 1 时等待急剧变长""轮转和 FCFS 的平均响应一样”——P4 把这些变成精确的结论：Little 定律、M/M/1 与 M/G/1（Pollaczek–Khinchine 公式）、批服务队列，以及怎样做可信的性能实验：开环与闭环负载、预热与稳态、分位数与置信区间、SLO 达成率与 goodput。