nano-vllm-omni · 提示 ← P10P07 →
#15 · Track B · Stage 进程与调度 · 书 p.68

P11 · WAITING_FOR_CHUNK:停靠与归还

上游 scheduler 不认识“等 chunk”这种状态;你要在它外面包一层——没数据的请求在它眼里必须不存在。

⏱ 45 min 难度 中 实现 mine/p11_chunk_aware_scheduler.py 验收 ./check.sh p11 提示 A-15 · 参考解 C-15 solutions/p11_chunk_aware_scheduler.py

题面速览

schedule():
    ① 把已就绪的停靠请求放回原队列
    ② 把 needs_chunk 且未就绪的请求从 waiting/running 中移出,状态设为 WAITING_FOR_CHUNK,
       记录来源队列和原状态,第一次停靠时调用 source.load_async(id)
    try:     ③ base.schedule()        # 上游只看得到有数据的请求
    finally: ④ 再归还一次已就绪的      # 即使上游抛异常也要归还

验收要点:未就绪请求从不被调度、load_async 只调用一次 · 就绪后下一次 schedule 一定被调度 · running 中的请求等下一个 chunk 时同样被停靠 · 上游 schedule 抛异常时 finally 仍然归还 · 停靠期间 abort:不会再被调度/归还 · 同时归还多个请求时保持到达顺序。

直觉与类比

后厨的订单板和“等料夹”

主厨(上游 scheduler)只认墙上的订单板:“待做”栏(waiting)、“在做”栏(running),看到写着“等料”的单子会直接发火(AssertionError)。你是领班:每轮开工前把“料还没到”的单子从板上摘下,夹进等料夹(parked),背面写两行字:原来挂在哪栏(origin)、原来什么状态(previous status);同时给隔壁打电话“这单的料请送来”(load_async,每摘一次打一次)。料到了就挂回原栏、恢复原状态;好几张同时到时按客人下单先后(Req.arrival)挂回。

主厨摔锅、客人退单

主厨摔锅(base.schedule() 抛异常):领班下班前仍要把“料已到”的单子挂回板上(finally),再把事故照实上报(异常继续往上抛)。客人退单(abort):单子可能在待做栏、在做栏、等料夹三处——三处都要找、都要撕;只撕等料夹的,板上那张主厨照做;只写“已退”不摘下,主厨又要发火。

框架视角 · T · SBWC · LIFE

P11 是 P11–P13 三道题里唯一完全单线程的一道:add / abort / schedule 都在同一个调度线程里调用。它的“并发”只来自 is_ready() 的答案由别的线程(P13 的 recv 线程)推进,你每次问都可能得到不同结果。

P11
T 下游 stage 进程里的调度线程(P10 busy loop)。P11 只跨“调度线程 ↔ ChunkSource”一条边界,且只用两个非阻塞调用
S parked、base.waiting / base.running、req.status:全部只由调度线程写(单写者,不用锁)
B 哪里都不许等。schedule() 绝不能阻塞等 chunk(会让整张 GPU 空转)——所以是“停靠 + 下一轮再问”
W 没有后台 worker。领班只负责摘单、挂单;送料的是 P13 的 recv 线程
C ChunkSource 就是通道:load_async 是请求,is_ready 是回答
L needs_chunk 请求会在 WAITING/RUNNING ⇄ WAITING_FOR_CHUNK 之间来回很多次;终点是完成或 ABORTED
F ① 上游 (c) 执行期间队列里没有 WAITING_FOR_CHUNK / ABORTED;② 每个请求任一时刻只在 waiting、running、parked 之一;③ 每次停靠恰好一次 load_async;④ 归还 = 原队列 + 原状态,同一批按 arrival 排序
E 上游抛异常(finally 仍归还、异常照抛);chunk 恰好在 (c) 期间到达;同一请求先从 waiting、后从 running 停靠;abort 后 is_ready 仍返回 True

易错点

逐步图:例 1(x 普通请求,t1 等 chunk)

▶ R=RUNNING,W=WAITING,WFC=WAITING_FOR_CHUNK
1. #1 schedule,is_ready(t1)=F

(a) 无变化 → (b) waiting=[x(W)],parked={t1: (waiting, W)},t1(WFC),load_async("t1")

base.schedule() → ["x"];(d) running=[x(R)],t1 仍停靠。loads = [t1]

2. #2 schedule,仍未就绪

t1 不在任何队列里,(b) 根本看不到它 → 不会再调 load_async。

返回 ["x"];loads = [t1]

3. #3 schedule,is_ready(t1)=T

(a) 归还:waiting=[t1(W)],parked={} → 上游返回 ["x", "t1"];running=[x(R), t1(R)]

4. #4 schedule,t1 吃完这块、下一块未到

(b) 从 running 停靠:parked={t1: (running, R)},再调一次 load_async。

返回 ["x"];loads = [t1, t1]——origin 和 previous status 是每次停靠时记录的。

5. #5 schedule,下一块到了

(a) 归还到 running,status 恢复 R → 返回 ["x", "t1"]

6. 小练习

若 #2 和 #3 之间,chunk 是在上游 schedule 执行过程中到达的:

t1 在第几次调用的哪一步被归还?第几次被调度?

#2 的 (d) 归还到 waiting,#3 调度它。

三级提示

L1I/O 示例与关键问题I/O 示例 + 关键问题 + 细节(轻度剧透)

例 1 见逐步图。

例 2:同时归还按 arrival 排序:add k(5)、m(3)、n(4)(都 needs_chunk)→ schedule() → [](三个都停靠,load_async 记录 ["k","m","n"])→ 三个 chunk 同时到达 → schedule() → ["m", "n", "k"]。

例 3:上游抛异常时 finally 仍归还:

class Exploding(BaseScheduler):
    def schedule(self):
        src.ready.add("z")            # z 的 chunk 恰好在上游调度期间到达
        raise RuntimeError("boom")

s = ChunkAwareScheduler(Exploding(), src)
s.add(Req("z", 0, needs_chunk=True)); s.add(Req("y", 1))
s.schedule()       # RuntimeError("boom") 原样抛出
# 之后:base.waiting == [y(WAITING), z(WAITING)],parked == {},load_async 记录 ["z"]

z 归还时 append 到 waiting 末尾,所以排在 y 之后;异常没被吞掉。

关键问题

  1. BaseScheduler 一看到 WAITING_FOR_CHUNK 就断言失败。“停靠”只改 status 够不够?请求此时应该在哪个容器里?
  2. 同一请求连续 3 次 schedule() 都没就绪,load_async 应调用几次?归还后又没就绪呢?什么机制天然保证“每次停靠一次”?
  3. running 中的请求被停靠时,previous status 是什么?归还时一律写 "WAITING" 的后果?
  4. 为什么 (a) 先归还再 (b) 停靠?去掉 (a) 只靠上一轮的 (d),会晚几轮被调度?
  5. 在 (d) 中归还的请求,本轮 base.schedule() 的返回值里有它吗?
  6. “按 arrival order 归还”的 arrival 指什么?
  7. abort(id) 之后 is_ready(id) 仍可能 True,什么保证它不会被归还?它可能藏在哪几个地方?

细节

  • parked[id] = (req, origin, previous_status);origin 用什么表示由你决定(如 "waiting" / "running")。
  • BaseScheduler:返回 running 的 id + waiting 的 id,然后把 waiting 全部挪进 running 并设为 RUNNING——它从不改 running 中请求的 status,恢复 status 的责任完全在你这层。
  • 只有 needs_chunk=True 的请求才会被停靠;is_ready 可以 True → False → True 反复变化。
  • 归还放回 origin 队列末尾(waiting 是 deque,running 是 list)。
L2思路与常见坑思路拆分与常见坑(中度剧透)
  • 拆两个私有 helper:_restore_ready()(扫描 parked,把就绪的按 arrival 放回来源队列)和 _park_not_ready()(扫描两个队列,把 needs_chunk 且未就绪的移进 parked)。schedule() 就只剩四行:restore → park → try: return base.schedule() → finally: restore。
  • load_async 去重:被停靠的请求已经不在队列里,(b) 下一轮看不到它,“停靠的那一刻调一次”天然满足“每次停靠一次”。想更保险可维护“已请求加载”集合,但要在归还/abort 时清掉。
  • 归还顺序:先收集所有 is_ready 的条目,按 req.arrival 排序,再逐个删除、恢复 status、append。
  • abort 的三个藏身处:parked、base.waiting、base.running 都要查并移除,状态可设为 ABORTED。
L3详解:答案详解:答案、逐步追踪、骨架提示(重度剧透)
关键问题答案
  1. 只改 status 不够:上游遍历 waiting/running,见到 WFC 就断言。必须从队列中移出,只存在于 parked。
  2. 连续 3 次未就绪:1 次。归还后再次停靠:再 1 次(共 2 次)。机制:停靠后请求不在队列,(b) 遍历不到它。
  3. "RUNNING";写死 "WAITING" 会让它永远带着错误状态待在 running。
  4. 没有 (a) 时,两次调用之间就绪的请求要等下一次的 (d) 才回队列,晚 1 轮。
  5. 不在(上游已经跑完),下一轮被调度。
  6. Req.arrival 字段。
  7. 从 parked 删除即可阻止归还(归还只扫描 parked);它还可能在 base.waiting 或 base.running,三处都要删。

abort 的追踪(add a(0)、b(1, needs_chunk)、c(2);b 没就绪):

操作 waiting running parked
schedule() → ["a","c"] [] [a, c] {b}
abort("b") [] [a, c] {}(从停靠表删除)
abort("c") [] [a] {}
b 的 chunk 到了;schedule() → ["a"] [] [a] {}——b 不在 parked,(a)/(d) 根本看不到它

面试官追问 & 对照源码

对照源码:core/sched/omni_ar_scheduler.py:408-451 · distributed/omni_connectors/transfer_adapter/chunk_transfer_adapter.py:1120-1186 · :1488-1532 · patch.py:364-372