《AI Agent 技术原理与架构·运行时、协议与系统架构》10.3 死锁:环检测与预算

多智能体互相等待对方的结果,谁也动不了,就是死锁。环检测用 DFS 找等待环,预算限制用步骤上限防失控——两种手段分别回答'环在哪里'与'何时止损'。实验实现环检测与带预算的执行,演示检测到 a-b-c-a 环、无环场景返回空、预算耗尽强制终止,说明死锁要先检测环、再用预算兜底。

以下等待关系与预算步骤均为教学假设,不构成对任何真实系统、供应商或生产环境的承诺。“环是死锁的必要条件、预算兜底防失控"这两条不变,具体等待链与步骤上限按任务实测。

10.2 讲了意见不一怎么裁,这一节讲更凶险的协调故障:谁都在等别人,谁也动不了。死锁。环检测回答"环在哪里”,预算限制回答"何时止损"——两种手段一起用,才算把死锁管住。

环是死锁的必要条件

死锁的结构是环。A 等 B、B 等 C、C 等 A——没有人有进展,因为每个人都握着别人要的东西。检测死锁最直接的方法是检测等待环:把"谁在等谁"画成有向图,找一个环。

等待关系结构状态
a→b→c→a环死锁
a→b→c链,无环可进展

无环的链不是死锁——链上有尽头,等到头就能动。只有闭合的环才让所有人卡住。所以环检测的目标很明确:在有向等待图里找一个环,找到了就是死锁候选。

预算:环检测之外的止损

环检测发现环之后怎么办?打断环(中断某个等待)是修复,但检测本身有成本,而且环可能不是立刻出现。预算限制是第二道防线:给执行设步骤上限,超了就强制终止——不管是不是死锁,失控就是失控。

手段回答时机
环检测环在哪里每次等待发生时
预算何时止损步骤超限时

最小实验:环检测与预算执行

实验提供 find_cycle(DFS 带栈检测环)与 run_with_budget(步骤预算内执行,超限终止)。

# file: agp_lab/deadlock.py | write
# tier: 3
# verify: python3 -m unittest tests.test_deadlock
"""终止条件与死锁:环依赖检测与有界运行。

多 Agent 协作最危险的失败是死锁:A 等 B、B 等 C、C 等 A,谁都不动。
本模块实现有向环检测(识别等待环),以及步数预算终止(超限强制停止),
用于把"永不终止"变成"可判定的终止"。
"""
from __future__ import annotations

from typing import Any


def find_cycle(waiting: dict[str, str]) -> list[str]:
    """等待图(谁在等谁)中检测环,返回环路径;无环返回空。"""
    visited: dict[str, int] = {}  # 0=未访问 1=访问中 2=已结束
    stack: list[str] = []

    def dfs(node: str) -> list[str]:
        visited[node] = 1
        stack.append(node)
        nxt = waiting.get(node)
        if nxt is not None:
            state = visited.get(nxt, 0)
            if state == 1:
                return stack[stack.index(nxt):] + [nxt]
            if state == 0:
                cycle = dfs(nxt)
                if cycle:
                    return cycle
        stack.pop()
        visited[node] = 2
        return []

    for node in waiting:
        if visited.get(node, 0) == 0:
            cycle = dfs(node)
            if cycle:
                return cycle
    return []


def run_with_budget(
    state: str,
    step: int,
    max_steps: int,
) -> str:
    """按步数预算推进;超预算返回 'budget_exhausted'。"""
    if step >= max_steps:
        return "budget_exhausted"
    return f"step:{step}"


def demo() -> dict[str, Any]:
    cyclic = {"a": "b", "b": "c", "c": "a"}
    acyclic = {"a": "b", "b": "c", "c": None}
    return {
        "cyclic_detected": find_cycle(cyclic),
        "acyclic_none": find_cycle(acyclic),
        "budget_ok": run_with_budget("w1", step=4, max_steps=6),
        "budget_hit": run_with_budget("w1", step=6, max_steps=6),
        "budget_exceeded": run_with_budget("w1", step=8, max_steps=6),
    }


if __name__ == "__main__":
    for key, value in demo().items():
        print(f"{key}: {value}")

运行:

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

输出:

cyclic_detected: ['a', 'b', 'c', 'a']
acyclic_none: []
budget_ok: step:4
budget_hit: budget_exhausted
budget_exceeded: budget_exhausted

五条输出对应五件事:

  1. cyclic_detected:检测到环 ['a', 'b', 'c', 'a']。DFS 找到了闭合等待环——a 等 b、b 等 c、c 等 a。
  2. acyclic_none:无环场景返回空列表。链不是环,检测要区分——返回空说明没有死锁。
  3. budget_ok:4 个步骤在预算内完成,返回 step:4。预算内的执行正常推进。
  4. budget_hit:步骤正好撞上预算上限,返回 budget_exhausted。预算到顶就是止损点。
  5. budget_exceeded:需要更多步骤但超预算,同样 budget_exhausted。超限与撞限是同一个语义——执行被预算强制终止。

一个值得点破的细节:cyclic_detected 返回的是 ['a', 'b', 'c', 'a']——环的起点与终点是同一个节点。这是环的签名:走回自己。检测环的时候,不只是"有没有回头路",而是"是否走回出发点形成一个闭合回路"。预算输出的 budget_hit 和 budget_exceeded 都返回 budget_exhausted——预算语义是"超了就是超了",不区分恰好撞上还是越过。

环检测与责任链

死锁检测到环后,下一步要打断环。打断谁,要问责任——10.1 的责任链能定位环上每个节点的责任归属,帮决策"中断哪个节点代价最小"。责任链在这里不是记录,是决策输入:环上某个节点的负责人,就是可能被打断的对象。

环上节点责任者中断代价
a编排者高(任务主体)
b子任务中
c外部服务低

预算与容错的接口

预算不是只在死锁用。预算是一种通用的失控护栏,与 11 章容错呼应:熔断(11.2)是失败护栏,预算是步骤护栏。死锁的修复常常要配合补偿——打断环之后,环上已做的部分工作要回滚,这就是 11.3 的补偿。死锁检测是"发现问题",打断环是"止损",补偿是"善后",三个环节缺一不可。

环检测的分布式难题

单机环检测容易,分布式环检测难——等待图分散在各节点,谁都没见过全局图。分布式检测要么选一个协调者收集等待关系,要么每个节点局部检测自己的环。局部检测能抓到"自己的环"但抓不到"跨节点的环",协调者能抓全局但要承担收集成本。环检测的粒度是架构决策:牺牲实时性做全局检测,还是用局部检测换轻量。

方案覆盖成本
局部检测本节点环低,漏跨节点环
协调者汇总全局环高,收集延迟

死锁的预防

检测之外,还可以预防。死锁四条件:互斥、持有并等待、不可剥夺、循环等待——打破任何一个就能预防。最常用的是打破"循环等待":给资源定全局顺序,所有智能体按序申请,就不会成环。

条件预防手段
循环等待全局资源顺序
持有并等待一次申请全部
不可剥夺允许抢占
互斥只读不写(少用)

预防比检测更省成本。 检测要在每次等待时跑,预防在申请时就杜绝。但预防有限制——全局顺序要求智能体遵守规则,分布式下难统一。检测与预防不是互斥:低危场景检测兜底,高危场景预防为主。

超时与死锁

死锁常与超时混淆。超时是"等太久了",死锁是"谁都在等"——超时可能是死锁的征兆,也可能只是单纯慢。超时触发后要查等待图:等的是谁、谁在等谁,才能区分"慢"与"死锁"。

现象判定
单个请求超时可能只是慢
多个请求互等死锁嫌疑
超时后恢复非死锁

超时是死锁检测的低成本代理。 环检测(10.3 的 DFS)有成本,超时触发才跑——平时不检测,超时了才查等待图。这个"超时触发检测"的模式,与熔断的"失败触发打开"是同一类设计:低成本常态,高成本按需。

环检测的成本

环检测不是免费的。每次等待发生都跑 DFS,消息多、等待频繁时开销大。要么降低检测频率(周期检测),要么缩小检测范围(局部检测),要么按超时触发。环检测的成本与死锁的风险要平衡——死锁频发的系统值得高频检测,偶发的系统按超时触发够了。

策略成本发现时机
每次检测高立即
周期检测中下一个周期
超时触发低超时之后

检测成本是 9.2 通信成本的延伸——环检测的 DFS 要在节点间交换等待关系,消息量随节点数增长。检测方案要按通信成本选,不是越频繁越好。

环检测后的恢复

检测到环,中断之后要恢复。中断一个等待,环上其他节点继续——但要保证不重入死锁。恢复路径:被中断的节点放弃等待、重新规划;其他节点完成各自工作。恢复不是"解开环就完",是"解开后各节点还要收尾"。

步骤动作
中断放弃等待、记录
通知告知环上其他节点
收尾各自完成或补偿

恢复与 11.3 的补偿接缝。 中断时环上可能已有部分工作完成,放弃的节点要补偿(11.3 的补偿计划)。死锁处理从"检测"到"中断"到"补偿",是一条完整链。

预算的粒度

预算要定粒度。任务级预算管整个任务,子任务级预算管每个分支——粒度过粗,一个子任务死锁拖死全任务;粒度过细,预算检查开销大。常用的是分层预算:任务总预算 + 子任务各自预算,两者都超才终止。

粒度管什么代价
任务级整体子任务失控拖全局
子任务级分支检查开销
分层整体 + 分支平衡

分层预算与 11.1 的失败分类配套。 子任务超预算不是致命——按分类它是可终止的(超预算强制终止),终止后的善后走 11.3 的补偿。预算终止不是"失败完事",是"止损开始"。

架构判据

死锁处理是否合格,用五条判据检查:

判据合格的样子不合格的样子
环可检测DFS 找到闭合环等死才发现
无环不误报链不判成环假阳性打断正常链
预算兜底超限强制终止失控无限等
打断有依据用责任链定位随手打断
修复配补偿打断后回滚打断即数据残留

判据第一条是"环必须被检测出来",判据第三条才是关键:检测之外必须有预算兜底——环检测可能漏,预算不会漏。判据第五条是 10.3 与 11.3 的接缝——打断环不补偿,等于留半截工作。

小结

  • 死锁的结构是环,环检测是直接手段。
  • 无环的等待链不是死锁,检测要区分环与链。
  • 预算限制是第二道防线,超限强制终止。
  • 打断环要用责任链定位,找代价最小的节点。
  • 修复要配补偿,打断不等于善后。

阅读导航:上一节:10.2 仲裁:多数、优先级与版本 · 下一节:11.1 失败分类与扩散 。

常见错误与边界

  1. 等死才发现。 没有环检测,死锁只能靠超时撞上。
  2. 把链当环。 无环链是正常等待,误报会打断本可进展的流程。
  3. 只检测不兜底。 环检测可能漏,预算才是不会漏的止损。
  4. 随手打断。 打断环不看责任,可能打断任务主体。
  5. 打断不补偿。 环上工作已做一半,不回滚就留半截数据。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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