《AI Agent 技术原理与架构·运行时、协议与系统架构》3.1 队列、优先级与公平调度

高优先级任务持续到达时,严格优先级会让低优先级队列彻底饿死。实验用固定到达序列跑两种调度器:严格优先级把所有时间片给了高优先级,加权公平(DRR)按权重配额轮转,保证每个队列的最小份额。结论是高优先级要有优先权但不能无限优先,公平调度把优先权从占满改成配额。

以下到达率、权重、队列模型均为教学假设,不构成对任何真实系统、供应商或生产环境的承诺。weighted 的 {high:2, mid:1, low:1} 权重是讲解用的一组数字,真实调度器按服务等级协议分配,但"严格优先级会饿死低优先级"这一条不变。

Agent 系统里同时跑着很多任务:用户请求、后台检索、批处理。它们不可能都立刻执行,必须排队。这一节问:队列怎么排,才能既让高优先级任务快,又不把低优先级任务饿死?

答案是一个经典的取舍。严格优先级(每次都挑最高优先级)实现最简单,但高优先级持续到达时,低优先级会被无限期饿死。加权公平调度(DRR 风格)按权重配额轮转,保证每个队列的最小份额——优先权还在,但变成"配额"而不是"占满"。

为什么严格优先级会饿死

严格优先级调度器的规则只有一条:每次出队都挑最高优先级的非空队列。

这条规则在最坏情况下是什么效果?只要高优先级队列一直有任务(哪怕每个 tick 只来一个),调度器就永远轮不到低优先级队列。低优先级任务不是"慢",是"永远"。这正是饿死(starvation)的定义:不是延迟,是无限期得不到服务。

饿死的危害比"慢"更隐蔽:任务看起来还在队列里,状态正常,但没有进展。对 Agent 系统来说,饿死的可能是低优先级的批处理、后台索引、慢速重试——它们不急,但始终不来,最后以"超时"或"任务堆积"的形式爆发。

加权公平调度:优先权变成配额

加权公平调度(Deficit Round Robin 的简化版)换一条规则:每个队列有一个权重,每轮按权重配额服务,一个队列服务够了自己权重的次数就把机会让给下一个。

队列权重每轮配额含义
high22 次高优先级,拿双份
mid11 次中优先级
low11 次低优先级,至少每轮被服务一次

权重保证的是"最小份额",不是"绝对优先"。高优先级任务依然比低优先级多拿(2:1),但只要低优先级队列非空,它每轮都会轮到。优先权从"占满"变成"配额",饿死被消除。

最小实验:固定到达序列跑两种调度器

实验用固定的到达表(high 每 tick 1 个、mid 每 2 tick 1 个、low 每 3 tick 1 个)跑 60 个 tick,统计各队列完成数。

# file: agp_lab/scheduler.py | write
# tier: 3
# verify: python3 -m unittest tests.test_scheduler
"""队列、优先级与公平调度:严格优先级 vs 加权公平。

高优先级任务持续到达时,严格优先级会让低优先级饿死;
加权公平调度按权重配额分配带宽,保证每个队列的最小份额。

本模块用固定的到达序列跑两种调度器,统计各队列完成数,
并演示加权公平如何保证低优先级队列仍有产出。
"""
from __future__ import annotations

from collections import deque
from typing import Any


class StrictPriorityScheduler:
    """严格优先级:每次选最高优先级非空队列。"""

    def __init__(self, priorities: list[int]) -> None:
        self.priorities = list(priorities)
        self.queues: dict[int, deque[str]] = {p: deque() for p in priorities}

    def push(self, priority: int, task_id: str) -> None:
        self.queues[priority].append(task_id)

    def pop(self) -> tuple[int, str] | None:
        for priority in sorted(self.priorities, reverse=True):
            if self.queues[priority]:
                return priority, self.queues[priority].popleft()
        return None


class WeightedScheduler:
    """加权轮询(DRR 风格):每轮按权重配额服务,保证最小份额。"""

    def __init__(self, weights: dict[str, int]) -> None:
        self.weights = list(weights.items())
        self.queues: dict[str, deque[str]] = {name: deque() for name in weights}
        self.round_index = 0
        self.round_count = 0

    def push(self, name: str, task_id: str) -> None:
        self.queues[name].append(task_id)

    def pop(self) -> tuple[str, str] | None:
        for _ in range(len(self.weights)):
            name, weight = self.weights[self.round_index]
            if self.queues[name]:
                self.round_count += 1
                if self.round_count >= weight:
                    self.round_count = 0
                    self.round_index = (self.round_index + 1) % len(self.weights)
                return name, self.queues[name].popleft()
            self.round_count = 0
            self.round_index = (self.round_index + 1) % len(self.weights)
        return None


def simulate(kind: str, weights: dict[str, int] | None = None, ticks: int = 60) -> dict[str, int]:
    """跑固定到达序列,返回各队列完成数。

    kind 取值:"strict"(高 3 / 中 2 / 低 1)或 "weighted"。
    到达表:high 每 tick 1 个,mid 每 2 tick 1 个,low 每 3 tick 1 个。
    """
    weights = weights or {"high": 2, "mid": 1, "low": 1}
    sched: StrictPriorityScheduler | WeightedScheduler
    if kind == "strict":
        sched = StrictPriorityScheduler([3, 2, 1])
    else:
        sched = WeightedScheduler(weights)
    completed = {"high": 0, "mid": 0, "low": 0}
    seq = 0

    def arrival(step: int, name: str, every: int) -> None:
        nonlocal seq
        if step % every == 0:
            seq += 1
            if kind == "strict":
                sched.push({"high": 3, "mid": 2, "low": 1}[name], f"{name}{seq}")
            else:
                sched.push(name, f"{name}{seq}")

    for tick in range(ticks):
        arrival(tick, "high", 1)
        arrival(tick, "mid", 2)
        arrival(tick, "low", 3)
        picked = sched.pop()
        if picked:
            name = {3: "high", 2: "mid", 1: "low"}[picked[0]] if kind == "strict" else picked[0]
            completed[name] += 1
    return completed


def demo() -> dict[str, Any]:
    return {
        "strict": simulate("strict"),
        "weighted": simulate("weighted"),
    }


if __name__ == "__main__":
    for name, result in demo().items():
        print(f"{name:<10} completed={result}")

运行:

cd private/labs/agp-lab
python3 -m agp_lab.scheduler

输出:

strict     completed={'high': 60, 'mid': 0, 'low': 0}
weighted   completed={'high': 30, 'mid': 15, 'low': 15}

两行输出把取舍量化了:

  1. strict:high=60, mid=0, low=0。60 个 tick,高优先级到达 60 个,全部完成;中、低优先级 0 完成——完全饿死。这不是数字没跑对,是严格优先级的必然结果:只要 high 一直在,mid 和 low 永不出队。
  2. weighted:high=30, mid=15, low=15。同样的到达序列,加权公平下 high 完成 30(略少),但 mid 和 low 各有 15 完成——饿死被消除,每个队列都有产出。

两个值得点破的细节:

  • weighted 的 total 恰好 60(30+15+15),与 strict 的 60 一致。公平调度不是"浪费吞吐",而是把同一批时间片重新分配:从"全给 high"变成"按 2:1:1 分配"。在这个到达率下,high 该到 60 个只完成了 30,是因为 mid、low 的产出抢走了原本会被 high 占满的时间片——这是公平的代价,也是公平的收益:以 high 的一部分延迟,换 mid/low 的存活。
  • 实现上的坑:weighted 用的是 DRR 风格的轮转配额(每轮 high 服务 2 次、mid/low 各 1 次),不是"按权重算概率"的随机选择。轮转保证确定性:每个队列在每轮内至少被服务到一次,不会像概率式调度那样出现"低优先级这轮又没被抽中"的抖动。

调度策略的另一个维度是任务的估计耗时。同一优先级的任务,一个跑 1 秒、一个跑 10 分钟,严格按优先级轮转会让快任务被慢任务阻塞。生产调度器通常给任务标注估计耗时,配合优先级一起决定调度顺序;实验里权重只管了优先级维度,真实系统要再加一维。

优先级还会随时间变化。一个任务刚进来可能只是低优先级批处理,等用户开始等待它就升级。优先级不是任务的固有属性,而是随情境变化的动态值,调度器要支持在任务生命周期里调整优先级,而不是只读一次初始值。

维度调度决策风险
优先级谁先饿死低优先级
估计耗时快任务先走慢任务被饿死
权重配额最小份额高优先级延迟
动态调整随情境升级频繁升级引发抖动

公平调度的另一个被低估点是配额(fair share)与优先级的相互作用。优先级决定"下一个执行谁",配额决定"一段时间里谁拿多少份额"——两个维度可以冲突:高优先级任务如果不受配额约束,可能独占所有资源;低优先级任务如果只靠配额,可能在高负载下长期拿不到调度。生产调度器通常把两者叠起来:配额保底、优先级定序。

调度器保底定序饿死风险
纯优先级无优先级低优先级饿死
纯配额有无高优先级延迟
配额+优先级有优先级需要权重校准

配合背压(3.2),调度器的公平才完整。 调度决定"谁先执行",背压决定"装不下的任务怎么办";一个是排序问题,一个是容量问题。两者分开建模,但配置要一起调——调整背压队列容量会改变任务积压的分布,进而改变调度的负载形态。

调度策略的可观测性决定了能不能调对参数。要监控的不只是"任务最终完成",还有"每个优先级任务的平均等待时间、最大等待时间"。等待时间分布暴露饿死:低优先级任务的最大等待时间持续攀升,说明权重失衡。等待时间是调度器健康度最直接的信号。

指标观测什么异常信号
平均等待一般体验整体攀升
最大等待极端情况单个任务饿死
等待分布公平性低优先级长尾

参数调整也要有依据而不是拍脑袋:改变权重、改变队列容量,先跑模拟(如本实验的调度器)看等待分布变化,再上线。模拟与线上结合——模拟器给参数范围,线上观测校准范围。

调度还有一个批次语义值得注意:批量任务的调度粒度不是单个任务,而是"一批"。一批任务一起提交、希望一起完成;调度器若把一批拆散到不同优先级段,批的完成时间取决于最慢的一个。批任务的调度要把"整批"当调度单元,或至少保证批内任务同优先级——否则一个批被拆散,等待时间被最差成员决定。

调度单元优点缺点
单个任务灵活批完成时间不可控
整批调度批完成可预期批间资源分配粗糙

架构判据

调度策略是否合格,用五条判据检查:

判据合格的样子不合格的样子
无饿死每个非空队列都有产出低优先级队列永远无进展
优先权保留高优先级拿更多配额高低无差别,全均分
确定性轮转配额,结果可预测概率式选择,抖动大
权重可配置权重按 SLA 调整权重写死在代码里
可观测每队列延迟/产出可统计队列状态黑盒

判据第一条"无饿死"是硬门槛:优先权可以给,饿死不能有。 如果观测到某个队列持续无产出,优先改调度策略而不是加大该队列的优先级——后者只会让情况更糟。

小结

  • 严格优先级实现简单,但高优先级持续到达时低优先级会被饿死——不是慢,是无限期。
  • 加权公平调度(DRR)按权重配额轮转,保证每个队列的最小份额;优先权从"占满"变成"配额"。
  • 实验量化了取舍:同一到达序列,strict 只有 high 有产出,weighted 让三个队列都有产出。
  • 优先权可以给,饿死不能有;可观测性是发现饿死的前提。

阅读导航:上一节:2.3 崩溃恢复:重放、补偿与故障注入 · 下一节:3.2 并发上限、背压与取消 。

常见错误与边界

  1. 只加优先级不防饿死。 高优先级任务持续到达时,低优先级永远轮不到;必须用配额机制兜底。
  2. 把公平当均分。 加权公平不是人人一份,是按权重给份额;权重体现 SLA 差异。
  3. 用概率式选择冒充轮转。 随机抽样会让低优先级偶尔连续多轮不被抽中,饿死从确定性变成概率性。
  4. 权重写死。 权重应随服务等级协议可配置;写死之后没法在不改代码的前提下调平衡。
  5. 没有可观测性。 队列状态黑盒时,饿死已经发生很久才被发现;每队列延迟、产出要可统计。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图