跳转至
ACCEPTED

AIOS · RUNQ 调度算法规范 v1.0

关联:本文件是 ADR-AIOS-06 §2.6 的展开实施手册。 配合 Process-Model.md(进程/线程定义)+ Commit-Convention.md(commit 校验)+ Concurrency-Domains.md(并发域配置)使用。

1. RUNQ 总览

1.1 RUNQ 是什么

RUNQ(Ready Queue · 就绪队列) = AIOS 内核维护的"当前所有 ready 状态 U-thread 的优先排序视图"。

  • 数据源:全局 PCB(各进程 PROCESS.md 的 user_threads 数组)
  • 过滤规则:state == ready && blocked_on == null
  • 重算时机:每日 standup · 用户派活 · ADR 触发 · U-thread 完成 commit 后
  • 持久化:docs/08-implementation/40-aios/RUNQ.md(每次重算覆盖写入)

1.2 RUNQ 与 PCB 的真值关系

PCB(processes/<pid>/PROCESS.md · 真值源)
  ├── kernel_threads[]   ← 永远存在 · 不进 RUNQ
  └── user_threads[]
       ├── ready    ──→ 进 RUNQ
       ├── running  ──→ RUNQ 标"已派发" · 含 bound_cpu
       ├── blocked  ──→ 不进 RUNQ · 但显示在 RUNQ.md §阻塞清单
       └── zombie   ──→ 不进 RUNQ · 归档到 archive/

1.3 K-thread 不进 RUNQ 的原因

K-thread 是模块所有权登记 · 不是任务 · 永远存在 · 没有"等待派发"语义。RUNQ 调度算法仅在 §3 步骤 3 把 K-thread 当前置约束校验,不调度它们。

2. 优先级体系

2.1 四级优先级 + HARD-DEADLINE 加成

优先级 含义 典型场景
P-1 系统级 · 阻塞所有其他任务 P_contracts.U-freeze-tag(Day 5 EOD)· 紧急 hotfix
P0 当周硬截止 / 主路径任务 P5.U-source-sink-api(Week 3 末)· P2.U5 module-uid-namespace
P1 主路径但有缓冲 P1.U1 xilink-finalize · P3.U4 test-aux-extract
P2 后续路径 / 优化项 P3.U-test-fix-post-p0 · 文档同步

HARD-DEADLINE 加成:hard_deadline: true 的 U-thread 在排序时优先级临时 +1(P0 → P-1 · P1 → P0)· 但不修改原始 priority 字段(便于硬截止解除后回滚)。

2.2 优先级冲突仲裁

同优先级多 U-thread 候选时按以下顺序排序:

  1. hard_deadline: true 优先(临时升级)
  2. eta 距今最近的优先
  3. created 最早的优先(FIFO)
  4. PID 字典序(P0 < P1 < ... < P_contracts < P_arch)

3. RUNQ 6 步调度算法(核心)

本算法在每次 RUNQ 重算时执行 · 由 AIOS 调度内核(Cline-AIOS)运行。

Step 1 · 过滤候选集

INPUT: 全部进程的 PCB.user_threads
FILTER:
  state == "ready"
  AND blocked_on == null
OUTPUT: 候选 U-thread 集合 C

注意:state == blocked 的 U-thread 不进候选 · 但在 RUNQ.md §阻塞清单展示(供人类查看)。

Step 2 · 优先级排序

INPUT: 候选集 C
SORT BY:
  1. effective_priority = priority - (hard_deadline ? 1 : 0)   # P-1 最小最高
  2. eta ASC(NULL last)
  3. created ASC
  4. pid ASC
OUTPUT: 排序后候选队列 Q

Step 3 · K-thread 可获取性校验(核心)

INPUT: 排序后候选队列 Q
FOR EACH U IN Q:
  available = TRUE
  FOR EACH K IN U.occupies:
    K_state = lookup(K)         # 从 PCB.kernel_threads 查
    IF K_state != "sleeping":
      available = FALSE          # 该 K 已被其他 U 占用 · 跳过
      BREAK
  IF available:
    DISPATCH(U)                  # 进入 Step 4
  ELSE:
    SKIP(U)                      # 留到下一轮 RUNQ
OUTPUT: 通过校验的 U-thread 集合 D

冲突示例: - 候选 P3.U-x 占用 [P3.K7] - 候选 P3.U-y 占用 [P3.K7] - 同一轮派发:U-x 先派(优先级高) → P3.K7 状态变 running → U-y 校验失败 · 等下一轮

Step 4 · CPU 选择(缓存亲和性)

INPUT: 通过校验的 U-thread U
ALGORITHM:
  candidates = ALL idle CPUs in 并发域 A + 可调度的并发域 B Workers

  # 缓存亲和优先
  hot_cpu = lookup_last_cpu_for_kthreads(U.occupies)
  IF hot_cpu IN candidates AND hot_cpu.idle:
    bind(U, hot_cpu)
    RETURN

  # 主战场亲和(v0.3 新增 · 见 Concurrency-Domains.md)
  main_cpu = lookup_main_battlefield(U.pid)
  IF main_cpu IN candidates AND main_cpu.idle:
    bind(U, main_cpu)
    RETURN

  # 副战场 fallback
  sub_cpu = lookup_sub_battlefield(U.pid)
  IF sub_cpu IN candidates AND sub_cpu.idle:
    bind(U, sub_cpu)
    RETURN

  # 最闲 CPU
  bind(U, least_busy(candidates))
OUTPUT: U.bound_cpu = <CPU>

缓存亲和性的查找规则: - 遍历 U.occupies 中所有 K-thread - 取每个 K-thread THREAD.md 的 last_modified_by 字段 - 解析最近完成的 U-thread → 查 last_commit 的 git author - 同一 author 出现次数最多者 = hot_cpu

Step 5 · 派发执行

INPUT: U + bound_cpu
ACTIONS:
  1. U.state: ready → running
  2. U.bound_cpu = <CPU>
  3. U.dispatched_at = NOW
  4. FOR EACH K IN U.occupies:
       K.state: sleeping → running
       K.held_by = U.uid
  5. 写回 PCB(processes/<pid>/PROCESS.md)
  6. 写回 RUNQ.md(标 [running] · 含 bound_cpu)
  7. 通知用户(standup 输出 · 派发提示词文件)

Step 6 · 回收(U commit 完成时触发)

TRIGGER: 收到 commit hash · message 含 [pid=P_x] [uid=U_y]
ACTIONS:
  1. U.state: running → zombie
  2. U.completed_at = NOW
  3. U.last_commit = <hash>
  4. FOR EACH K IN U.occupies:
       K.state: running → sleeping
       K.held_by = null
       K.last_modified_by = U.uid + "(zombie · " + completed_at + " · commit " + hash + ")"
  5. 移动:processes/<pid>/user_threads/U_y-<name>/  →  archive/U_y-<name>/
  6. 写回 PCB · 写回 RUNQ.md(移除该行)
  7. 触发下一轮 RUNQ 重算(因为有 K-thread 释放了 · 之前被卡住的 U 可能可派)

4. 缓存亲和性详解

4.1 三级亲和层级

等级 含义 触发条件
hot 最近 24h 内同 CPU 跑过该 K-thread last_modified_by.author 与候选 CPU 匹配
warm 最近 7 天内同 CPU 跑过该 K-thread 历史 commit 匹配但超 24h
cold 该 CPU 从未碰过该 K-thread 默认状态

4.2 主战场作为"软亲和"补充(v0.3)

当 last_modified_by 字段不足以判断(如 K-thread 全新创建)时: - 使用 Concurrency-Domains.md 中定义的"主战场表"作为软亲和 - 例:U-thread 占用 P5.K1-controllers · 主战场 = ClaudeB → 默认派给 ClaudeB

4.3 work-cline 滞后场景的特殊处理

work-cline/ 当前 HEAD 滞后 xistudio 19 commit · Cline-Worker 此时 affinity = cold(因为不持有任何 K-thread 最近的 last_modified_by)。

处理策略: - AIOS 在派发前先要求 Cline-Worker git rebase xistudio 同步 - 同步完成后亲和性按"最近 commit author"重算 - 在同步完成前,Cline-Worker 仅作为 cold fallback 候选

5. 文件冲突避免(并发域 A 文件级隔离)

5.1 file_claims 子集校验

U-thread 入 RUNQ 时必须确保:

U.modified_files ⊆ ⋃ K.file_claims  for all K in U.occupies

例: - U 修改 stages/xitune/TuningModeSwitcher.vue - U.occupies = [P3.K5] - P3.K5.file_claims = [stages/xitune/toolbar/*] - ❌ 校验失败:TuningModeSwitcher.vue 不在 toolbar/* 范围

正例: - U 修改 stages/xitune/toolbar/TuningModeSwitcher.vue - U.occupies = [P3.K5] - ✅ 通过

5.2 K-thread file_claims 重叠场景

当多个 K-thread 的 file_claims 范围重叠(如 stores/linkStore.ts 同时被 P1.K7 和 P3.K7 声明):

场景 处理
P1.K7 = read-write owner · P3.K7 = read-only reference U 写 linkStore.ts 必须 occupies=[P1.K7] · 不能用 P3.K7
同时 read-only(罕见) 任何 occupies 至少含一个即可

写权限注册原则: - 一个文件全局只能有一个 K-thread 声明 read-write 权限(写所有者) - 其他 K-thread 只能声明 read-only 引用 - 在 K-thread THREAD.md 中通过 access 字段明示

6. 全栈 10 进程派发示例

U: P3.U-call-refresh-link
occupies:
  - P3.K7 (P3 stores · read-write)
  - P_contracts.K1 (read-only · 因为引用协议规范)
  - P0.K-shared-types (read-write · 改 types/refresh-link.ts)
ipc_channels:
  - to: P5-backend-csharp
    via: P_contracts.K1-protocol-v1
    section: §5 refresh-link

Step 3 校验:
  P3.K7      = sleeping?  ✅
  P_contracts.K1 = sleeping?  ✅(其他人没在改 protocol-v1.md)
  P0.K-shared-types = sleeping?  ✅
  → 全通过 · 派发

Step 4 CPU 选择:
  hot:    types/refresh-link.ts last_modified_by = ClaudeA(2 天前)
  main:   P3 主战场 = ClaudeA(机动)
  → bind(U, ClaudeA)

Step 5 派发:
  P3.K7.state         = running (held_by=P3.U-call-refresh-link)
  P_contracts.K1.state = running
  P0.K-shared-types.state = running
  U.bound_cpu = ClaudeA · U.state = running

注:期间任何想改 protocol-v1.md 的 U(包括 ClaudeB 的 B1-B4)都会被卡住。
→ 这正是 v0.3 P_contracts 独立提升的目的:跨栈契约竞争显式化。

6.2 后端域并行派发(P5 内部多 U)

当前 RUNQ 候选:
  P0  P5.U-refresh-link    (occupies P5.K4+P5.K5+P_contracts.K1)
  P0  P5.U-source-sink-api (occupies P5.K1+P5.K2+P_contracts.K1)
  P1  P5.U-preset-crud-api (occupies P5.K1+P5.K2+P5.K9)

Step 3 校验(假设 P_contracts.K1 已被 ClaudeB B1 占用 · running):
  P5.U-refresh-link:   P_contracts.K1=running → ❌ 跳过
  P5.U-source-sink-api: P_contracts.K1=running → ❌ 跳过
  P5.U-preset-crud-api: P5.K1=sleeping P5.K2=sleeping P5.K9=sleeping → ✅ 可派发

→ 派 P5.U-preset-crud-api 给 ClaudeB(主战场)
→ 其他两个 U 等 P_contracts.K1 释放

6.3 P_arch 架构事件派发(本 ADR 自身)

当前 P_arch/ADR-06 user_threads:
  U1-write-process-model    (zombie · ✅ 完成)
  U2-write-scheduling-algo  (running · 本文件)
  U3-write-commit-convention(ready)
  U4-write-concurrency-domains(ready)
  U5-migrate-prompts        (blocked · blocked_on=U3+U4)
  U6-split-kanban-pcb-runq  (blocked · blocked_on=U5)
  U7-update-roster-clinerules(blocked · blocked_on=U6)
  U8-build-backend-dsp-py-skeleton(blocked · blocked_on=U7)

Step 1 过滤:U2(running 不进新派) · U3 + U4 进候选
Step 2 排序:U3 与 U4 同优先级 · created 早者优先 = U3
Step 3 校验:P_arch 类进程没有 K-thread · occupies=[] · 永远通过
Step 4 CPU:全部由 Cline-AIOS 自己跑(arch 进程的 owner 是 AIOS)
Step 5 派发:U3 → Cline-AIOS · 启动写 Commit-Convention.md

7. 阻塞与升级机制

7.1 blocked 状态的两种来源

来源 处理
依赖未完成(如 U5.blocked_on = U3+U4) U3+U4 zombie 后 AIOS 自动解除 blocked → ready · 重新进 RUNQ
等契约 freeze(如等 Day 5 EOD protocol-v1) 需用户拍板或时间到达 · AIOS 不自动解除

7.2 ETA 滞后自动升级 🔴

来自 ADR-AIOS-01 v3 决议(铁律 6):ETA 滞后 ≥ 2 天自动升级 🔴

实施细节: - AIOS 每日 standup 时检查所有 running U-thread 的 eta 字段 - running_days >= eta_days + 2 时: - 标 🔴 严重滞后 - 写入 RUNQ.md §异常清单 - standup 输出 §需要你拍板的事项 包含该项

7.3 3 个硬截止(从 ADR-AIOS-01 继承)

硬截止 RUNQ 处理
Day 5 EOD P_contracts.K1-protocol-v1 freeze P_contracts.U-freeze-tag 优先级 P-1 · 一旦延期立即升级人类
Week 3 末 P5.U-source-sink-api hard_deadline=true · 临时 P0→P-1
Week 5 末 P5.U-preset-crud-api hard_deadline=true · 临时 P1→P0

8. RUNQ.md 文件格式

8.1 完整 schema(Markdown 表格)

# RUNQ · AIOS 就绪队列 · 2026-05-26 standup

## §1 当前 running U-thread

| 优先级 | PID.UID | Name | Occupies | Bound CPU | Affinity | dispatched_at |
|---|---|---|---|---|---|---|
| P0 | P5.U-refresh-link | refresh-link-finalize | P5.K4+P5.K5+P_contracts.K1 | Copilot-Worker | hot | 2026-05-25 16:00 |

## §2 ready 候选(按优先级排序)

| 优先级 | PID.UID | Name | Occupies | Affinity Hint | ETA |
|---|---|---|---|---|---|
| P-1 | P_contracts.U-freeze-tag | freeze-protocol-v1 | P_contracts.K1 | ClaudeB(hot) | Day 5 EOD ⚠️ |
| P0 | P2.U5 | module-uid-namespace | P2.K7+P0.K-shared-types | ClaudeA(hot) | Day 4 |
| P0 | P2.U3 | widget-registry | P2.K7 | ClaudeA(cold) | Day 6 |
| P1 | P1.U1 | xilink-finalize | P1.K3+P1.K5+P1.K6 | ClaudeA(hot) | Day 5 |
| P1 | P3.U4 | test-aux-extract | P3.K3+P0.K-shared-test-aux | ClaudeC/D(cold) | Day 9 |

## §3 blocked 清单

| PID.UID | Name | blocked_on | 解除条件 |
|---|---|---|---|
| P_arch.ADR-06.U5 | migrate-prompts | U3+U4 | U3 与 U4 完成后自动解除 |

## §4 异常 / 升级事项

(空 · 当前无 ETA 滞后超 2 天的项)

## §5 派发建议(本轮 standup)

- ClaudeB → P_contracts.U-freeze-tag(P-1 · HARD-DEADLINE)
- ClaudeA → P2.U5(P0 · HARD-DEADLINE)
- ClaudeC → P3.U4(P1 · 主战场机动)

8.2 重算时机的 commit 规范

每次 RUNQ 重算后必须 commit · message 形如:

chore(P_arch.ADR-06/runq-recompute): standup 2026-05-26 RUNQ 重算

[step=N/M] [pid=P_arch] [uid=U-runq-recompute]
[occupies=none] [files=docs/08-implementation/40-aios/RUNQ.md]
[ipc=none]

9. 与 ADR-AIOS-01 v3 决议的兼容性

ADR-01 决议项 在 RUNQ 中的实现
5 角色矩阵 + 跨栈职能解耦 Step 4 CPU 选择 · 主/副战场作为软亲和
任何 status 变更必须附 commit hash Step 6 回收 · last_commit 必填
3 个硬截止延期立即升级人类 §7.3 + §8.1 §4 异常清单
ETA 滞后 ≥ 2 天自动升级 🔴 §7.2
跨智能体不直接对话 · 通过 AIOS 中转 任何 U-thread [need: ClaudeB] trailer 进入 §4 异常清单 · AIOS 翻译为 ClaudeB 的新 U-thread

10. 验收清单

任何 RUNQ 重算后需通过以下校验:

  • RUNQ.md §1 running U 数 ≤ 可用 CPU 数
  • §2 ready U 全部通过 K-thread 可获取性校验
  • §3 blocked 清单的 blocked_on 指向真实 U-thread
  • §4 异常清单含全部 ETA 滞后 ≥ 2 天的项
  • §5 派发建议 CPU 与 §1 running 不冲突
  • commit message 含 [pid=P_arch] [uid=U-runq-recompute]

11. 文档元信息

  • 创建:2026-05-26 17:15 · Step B · T3(ADR-AIOS-06 v0.3 实施)
  • 版本:v1.0
  • 同栈姊妹文档:Process-Model.md / Commit-Convention.md / Concurrency-Domains.md