以下等待关系与预算步骤均为教学假设,不构成对任何真实系统、供应商或生产环境的承诺。“环是死锁的必要条件、预算兜底防失控"这两条不变,具体等待链与步骤上限按任务实测。
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
五条输出对应五件事:
- cyclic_detected:检测到环
['a', 'b', 'c', 'a']。DFS 找到了闭合等待环——a 等 b、b 等 c、c 等 a。 - acyclic_none:无环场景返回空列表。链不是环,检测要区分——返回空说明没有死锁。
- budget_ok:4 个步骤在预算内完成,返回
step:4。预算内的执行正常推进。 - budget_hit:步骤正好撞上预算上限,返回
budget_exhausted。预算到顶就是止损点。 - 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 失败分类与扩散 。
常见错误与边界
- 等死才发现。 没有环检测,死锁只能靠超时撞上。
- 把链当环。 无环链是正常等待,误报会打断本可进展的流程。
- 只检测不兜底。 环检测可能漏,预算才是不会漏的止损。
- 随手打断。 打断环不看责任,可能打断任务主体。
- 打断不补偿。 环上工作已做一半,不回滚就留半截数据。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。