DAG 怎么调度：Ready Queue、Parallel Execution 与 Scheduler

前置：Graph 怎样变成可执行依赖：Representation、Validation 与 Cycle Detection

A/B 同时 READY，但 max concurrency=1 时 scheduler 只能先启动一个；B 并不是依赖 A，只是等待容量。A 完成后将 C remaining deps 从 1 减到 0，C 才进入 READY；同一 completion event 重放不应让 C 入队两次。

DAG Scheduling

Scheduler 从 ready queue 取满足依赖的节点，并受 concurrency/resource policy 约束；它远比得到一个 topological order 更复杂。

Scheduler 根据依赖、状态、资源和 policy 决定哪些 node 何时运行。它比拓扑排序多处理并发、失败、取消、重试、等待和恢复。

Ready Queue 只包含所有必要 dependency 已满足的节点。节点从 READY 到 RUNNING 的 claim 要避免多 worker 重复领取，并结合全局/资源级 concurrency limit。

入队必须由状态/依赖变化驱动，并防止重复入队；多 worker 场景还需租约或原子 claim。

并行度由依赖和容量共同决定。Semaphore/worker pool 限制 in-flight，避免把 provider quota、DB pool 或 socket 打满。

并行执行利用无依赖节点重叠 I/O，但要与状态提交和失败语义协调。并行并不代表同一 super-step 的全部结果必须一起回滚。

假设 Graph 是：

text

A ──→ C ──→ E
B ──→ D ──→ E

开始时 A/B indegree 都为 0，因此进入 ready queue。两个 worker 并行完成 A、B 后，C、D 才分别变 ready；E 必须等待 C、D 都提交成功。

text

t0 ready=[A,B]
t1 running=[A,B]
t2 committed=[A,B], ready=[C,D]
t3 committed=[C,D], ready=[E]

实际 Scheduler 还要叠加资源约束。即使 C、D 都 ready，如果它们都需要同一个“单写 workspace” capability，Runtime 也可能只放行一个。于是要区分：

这三个状态分开以后，排查“为什么节点一直没启动”就不需要靠猜。

症状： 只计算拓扑顺序，没有 node state、capacity、retry、deadline、pause/resume。

为什么危险： 真实并发、失败和恢复无法表示。

处理： Scheduler 维护 READY/RUNNING/terminal、资源上限与 failure policy；ordering 只是输入之一。

Case	断言
把 Topological Sort 当成完整 Scheduler	并发节点一成功一失败后 resume，成功节点不重跑、依赖节点不提前 READY。