07-EFT.WP.Core.Threads v1.0 | 第2章 执行图与调度

目录 ／ 文档-技术白皮书 ／ 07-EFT.WP.Core.Threads v1.0

第2章 执行图与调度

I. 范围与目标

• 建立执行图 G = (V,E) 的数据模型、成本模型与可调度性条件，给出 makespan 近似式与上下界。
• 定义可复用的优先级启发式与资源绑定策略，覆盖异构资源、亲和性、截止期与背压协同。
• 产出流程 Mx-1（DAG 调度流程）、最小方程 S72-*、公设 P72-* 与 TS.* 观测字段映射。

II. 执行图模型与基本对象

1. 图与节点
   • G = (V,E) 为有向无环图（DAG）；dep(u,v) 表示从 u 到 v 的先行约束；源集合 Src(G)，汇集合 Sink(G)。
   • 节点属性：w(v)（执行成本）、affinity(v)、quota(v) ⊆ {R_cpu,R_mem,R_io}、deadline(v)|None、prio(v)|None。
2. 边与转移
   e = (u -> v) ∈ E，边成本 c(e)（数据传输或同步开销）；边标签：size(e)、locality(e)、sem(e)（消息语义）。
3. 就绪集与事件
   就绪条件：pred(v) ⊆ Done ⇒ v ∈ Ready(t)；事件 eid 记于 TS.*，因果以 hb 记录。

III. 成本模型与 makespan（S72 系列）

1. 工作量与跨度
   • 总工作量：W_tot(G) = ( ∑_{v∈V} w(v) ) + ( ∑_{e∈E} c(e) )。
   • 跨度（关键路径代价）：Span(G) = ( ∑_{v∈crit(G)} w(v) ) + ( ∑_{e∈crit(G)} c(e) )。
2. 最小方程（核心近似）
   • S72-1（关键路径近似）：T_make(G) approx Span(G)。
   • S72-2（工作–跨度下界）：T_p(G) >= max( W_tot(G) / p_eff , Span(G) )，其中 p_eff <= K_thr_total 且受就绪宽度约束。
   • S72-3（开销校正）：T_make(G) approx T_p(G) + alpha * |V| + beta * ctx_switch + gamma * migrations。
3. 并行度与可达上限
   • 平均并行度：A(G) = W_tot(G) / Span(G)；理论上 T_p(G) >= W_tot(G) / min(p_eff, A(G))。
   • 局部资源束缚：若某类资源 R_k 为主导，则 p_eff <= floor( capacity(R_k) / demand_max_k )。
4. 流式稳态与 Little 定律
   对于 steady-state stage，L = lambda * W，要求 rho = lambda / mu < 1；W 以 tau_mono 计量。

IV. 公设与约束（P72-*)

• 公设 P72-1（无环与完备）：G 必为 DAG，Src(G)、Sink(G) 非空；每个 v 的 w(v) 与每个 e 的 c(e) 必给出估计或上界。
• 公设 P72-2（时钟一致）：一切时间度量使用 tau_mono；发布用 ts 落库（见第1章 P71-1）。
• 公设 P72-3（稳态可行）：任一可运行队列需满足 rho < 1，否则必须配置 bp 或限流。
• 公设 P72-4（亲和与配额）：map(v) -> worker 不得违反 affinity(v) 与 quota(v)；资源不足触发 throttle 或延迟。
• 公设 P72-5（幂等容错）：跨机边 e 若 sem="at_least_once"，则 v 必声明 idemp_key 与 Delta_t_dedup。
• 公设 P72-6（关键路径优先）：启发式应使 crit(G) 上任务优先级不低于非关键任务。

V. 调度目标与代价函数

1. 目标族
   minimize T_make(G)；满足 deadline(v) 与 SLO；maximize utilization；bounded memory；minimize cross-host traffic。
2. 统一评分
   • score(v, w_i) = a * rank_cp(v) - b * slack(v) - d * penalty_loc(v, w_i) - m * mem_pressure(w_i) + r * reuse_cache(v, w_i)。
   • slack(v) = deadline(v) - est_finish(v)；rank_cp(v) 为关键路径向后层级（见下节）。

VI. 优先级启发式与算法

1. 拓扑就绪队列（基础）
   Ready(t) 以拓扑序维护；就绪节点按 prio(v) 或 rank_cp(v) 选择；空闲 worker 立即抢占就绪集头部。
2. 关键路径排序（CP/HEFT 风格）
   • 递推定义 rank_cp(v) = w(v) + max_{(v->u)∈E}( c(v,u) + rank_cp(u) )；无后继时取 rank_cp(v)=w(v)。
   • 策略：就绪集中优先较大 rank_cp 的节点；异构放置选 EFT 最小的 worker。
3. 最长处理时间优先（LPT）
   当 deadline=None 时，LPT 近似最小化 makespan：就绪集中按 w(v) 降序投放。
4. 截止期驱动（EDF）
   对存在 deadline(v) 的节点，按最早截止期优先；可用 slack(v) 协助打分。
5. 本地性与批合并
   对高 c(e) 边，倾向将相邻节点同放；对微任务可按 batch_size 合并为单工作单元。

VII. 资源绑定与放置

• 工作器与容量
  worker_i 拥有 cap(worker_i) = {cpu_i, mem_i, io_i, accel_i?}；队列服务率 mu_i 依任务画像估计。
• 约束满足
  feasible(v, worker_i) 当且仅当 quota(v) ⊆ cap_free(worker_i) 且满足 affinity(v) 与 cgroup。
• 提前结束时间（EFT）
  EFT(v, worker_i) = avail(worker_i) + setup(v, worker_i) + w_i(v)，其中 w_i(v) 为 worker 特定执行代价；选择 argmin EFT。
• 迁移与抢占
  迁移成本计入 gamma * migrations；对可中断任务，抢占保存 ctx 的 beta 开销。

VIII. 背压、限流与队列稳定

• 每队列稳定条件：rho_k = lambda_k / mu_k < 1；拥塞信号 bp_k = f(q_len, cap, W_q) 单调递增。
• 策略协同
  当 bp_k 超阈，触发上游限流或合并批；当 cap 达上限，策略为 delay|drop|shed，并上报 TS.sli.err_rate 与 TS.drop.count。
• 服务水平
  目标 P99(latency_ms) <= SLO；调度可提升 rank_cp 权重或扩容 p_eff。

IX. 截止期、超时与重试

• 超时组合上界
  W_retry <= timeout * (retries + 1) + J_total；对链路 e 取 J_total 为端到端抖动和。
• 调度器策略
  with_timeout 包裹节点；失败按 retry(policy) 重投；若 sem!="at_most_once" 必以 ensure_idempotent 包裹处理函数。
• 可抢占性
  对 deadline 紧张节点采用抢占（可中断）或提权（临时提升 prio）。

X. 图规范与不变量

1. 规格字段（建议最小集）
   • nodes: [ {id, w_est, affinity?, quota?, deadline?, prio?, tags?} ]
   • edges: [ {from, to, c_est, size?, sem?, locality?} ]
   • graph: {gid, name, version, created_ts}
2. 不变量
   acyclic(G)=true；gid 全局唯一；∑ demand(mem) on worker_i <= mem_i；跨卷字段以 TS.* 落库。

XI. 调度流程 Mx-1（标准化）

• import spec -> build_graph(spec) -> GraphRef。
• validate(G)：DAG 检查、w/c 存在性、affinity/quota 合法性、rho 初算。
• rank_cp(all v) 并初始化就绪队列 Ready(0)。
• place：对每个空闲 worker_i，从 Ready(t) 选 v，按 score(v, worker_i) 与 EFT 放置。
• run_graph(G, inputs, opts)：执行、收集 TS.* 指标；周期性重估 w_i(v) 与 mu_i。
• bp/limit：监听 bp_k 与 rho_k，动态调 K_thr、批大小与限流。
• contract：assert_thread_contract(G, tests) 校验 SLO/deadline/err_rate。
• export：持久化 Trace、TS.*、gid 与 schema_version。

XII. 观测与度量（TS. 对齐）*

1. 关键字段
   • TS.sli.queue_time_ms、TS.sli.run_time_ms、TS.sli.latency_ms、TS.sli.p99_ms、TS.sli.err_rate、TS.sli.qps。
   • TS.thr.K_thr、TS.chan.cap、TS.backpressure.level、TS.retry.count、TS.timeout.count、TS.drop.count。
2. 关联关系
   Span(G) 的在线估计可由 trace_span 的最长链路近似；W_tot(G) 由所有 w(v) 与 c(e) 的滑窗和估计。

XIII. 策略模板（可直接套用）

• 批处理（无截止期）
  排序：LPT；放置：EFT；批量：大批；目标：min T_make；收敛条件：rho_k < 1。
• 在线服务（有截止期）
  排序：EDF + rank_cp 加权；放置：本地性优先（最小 penalty_loc）；批量：小批或单件；目标：P99。
• 事件流（背压驱动）
  排序：rank_cp；放置：跨 stage 复用缓存；批量：自适应；目标：rho 稳定与丢弃率最小。

XIV. 跨卷绑定与到达时引用

1. 若以传播到达时 T_arr 做时序校准或网络传播估计，采用两口径：
   • 常量外提：T_arr = ( 1 / c_ref ) * ( ∫ n_eff d ell )
   • 一般口径：T_arr = ( ∫ ( n_eff / c_ref ) d ell )
2. 差异报告：delta_form = | ( 1 / c_ref ) * ( ∫ n_eff d ell ) - ( ∫ ( n_eff / c_ref ) d ell ) |。
3. 路径与测度：声明 gamma(ell) 与 d ell，避免与执行图 G 混淆。

XV. 契约与测试要点

• acyclic(G)=true；crit(G) 不为空；rho_k < 1；P99 <= SLO；deadline miss rate <= bound。
• idemp_key 一致性；affinity/quota 不被破坏；TS.* 字段齐备与量纲校核 check_dim( L - lambda * W ) = 0。

XVI. 出厂条件与交付件

• 通过 S72-* 校核与 P72-* 约束；Mx-1 全流程跑通且产出 gid、Trace、TS.*。
• 交付 spec、rank_cp 报告、rho 稳态评估与 SLO 达成证明；提供三类场景的策略参数表与回归基线。