“延迟感知的指令列表调度进一步交付具体启动时刻：消费者等到生产者完成，同时遵守各类流水启动口的容量。其纯总操作模型用新鲜结果名证明数值保持，并给出合法但不最优的反例；实际选择结果若含 trap…”
形式陈述
先把指令的顺序与时间分开
假设乘法从启动到结果可用需要四拍。把依赖它的加法写在后面，只说明次序正确；若下一拍就读取乘积，仍然太早。另一方面，流水乘法器可能每拍接受一条新乘法，不必等上一条完成。指令调度要同时回答“数据何时可读”和“这一拍还能启动什么”，这两种限制不能用同一个数字代替。
输入是一张有限有向无环依赖图 G=(V,E)。每个节点是一条已经选定的操作，每条边 u→v 表示 v 启动前必须等到 u 完成。节点 v 有固定正整数延迟 L(v)，以及唯一的启动资源类别 r(v)。资源 r 每拍最多启动 cᵣ 条操作，其中 cᵣ 为正整数。所有操作都必须安排一次，不能以丢弃结果的方式缩短时间。
时间为从0开始的整数边界。操作 v 在 s(v) 启动，读取操作数，在 s(v)+L(v) 完成并交付结果。同一边界先处理完成，再处理启动，因此恰好在生产者完成的时刻启动消费者是合法的。每个类别的资源完全流水化：一条延迟四拍的操作只占用启动当拍的名额，不连续占住四个启动名额。本模型没有另外的总发射宽度、写回端口争用或可变缓存延迟。
输出是覆盖 V 的非负整数时间表 s，满足
调度长度为
什么样的源码可以交给它
语义证明先限定纯粹、确定、总定义的操作，使用数学整数和新鲜的结果名字，每条读取都由图中的生产者或初始输入提供。不存在异常、溢出、I/O、别名写入或对物理寄存器的覆盖。所有最终需要的结果都视为输出；固定延迟只是此教学机器的时间标签，不是 Python 计算该表达式实际所需的秒数。
若用于含存储访问的实际基本块，依赖图还必须覆盖不能交换的读写、异常及其他效果顺序。普通真数据依赖并不自动包含这些限制。若两条指令复用同一物理寄存器，也需要保持旧值的读写顺序，或者先正确重命名。调度器接受一张完整的约束图，不承担从任意机器代码恢复全部语义约束的任务。
指令选择已经决定每个操作使用什么模式；本页只改变启动时间。它也不负责把新鲜虚拟值装入有限寄存器。较早启动可能延长值的存活时间，随后分配寄存器若插入溢出读写，就需要重新处理这些指令及其依赖。
可复算的优先级与算法
先用拓扑排序获得顺序，逆序计算到出口的剩余路径长度：
没有后继时最大值取0。优先选择 h 较大的操作；相同 h 按输入声明次序打破平局。h 只计算依赖路径，不把端口争用算进去，所以它是一种明确可复算的启发式。
在当前时刻 t，列出尚未启动、且每个前驱已经完成的操作，形成就绪表。按上述优先级扫描，每遇到一个所属类别仍有名额的操作，就记录 s(v)=t 并扣除一个名额。某类别满了不妨碍扫描后面的其他类别。正延迟保证这一拍刚启动的操作不会在同一拍使后继就绪。
如果还有未安排操作，就跳到下一个可能改变决定的边界：已启动操作中最早的未来完成时刻，或者因名额不足留下就绪操作时的 t+1，取二者中较小者。这样长延迟空隙不必一拍一拍扫描。每次启动都会记录生产者的完成时间；“已经启动”绝不能当成“结果已经可读”。
直觉
拓扑序像菜谱上写的“先烤好面包，再夹馅”，时间表还得说明面包究竟几点出炉。就绪表只放材料已经齐全的工作，启动容量则是这一刻能接收多少新订单。正在烘烤的面包可以很多，但如果炉子的入口每分钟只能接收一个，就不能同一分钟送入两个。
关键路径优先的动机是尽早推动后续工作很多的操作。它没有预见所有竞争：两个当前高度相同的操作，可能分别占用未来关键端口或释放另一类别的端口。下面的反例保留这个平局规则，让“合法但不最优”成为可以逐拍检查的事实。
例子与边界
六条操作的两份时间表
设有主启动口 M 和辅助启动口 A，各自每拍容量1。它们是本例资源类别的名字，不意味着 M 只能乘法、A 只能加法。输入 x，六个结果全部需要交付：
| 操作 | 计算 | 延迟 | 资源 | 直接前驱 |
|---|---|---|---|---|
| A | a=x·x | 4 | M | 无 |
| B | b=x+1 | 3 | M | 无 |
| C | c=x−1 | 1 | M | 无 |
| D | d=2c | 1 | A | C |
| E | e=a+d | 1 | M | A、D |
| F | f=d+3 | 1 | M | D |
声明次序 A、B、C、D、E、F。逆拓扑求得 h=(5,3,3,2,1,1)。t=0 时 A、B、C 都就绪，先发 A。t=1 时 B 与 C 同为3，按声明次序发 B；t=2 才发 C。注意 B 的延迟为3，并没有阻止 M 在下一拍接收 C。
C 在 t=3 完成，D 同时启动并在 t=4 完成。A 也在 t=4 完成，所以 E、F 都已就绪；M 只有一个名额，先 E 后 F。时间表按 A 至 F 排列为 (0,1,2,3,4,5)，最后 F 在6完成。每一条边都满足完成后再启动，每个 M 启动时刻也互不相同。
改为时间表 (0,2,1,2,4,3)。这次 t=1 提前发 C，t=2 可以同时发主口的 B 与辅助口的 D；D 在3完成后立刻发 F，A 在4完成后发 E。最后 B、E 都在5完成，因此 T=5。x=4 时两份表都交付 (a,b,c,d,e,f)=(16,5,3,6,22,9)，只是完成时刻不同。
这里还能证明第二份表最优。M 上有五条操作，容量1，非负整数启动时刻中最后一次至少为4；所有延迟至少为1，所以任何表都有 T≥5。第二份达到5。这个证明针对本例，不把列表算法变成全局最优算法。
两种容易混淆的失败
若只取某个拓扑次序，然后每拍把下一条写进表，D 可能排在 C 的后面，却仍早于 C 的完成。拓扑关系只保障先后，不携带延迟。更小的反例是 u 延迟4、v 依赖 u；s(u)=0、s(v)=1 虽然顺序正确，依赖不等式却差3拍。
反过来，若把 L(v) 当成连续占用启动口的时长，就会把本例 B 在1启动、C 在2启动误判为冲突。那是另一种非流水机器的约束。本页的证书只检查启动时刻；若真实资源需要持续占用，必须改用占用区间或预约表，不能直接拿本页的合法证书作保证。
Brent 调度定理讨论单位时间任务与同质处理器上的工作量—深度保证。这里既有不同延迟，也有固定资源类别和流水启动能力，不能把操作数直接代入那个界而声称得到本算法的性能保证。
推论与应用
合法、终止及语义保持
不变量是：已安排的每条操作都有全部前驱的完成时间作证；每个已处理时刻、每个类别的启动数没有超过容量。初始化显然成立。算法只从就绪表取操作，并在扣减名额后记录，因此每一步保留两项性质。已经记录的启动时间不再改写，最终表满足全部不等式。
若还有未启动节点，无环性保证未启动子图中存在没有未启动前驱的节点。它的前驱不是已经完成，就是将在某个有限时刻完成。前一种情形有就绪操作，后一种情形有未来完成事件；因此算法不会无缘无故停住。每个时刻若没有启动，至少消费一个以前尚未经过的完成边界。把有启动的轮次记在某次唯一启动上，把无启动轮次记在某次完成上，总轮次不超过 2|V|。正有限延迟与正容量是此论证的条件。
对纯总操作，按依赖拓扑归纳可得值保持。初始输入相同；若所有直接生产者交付了与源表达式相同的值，操作在启动时读取的就是这些值，确定性计算得到同一个结果。时间表保证读取不早于交付，新鲜名字保证结果不会被其他操作覆盖。每个节点恰好执行一次，故全部输出相同。该证明没有把“端口合法”当成“所有源码依赖已经找全”的证明。
成本与下一步
令 n=|V|、e=|E|、r 为资源类别数。拓扑排序和高度计算需 O(n+e)；参考器为了透明，每轮重新扫描未发射节点及其前驱、排序就绪表，再扫描未来完成事件。因此总时间为
可执行终点交付实际启动表、就绪事件和按完成时刻读取的数值执行。先复算六拍表，再提交五拍证书和它的下界证明；随后把同一套“可读时间＋启动名额”约束扩展到跨迭代的模调度。后一页还必须保留原迭代距离，不能把循环直接当成这一张有限 DAG。
参考资料
- EPFL CS-420，Instruction scheduling，§2–4：依赖图、就绪/活动集合、启发式优先级与寄存器分配的接口。本页的固定资源模型、六操作反例和证明独立给出
- MIT 6.035，Instruction Scheduling，讲义页16–19、25–27：列表调度、路径高度与流水资源约束；本页明确采用完成先于同拍启动的边界约定