课程 03 · 调度

谁上 GPU，谁在等

schedule() 只有 50 行，却要同时回答三个问题：预算还剩多少、显存够不够、等不下的序列怎么处理。这一课把 waiting 和 running 两条队列彻底拆开。

约 50 分钟 源码：engine/scheduler.py（92 行） 前置：02

1调度器的合同

def schedule(self) -> tuple[list[Sequence], bool]:
    ...
    if scheduled_seqs:
        return scheduled_seqs, True     # 这一轮是 prefill
    ...
    assert scheduled_seqs
    return scheduled_seqs, False        # 这一轮是 decode

它只做一件事：挑出这一轮要上 GPU 的序列，并告诉调用方这轮是 prefill 还是 decode。所有策略都藏在两个循环里：先尽力塞 prefill，塞不进去才转 decode。

2prefill 循环：三个约束同时收紧

scheduler.py · L29–55while self.waiting and len(scheduled_seqs) < self.max_num_seqs:   # 约束① 序列数
    seq = self.waiting[0]
    remaining = self.max_num_batched_tokens - num_batched_tokens  # 约束② token 预算
    if remaining == 0:
        break
    if not seq.block_table:
        num_cached_blocks = self.block_manager.can_allocate(seq)
        if num_cached_blocks == -1:      # 约束③ 显存
            break                        # 队首都放不下，后面更长的更放不下
        num_tokens = seq.num_tokens - num_cached_blocks * self.block_size
    else:
        num_tokens = seq.num_tokens - seq.num_cached_tokens
    if remaining < num_tokens and scheduled_seqs:   # 只允许第一条分块
        break
    if not seq.block_table:
        self.block_manager.allocate(seq, num_cached_blocks)
    seq.num_scheduled_tokens = min(num_tokens, remaining)
    num_batched_tokens += seq.num_scheduled_tokens
    if seq.num_cached_tokens + seq.num_scheduled_tokens == seq.num_tokens:
        seq.status = SequenceStatus.RUNNING
        self.waiting.popleft()
        self.running.append(seq)
    scheduled_seqs.append(seq)

三个 break 对应三个不同的放弃理由，面试里能分清这三个，就已经超出大多数人：

条件	含义	为什么不继续尝试后面的序列
remaining == 0	token 预算用完	预算只会更少，后面的也塞不下
can_allocate == -1	显存不够	队列按长度递增假设，后面的只会更长
remaining < num_tokens 且已有序列	放不下完整 prompt	只有第一条允许被切成多轮（chunked prefill）

3chunked prefill：只给第一条

if remaining < num_tokens and scheduled_seqs: break 这行的意思是：

• 如果这是本轮第一条序列（scheduled_seqs 为空），即使预算不够算完整个 prompt，也切一块先算——这就是 chunked prefill。
• 如果本轮已经排了别的序列，就不再接受「需要切块」的请求，宁可留到下一轮。

为什么限制得这么死？因为切块会让一条序列横跨多轮：它的 num_cached_tokens 在一轮轮增长，期间不能采样、不能结束。如果允许多条序列同时分块，is_prefill 这个布尔值就不够用了——你没法用一个全局标志描述「一半序列在补 prefill、一半在 decode」。nano-vllm 用「一轮一种模式」换来了代码的极简，代价是调度自由度。

4decode 循环：显存不够就抢

scheduler.py · L57–73while self.running and len(scheduled_seqs) < self.max_num_seqs:
    seq = self.running.popleft()
    while not self.block_manager.can_append(seq):
        if self.running:                       # 还有别的序列可以牺牲
            self.preempt(self.running.pop())
        else:                                  # 只剩自己了
            self.preempt(seq)
            break
    else:                                      # while 正常结束（没被 break）
        seq.num_scheduled_tokens = 1
        seq.is_prefill = False
        self.block_manager.may_append(seq)
        scheduled_seqs.append(seq)
assert scheduled_seqs
self.running.extendleft(reversed(scheduled_seqs))

这段代码里有三个值得单独讲的点。

① 抢谁：running.pop()

pop() 取的是队列尾部，也就是最近才进入 running 的序列。它的 KV 最短、重算成本最低——抢占是一个经济学问题，不是公平性问题。

② 抢占做了什么

scheduler.py · L75–79def preempt(self, seq):
    seq.status = SequenceStatus.WAITING
    seq.is_prefill = True
    self.block_manager.deallocate(seq)     # 块全部归还，num_cached_tokens 清零
    self.waiting.appendleft(seq)           # 插到队首，下一轮优先重算

注意 is_prefill = True：被抢占的序列要重新走一遍 prefill，因为它已经生成的 KV 全没了。num_cached_tokens 在 deallocate 里被清零，所以下一轮的 num_tokens 会重新等于整条序列长度——除非前缀缓存还能命中一部分。

③ 那个 while ... else

Python 的 while/else 在这里不是炫技：else 只在循环没有被 break 时执行。也就是说，只有当 can_append 最终返回真（腾出了空间），这条序列才会被排进本轮；如果它是被自己抢占掉的那一条，break 让 else 跳过，本轮就不跑它。

5postprocess：真正的记账处

scheduler.py · L81–92def postprocess(self, seqs, token_ids, is_prefill):
    for seq, token_id in zip(seqs, token_ids):
        self.block_manager.hash_blocks(seq)          # 满块登记进前缀缓存
        seq.num_cached_tokens += seq.num_scheduled_tokens
        seq.num_scheduled_tokens = 0
        if is_prefill and seq.num_cached_tokens < seq.num_tokens:
            continue                                  # 分块没算完：不加 token、不判死
        seq.append_token(token_id)
        if (not seq.ignore_eos and token_id == self.eos) or seq.num_completion_tokens == seq.max_tokens:
            seq.status = SequenceStatus.FINISHED
            self.block_manager.deallocate(seq)
            self.running.remove(seq)

这里有本课最隐蔽的一处浪费：分块 prefill 时采样出的 token 被直接丢掉了。model_runner 每轮都会对所有序列采样，但 continue 让这个 token 永远不会被 append。下一轮算完剩下的 prompt，还会再采一次。

这是教学实现的取舍：与其在 run() 里判断「哪些序列还没算完、不要采样」，不如统一采样再丢弃。正确性没问题，浪费一次采样而已——面试时能主动说出这一点，是很强的信号。

6三个旋钮

参数	默认	调大之后	调小之后
max_num_seqs	512	并发上限更高，但每序列更慢	延迟更稳，吞吐下降
max_num_batched_tokens	16384	一轮能吃更长 prompt，TTFT 波动更大	长 prompt 被切更多块，首 token 更慢
gpu_memory_utilization	0.9	KV 块更多，能扛更多并发	更安全，但并发受限

7练习 A · 手算一次抢占

block_size = 4，空闲块 2 个。running 里有 A（长度 8）、B（长度 5），waiting 里 C（长度 20）。这一轮要跑 decode。请写出 schedule() 的过程。

展开：答案

A 先 popleft。A 长度 8，8 % 4 == 0，追加一个 token 需要新块吗？len % block_size == 0 ≠ 1，不需要新块——can_append 返回真，A 进本轮。

B 长度 5，5 % 4 == 1，追加会进入新块，需要 1 个空闲块——有 2 个，直接通过，B 进本轮。

本轮 decode 两条序列。注意 waiting 里的 C 根本不会被考虑：只要 prefill 循环一个都没排上，就会走到 decode；而 C 之所以没排上，是因为它需要 5 个新块，空闲只有 2 个，can_allocate 返回 -1 直接 break。

8练习 B · 闭卷测验

9练习 C · 代码寻宝

1. 如果删掉 assert scheduled_seqs，什么情况下 decode 会返回空列表？

当 running 里唯一的序列也被抢占时（else 分支的 preempt(seq)）。此时本轮没有可跑的序列——理论上应该回到调度循环重新尝试 prefill。这个 assert 是在声明「这种情形不应发生」，因为抢占自己时自己也进了 waiting，下一轮会走 prefill 路径。

2. running.extendleft(reversed(scheduled_seqs)) 为什么不直接 running.extend(...)？

popleft 已经把序列从头取走了，但要保持它们在 running 里的原有顺序。倒序 + extendleft 等价于按原顺序插到队首，这样下一轮 popleft 拿到的还是最早的序列——FIFO 语义。

3. 被抢占的序列为什么插到 waiting 的队首，而不是队尾？

它本来就在运行，只是缺显存。插队首能让它尽快恢复，避免饥饿；同时也符合「它已经等得最久」的直觉。代价是可能挤掉新来的请求——这正是调度策略要权衡的。

10面试复述卡

「continuous batching 和静态 batching 差在哪？」

展开：30 秒版本

「静态 batching 是把一批请求打包，等整批全部生成完才换下一批——快的请求要等慢的，新请求也进不来。continuous batching 是每一轮重新组 batch：谁做完了立刻退场释放块，新请求立刻补位。代价是每一步都要重新决定 batch 组成，还要处理显存不够时的抢占。nano-vllm 的 schedule() 就是这个决策的全部代码。」