Month 3 · 调度器与 Continuous Batching

这是把"显存优化"变成"吞吐优化"的关键一步。

Month 2 学完后你已经知道显存怎么省。但 GPU 算力本身怎么榨干？ 传统做法 batching 是 "等到 32 个请求凑齐再一起跑"——延迟高、长短不一时浪费。 Orca (OSDI'22) 和 vLLM 的答案叫 continuous batching：每一步都重组 batch。 这一节学这套机制。读完你应该能回答： "为什么 LLM serving 不用 Linux CFS？"、 "prefill 来了为什么 decode 会卡？"、 "显存满了 vLLM 怎么决定抢谁？"。

01背景 · 三种 batching 策略全景

在拆解 vLLM 之前，先把"batching"这个词在 LLM serving 里的三个不同含义分清。 这一节是 OS 调度章节通常没有的，因为对 OS 而言"批处理"只是历史名词。 但对 LLM 而言，它是设计空间的主轴。

① Static batching · 古早做法

给定 batch size B，等够 B 个请求就一起跑，跑完整批后切下一批。 T5/BERT 时代的 fastapi + ONNX serving 几乎都这么干。它的好处是 kernel 简单——每一步整个 batch 都做同样形状的矩阵乘。但对 LLM 致命：

• 请求长度方差大（min_len << max_len），最长的拖死全 batch。
• 新请求要等下一批，TTFT 上涨 O(batch_make_up_time + slowest_request_time)。

② Padding-based batching · 折中

同一个 batch 里允许长度不同，padding 到最长那条。kernel 通过 attention mask 忽略 padding 位置。 这是 HuggingFace generate(batch=…) 的默认。问题：

• padding 位上仍然要算（attention mask 只屏蔽结果，不省 FLOPs）。如果 batch 内长度方差 50%，一半算力浪费。
• 仍然是"等齐再跑"——长 prompt 和短 prompt 不能错峰。

③ Continuous batching · Orca 提出，vLLM 推广

核心动作：把"batch"从"一组请求"重定义为"一组 token 计算位"。 每个 step 只算"现在该算的那一个 token"，不同请求处于不同阶段（有的 prefill、有的 decode），但凑成一个 batch 一起 forward。 完成的请求当场离开 batch、新请求当场加入。

02Prefill vs Decode · 微观分析

LLM 推理分两阶段，节奏天差地别。读 scheduler 前必须先理解这个—— 所有 batching 策略的复杂性，根源就在 prefill 和 decode 的"性格"完全不一样。

Roofline 视角 · 用 arithmetic intensity 量化

Arithmetic intensity（AI）= FLOPs / bytes，单位 FLOP/B。 当 AI 远高于硬件的"ridge point"（compute 峰值 / 带宽，A100 BF16 ≈ 312e12 / 1.5e12 ≈ 208 FLOP/B）， 计算阶段是 compute-bound；远低于则是 memory-bound。 对 Transformer 的 attention + FFN 做近似计算：

# Llama 3.1 8B, hidden=4096, n_layer=32, n_head=32, head_dim=128
# 一个 token 走全部层的 FLOPs ≈ 2 · params ≈ 2 · 8e9 = 16 GFLOPs  (per token)
# Decode 一步要读：weights(16 GB BF16) + KV(K + V, 之前所有 tokens)
# Prefill N tokens 要读：weights 一次 (amortized) + 计算 ~N · 16 GFLOPs

# === Decode（生成第 (T+1) 个 token，已经累计 T 个 token）===
flops_decode  = 16e9                              # FLOPs / token
bytes_decode  = 16e9                              # weight bytes (BF16, 8B params · 2 B/param)
              + 2 · 32 · 32 · 128 · T · 2         # KV bytes: 2(K,V) · n_layer · n_head · head_dim · T · 2 B
              = 16e9 + 524288 · T                 # ≈ 16 GB + 0.5 MB per past token
AI_decode(T=1024)   = 16e9 / (16e9 + 5e8) ≈ 0.97 FLOP/B   # 强烈 memory-bound
AI_decode(T=4096)   = 16e9 / (16e9 + 2e9) ≈ 0.89 FLOP/B   # 略低

# === Prefill（处理 N=1024 个 prompt token，一次性算完）===
flops_prefill = 1024 · 16e9 ≈ 1.6e13            # 16 TFLOPs
bytes_prefill ≈ 16e9 + 524288 · 512             # weights + 中位 KV ≈ 16.3 GB
AI_prefill(N=1024) ≈ 1.6e13 / 1.6e10 ≈ 1000 FLOP/B  # compute-bound

两个数对比：

• Decode AI ≈ 1 FLOP/B。A100 的 ridge point 是 208——AI 比它低两个数量级，意味着 ~99.5% 的算力是闲的。每步真正花的时间是"把 16 GB 权重从 HBM 搬到 SM"。增大 batch 几乎不影响时间，但能多算 batch_size 倍——所以 decode 是 batching 的"主战场"。
• Prefill AI ≈ 1000 FLOP/B。远高于 ridge——算力已经满了。增大 batch 不会变快，反而可能拖累。

把两类混 batch 的核心后果：prefill 一来，整个 step 的时间被它"卡住"—— 即使 31 个 decode 请求也得等 prefill 完成。你为了照顾一个"重活"，让 31 个"轻活"也卡住。 这就是 Sarathi-Serve (OSDI'24) 要解的问题（chunked prefill，本章第 11 节展开）。

03OS 调度器的复习

OS 的调度器有一段几十年的历史。把它们梳理一遍，再看 vLLM 的选择就清楚多了。 这一节不深入 OSTEP 的细节，只把每个算法的核心 idea + 为什么这么设计讲清。

这套历史揭示的两个根本 trade-off

• 公平 vs 吞吐。SJF 给最佳平均等待时间，但牺牲了"先到的优势"，长任务可能饿死。CFS 给完全公平，但牺牲了 SJF 的最优性。没有免费的 lunch。
• 响应 vs 切换开销。Quantum 短 → 响应快，但 context switch 占比上升；quantum 长 → 反之。OS 的"~10ms quantum"是几十年实测的甜点。

记住这两条，下一节看 vLLM 的选择就豁然开朗。

04vLLM 的调度选择 · 为什么不用 CFS

OS 进程调度跟 LLM 请求调度结构上同构——都是"有限资源 + 多并发用户 + 时间分片"——但具体策略 vLLM 选了不同的解。把差别一项一项拆开：

① 切换代价 · 关键差异

OS context switch 要做：保存寄存器、刷 TLB、换页表 root、可能 L1/L2 cache miss。 Linux 测得 ~3 µs（intel x86），是 quantum 的 0.05%（10ms quantum），可观但可承受。 这就是为什么 OS quantum 不能太短——切换占比会失控。

vLLM 的"context switch"是什么？答案：什么都不用做。 所有"上下文"（KV cache、block table、token 位置）都在 metadata 数据结构里，每 step 都重新打包给 kernel。 "换出一个请求 + 换入另一个" = 在 scheduler 的 Python list 里删一行加一行。开销 < 1 µs。

结论：vLLM 可以每 step 都重排，没有"切换 vs 不切换"的 trade-off。 这就是 continuous batching 能 work 的另一半基础（第一半是 decode memory-bound）。

② 请求长度方差 · 决定不能用 CFS

CFS 的核心假设："每个进程都想要等量 CPU"。它把 100ms 平均分给 100 个进程，每个拿 1ms。 这在桌面 OS 是合理的（你不希望浏览器卡死）。 但 LLM 请求长度方差极大：

• "Hi" → 5 token prompt + 10 token output = 15 步
• "帮我把这份合同（10 页）翻译成英文" → 4000 prompt + 4000 output = 8000 步

把这两个请求"公平"地交错跑（CFS 思路），结果是：

1. 短请求多等 ~1000 步才能完成（被长请求公平地穿插）。
2. 长请求也没多省时间（它本来就要 8000 步）。
3. 每 step 切换 batch 成员 → KV 频繁分配释放 → 显存碎片化 → 命中率下降。

对比 FCFS：短请求几乎不等就出去了，长请求按到达顺序"占住"slot 但不影响后来的（continuous batching 允许新短请求复用其他 slot）。 请求长度方差大时，FCFS 几乎没有公平性损失——因为长请求本来就该长。

③ 工作量"颗粒度"较均匀

这条容易被忽略：在 LLM serving 里，一个 token step 的每个请求的算力消耗几乎相等（decode 模式下）。 不像 OS 里"进程 A 在做密集 FFT、进程 B 在等 I/O"那种异质负载。所以 vLLM 不需要 CFS 那种"用 vruntime 衡量真实 CPU 使用量"的复杂记账—— "用了几个 step" 就等于 "用了几份算力"，简单计数足够。

④ Token budget = LLM 的 quantum

OS 的 quantum 是时间（ms）；vLLM 的"quantum"是 token budget： "这一步最多算 max_num_batched_tokens 个 token（包括所有 prefill + 所有 decode）"。 这是个比时间更直接的资源单位——因为每个 token 的算力消耗近乎常数。 配上 KV 余量，就够支撑整个调度决策。下一节详细看。

05Continuous Batching 实现的 4 个子问题

"每步重组 batch" 一句话听着简单，实现要同时回答 4 个互相耦合的问题。 这 4 个问题分别对应 vLLM 代码的 4 个子系统：

这 4 个问题耦合在一起——比如 token budget 决定了 ② 能放多少新 prefill，prefill 多了 ③ 的显存压力就大。 这就是为什么 scheduler 不是"挑请求"那么简单。下面几节都是在拆这个耦合。

06vLLM Scheduler 状态机

每个请求在 vLLM 内部有 4 个状态。这是 Linux task_struct.state 的 LLM 版。

转移条件 · 一句话总结

Worked example · 5 个请求 10 个 ticks

假设 token budget = 8、KV capacity = 6 blocks（每 block 16 tokens）。5 个请求：

R1: prompt=16, output=32     # 1 block prefill, +2 blocks decode
R2: prompt=8,  output=8      # 0.5 block prefill, +0.5 decode → 1 block total
R3: prompt=32, output=16     # 2 blocks prefill, +1 decode
R4: prompt=8,  output=64     # 0.5 prefill, +4 decode
R5: prompt=16, output=8      # 1 prefill, +0.5 decode

注意 tick 10 的 preempt 决策：选 R4 是因为它是 running 中最年轻的（最近加入），这是 vLLM 默认策略—— 理由是"已生成最少 token，重 prefill 代价最小"。

07Token Budget 与 KV Budget · 双约束

每个 step 上，scheduler 必须同时满足两个独立的资源约束。同时满足—— 单看其中一个会得出错误的调度决策。

两个 budget 怎么互动

看一个具体情景：

configuration: max_num_batched_tokens = 8192, kv_blocks_total = 1000, block_size = 16
state: running = [R1: 500 toks, R2: 1500 toks, R3: 300 toks]
       KV used = ceil(500/16) + ceil(1500/16) + ceil(300/16) = 32 + 94 + 19 = 145 blocks
       budget for new prefills this step = 8192 - 3 (decode tokens) ≈ 8189

waiting = [R4: 5000 prompt, R5: 1000 prompt, R6: 200 prompt]

scheduler 决定：
 - 看 R4: 5000 tokens 能塞吗？token budget OK (5000 < 8189)。
          KV: 需要 ceil(5000/16) = 313 blocks。当前 free = 1000 - 145 = 855。OK。
          → admit R4，budget 剩 3189，KV 剩 542
 - 看 R5: 1000 tokens。budget OK。KV 需要 63 blocks，剩 479。
          → admit R5
 - 看 R6: 200 tokens。budget = 1989 OK。KV 需要 13 blocks。
          → admit R6
 - waiting 空，本 step admit 3 个，全部进入 RUNNING。

但如果 KV 不够呢？比如 R4 进来发现需要 800 blocks 但只剩 600：

1. 简单情况：跳过 R4，看 waiting 后面的小请求 R5 能否塞下。这是 head-of-line blocking 的代价——vLLM 默认 strict FCFS，不跳过；但有些版本允许 "skip large requests"。
2. 更激进：preempt running 里的低优先级请求，腾出 KV。但只有在 R4 紧急（高 priority）时才做。

实际 vLLM 默认值

• max_num_batched_tokens：默认会被 vLLM 根据模型与显存自适应；典型 2048-16384。
• max_num_seqs：默认 256。绝大多数情况下不是 bottleneck（KV 先吃光）。
• gpu_memory_utilization：默认 0.9，间接决定 kv_blocks_total。

调参的常识：

• TTFT 太高 → 减 max_num_batched_tokens（小 batch 让新请求更快被 admit）。
• 吞吐低且 GPU 利用率低 → 加 max_num_batched_tokens。
• preempt 频繁 → 减 max_num_seqs 或加 GPU 内存利用率。

08Preemption · 两种实现深读

Preemption 是 vLLM 区别于"普通 batching"的最关键动作。OS 的 swap 是页粒度，vLLM 的 preempt 是整请求粒度—— 要么把它的 KV 全释放（recompute），要么全 swap 到 host RAM。

① 触发条件：什么时候 preempt

② Recompute · 默认实现

动作：

1. 把 victim 请求从 running 移到 waiting 头（保留位置优势）。
2. 释放它的所有 KV blocks（kv_cache_manager.free(req_id)）。
3. 重置 num_computed_tokens = 0——下次轮到时从头 prefill。

代价 = 已浪费的 prefill 工作。如果它已经生成了 G 个 token，则 prefill 长度为 prompt_len + G。 公式上：

recompute_cost(req) ≈ flops_per_token · (prompt_len + tokens_generated)
                    ≈ 16e9 · (P + G)   # Llama-8B BF16

具体数：

• 短请求：prompt 200，已生成 10 → 重算 3.4 TFLOPs ≈ 11 ms on A100。可以忍受。
• 长请求：prompt 4000，已生成 100 → 重算 65 TFLOPs ≈ 210 ms。痛苦。

所以 recompute 适合短请求或刚开始 decode 的请求。这也是为什么 vLLM 选"最年轻的 victim"—— 它生成的少，重算便宜。

③ Swap-out · 长请求救星

动作：

1. 把 victim 的所有 physical blocks 内容拷贝到 host RAM 的"swap pool"。
2. 释放 GPU 上的 blocks。
3. victim 状态 → "swapped"，记录它在 swap pool 的位置。
4. 下次调入时：拷回 GPU、重新挂回 block table、状态 → RUNNING。

代价 = PCIe 拷贝时间。每 token 的 KV 大约：

# KV 单 token 大小（BF16, Llama-8B）
kv_bytes_per_token = 2 (K and V) · n_layer · n_head · head_dim · 2 (BF16)
                   = 2 · 32 · 32 · 128 · 2
                   = 524288 bytes ≈ 0.5 MB / token

# A100 PCIe Gen4 x16: ~32 GB/s 实际单向
swap_time(N tokens) = N · 0.5e6 / 32e9   ≈ N · 16 µs / token

# 例子
swap(prompt=4000, generated=100) = 4100 · 16 µs = 65.6 ms
recompute(prompt=4000, generated=100) ≈ 210 ms   # 上面算过

对长请求，swap 比 recompute 快 ~3x。所以 vLLM 提供 preemption_mode='swap' 选项。 默认 recompute 是因为：

• 实现更简单（不需要 swap pool 管理）。
• 不需要 host RAM 预留（云上 GPU 实例 host RAM 也是资源）。
• 大多数 workload 的请求不太长（< 2K tokens）。

09代码深读 · scheduler.py

这是本月的"硬核教材"。不要试图一次看懂全部——按下面 6 个 walk 顺序进。 每个 walk 配合 scheduler.py 一起读， 代码版本以 main 分支为准（截至 2026 年）。

Walk 1 · SchedulerConfig 和构造器

先看 scheduler 的"知识范围"：它需要哪些配置？维护哪些状态？

class SchedulerConfig:
    # 容量上限
    max_num_batched_tokens: int       # 每 step 全 batch token 数上限（"token quantum"）
    max_num_seqs: int                 # 同时 RUNNING 的请求数上限
    max_model_len: int                # 单请求最大长度（prompt + output）

    # 调度策略
    policy: str = "fcfs"              # "fcfs" | "priority"
    enable_chunked_prefill: bool      # 是否切分大 prefill
    long_prefill_token_threshold: int # 多长才算"长" prefill

    # Preempt 策略
    preemption_mode: str = "recompute"  # "recompute" | "swap"

class Scheduler:
    def __init__(self, vllm_config, kv_cache_config):
        self.scheduler_config = vllm_config.scheduler_config
        self.cache_config = vllm_config.cache_config
        self.kv_cache_manager = KVCacheManager(...)   # 内存子系统 (M2)

        # 三个状态队列
        self.waiting: deque[Request] = deque()
        self.running: list[Request] = []              # 顺序很重要：pop() 是最新加入
        self.finished_req_ids: set[str] = set()

        # 统计
        self.num_preempted: int = 0
        self.step_count: int = 0

关键观察：

• waiting 是 deque，FIFO，popleft() 拿队首。
• running 是 list，.pop() 拿队尾（最新加入）——这是 preempt victim 的来源。
• scheduler 不持有 GPU 资源，它只通过 kv_cache_manager 操作 block 元数据。这个分离是关键架构选择。

Walk 2 · schedule() 顶层结构

scheduler 的入口。每次 engine step 调一次。它的契约：

• 输入：当前 waiting + running 状态（已经在 self 里）。
• 输出：一个 SchedulerOutput，告诉 worker "这一步算什么"。
• 副作用：更新 running / waiting / preempted 状态。

def schedule(self) -> SchedulerOutput:
    """每个 engine step 调一次。决定这一 step 谁参与、各算多少 token。"""
    self.step_count += 1

    # === 阶段 1: 处理已 RUNNING 的请求 ===
    # 给每个继续生成一个 token (decode)，或继续推进 chunked prefill
    scheduled_running_reqs = []
    token_budget = self.max_num_batched_tokens

    req_index = 0
    while req_index < len(self.running):
        request = self.running[req_index]
        num_new_tokens = self._get_num_new_tokens(request, token_budget)
        # decode 通常 num_new_tokens = 1
        # prefill 阶段（chunked） num_new_tokens = chunk_size

        # 分配新 KV blocks（如果跨入新 logical block）
        new_blocks = self.kv_cache_manager.allocate_slots(
            request, num_new_tokens
        )

        if new_blocks is None:        # KV 满了！
            preempted = self._preempt()         # 抢最年轻的
            if preempted is request:           # 抢的是自己 → 这个 req 也不能跑了
                break
            else:
                continue              # 抢了别人 → 再试一次

        scheduled_running_reqs.append((request, num_new_tokens))
        token_budget -= num_new_tokens
        req_index += 1

        if token_budget <= 0:
            break

    # === 阶段 2: 从 WAITING 招新 ===
    scheduled_new_reqs = []
    while self.waiting and token_budget > 0:
        request = self.waiting[0]    # peek
        num_new_tokens = min(
            request.num_prompt_tokens,
            token_budget,
            self.long_prefill_token_threshold if chunked else float('inf'),
        )

        new_blocks = self.kv_cache_manager.allocate_slots(
            request, num_new_tokens
        )
        if new_blocks is None:
            break                    # KV 不够，等下个 step

        self.waiting.popleft()
        self.running.append(request)
        scheduled_new_reqs.append((request, num_new_tokens))
        token_budget -= num_new_tokens

    # === 阶段 3: 打包 SchedulerOutput ===
    return SchedulerOutput(
        scheduled_new_reqs=scheduled_new_reqs,
        scheduled_running_reqs=scheduled_running_reqs,
        num_scheduled_tokens={
            r.req_id: n for r, n in (scheduled_new_reqs + scheduled_running_reqs)
        },
        preempted_req_ids={...},
        finished_req_ids=self.finished_req_ids,
        # 加上 block_table 等元数据给 worker
    )

Walk 3 · 招新循环细节（WAITING → RUNNING）

放大上面阶段 2。两个关键点："先看 prefix cache" + "长 prefill 要 chunk"。

while self.waiting:
    request = self.waiting[0]

    # 关键 1: 先查 prefix cache（来自 M2 章节的 BlockPool）
    # 如果 prompt 前缀已在缓存里，跳过这些 tokens 的 prefill
    cached_block_ids = self.kv_cache_manager.get_cached_blocks(request)
    num_cached_tokens = len(cached_block_ids) · block_size
    num_tokens_to_compute = request.num_prompt_tokens - num_cached_tokens

    # 关键 2: chunked prefill
    if self.enable_chunked_prefill:
        # 把单次能算的 token 数限制在 budget 内
        num_new_tokens = min(num_tokens_to_compute, token_budget,
                             self.scheduler_config.max_num_batched_tokens // 2)
    else:
        # 严格模式：要么一次全算完，要么不开始
        if num_tokens_to_compute > token_budget:
            break
        num_new_tokens = num_tokens_to_compute

    # 关键 3: 分配 KV
    new_blocks = self.kv_cache_manager.allocate_slots(
        request,
        num_tokens=num_new_tokens,
        new_computed_blocks=cached_block_ids,    # 复用 prefix cache
    )
    if new_blocks is None:
        break    # KV 不够，本 step 不再 admit

    # 招进来
    self.waiting.popleft()
    self.running.append(request)
    request.status = RequestStatus.RUNNING
    request.num_computed_tokens = num_cached_tokens + num_new_tokens

    scheduled_new_reqs.append((request, num_new_tokens))
    token_budget -= num_new_tokens

注意：

• "招新" 顺序是严格 FIFO——队首阻塞则整队阻塞（head-of-line blocking）。这是 trade-off：简单且公平到达顺序，代价是大请求挡小请求。
• prefix cache 在这里被用——直接跳过已缓存的 tokens，省 prefill 工作。这是 M2 的成果延伸到 M3。

Walk 4 · 继续循环细节（RUNNING 自循环）

放大阶段 1。注意 chunked prefill 的请求和纯 decode 请求会走不同的分支。

for request in list(self.running):
    if request.num_computed_tokens < request.num_prompt_tokens:
        # 这个请求还在 prefill 阶段（chunked prefill 没算完）
        remaining = request.num_prompt_tokens - request.num_computed_tokens
        num_new_tokens = min(remaining, token_budget, chunk_size)
    else:
        # 纯 decode 模式：每 step 算 1 token
        num_new_tokens = 1

    # 分配 KV（很可能复用现有 block；只在跨 block 边界时申请新）
    new_blocks = self.kv_cache_manager.allocate_slots(
        request, num_new_tokens
    )

    if new_blocks is None:
        # KV 不够：触发 preempt（在另一个函数）
        victim = self._preempt_one()
        if victim is request:
            # 已经把自己抢了，退出循环
            self.running.remove(request)
            break
        else:
            # 抢了别人，腾出了空间，retry
            new_blocks = self.kv_cache_manager.allocate_slots(
                request, num_new_tokens
            )

    request.num_computed_tokens += num_new_tokens
    token_budget -= num_new_tokens
    scheduled_running_reqs.append((request, num_new_tokens))

Walk 5 · _preempt() 实现

def _preempt(self) -> Request | None:
    """从 running 队尾选 victim，释放其 KV，放回 waiting 头。

    返回被抢的 Request；如果 running 空，返回 None。
    """
    if not self.running:
        return None

    # 选 victim: 最年轻 = list 末尾（vLLM 默认；priority 模式下可以排序）
    victim = self.running.pop()      # 注意是 pop()，从尾部

    if self.preemption_mode == "recompute":
        # 1. 释放 KV blocks
        self.kv_cache_manager.free(victim)
        # 2. 重置已算 token 计数
        victim.num_computed_tokens = 0
        victim.status = RequestStatus.WAITING
        # 3. 放回 waiting 队首（保留位置优势）
        self.waiting.appendleft(victim)

    elif self.preemption_mode == "swap":
        # 1. 拷 KV blocks 到 host swap pool
        block_ids = self.kv_cache_manager.get_blocks(victim)
        self.kv_cache_manager.swap_out(block_ids)
        # 2. 状态切到 SWAPPED
        victim.status = RequestStatus.SWAPPED
        self.swapped.append(victim)

    self.num_preempted += 1
    return victim

实际代码里还会处理"prefix cache 命中的共享 block 不能 free"等细节。读时关注：

• "释放 KV" 是引用计数减一，不是真的归零——共享 block 还会被别的请求引用。
• swap 模式下，scheduler 维护 self.swapped 列表；下次 schedule 时先尝试 swap-in 这里的请求。

Walk 6 · SchedulerOutput dataclass

scheduler 跟 worker 的契约——这个数据结构决定了"调度器到底要告诉 worker 多少信息"。

@dataclass
class SchedulerOutput:
    # 谁是 prefill 阶段（首次或继续 chunked）
    scheduled_new_reqs: list[NewRequestData]
    # 谁是 decode 阶段（已 prefill 完成的）
    scheduled_cached_reqs: list[CachedRequestData]

    # 每个 req 这 step 算多少 token (1=decode, N=prefill chunk)
    num_scheduled_tokens: dict[str, int]
    total_num_scheduled_tokens: int

    # KV block 映射（worker 的 attention kernel 要）
    # 这是 M2 PagedAttention 的 block_table，传给 GPU
    # 略：实际通过 KVCacheManager 同步

    # 这 step 哪些请求被抢了（worker 端要清理）
    preempted_req_ids: set[str]

    # 哪些完成了（EOS / max_tokens）
    finished_req_ids: set[str]

    # 哪些被释放（aborted）
    free_encoder_input_ids: list[tuple[str, int]]

    # 可选：长 prefill 状态、speculative decode 状态等

这个结构反映 scheduler 的"输出"哲学：所有必要的工作打包成一个不可变的 step plan， worker 只看这个 plan 干活，不需要回头问 scheduler。这是 Orca-style "iteration-level batching" 的关键 API 设计—— scheduler 和 worker 解耦，可以并行（next step plan 计算与 current step forward 重叠）。

10Chunked Prefill (Sarathi-Serve)

Sarathi-Serve (Agrawal et al., OSDI'24) 是继 PagedAttention 之后 LLM serving 最重要的 paper 之一。 它的 contribution 看似简单：把长 prefill 切成小块，跟 decode 混在同一 step。但效果显著。

问题 · 没 chunked prefill 时的 stall

回顾第 02 节的 AI 图：prefill 是 compute-bound。一个 4000-token prefill 在 A100 上要 ~100 ms。 如果不 chunk，这 100 ms 里 batch 里所有 decode 请求都不能跑下一个 token——它们干等。

vLLM 的实现

核心代码在 schedule() 阶段 1 和阶段 2 共用的逻辑：num_computed_tokens 这个字段。 关键不变量：

• 请求初始 num_computed_tokens = 0。
• 每次被调度算 N tokens，num_computed_tokens += N。
• 当 num_computed_tokens < num_prompt_tokens：仍在 prefill 阶段。
• 当 num_computed_tokens >= num_prompt_tokens：进入 decode（每 step +1）。

Scheduler 看到一个新 admission 时，决定它本 step 算多少（num_new_tokens）：

num_new_tokens = min(
    request.num_prompt_tokens - request.num_computed_tokens,   # 还需要的
    token_budget,                                              # budget 余量
    self.scheduler_config.long_prefill_token_threshold,        # 单次 chunk 上限
)

这样一个 4000 token 的 prefill 会跨 ~8 个 step（chunk=512），每个 step 都为 decode 请求让出 budget。 **TTFT 不会增加**（甚至可能减少——因为 decode 请求不再被堵）。

什么时候 chunked prefill 反而吃亏

chunked 不是免费午餐：

• 小 chunk 增加 kernel launch overhead。每 chunk 都要重新 launch attention kernel，CUDA call 开销固定 ~10 µs。Chunk < 256 token 时这部分相对显著。
• 每 chunk 都要重读全 KV（attention 对 prefill chunk 内的 token 要看之前所有 token 的 K/V）。chunk 数翻倍 → KV 读次数翻倍。
• 小 workload 没必要。如果你 batch 里没 decode 请求等待，chunk 只是徒增延迟。

所以 vLLM 默认有阈值 long_prefill_token_threshold（典型 2048），只对超过它的 prefill 才切。

11Priority + Aging · 高级特性

实际 production 里有时需要"优先级"：付费用户高优、内部测试低优、batch 任务最低。 vLLM 在 v1 提供了 priority hint。

实现机制

请求带个 priority 字段（数字，小的优先）。当 policy = "priority"：

• waiting 队列按 priority 排序（实际用堆），不再是纯 FIFO。
• preempt victim 选最低 priority 的（而非最年轻）。

这立刻引入了 OS 调度里的经典问题：低优先级请求可能饿死。如果高优请求源源不断，低优永远 admit 不上。 解法是 aging：等久了优先级自动提升。

# 概念性代码
def effective_priority(request, now):
    wait_time = now - request.arrival_time
    age_bonus = math.floor(wait_time / aging_period_seconds)
    return request.priority - age_bonus    # 等久了数字变小（更优先）

vLLM 当前的实现细节在演进中——截至 2026 年 v1，aging 是个相对简单的版本， 也是社区频繁讨论的方向（搜 issue label priority 看活跃的 RFC）。

12动手 · 完整 mini-scheduler 代码

本月最重的作业。不要在真 GPU 上——用假数据跑通逻辑。 下面是完整可运行 Python 实现，~200 行，包含模拟器、调度器、指标。

把它存为 mini_sched.py，python mini_sched.py 即可跑。 依赖只有 stdlib + matplotlib（如果不画图，可省）。

"""
mini_sched.py — vLLM-style continuous batching scheduler simulator.
~200 lines. Run: python mini_sched.py
"""
import random
import math
from collections import deque
from dataclasses import dataclass, field
from typing import Literal, Optional

# ===== 1. Data classes =====

@dataclass
class Request:
    id: int
    prompt_len: int
    output_len: int
    arrival_time: float

    # state
    status: Literal["WAITING", "RUNNING", "FINISHED", "PREEMPTED"] = "WAITING"
    num_computed_tokens: int = 0      # how many we've processed (prefill + decode)

    # metrics
    first_token_time: Optional[float] = None
    finish_time: Optional[float] = None
    preempt_count: int = 0

    @property
    def total_tokens(self) -> int:
        return self.prompt_len + self.output_len

    @property
    def is_prefill(self) -> bool:
        return self.num_computed_tokens < self.prompt_len

    @property
    def is_done(self) -> bool:
        return self.num_computed_tokens >= self.total_tokens

    def kv_blocks_needed(self, block_size: int) -> int:
        return math.ceil(self.num_computed_tokens / block_size)


# ===== 2. Scheduler =====

class Scheduler:
    def __init__(
        self,
        kv_capacity_blocks: int = 200,
        block_size: int = 16,
        token_budget: int = 2048,
        long_prefill_chunk: int = 512,
        preempt_mode: str = "recompute",
    ):
        self.kv_capacity = kv_capacity_blocks
        self.block_size = block_size
        self.token_budget = token_budget
        self.chunk_size = long_prefill_chunk
        self.preempt_mode = preempt_mode

        self.waiting: deque[Request] = deque()
        self.running: list[Request] = []
        self.finished: list[Request] = []

        # metric counters
        self.num_preempted = 0
        self.step_count = 0
        self.total_tokens_processed = 0

    def kv_used(self) -> int:
        return sum(r.kv_blocks_needed(self.block_size) for r in self.running)

    def kv_free(self) -> int:
        return self.kv_capacity - self.kv_used()

    def step(self, now: float) -> list[tuple[Request, int]]:
        """Run one scheduling step. Returns [(request, num_tokens_this_step), ...].
        Simulates 'execute' = increment num_computed_tokens for each.
        """
        self.step_count += 1
        scheduled: list[tuple[Request, int]] = []
        budget = self.token_budget

        # === Phase 1: continue running ===
        for req in list(self.running):
            if budget <= 0:
                break
            if req.is_prefill:
                # chunked prefill
                remaining = req.prompt_len - req.num_computed_tokens
                n = min(remaining, budget, self.chunk_size)
            else:
                n = 1  # decode

            # Need new KV block?
            tokens_after = req.num_computed_tokens + n
            blocks_after = math.ceil(tokens_after / self.block_size)
            new_blocks_needed = blocks_after - req.kv_blocks_needed(self.block_size)

            if new_blocks_needed > self.kv_free():
                # preempt one and retry
                victim = self._preempt(exclude=req)
                if victim is None:
                    break
                # retry below
                if new_blocks_needed > self.kv_free():
                    # still not enough → preempt self
                    self._do_preempt(req)
                    continue

            scheduled.append((req, n))
            budget -= n

        # === Phase 2: admit from waiting ===
        while self.waiting and budget > 0:
            req = self.waiting[0]

            # try chunked admit
            n = min(req.prompt_len, budget, self.chunk_size)
            blocks_needed = math.ceil(n / self.block_size)

            if blocks_needed > self.kv_free():
                break  # not enough KV, give up this step

            self.waiting.popleft()
            self.running.append(req)
            req.status = "RUNNING"
            scheduled.append((req, n))
            budget -= n

        # === Phase 3: execute (simulated) ===
        for req, n in scheduled:
            was_prefill = req.is_prefill
            req.num_computed_tokens += n
            self.total_tokens_processed += n

            # record first token time when prefill done
            if was_prefill and not req.is_prefill and req.first_token_time is None:
                req.first_token_time = now

            # check finish
            if req.is_done:
                req.status = "FINISHED"
                req.finish_time = now
                self.running.remove(req)
                self.finished.append(req)

        return scheduled

    def _preempt(self, exclude: Optional[Request] = None) -> Optional[Request]:
        """Pick a victim, free its KV. Returns victim or None if no victim."""
        for victim in reversed(self.running):
            if victim is not exclude:
                self._do_preempt(victim)
                return victim
        return None

    def _do_preempt(self, victim: Request):
        self.running.remove(victim)
        victim.preempt_count += 1
        self.num_preempted += 1

        if self.preempt_mode == "recompute":
            victim.num_computed_tokens = 0
            victim.status = "WAITING"
            victim.first_token_time = None    # will be re-set
            self.waiting.appendleft(victim)
        else:  # swap
            victim.status = "PREEMPTED"
            # in real vLLM, KV would go to host; here we just track
            self.waiting.appendleft(victim)


# ===== 3. Simulator =====

def simulate(
    num_requests: int = 100,
    arrival_rate: float = 5.0,           # requests per "second"
    prompt_dist=(50, 2000),
    output_dist=(50, 500),
    sim_duration: float = 30.0,
    seed: int = 42,
    **sched_kwargs,
):
    random.seed(seed)
    sched = Scheduler(**sched_kwargs)

    # Pre-generate arrivals (Poisson process)
    arrivals = []
    t = 0.0
    for i in range(num_requests):
        t += random.expovariate(arrival_rate)
        arrivals.append(Request(
            id=i,
            prompt_len=random.randint(*prompt_dist),
            output_len=random.randint(*output_dist),
            arrival_time=t,
        ))

    # Time-stepped simulation: each step = 1 ms of wall time
    # In real vLLM, a step's wall time depends on batch; we approximate ~30ms / step
    STEP_MS = 30
    now = 0.0
    arrival_idx = 0
    log = []
    while now < sim_duration * 1000:
        # admit arrivals
        while arrival_idx < len(arrivals) and arrivals[arrival_idx].arrival_time * 1000 <= now:
            sched.waiting.append(arrivals[arrival_idx])
            arrival_idx += 1

        sched.step(now)

        log.append({
            "t": now,
            "running": len(sched.running),
            "waiting": len(sched.waiting),
            "kv_used": sched.kv_used(),
            "preempted": sched.num_preempted,
        })
        now += STEP_MS

        if arrival_idx == len(arrivals) and not sched.waiting and not sched.running:
            break

    return sched, log


def report(sched, log):
    finished = sched.finished
    if not finished:
        print("No finished requests.")
        return

    ttfts = [r.first_token_time - r.arrival_time * 1000 for r in finished
             if r.first_token_time is not None]
    latencies = [r.finish_time - r.arrival_time * 1000 for r in finished]

    print(f"=== mini-scheduler report ===")
    print(f"Finished:           {len(finished)} / {len(finished) + len(sched.running) + len(sched.waiting)}")
    print(f"Total steps:        {sched.step_count}")
    print(f"Total tokens:       {sched.total_tokens_processed}")
    print(f"Throughput:         {sched.total_tokens_processed / log[-1]['t'] * 1000:.0f} tok/s")
    print(f"TTFT  p50 / p99:    {sorted(ttfts)[len(ttfts)//2]:.0f} / {sorted(ttfts)[int(len(ttfts)*0.99)]:.0f} ms")
    print(f"Latency p50 / p99:  {sorted(latencies)[len(latencies)//2]:.0f} / {sorted(latencies)[int(len(latencies)*0.99)]:.0f} ms")
    print(f"Preemptions:        {sched.num_preempted}")


def plot(log):
    """Optional: visualize state over time."""
    try:
        import matplotlib.pyplot as plt
    except ImportError:
        return
    ts = [e["t"] / 1000 for e in log]
    fig, ax = plt.subplots(2, 1, figsize=(10, 5), sharex=True)
    ax[0].plot(ts, [e["running"] for e in log], label="running")
    ax[0].plot(ts, [e["waiting"] for e in log], label="waiting", alpha=0.6)
    ax[0].set_ylabel("# requests")
    ax[0].legend()
    ax[1].plot(ts, [e["kv_used"] for e in log], color="tab:orange")
    ax[1].set_ylabel("KV blocks used")
    ax[1].set_xlabel("time (s)")
    plt.tight_layout()
    plt.savefig("mini_sched.png", dpi=120)
    print("Saved mini_sched.png")


if __name__ == "__main__":
    sched, log = simulate(
        num_requests=100,
        arrival_rate=5.0,
        kv_capacity_blocks=200,
        token_budget=2048,
    )
    report(sched, log)
    plot(log)

预期输出

=== mini-scheduler report ===
Finished:           100 / 100
Total steps:        ~700
Total tokens:       ~45000
Throughput:         ~2100 tok/s
TTFT  p50 / p99:    180 / 2800 ms
Latency p50 / p99:  6200 / 14000 ms
Preemptions:        ~25

数字会因随机种子和参数浮动。关键是看趋势——下一节让你跑参数 sweep 验证 trade-off。

13基准测试 · 把你的 scheduler 调参

跑通基本版本只是第一步。真正学到东西是看参数 sweep 的曲线，验证你对系统的直觉。 下面 3 个实验，每个 ~10 行代码：

实验 1 · Token budget 扫描

for budget in [256, 512, 1024, 2048, 4096, 8192]:
    sched, log = simulate(token_budget=budget, kv_capacity_blocks=400)
    print(f"budget={budget:5d}  thpt={sched.total_tokens_processed/log[-1]['t']*1000:6.0f} tok/s  "
          f"TTFT p50={...}  preempt={sched.num_preempted}")

预期观察：

• Budget ↑ → 吞吐 ↑ 到某点饱和（GPU 算力上限或 KV 上限）。
• Budget ↑ → TTFT 可能 ↑（新请求被推后给大 batch 让路）。
• Budget 很小（256）→ 每 step 容量小、step 数量爆炸、context overhead 占比上升。

实验 2 · KV capacity 扫描

for kv in [50, 100, 200, 400, 800, 1600]:
    sched, log = simulate(kv_capacity_blocks=kv, token_budget=2048)
    print(f"kv={kv:5d}  thpt=...  preempt={sched.num_preempted}  ttft p99=...")

预期：

• KV ↑ → preempt 数 ↓（容得下更多并发）。
• KV ↑ → 吞吐 ↑（到某点饱和：token budget 或 arrival rate 成为新 bottleneck）。
• KV 很小 → preempt 爆炸（10x 以上）→ 吞吐反而暴跌（recompute 浪费）。

实验 3 · 长度方差敏感性

for prompt_max in [200, 500, 1000, 2000, 5000]:
    sched, log = simulate(
        prompt_dist=(50, prompt_max),
        token_budget=2048,
        kv_capacity_blocks=400,
    )
    # ...

预期：

• 长度方差 ↑ → tail latency P99 显著 ↑（短请求被长请求堵）。
• 这就是为什么 production 里要么加 priority、要么用 chunked prefill 缓解。

14常见误解

15本月 PR 候选

Month 3 的 KPI：至少 1 个 scheduler 相关 PR。下面是真实可下手的方向：

低难度（一周内可完成）

• 给 scheduler 加 metric 暴露：每 step batch size 分布、preempt 次数、queue length。Prometheus exporter 已有，只是某些字段没暴露。
• 修一个 边界 bug：搜 issue tracker label:bug + label:scheduler，按"oldest"排序，前几页常有"已确认但没人修"的小 bug（比如 preempt 后 num_computed_tokens 没正确归零这类）。
• 补 docstring 和 type hint：scheduler.py 的某些函数还缺，是个无害但被 maintainers 欢迎的 PR。

中难度（两周内）

• 实现一个 新的 victim 选择策略："选剩余 token 数最少的"或"选已生成 token 最少的"，作为实验性选项。配测试 + benchmark。
• 给 chunked prefill 写新测试覆盖某 corner case（比如 chunk size 不是 block size 整数倍时的 KV 分配）。
• 实现 preemption 的自适应模式：根据 tokens_generated 自动选 recompute vs swap。

高难度（一个月，作为 Month 5 候选）

• 实现一个 新的 scheduling policy（比如 SJF-with-prediction，用历史平均输出长度预测）。
• 把某篇 paper 的算法 port 进来（DistServe 的 prefill/decode 拆分、Llumnix 的 migration 等）。

16本页自检

17延伸阅读

读完本章后，按下面顺序消化论文，每篇花 2-3 小时（读 abstract + intro + 关键 figure + 关键 algorithm，不必逐行）。 这是把"看懂 vLLM"升级到"参与 serving 研究"的桥梁。

读论文的关键问题清单（每篇都带着问）：

• 它解的 problem 是什么？为什么之前的方案不够？
• 核心 idea 一句话能不能讲清？(应该可以)
• 它的实验环境跟 vLLM 接近吗？(workload / hardware)
• vLLM 实现了哪些？没实现的为什么？(成本 / 复杂度 / 收益)