死锁 (Deadlock)

一、死锁概述

什么是死锁

死锁 (Deadlock):两个或多个线程/进程互相等待对方持有的资源而形成的无限等待。

   线程 A                      线程 B
     │                            │
   持有 锁 1                  持有 锁 2
     │                            │
   等待 锁 2 ──────────────→   等待 锁 1
     │                            │
     └──── 互相等待 ─────────────┘
              (死锁)

死锁 vs 饥饿 vs 活锁

状态	描述	进程是否在动
死锁	互相等待,永久阻塞	❌ 不动
饥饿	长期得不到资源(如低优先级)	❌ 不动
活锁	都在动但都没进展(互相礼让)	✅ 动但没用

死锁的危害

• 永久阻塞:无法自动恢复
• 资源浪费:持有的资源无法释放
• 用户体验差:程序挂起
• 系统瘫痪:严重时整个应用死掉

---

二、死锁的 4 个必要条件

Coffman 条件 (1971)

死锁发生必须同时满足以下 4 个条件:

1. 互斥 (Mutual Exclusion)
2. 占有并等待 (Hold and Wait)
3. 不可抢占 (No Preemption)
4. 循环等待 (Circular Wait)

关键:破坏其中任意一个,死锁就不会发生。

1. 互斥 (Mutual Exclusion)

含义:资源一次只能被一个线程占用

不可共享的资源: - 互斥锁 (Mutex) - 写锁 - 打印机 - 硬件设备

可共享的资源(不构成死锁条件): - 读锁(共享锁) - 只读数据

破坏方法:让资源可共享(很多情况下做不到)

2. 占有并等待 (Hold and Wait)

含义:线程持有资源,同时等待新资源

// 持有 锁 1
pthread_mutex_lock(&lock1);

// 等待 锁 2
pthread_mutex_lock(&lock2);  // 可能阻塞

破坏方法: - 一次性申请所有资源(原子申请) - 申请前释放已持有资源

3. 不可抢占 (No Preemption)

含义:资源不能被强制抢走,只能由持有者主动释放

不可抢占的资源: - 互斥锁 - 文件锁 - 数据库连接

可抢占的资源: - CPU(可被调度) - 内存(可被换出)

破坏方法: - 抢占资源(请求不到时释放已有的) - 操作系统可抢占:内存、CPU - 应用程序难以抢占:锁、数据库连接

4. 循环等待 (Circular Wait)

含义:存在等待环路

T1 等待 T2 持有的资源
T2 等待 T3 持有的资源
T3 等待 T1 持有的资源

破坏方法: - 给资源编号,按顺序申请(推荐) - 不允许反向申请

4 条件示意图

   ┌──────┐                ┌──────┐
   │  T1  │ ───需要───→  │  T2  │
   │      │ ←──需要───   │      │
   │ hold │                │ hold │
   └──┬───┘                └──┬───┘
      │ R_a                  │ R_b
      └───────需要──────→     │
                              ↓
                          等待

---

三、资源类型

1. 可重用资源 (Reusable Resources)

• 可重复使用
• 一次只能被一个进程占用
• 用完后释放
• 例子:CPU、内存、文件、锁、I/O 设备
• 可能死锁

2. 消耗性资源 (Consumable Resources)

• 一次产生,一次消耗
• 例子:信号、消息、I/O 中断
• 一般不死锁(短暂、状态少)
• 但可能死锁:生产者-消费者 + 缓冲区满

3. 资源分配图

资源分配图:描述线程和资源关系

   资源 R1 持有者:T1              资源 R2 持有者:T2
         │                              │
         ↓ (分配)                       ↓ (分配)
        T1 ─────需要 R2───→ T2 ─────需要 R1
                 ↑                          │
                 └────── 需要 R1 ────────────┘
                          (循环等待!)

• 圆圈=资源
• 方框=线程
• 资源→线程 = 分配
• 线程→资源 = 请求

有环 = 可能死锁(不必然)

---

四、死锁处理四大策略

1. 鸵鸟策略 (Ostrich)

不处理死锁,假设不会发生

适用: - 死锁极少发生 - 代价小(重启就好) - 实用主义:UNIX、Windows 都是这样

理由: - 解决死锁的代价大于死锁的损失 - 难完美解决

2. 死锁预防 (Prevention)

破坏 4 个必要条件之一

破坏条件	方法	副作用
互斥	让资源可共享	不可能/不实用
占有并等待	一次性申请所有资源	效率低,饥饿
不可抢占	可抢占资源(OS 级)	难实现,会引发新问题
循环等待	资源按序申请	强制顺序,可能不灵活

评价:理论上有效,实际代价大,很少用

3. 死锁避免 (Avoidance)

运行时根据资源分配状态,避免进入不安全状态

关键算法:银行家算法

银行家算法 (Banker's Algorithm)

Dijkstra 1965

核心思想: - 每次分配前,模拟分配 - 若分配后系统仍安全,则分配 - 否则拒绝分配,等待

数据结构:

// 资源总量
int total[N];

// 最大需求
int max[N][M];  // 进程 i 对资源 j 的最大需求

// 已分配
int allocation[N][M];  // 进程 i 已分配资源 j

// 还需
int need[N][M];  // = max - allocation

// 可用
int available[M];  // 系统剩余资源

安全状态:存在一个安全序列,每个进程按顺序都能完成。

算法:

检查 need[i] <= work (可用资源)
  ├─ 是 → 假设分配,work += allocation[i],标记完成
  └─ 否 → 该进程等待

重复直到所有进程完成 → 安全
若有进程无法完成 → 不安全

示例:

A B C  (资源: 3 个,A=10, B=5, C=7)

        Max    Allocation   Need   Available
P0      7 5 3   0 1 0      7 4 3   3 3 2
P1      3 2 2   2 0 0      1 2 2
P2      9 0 2   3 0 2      6 0 0
P3      2 2 2   2 1 1      0 1 1
P4      4 3 3   0 0 2      4 3 1

求安全序列?

Work = Available = (3 3 2)

P1: Need (1 2 2) ≤ Work (3 3 2)? 是
  Work = (3 3 2) + Allocation(P1) (2 0 0) = (5 3 2)

P3: Need (0 1 1) ≤ Work (5 3 2)? 是
  Work = (5 3 2) + (2 1 1) = (7 4 3)

P0: Need (7 4 3) ≤ Work (7 4 3)? 是
  Work = (7 4 3) + (0 1 0) = (7 5 3)

P2: Need (6 0 0) ≤ Work (7 5 3)? 是
  Work = (7 5 3) + (3 0 2) = (10 5 5)

P4: Need (4 3 1) ≤ Work (10 5 5)? 是
  Work = (10 5 5) + (0 0 2) = (10 5 7)

所有完成 → 安全
安全序列: P1, P3, P0, P2, P4

缺点: - 进程数多时慢 - 需提前声明最大需求(实际难) - 不实用,主要用于教学

4. 死锁检测与恢复 (Detection and Recovery)

允许死锁发生,定期检测,死锁后恢复

检测算法

类似银行家算法,但从"是否能完成"改为"是否能检测出死锁"。

算法:

1. 找未完成进程 P (非 finish)
2. 如果 P 的 request <= work:
   - 假设 P 完成,work += allocation[P]
   - 标记 P 为 finish
   - 回到 1
3. 如果没有 P 满足:
   - 剩下的未完成进程就是死锁的

类似银行家算法,但只关心是否能完成

恢复策略

• 撤销进程:杀掉死锁进程(可能要杀多个)
• 剥夺资源:从死锁进程剥夺资源给其他进程
• 回滚:回滚到检查点(checkpoint),重新执行
• 优先级:杀优先级最低的
• 回滚次数:杀回滚次数最少的

Linux 实际行为: - 内核用 lockdep 检测潜在死锁 - 检测到就 dump stack trace 和持有关系 - 不会自动恢复,需要用户解决 - OOM Killer 在严重死锁导致资源耗尽时介入

死锁处理策略对比

策略	复杂度	性能影响	实用性	实际使用
鸵鸟策略	无	无	高	主流(UNIX/Windows)
死锁预防	高	大	低	少(代价大)
死锁避免	高	中-大	低	少(理论为主)
检测 + 恢复	中	中	高	主流(InnoDB 等)

---

五、死锁的常见场景与实例

1. 经典问题:哲学家就餐

问题描述:5 个哲学家围坐,5 把叉子,每人必须拿两把才能吃,吃完放下

// 危险:5 个哲学家同时拿左叉
void* philosopher(void* arg) {
    int i = (int)arg;
    while (1) {
        think();
        pthread_mutex_lock(&fork[i]);        // 拿左叉
        pthread_mutex_lock(&fork[(i+1) % 5]); // 拿右叉 ← 可能死锁
        eat();
        pthread_mutex_unlock(&fork[i]);
        pthread_mutex_unlock(&fork[(i+1) % 5]);
    }
}

死锁情形:5 个哲学家都拿了左叉,等右叉,全阻塞

解法: - 资源有序:规定 4 个哲学家先拿小叉 - 仲裁:加 mutex,只能 4 个同时进餐 - trylock:拿不到就放下

2. 生产者-消费者

问题:缓冲区满,生产者还在写;缓冲区空,消费者还在读

死锁条件: - 互斥(缓冲区访问) - 占有并等待(持有锁 + 等待对方) - 不可抢占 - 循环等待

解法: - 信号量:控制缓冲区满/空 - 条件变量:wait 释放锁 - 死锁检测:trylock

3. 多锁顺序不一致

问题:函数 A 锁(L1, L2),函数 B 锁(L2, L1)

// 线程 1        // 线程 2
A: lock(L1)    B: lock(L2)
A: lock(L2) → 阻塞  B: lock(L1) → 阻塞
                  (死锁)

解法:统一锁顺序(按地址大小)

4. 自死锁(单线程)

问题:同一线程对同一互斥锁 lock 两次

// 不可重入锁
pthread_mutex_lock(&m);
pthread_mutex_lock(&m);  // 死锁!

解法:用递归锁 (Reentrant Mutex)

pthread_mutex_t m = PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP;

5. 数据库死锁

问题:两个事务互相等对方释放行锁

解法: - 锁顺序:查询/更新按固定顺序 - 锁超时:SET innodb_lock_wait_timeout = 5 - 检测:InnoDB 自动检测并回滚代价小的事务

6. 资源池死锁

问题:连接池满,线程持有连接等另一个连接

解法: - 限制每线程只能用一个连接 - 死锁检测(超时回退)

---

六、死锁的解决模式

1. 加锁顺序

核心原则:所有线程按相同顺序加锁

// 资源排序: 总是先加小编号
void lock_both(LOCK a, LOCK b) {
    if (a.id < b.id) {
        lock(a);
        lock(b);
    } else {
        lock(b);
        lock(a);
    }
}

实际使用:地址排序

void lock_two(pthread_mutex_t *a, pthread_mutex_t *b) {
    if (a < b) {
        pthread_mutex_lock(a);
        pthread_mutex_lock(b);
    } else {
        pthread_mutex_lock(b);
        pthread_mutex_lock(a);
    }
}

2. trylock + 回退

// trylock 模式
if (pthread_mutex_trylock(&a) == 0) {
    if (pthread_mutex_trylock(&b) == 0) {
        // 都拿到
        do_work();
        pthread_mutex_unlock(&b);
        pthread_mutex_unlock(&a);
    } else {
        pthread_mutex_unlock(&a);  // 回退
    }
}

优点:简单,适合锁少的场景 缺点:浪费 CPU 等待

3. 超时回退

#include <pthread.h>
#include <time.h>

int lock_with_timeout(pthread_mutex_t *m, int timeout_ms) {
    struct timespec ts;
    clock_gettime(CLOCK_REALTIME, &ts);
    ts.tv_sec += timeout_ms / 1000;
    ts.tv_nsec += (timeout_ms % 1000) * 1000000;
    if (ts.tv_nsec >= 1000000000) {
        ts.tv_sec++;
        ts.tv_nsec -= 1000000000;
    }
    return pthread_mutex_timedlock(m, &ts);
}

// 用法
if (lock_with_timeout(&lock, 1000) == 0) {
    // 拿到锁
    do_work();
    pthread_mutex_unlock(&lock);
} else {
    // 超时,放弃
    retry_or_give_up();
}

4. 锁层次 (Lock Hierarchy)

强制锁顺序:

// 定义锁层次
typedef enum {
    LOCK_LEVEL_ROOT = 0,    // 最高层
    LOCK_LEVEL_DB,
    LOCK_LEVEL_BUSINESS,
    LOCK_LEVEL_CACHE,
    LOCK_LEVEL_LEAF         // 最低层
} lock_level_t;

// 任何线程只能从高层锁到低层锁
// 任何线程获取锁,只能从高到低
// 违反会运行时检测(assert)

5. 一次性申请所有资源

原子申请:一个事务要么拿到所有资源,要么一个都不拿

// 批量申请
bool acquire_all(RESOURCE_TYPE *res, int n) {
    for (int i = 0; i < n; i++) {
        if (try_acquire(res[i]) != 0) {
            // 失败,释放已拿的
            for (int j = 0; j < i; j++) {
                release(res[j]);
            }
            return false;
        }
    }
    return true;
}

6. 消息传递(避免共享)

用消息传递代替共享数据,天然避免死锁

Actor 模型、Erlang、CSP 都是这思路

---

七、Linux 内核的锁与死锁检测

1. 内核锁的层次

Linux 内核有严格的锁顺序规则:

slock                                         (最低)
└── 各种局部锁
    └── inode->i_lock
        └── 通用文件锁
            └── super_block->s_umount_lock
                └── sb->s_umount
                    └── namespace semaphore      (最高)

违反会触发 lockdep 警告。

2. lockdep (Lock Dependency Checker)

功能:运行时检测锁依赖关系,预测死锁

配置:

# 内核选项
CONFIG_DEBUG_LOCK_ALLOC=y
CONFIG_PROVE_LOCKING=y
CONFIG_LOCK_STAT=y

触发: - 锁循环等待(可能死锁) - 重复锁(自死锁) - 错误释放锁 - 错误的 IRQ 上下文用锁

输出:

=============================================
WARNING: possible circular locking dependency detected
6.0.0 #1 Tainted: G        W
---------------------------------------------
task1/123 is trying to acquire lock:
 &sb->s_type_lock{....}, at: deactivate_sb+0x...

but task1 is already holding lock:
 &mm->mmap_lock{....}, at: exit_mmap+0x...

3. Linux 的锁类型

锁类型	特点
spinlock	忙等,中断关闭,短临界区
mutex	可睡眠,长临界区
rwlock	读写锁
rcu	读多写少,极高性能
seqlock	读多写少,数据版本
percpu_rwlock	per-CPU 读写锁
completion	完成量,任务同步
wait_queue	等待队列

死锁概率: - spinlock:中等(配置不当) - mutex:中等 - 多锁:高 - 嵌套锁:高

4. 死锁常见位置

Linux 内核中常见死锁位置:

• VFS:inode_lock + super_block_lock
• mmap:mmap_lock + i_mmap_lock
• 网络栈:sock_lock + qdisc_lock
• 文件系统:inode_lock + 父目录 lock
• 内存管理:mmap_lock + anon_vma_lock

lockdep 会检测这些。

---

八、Java 死锁

1. 常见死锁

// 经典多锁死锁
synchronized(lock1) {
    synchronized(lock2) {
        // ...
    }
}

// 另一个线程
synchronized(lock2) {
    synchronized(lock1) {
        // ...
    }
}

2. 死锁检测

// jstack / jcmd
jps                        # 看 Java 进程
jstack <pid>                # 看线程栈,会显示 "Found one Java-level deadlock"

// ThreadMXBean 检测
ThreadMXService tmx = ManagementFactory.getThreadMXBean();
long[] deadlocked = tmx.findDeadlockedThreads();
if (deadlocked != null) {
    ThreadInfo[] infos = tmx.getThreadInfo(deadlocked);
    for (ThreadInfo info : infos) {
        System.out.println(info);
    }
}

3. 避免 Java 死锁

• 按固定顺序加锁
• tryLock() + 超时
• 使用并发包 (java.util.concurrent)
• ReentrantLock (可重入)
• ReentrantReadWriteLock (读写锁)
• Semaphore (信号量)
• ConcurrentHashMap (无锁)
• CompletableFuture (异步)

4. 实际案例

Tomcat / Netty / Spring 都对死锁有防护: - Netty 用 Future + 超时 - Spring 用 synchronized + 显式锁顺序 - Kafka 用 ReentrantLock + 超时

---

九、数据库死锁

1. 死锁原因

-- 事务 A
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;

-- 事务 B (同时)
UPDATE accounts SET balance = balance - 100 WHERE id = 2;
UPDATE accounts SET balance = balance + 100 WHERE id = 1;

2. 死锁检测

InnoDB 自动检测:

• 维护等待图 (Wait-for Graph)
• 周期检查环路
• 选中回滚代价最小的事务回滚
• 回滚后释放锁

-- 查看最近死锁日志
SHOW ENGINE INNODB STATUS\G

-- 看死锁相关配置
SHOW VARIABLES LIKE 'innodb_deadlock_detect';
SHOW VARIABLES LIKE 'innodb_lock_wait_timeout';

3. 避免

• 锁顺序:所有事务按固定顺序访问行
• 索引:用索引减少锁范围
• 短事务:事务尽量短
• 合理隔离级别:用 READ COMMITTED 减少锁

---

十、分布式死锁

1. 分布式系统死锁

原因: - 多机协调 - 网络分区 - 资源分散

例子: - 两阶段提交(2PC)可能死锁 - 分布式锁可能死锁

2. 解决

• 超时:每个事务设置超时
• 死锁检测:协调者定期检测
• 租约:资源有租约,过期自动释放
• 资源分配图:记录全局分配

3. 分布式锁框架

框架	特点
ZooKeeper	ZAB 协议,临时节点
etcd	Raft,lease
Redis	Redlock,有争议
Consul	Raft,session
Chubby	Google,基于 Paxos

---

十一、死锁的检测工具

1. Linux

# strace 看系统调用
strace -f -e trace=futex,flock command

# perf 看锁竞争
perf lock contention -a -b 1000

# 看 /proc/lock_stat (lockdep 启用)
cat /proc/lock_stat

# 死锁 dump
sysctl kernel.hung_task_timeout_secs    # 检测 hung task
echo 1 > /proc/sys/kernel/hung_task_panic  # hung task 时 panic

2. 编程语言工具

• C/C++:lockdep、ThreadSanitizer (TSan)
• Java:jstack、jConsole、VisualVM、Arthas
• Go:runtime stack、go race
• Python:faulthandler

3. ThreadSanitizer (TSan)

编译器插件,编译时插桩,运行时检测数据竞争和死锁

gcc -fsanitize=thread program.c
./a.out
# 警告:WARNING: ThreadSanitizer: data race...

---

十二、死锁与活锁、饥饿的区别

状态	描述	解决
死锁	互相等待,都不动	破坏 4 条件
活锁	都在动但都没进展(互相礼让)	随机退避
饥饿	长期得不到资源	公平锁、优先级
死循环	程序逻辑错误,CPU 100%	加超时
假死	进程在 D 状态(不可中断睡眠)	检查硬件/驱动

活锁示例:

// 两人都让对方,都不过
while (true) {
    if (left_lane_busy) yield();
    if (right_lane_busy) yield();
    // 走
}

解决:随机退避时间

int delay = rand() % 100;  // 随机等待
usleep(delay);

---

十三、死锁的实际处理经验

1. 代码层面

• 明确锁的所有权:谁拿谁放
• 避免长事务 / 长临界区
• 统一锁顺序(最重要)
• 用现成的并发原语(concurrent 包、thread pool)
• 避免嵌套锁
• 优先用 trylock + 回退
• 用读写锁代替 mutex(读多写少)
• 避免递归锁
• 定时清理锁(超时)

2. 架构层面

• 数据分区:让数据更独立
• 无锁数据结构:原子变量、CRDT
• 消息队列:解耦
• Actor 模型:天然避免
• 事务:数据库事务封装

3. 监控层面

• 死锁检测工具
• 慢查询监控(数据库)
• 锁等待时间
• 上下文切换监控

4. 常见反模式

// 1. 锁内 sleep
pthread_mutex_lock(&m);
sleep(1);  // 死锁高危
pthread_mutex_unlock(&m);

// 2. 锁内 IO
pthread_mutex_lock(&m);
read(fd, buf, 100);  // 死锁高危
pthread_mutex_unlock(&m);

// 3. 锁内分配内存
pthread_mutex_lock(&m);
malloc(1024);  // 可能阻塞
pthread_mutex_unlock(&m);

// 4. 锁内回调用户函数
pthread_mutex_lock(&m);
user_callback();  // 不知道用户干什么
pthread_mutex_unlock(&m);

---

十四、死锁的检测算法(理论)

1. 资源分配图算法

算法:

1. 标记所有节点为未访问
2. 从某个节点 P 开始:
   a. 标记 P 为 visited
   b. 检查 P 的所有请求:
      - 如果请求资源 R 且 R 被其他节点占用:
        - 如果该节点未 visited,递归访问
        - 如果该节点已 visited,环路! 死锁!
3. 重复 2 直到所有节点访问过

复杂度:O(N) (N = 节点数)

2. 等待图 (Wait-for Graph)

简化版资源分配图:只画进程和等待关系

T1 → T2 (T1 等 T2 释放)
T2 → T3
T3 → T1
(有环,死锁)

周期检查:用 DFS 或拓扑排序

3. 实际工具的算法

• Java ThreadMXBean.findDeadlockedThreads():
• 用信号量图(Semaphore Graph) 等待图
• 检测环路
• InnoDB:等待图 + 周期检查
• Linux lockdep:维护锁依赖图,检测环路

---

十五、死锁的面试题精选

1. 死锁的必要条件

4 个:互斥、占有并等待、不可抢占、循环等待

2. 死锁的处理策略

4 种:鸵鸟(不处理)、预防(破坏 4 条件)、避免(银行家)、检测+恢复

3. 银行家算法

核心:模拟分配,保持安全状态 数据:Max、Allocation、Need、Available 判断:找安全序列

4. 哲学家就餐

死锁:5 人同时拿左叉 解法: - 资源编号,规定顺序 - 仲裁,最多 4 人 - trylock

5. 数据库死锁

InnoDB 自动检测,回滚代价小的事务

6. 死锁与饥饿、活锁区别

死锁 都不动,饥饿 长期等不到,活锁 都在动但无进展

7. 怎么调试死锁

• jstack / jConsole (Java)
• lockdep (Linux)
• ThreadSanitizer (编译时插桩)
• strace -f 看系统调用

8. 如何预防死锁

• 统一锁顺序(最重要)
• trylock + 回退
• 超时
• 减少锁粒度
• 避免嵌套锁
• 使用消息队列

---

十六、核心要点速记

• 4 必要条件:互斥、占有并等待、不可抢占、循环等待
• 4 处理策略:鸵鸟、预防、避免、检测+恢复
• 银行家算法 = 模拟分配 + 安全序列
• 鸵鸟策略 = 假装没事(UNIX/Windows 实际做法)
• lockdep = Linux 内核死锁检测
• jstack = Java 死锁检测
• InnoDB = 数据库死锁自动检测
• 哲学家就餐 = 经典死锁问题
• 统一锁顺序 = 解决多锁死锁的最佳方法
• trylock + 回退 = 简单可重试的方案
• 优先级继承 = 解决优先级反转
• 死锁 4 条件破坏一个就不死锁
• 预防 实际很少用(代价大)
• 避免 银行家算法理论完美,实际不实用
• 检测+恢复 是实际方案(如 InnoDB)
• 多锁必须统一顺序,否则必死
• 递归锁 = 同一线程可重入
• 活锁 = 双方都让,加随机退避
• lockdep 检测潜在死锁,警告但不恢复
• ThreadSanitizer 编译时检测
• InnoDB 死锁回滚 = 回滚代价小的事务
• ZooKeeper 临时节点 = 解决分布式锁死锁