ARTICLE · 1385006
Nano-vLLM源码学习(5):Scheduler 与连续批处理
📑 目录
1. 调度器要回答的三个问题 2. 两个队列与一次 schedule 3. Prefill 调度:吃 Token Budget 4. Decode 调度:抢占来腾地方 5. postprocess:写回与结束判定 总结 自我检验清单 参考资料
1. 调度器要回答的三个问题
引擎每跑一步(step),都要先问调度器:这一轮算谁?是 prefill 还是 decode?它们的 KV 放得下吗?scheduler.py只有 90 多行,职责就是回答这三个问题。它不碰矩阵乘法,只做资源分配和批次组装的决策。
调度器可以类比成餐厅领位员:门口排队的客人是 waiting,已经落座点菜的是 running。领位员每轮先看门口还能不能再安排一桌,安排不了才去照顾已经落座的客人;桌子不够时,就请最后落座的那桌先起身,回门口重新排队。
nano-vllm 采用和 vLLM V0 默认调度相同的做法:一轮要么全是 prefill,要么全是 decode,不混批。两个阶段的输入形状不同:prefill 是多条变长的整段 prompt,走 flash_attn_varlen_func;decode 是每条序列 1 个 token,走 flash_attn_with_kvcache,还能用 CUDA Graph 回放(见 3.3、3.6)。分开调度后,每一步只需要准备一种输入、走一条执行路径。
2. 两个队列与一次 schedule
调度器维护两个双端队列(deque)和若干预算约束:
●●●Pythonclass Scheduler:
def__init__(self, config):
self.max_num_seqs = config.max_num_seqs # 一轮最多几条序列
self.max_num_batched_tokens = config.max_num_batched_tokens # 一轮最多几个 token
self.eos = config.eos
self.block_size = config.kvcache_block_size
self.block_manager = BlockManager(config.num_kvcache_blocks,
config.kvcache_block_size)
self.waiting = deque() # 还没 prefill 完的序列(新请求、chunked 未算完、被抢占的)
self.running = deque() # prefill 已完成、正在逐 token decode 的序列一条序列的流动路径如下,黄色是 waiting 队列,蓝色是 running 队列,下方的弧线是抢占:

schedule()返回 (seqs, is_prefill),即选中的这批序列,以及这一轮是 prefill 还是 decode。它的逻辑是 prefill 优先:只要 prefill 分支选出了至少一条序列,本轮就做 prefill;一条都选不出来(waiting为空,或队头序列的块不够),才去 running做 decode。
3. Prefill 调度:吃 Token Budget
Prefill 分支从 waiting队头依次取序列,往一个 batch 里塞,直到撞上任一预算上限:
●●●Pythondefschedule(self):
scheduled_seqs = []
num_batched_tokens = 0
whileself.waiting andlen(scheduled_seqs) < self.max_num_seqs:
seq = self.waiting[0]
remaining = self.max_num_batched_tokens - num_batched_tokens # 剩余 token 预算
if remaining == 0:
break
ifnot 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: # chunked prefill 续算:块已分配
num_tokens = seq.num_tokens - seq.num_cached_tokens
if remaining < num_tokens and scheduled_seqs:
break# 预算不够、且已有序列:收手
ifnot seq.block_table:
self.block_manager.allocate(seq, num_cached_blocks)
# 允许对「本轮第一条」做 chunked prefill:只算预算内的部分
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 # 整段 prompt 算完才转 running
self.waiting.popleft(); self.running.append(seq)
scheduled_seqs.append(seq)
if scheduled_seqs:
return scheduled_seqs, True# is_prefill = True
# ...否则进入 decode 分支(见第 4 节)两个预算共同构成 Token Budget:
🔑 max_num_batched_tokens:一轮最多处理多少 token,主要约束 prefill(prompt 可能很长)。超了就停止往 batch 里加。🔑 max_num_seqs:一轮最多多少条序列,主要约束 decode(每条只算一个 token,但条数不能无限多)。
循环里有三个出口,含义各不相同:
can_allocate返回-1就break:队头序列的块不够时,后面即使有更短、放得下的请求也不会被调度。这是严格的先来先服务,代价是队头阻塞。remaining < num_tokens and scheduled_seqs就break:只有 batch 里已经有序列时,预算不够才收手。如果队头是一条超长 prompt,batch 还空着,调度器就用min(num_tokens, remaining)只排预算内的一段,这就是 chunked prefill。源码注释写的是 "only allow chunked prefill for the first seq"。remaining == 0就break:第一条序列被截断后预算正好用完,下一轮循环直接退出,所以被截断的序列总是本轮唯一的一条。
被截断的序列不会离开 waiting:它仍在队头,block_table在第一次调度时已经整段分配好,状态还是 WAITING,is_prefill还是 True。下一轮它走 else分支,num_tokens按 num_tokens - num_cached_tokens算出剩余部分继续 prefill,直到最后一段被调度时才移进 running。
💡 提示:prefill 优先意味着只要 waiting队头能排上,running里的序列这一轮就不 decode。一条很长的 prompt 分成多段 chunked prefill 时,已经在生成的请求会停顿好几步,出词间隔随之变长。vLLM V1 的调度器去掉了 prefill/decode 的阶段区分,每步按固定的 token 预算给每个请求分配要算的 token 数(调度结果就是 {request_id: num_tokens}),prefill 片段和 decode token 可以在同一个 batch 里。
4. Decode 调度:抢占来腾地方
当 prefill 分支一条都没选出来,schedule()转去给 running里的序列做 decode。decode 每条序列每步只 +1 个 token,风险在于这个 token 正好要开新块,而空闲块已经用完。nano-vllm 的处理方式是抢占(preemption):
●●●Python# decode 分支
whileself.running andlen(scheduled_seqs) < self.max_num_seqs:
seq = self.running.popleft()
whilenotself.block_manager.can_append(seq):
ifself.running:
self.preempt(self.running.pop()) # 牺牲 running 队尾的序列
else:
self.preempt(seq); break# 没有别人可牺牲,牺牲自己
else:
seq.num_scheduled_tokens = 1
seq.is_prefill = False# 第一次进 decode batch 时在这里置 False
self.block_manager.may_append(seq) # 真的跨块就取新块
scheduled_seqs.append(seq)
assert scheduled_seqs
self.running.extendleft(reversed(scheduled_seqs)) # 选中的序列按原顺序放回队头
return scheduled_seqs, False# is_prefill = False内层 while可能连续抢占好几条,直到当前序列能追加为止。循环结束后,extendleft(reversed(...))把本轮选中的序列按原来的先后放回 running队头;因为 max_num_seqs没轮到的序列一直留在队里,排在它们后面。
抢占做的事:
●●●Pythondefpreempt(self, seq):
seq.status = SequenceStatus.WAITING # 打回等待队列
seq.is_prefill = True# 下次要重新 prefill
self.block_manager.deallocate(seq) # 释放它占的所有 KV 块,num_cached_tokens 清零
self.waiting.appendleft(seq) # 插回队头,下一轮优先重新调度📌 关键点:nano-vllm 的抢占策略是重计算(recomputation)而非换出(swap)。被抢占的序列直接释放 KV、打回 waiting,下次把 prompt 和已生成的 token 当成一整段重新 prefill。这比把 KV 搬到 CPU 内存再搬回来简单得多,代价是重算。重算的量通常比整段小:deallocate只把块放回空闲队列、不清哈希(见 3.4),只要这些块还没被别的请求覆盖,重新 prefill 时就能命中前缀缓存。
被牺牲的是 running队尾,也就是最近才完成 prefill 的序列。先来的请求因此能继续推进,整体接近先来先服务。它已生成的 token 通常也最少,但占用的 KV 还取决于 prompt 长度,不一定是最小的。
⚠️ 注意:while ... else的 else只在循环条件变为假(can_append成功)时执行,被 break跳出则不执行。牺牲自己的分支以 break结束,所以这条序列不会进入本轮 batch,它已经在 preempt里被插回了 waiting队头。
5. postprocess:写回与结束判定
模型算完、采样出 token 后,引擎调用 scheduler.postprocess把结果写回序列并判断是否结束:
●●●Pythondefpostprocess(self, seqs, token_ids, is_prefill):
for seq, token_id inzip(seqs, token_ids):
self.block_manager.hash_blocks(seq) # 本轮新填满的块登记哈希(见 3.4)
seq.num_cached_tokens += seq.num_scheduled_tokens # 本轮算过的 token 记为已缓存
seq.num_scheduled_tokens = 0
if is_prefill and seq.num_cached_tokens < seq.num_tokens:
continue# chunked prefill 还没算完:丢弃本轮采样结果
seq.append_token(token_id) # 追加采样出的新 token
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) # 结束就释放 KV
self.running.remove(seq)几个要点:
chunked prefill 的中间段也会采样:模型照常对这一段的最后一个位置算 logits、采样出一个 token,但那个位置不是 prompt 的末尾,结果没有意义, continue直接丢掉。只有最后一段算完,采样出的才是真正的第一个生成 token。结束条件:命中 EOS(且没设 ignore_eos),或生成数达到max_tokens。满足任一就标记FINISHED、释放 KV 块、从running移除;未结束的序列留在running里等下一轮 decode。max_tokens = 1的请求在 prefill 这一步就会结束,这时它已经在schedule里被移进running,remove不会出错。ignore_eos/max_tokens是Sequence的实例属性(构造时从SamplingParams摊平而来,见 3.4)。
把这一节串起来,每一步的调度闭环如下图。左边是 prefill 路径(黄色),右边是 decode 路径(蓝色),红色框是 decode 时 KV 不够触发的抢占:

📝 总结
调度器只做决策、不算矩阵:维护 waiting/running两个 deque,schedule()返回(seqs, is_prefill)。Prefill 优先、不混批:prefill 分支选出序列就做 prefill,否则才 decode。 waiting队头放不下时直接停,严格先来先服务。Token Budget= max_num_batched_tokens(约束 prefill)+max_num_seqs(约束 decode)。只有本轮第一条序列可以被 chunked prefill 截断,截断后它留在waiting队头续算,中间段的采样结果被丢弃。Decode 遇到空闲块不足时抢占 running队尾,采用重计算而非换出:打回waiting队头、重置is_prefill=True、释放 KV。释放的块保留哈希,重新 prefill 时可能命中前缀缓存。postprocess先登记新填满块的哈希、更新num_cached_tokens,再追加 token;命中 EOS 或达到max_tokens则FINISHED并释放 KV。
📚 参考资料
nano-vllm GitHub 仓库 Efficient Memory Management for Large Language Model Serving with PagedAttention(Kwon et al., 2023) Orca: A Distributed Serving System for Transformer-Based Generative Models(Yu et al., 2022) vLLM 官方文档 - 架构概览 vLLM V1: A Major Upgrade to vLLM's Core Architecture(vLLM 官方博客,2025-01-27)
📚 推荐阅读
AIInfraGuide : 开源全栈AI Infra 学习教程
推理优化系列:
AIInfra推理优化(3):PagedAttention - 像操作系统管理内存一样管理 KV Cache
AIInfra推理优化(4):Continuous Batching - 让 GPU 不再空等的动态批处理
AIInfra推理优化(5):Prefix Cache 与 RadixAttention 复用共享前缀的 KV
AIInfra推理优化(6):Chunked Prefill 与统一 Token Budget 调度
AIInfra推理优化(7):Attention 后端与CUDA Graph












































































