12.1 死锁为何形成

两把锁单独看都没有问题，组合起来却可能让整个程序停住：

text

线程 A：持有 orders，等待 inventory
线程 B：持有 inventory，等待 orders

CPU 仍在运行，线程也没有崩溃，但它们等不到任何能改变现状的事件。这就是死锁。真正危险的地方不在“锁很多”，而在资源依赖形成了环。

本章先建立分析模型和预防方法；下一节再进入现场诊断，用线程栈与等待关系找到环。

1. 死锁不是“程序很慢”

几个相似现象要先分开：

现象	状态是否变化	是否可能自行结束
死锁	相关执行单元都在等待	若没有外部干预，不能
活锁	一直重试、让步或撤销	理论上能，实际可能长期无进展
饥饿	某个执行单元总拿不到资源	其他工作仍可能前进
长时间阻塞	正在等 I/O、条件或持锁者	条件满足后可以继续
性能拥塞	工作在完成，但吞吐下降	会完成，只是很慢

“超过 5 秒没响应”只能作为告警信号，不能证明死锁。诊断需要知道每个线程持有什么、等待什么，以及等待链是否闭合。

2. 四个必要条件

Coffman 条件描述了资源死锁出现时必须同时成立的四件事：

互斥：至少一种资源不可共享，一个实例同一时刻只能由一个执行单元使用；
持有并等待：执行单元保留已有资源，同时等待新资源；
不可剥夺：系统不能随意从持有者手中收回资源；
循环等待：存在一个闭环，每个成员都等待下一个成员持有的资源。

以开头的两把锁为例，mutex 只能由一个线程持有；A 与 B 都拿着一把等另一把；锁不会被强行转让；等待关系是 A → B → A。四项同时成立。

这些条件是必要条件，不是日常排查时的充分预测器。系统里存在互斥、持有等待和不可剥夺，并不表示当前已经死锁；还要形成实际的循环等待。

pthread_mutex_trylock 也不等于“剥夺”。它只是获取失败时立即返回，既没有从持有者手中夺锁，也不会自动释放调用者已有的锁。只有调用者在失败后主动撤销、释放并重试，才可能打破持有并等待。

3. 用等待图看问题

把线程画成节点。若线程 A 等待线程 B 持有的资源，就画一条 A → B 的边：

text

A ──等待 B 持有的 L2──> B
▲                         │
└──等待 A 持有的 L1───────┘

当每种资源只有一个实例时，等待图中的环意味着死锁。若同类资源有多个实例，只看到环还不一定足够，需要继续考虑每类资源的可用数量与持有数量。

工程中的“全局加锁顺序”正是在结构上禁止这种环。如果所有线程只允许从低等级锁指向高等级锁，等待边就不可能绕回起点。

4. 最实用的预防：固定锁顺序

假设转账必须同时锁住两个账户。若一律“先锁付款方、再锁收款方”，两个相反方向的转账就可能形成环。下面始终按稳定、唯一的账户编号加锁，保存为 ordered-transfer.c。账户指针必须有效，ID 在并发期间保持不变，余额初始非负。amount 为整数单位；负数、重复 ID、余额不足或目标溢出返回 0，同一账户的非负转移按 no-op 返回 1。pthread 失败会终止演示进程，不继续访问未保护的数据。

#include <limits.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    unsigned id;
    long balance;
    pthread_mutex_t mutex;
} account_t;

typedef struct {
    account_t *from;
    account_t *to;
    int rounds;
} transfer_job_t;

static void check_pthread(int error, const char *operation) {
    if (error != 0) {
        fprintf(stderr, "%s: %s\n", operation, strerror(error));
        exit(EXIT_FAILURE);
    }
}

static int transfer(account_t *from, account_t *to, long amount) {
    if (amount < 0) {
        return 0;
    }
    if (from == to) {
        return 1;
    }

    if (from->id == to->id) {
        return 0;
    }

    account_t *first = from->id < to->id ? from : to;
    account_t *second = from->id < to->id ? to : from;

    check_pthread(pthread_mutex_lock(&first->mutex), "lock first");
    check_pthread(pthread_mutex_lock(&second->mutex), "lock second");

    int completed = 0;
    if (from->balance >= amount && to->balance <= LONG_MAX - amount) {
        from->balance -= amount;
        to->balance += amount;
        completed = 1;
    }

    check_pthread(pthread_mutex_unlock(&second->mutex), "unlock second");
    check_pthread(pthread_mutex_unlock(&first->mutex), "unlock first");
    return completed;
}

static void *run_transfers(void *argument) {
    transfer_job_t *job = argument;
    for (int i = 0; i < job->rounds; ++i) {
        transfer(job->from, job->to, 1);
    }
    return NULL;
}

int main(void) {
    account_t a = { 10, 100000, PTHREAD_MUTEX_INITIALIZER };
    account_t b = { 20, 100000, PTHREAD_MUTEX_INITIALIZER };
    transfer_job_t ab = { &a, &b, 50000 };
    transfer_job_t ba = { &b, &a, 50000 };
    pthread_t first;
    pthread_t second;

    if (pthread_create(&first, NULL, run_transfers, &ab) != 0
            || pthread_create(&second, NULL, run_transfers, &ba) != 0) {
        return EXIT_FAILURE;
    }
    if (pthread_join(first, NULL) != 0
            || pthread_join(second, NULL) != 0) {
        return EXIT_FAILURE;
    }

    check_pthread(pthread_mutex_destroy(&a.mutex), "destroy a");
    check_pthread(pthread_mutex_destroy(&b.mutex), "destroy b");
    printf("a=%ld b=%ld total=%ld\n",
           a.balance, b.balance, a.balance + b.balance);
    return a.balance == 100000 && b.balance == 100000
        ? EXIT_SUCCESS : EXIT_FAILURE;
}

bash

cc -std=c17 -O2 -Wall -Wextra -Werror -pthread ordered-transfer.c
./a.out
# a=100000 b=100000 total=200000

关键不是“解锁顺序必须相反”这条习惯，而是所有路径获取多把锁时采用同一个偏序。反向释放通常让嵌套关系更清楚，但死锁预防依赖的是获取顺序。

锁等级需要稳定且唯一。若两个对象的等级相同，必须再定义不会变化的决胜规则；对象地址排序在某些语言或运行时里也未必是合适、可移植的标识。

当顺序很难统一

回调、插件和跨模块调用常把锁依赖藏起来。可以继续改变设计：

以完整申请或 try-lock 回退协议取得全部资源；若中途失败，先释放已取得部分，再等待或重试；
缩小锁的作用域，调用未知代码前先释放内部锁；
用消息传递把资源所有权集中到一个执行单元；
把大锁拆分时同时定义锁等级，而不是只追求并行度；
使用超时或 try-lock 后回退，但必须设计退避，避免活锁；
对数据库事务允许死锁发生，再检测并回滚受害事务。

“加一个全局大锁”确实能消除多锁环，但会牺牲并行度，而且调用者若在持有它时等待外部资源，仍可能与系统其他部分形成环。

5. 哲学家就餐真正教了什么

五位哲学家围坐，每人吃饭需要左右两根筷子。如果所有人先拿左边，再等右边，就可能构成五节点环。这个模型不是在教筷子的 API，而是在展示几类结构性解法：

资源排序。 给筷子编号，每个人总是先拿编号小的，再拿编号大的。最后一位哲学家的获取方向会与直觉相反，环因此无法闭合。

限制并发申请者。 只允许最多四人同时尝试取筷子，至少保留一条完成路径。不过“有完成路径”不等于每个人都公平，仍需考虑饥饿。

集中仲裁。 由服务员一次批准一对筷子。它消除了分散的持有并等待，却把吞吐与可用性集中到仲裁者。

失败后撤销。 拿不到第二根时放回第一根，并在随机或有界退避后重试。若所有人严格同步地拿起、放下，死锁会变成活锁。

同一个例子因此同时涉及安全性和活性：不死锁只说明系统不会永久卡在资源环里，并不保证等待有上界，也不保证每位参与者最终成功。

6. 四类处理策略

教材通常把方法分成四类：

策略	时机	典型手段
预防	设计时破坏必要条件	锁排序、一次申请、减少互斥
避免	每次分配前判断是否仍安全	银行家算法
检测	允许进入死锁，再寻找等待环	数据库等待图、线程转储分析
恢复	检测后打破环	回滚事务、终止任务、重启组件

真实系统常混合使用。例如进程内 mutex 通过锁等级预防，数据库事务通过检测选出受害者并回滚，外部服务调用则用截止时间阻止资源无限占用。

超时是一种止损机制，不自动证明或修复死锁。超时后若没有释放已持有资源、撤销半成品并保证重试幂等，系统可能从“永远等待”变成“不断失败且状态混乱”。

7. 银行家算法：安全比眼下无死锁要求更多

银行家算法要求每个任务预先声明每类资源的最大需求。系统试分配后，只在仍存在一条“让所有任务依次完成”的安全序列时批准请求。

下面用非负整数表示资源数量，矩阵尺寸必须匹配，已分配量不能超过声明上限。函数返回一个安全序列；不存在则返回 None。保存为 banker.py 并用 Python 3 运行：

python

def safe_sequence(available, maximum, allocation):
    process_count = len(maximum)
    resource_count = len(available)

    if len(allocation) != process_count:
        raise ValueError("matrix height mismatch")

    if any(type(value) is not int or value < 0 for value in available):
        raise ValueError("available must contain nonnegative integers")

    need = []
    for maximum_row, allocated_row in zip(maximum, allocation):
        if len(maximum_row) != resource_count:
            raise ValueError("maximum width mismatch")
        if len(allocated_row) != resource_count:
            raise ValueError("allocation width mismatch")

        row = []
        for claim, held in zip(maximum_row, allocated_row):
            if (type(claim) is not int or type(held) is not int
                    or claim < 0 or held < 0):
                raise ValueError("resource counts must be nonnegative integers")
            if claim < held:
                raise ValueError("allocation exceeds maximum claim")
            row.append(claim - held)
        need.append(row)

    work = list(available)
    finished = [False] * process_count
    order = []

    while len(order) < process_count:
        progressed = False
        for process in range(process_count):
            if finished[process]:
                continue
            if all(need[process][resource] <= work[resource]
                   for resource in range(resource_count)):
                for resource in range(resource_count):
                    work[resource] += allocation[process][resource]
                finished[process] = True
                order.append(process)
                progressed = True
        if not progressed:
            return None

    return order

available = [3, 3, 2]
maximum = [
    [7, 5, 3],
    [3, 2, 2],
    [9, 0, 2],
    [2, 2, 2],
    [4, 3, 3],
]
allocation = [
    [0, 1, 0],
    [2, 0, 0],
    [3, 0, 2],
    [2, 1, 1],
    [0, 0, 2],
]

order = safe_sequence(available, maximum, allocation)
assert order is not None
print(order)

不安全表示在声明的最大需求下不存在安全序列，不表示此刻已经死锁。如果任务实际请求低于上限，它们仍可能完成；未来请求也可能把系统推入死锁。银行家算法判断的是这个资源模型中的安全性，不能替代实际等待图。

这套方法在通用线程锁里很少实用，因为程序通常不能预报完整最大需求，任务与资源也会动态出现。它的价值在于把“当前还有资源”与“承诺这次分配后仍可收尾”区分开。

银行家算法也不是两阶段锁或两阶段提交的同义词。数据库通常更愿意从等待图检测死锁并回滚一个事务，而不是要求事务预先声明所有锁。

8. 设计检查清单

代码评审多锁路径时，逐项追问：

这段路径进入时已经持有哪些锁？
它会调用可能拿锁、阻塞或执行回调的函数吗？
全局锁等级记录在哪里，自动检查能否覆盖？
错误、取消和超时路径是否释放相同资源？
一个线程等待条件变量时，相关 mutex 是否按协议释放？
锁跨越网络、磁盘或用户交互了吗？
失败后重试会不会让所有参与者同步活锁？
若仍可能死锁，系统如何检测、选择受害者并恢复一致状态？

9. 小结

死锁要看资源依赖。即使只有一把 PTHREAD_MUTEX_NORMAL 锁，同一线程重复获取也可能形成“自己等自己”的自环。四个必要条件帮助解释它为何可能出现，而工程上最有力的手段通常是让依赖边只能朝一个方向：

用稳定锁等级统一获取顺序；
减少持锁时的外部调用和阻塞；
无法预防时，明确检测与恢复机制；
把超时当作止损，不当作正确性证明；
同时检查活锁与饥饿，避免只消灭一种停滞。

下一节进入死锁现场诊断：先抓住所有线程的瞬时状态，再从“等待什么、由谁持有”还原完整的环。

第1章逻辑

第2章集合论

第3章证明方法

第4章递归、归纳与递推

第5章关系与函数

第6章组合数学

第7章图论

第8章概率与统计

第9章数论

第10章线性代数

第11章微积分与优化

第12章信息论与数值计算