5.1 资源竞争：车道、水井与死锁

5.1 资源竞争：车道、水井与死锁

摘要：多个自利镇民抢有限资源，会生四种病：竞争浪费、饿死、死锁、活锁。本节盘点病症、解剖死锁四条件与四条应对路线（预防、避免、检测恢复、鸵鸟政策），用代码复现十字路口互不相让的死锁与按序申请的解法，并比较信号灯与环岛两种"路口治理"的工程哲学。

枯水期的水井边，天不亮就排起了桶。有人加塞、有人占着辘轳聊天、有人干脆搬来小板凳打持久战——最后井台堵死，谁也打不上水。这一幕是多智能体系统最古老的病灶：资源竞争。第 4 章讲的是"把活分好"让竞争不发生，这一章讲竞争发生了怎么办。本节是法庭的第一类案子：没有恶意、没有欺骗，只是大家都要用同一件东西，就足以把系统逼进死角。

四种病症：从浪费到卡死

竞争浪费：多个镇民无协调地抢同一资源，撞车、重复劳动、互相干扰。无人机都去扫同一片火场，边缘没人管——第 4 章的市场与协调机制治的就是它。

饿死（starvation）：资源总被别人抢走，某个镇民永远排不上队。调度策略若只看紧急度，慢任务可能永远让路——公平性条款（最长等待优先、轮转配额）是特效药。

死锁（deadlock）：一组镇民互相握着对方要的资源，循环等待，全体冻结。木匠拿着钉子等锤子，铁匠拿着锤子等钉子，两人在工棚里站到天黑。

活锁（livelock）：都在动，都在让，就是没人能前进。窄桥两端的两辆车同时后退、同时前进、同时再后退——礼貌过度也是一种病。死锁是"都不动"，活锁是"白动"，分辨全靠看有没有进展。

死锁四条件：病理切片

教科书总结的死锁四条件，四个同时成立才会发病：互斥（资源一次只能一人用）、持有并等待（握着手里的，还要别人的）、不可剥夺（抢不走，只能主人放手）、循环等待（等待链闭合成环，A 等 B、B 等 C、C 又等 A）。四条像四根支柱，抽掉任何一根，死锁就塌。于是有了四条应对路线：

预防（结构上拆条件）：一次申请全部资源（拆"持有等待"）；全局编号、只许从小到大申请（拆"循环等待"）；允许剥夺重来的任务（拆"不可剥夺"）。代价是资源利用率下降或任务要能回滚。

避免（运行时看风险）：分配前先问"批了这笔之后，系统还存在安全序列吗"——银行家算法的名场面。数学漂亮，但要预知每个镇民的最大需求；开放式 MAS 里谁也不肯亮家底，水土不服。

检测与恢复（发病再治）：定期扫资源等待图找环，找到了就挑一个倒霉蛋剥夺（选代价最小者回滚）。数据库与操作系统的主流选择，代价是检测开销与回滚损失。

鸵鸟政策（装没看见）：发生概率低、处理代价高，就赌它不发生。真实工程里最常见也最少被写进教材的选择——但前提是你算过概率与损失的账。

图 5-1 十字路口死锁：循环等待的诞生

复现死锁：代码里的十字路口

把路口搬进代码。每段车道是一把锁，每辆车先占面前一段、再申请拐弯需要的那段；四辆车同时出发，等待图闭合成环，全镇冻结。

import threading, time

class Lane:
    """一段车道：互斥资源。"""
    def __init__(self, name):
        self.name = name
        self.lock = threading.Lock()
        self.held_by = None

    def acquire(self, cart):
        ok = self.lock.acquire(timeout=0.3)   # 限时申请，防止测试挂死
        if ok:
            self.held_by = cart
        return ok

    def release(self, cart):
        if self.held_by is cart:
            self.held_by = None
            self.lock.release()

def drive(cart, first, second, results):
    """占住 first，再要 second；两段都到手才算通过路口。"""
    if first.acquire(cart):
        time.sleep(0.05)                      # 留出撞死锁的时间窗
        if second.acquire(cart):
            results.append(f"{cart} 通过路口")
            second.release(cart); first.release(cart)
        else:
            results.append(f"{cart} 卡死：让不出 {first.name}")
            first.release(cart)               # 限时策略下退回，形成活锁

N, E, S, W = Lane("北段"), Lane("东段"), Lane("南段"), Lane("西段")
results = []
carts = [threading.Thread(target=drive, args=(c, a, b, results))
         for c, a, b in [("北车", N, E), ("东车", E, S),
                         ("南车", S, W), ("西车", W, N)]]
for t in carts: t.start()
for t in carts: t.join()
print(sorted(results))
​

超时退让参数下你会看到"卡死"字样刷屏——四辆车轮流占道、轮流失败、再轮流重试，谁也过不去：死锁被超时软化成了活锁（都在动，都没进展）。把超时去掉，程序就真的站住不动了。

药方：按序申请

四根支柱拆一根就够，工程最爱拆"循环等待"：给所有资源全局编号，规定只能按编号递增申请。北车东车都要"北段、东段"两段，就让它们都先申请编号小的北段——申请不到就不占东段，环闭不起来。

def drive_ordered(cart, lanes, results):
    """按全局编号递增申请，拆掉循环等待。"""
    for lane in sorted(lanes, key=lambda l: l.no):
        while not lane.acquire(cart):
            time.sleep(0.02)                  # 排队等，但不持有后面的
    results.append(f"{cart} 通过路口")
    for lane in sorted(lanes, key=lambda l: l.no, reverse=True):
        lane.release(cart)

N, E, S, W = Lane("北段"), Lane("东段"), Lane("南段"), Lane("西段")
for i, l in enumerate([N, E, S, W]):
    l.no = i                                  # 全局编号 0-3
results = []
carts = [threading.Thread(target=drive_ordered,
                          args=(c, pair, results))
         for c, pair in [("北车", [N, E]), ("东车", [E, S]),
                         ("南车", [S, W]), ("西车", [W, N])]]
for t in carts: t.start()
for t in carts: t.join()
print(f"通过 {len(results)} 辆：", sorted(results))
​

四辆车全部通过——没有环，就没有死锁。代价也看得见：申请顺序与通行逻辑脱钩（有的车要先拿用不上的路段），资源利用率打了折。预防死锁从来不是免费的，是用效率换确定。

路口治理的两种哲学

真实路口的两种设计对应两套竞争治理哲学。信号灯是集中式：中央时钟分配路权，镇民服从即可，公平可调但依赖基础设施、坏一盏全路口瘫痪。环岛是分散式：人人遵守"让行已入环车辆"的局部规则，无中心、能自愈，但高峰吞吐靠涌现、无优先级。多智能体系统的资源治理在这两极之间摇摆：信号灯式的中心分配器（第 4 章指派）与环岛式的协议自组织（本章按序申请、下一章的机制设计），选型看的还是老三样——规模、动态性、基础设施可信度。

⚠️ 常见坑：把活锁当死锁治。对活锁上"检测等待图找环"是查不出病的（图上没有环，大家都在让）。活锁的解法是引入随机性或差异化退避——让同步礼让的两方错开节奏，比如各按随机时长再试。

沙盘推演小结

井台重开那天立了新规：取水按"桶号"顺序申请辘轳与井位，打完一桶再还。桶号制度牺牲了一点灵活性，换来了枯水期最宝贵的确定性。法庭的第一类案子结案，但很多纠纷没这么单纯——两家的目标本身就相撞，不是排个队就能解决的。下一节正式开庭：冲突怎么查、怎么分级、谁说了算。