vLLM 源码精读：调度器 —— Continuous Batching 与抢占

1. 调度器的位置与职责

Scheduler（scheduler.py，113KB）是 vLLM V1 的中枢。一句话职责：

它持有的核心状态：

2. schedule() 主循环六步全景

schedule()（行 351 ~ 970，约 620 行）每轮被 Engine 调用一次。六步流程：

3. Step 1-2：收尾 + 算剩余资源

Step 1 并不在 schedule() 内部

schedule() 开头调 kv_cache_manager.new_step_starts() 重置计数器，但真正"收尾"发生在上轮 Worker 返回后、Engine 调 update_from_output() 时（见 §8）。Scheduler 上轮结束后，已完成请求的 block 已被释放。

Step 2：token_budget

token_budget = self.max_num_scheduled_tokens
# 如果调度器 paused，token_budget = 0（任何请求都不调度）

token_budget 约束本轮能处理的总 token 数。RUNNING 和 WAITING 共享这个预算，消耗完即止。

另外，block 资源约束是隐式的：当 kv_cache_manager.allocate_slots() 返回 None 时，表示 block 不够。

4. Step 3：调度 RUNNING 请求

遍历 self.running 列表，逐个尝试加入本轮 batch：

while req_index < len(self.running) and token_budget > 0:
    request = self.running[req_index]

    # ---- 跳过条件 ----
    if 已达 max_tokens 且没 spec tokens 可验证: continue
    if 未到 next_decode_eligible_step（V2+PP+async）: continue
    if num_new_tokens == 0（PP 未完成/达上限/encoder budget 耗尽）: continue

    # ---- 确定本步 token 数 ----
    num_new_tokens = 请求剩余待处理 token 数
    if long_prefill_token_threshold 生效: 截断到这个阈值
    num_new_tokens = min(num_new_tokens, token_budget)
    num_new_tokens = min(num_new_tokens, max_model_len - 1 - 已计算 token 数)

    # ---- 分配 block ----
    while True:
        new_blocks = kv_cache_manager.allocate_slots(request, num_new_tokens)
        if new_blocks is not None:
            break  # 分配成功
        # 分配失败 → 抢占
        preempted_req = self.running.pop()  # 默认抢最后一个
        或 max(running, key=priority)       # PRIORITY 策略
        self._preempt_request(preempted_req)
        preempted_reqs.append(preempted_req)

    # ---- 加入本轮 ----
    scheduled_running_reqs.append(request)
    token_budget -= num_new_tokens
    req_index += 1

5. Step 4-5：调度 WAITING 请求

RUNNING 调度完成后，用剩余 token_budget 从等待队列拉新请求：

while (self.waiting or self.skipped_waiting) and token_budget > 0:
    request_queue = self._select_waiting_queue_for_scheduling()
    request = request_queue.peek()

    # ---- 跳过条件 ----
    if 已停等（lora 约束 / kv connector 传输中等）: 跳过 / 放回
    if 超过 max_loras 限制: break  # 整个队列停止

    # ---- 分配 block（同 RUNNING 流程） ----
    new_blocks = kv_cache_manager.allocate_slots(request, num_new_tokens)
    if new_blocks is None:
        if 已经有过抢占: break  # 不能再抢了
        抢占最后一个 running 请求
        continue  # 重试

    # ---- 加入本轮 ----
    scheduled_new_reqs.append(request)
    token_budget -= num_new_tokens

6. 抢占：_preempt_request

仅 23 行（行 995-1017）：

def _preempt_request(self, request, timestamp):
    # 1. 释放该请求的所有 KV block
    self.kv_cache_manager.free(request.request_id)
    # 键：释放后 block 回到 free_block_queue，hash 保留（Lazy Eviction）

    # 2. 重置请求状态
    request.status = waiting 状态
    # 重新 put 到 waiting 队列头部 → 等有资源后优先恢复

V1 代码里不区分 Swap 和 Recomputation——抢占 = 释放 block + 重新入队。论文描述的两种策略在 V1 被统一为"释放重排"——block 回到 free_queue 时 hash 还留着，如果短时间内恢复且命中 Prefix Cache 就是"免费召回"；如果 block 被新请求占用则等价于 recomputation。

7. Step 6：打包 SchedulerOutput

schedule() 末尾把本轮决策组装成 SchedulerOutput（定义在 interface.py）：

8. update_from_output：下一轮前的收尾

update_from_output()（行 1350 ~ 1673，约 320 行）在 Worker 完成后被 Engine 调用。核心逻辑：

def update_from_output(self, scheduler_output, model_runner_output):
    for req_id, output in model_runner_output.items():
        request = self.requests[req_id]

        # 1. 更新请求状态
        request.num_computed_tokens += output.num_tokens
        追加 output.new_token_ids

        # 2. 处理完成
        if 生成了 EOS 或 stop_string 或达到 max_tokens:
            self._free_request(request)   # 释放所有 block
            running 列表移除

        # 3. 处理抢占后的恢复
        如果之前被抢占的请求恢复 → scheduled_resumed_reqs

        # 4. 更新 running 列表
        self._update_after_schedule(scheduler_output)

核心操作：_free_request → kv_cache_manager.free(request_id) → block_pool.free_blocks → ref_cnt - 1 → 到 0 归还。

9. 论文映射 + 关键文件索引

10. ⭐ 高频卡点答疑

这是 Stage 1 / Week 3 的内容，对应 AI Infra 转型学习计划中"vLLM 调度器"任务。
上一篇：09 · KV Cache 管理层 | 下一篇预告：worker/ 和 attention/ 模块。