377 lines
8.8 KiB
Markdown
377 lines
8.8 KiB
Markdown
|
# 第12讲：死锁
|
|||
|
|
|
|||
|
|
> 🎯 **本节目标**：理解死锁的概念，掌握死锁的预防、避免和检测方法
|
|||
|
|
|
|||
|
|
## 📋 前置知识
|
|||
|
|
- [[07_多线程编程]] — 互斥锁和信号量
|
|||
|
|
- [[11_处理机调度]] — 调度的基本概念
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 🤔 为什么需要这个？
|
|||
|
|
|
|||
|
|
想象这样一个场景：
|
|||
|
|
- 线程 A 持有锁 1，等待锁 2
|
|||
|
|
- 线程 B 持有锁 2，等待锁 1
|
|||
|
|
- 两个线程互相等待，永远无法继续
|
|||
|
|
|
|||
|
|
这就是**死锁**——多个进程互相等待对方释放资源，导致所有进程都无法继续执行。
|
|||
|
|
|
|||
|
|
**生活比喻**：
|
|||
|
|
- **死锁** = 两个人在狭窄的走廊相遇，谁都不肯让路，结果谁也过不去
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 📖 核心概念
|
|||
|
|
|
|||
|
|
### 1. 死锁的四个必要条件
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
graph TD
|
|||
|
|
A[死锁四个条件] --> B[互斥条件]
|
|||
|
|
A --> C[持有并等待]
|
|||
|
|
A --> D[不可抢占]
|
|||
|
|
A --> E[循环等待]
|
|||
|
|
|
|||
|
|
B --> B1[资源一次只能被一个进程使用]
|
|||
|
|
C --> C1[进程持有资源的同时请求新资源]
|
|||
|
|
D --> D1[资源不能被强制剥夺]
|
|||
|
|
E --> E1[存在进程的循环等待链]
|
|||
|
|
|
|||
|
|
style A fill:#ffcdd2
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**必须同时满足这四个条件才会发生死锁**。
|
|||
|
|
|
|||
|
|
### 2. 资源分配图
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
graph LR
|
|||
|
|
subgraph 进程
|
|||
|
|
P1[P1]
|
|||
|
|
P2[P2]
|
|||
|
|
end
|
|||
|
|
subgraph 资源
|
|||
|
|
R1[R1]
|
|||
|
|
R2[R2]
|
|||
|
|
end
|
|||
|
|
|
|||
|
|
R1 -->|分配| P1
|
|||
|
|
R2 -->|分配| P2
|
|||
|
|
P1 -->|请求| R2
|
|||
|
|
P2 -->|请求| R1
|
|||
|
|
|
|||
|
|
style P1 fill:#e1f5fe
|
|||
|
|
style P2 fill:#e1f5fe
|
|||
|
|
style R1 fill:#e8f5e9
|
|||
|
|
style R2 fill:#e8f5e9
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**图例**：
|
|||
|
|
- 方框表示资源，圆圈表示进程
|
|||
|
|
- 资源→进程：已分配
|
|||
|
|
- 进程→资源：请求中
|
|||
|
|
|
|||
|
|
### 3. 死锁的处理策略
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
graph TD
|
|||
|
|
A[死锁处理策略] --> B[死锁预防]
|
|||
|
|
A --> C[死锁避免]
|
|||
|
|
A --> D[死锁检测]
|
|||
|
|
A --> E[死锁恢复]
|
|||
|
|
|
|||
|
|
B --> B1[破坏四个条件之一]
|
|||
|
|
C --> C1[银行家算法]
|
|||
|
|
D --> D1[资源分配图]
|
|||
|
|
E --> E1[终止进程]
|
|||
|
|
|
|||
|
|
style B fill:#e8f5e9
|
|||
|
|
style C fill:#e1f5fe
|
|||
|
|
style D fill:#fff3e0
|
|||
|
|
style E fill:#ffcdd2
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 4. 死锁预防
|
|||
|
|
|
|||
|
|
破坏死锁的四个必要条件之一：
|
|||
|
|
|
|||
|
|
| 条件 | 破坏方法 | 代价 |
|
|||
|
|
|------|----------|------|
|
|||
|
|
| 互斥 | 使用可共享资源 | 不总是可行 |
|
|||
|
|
| 持有并等待 | 一次性申请所有资源 | 资源浪费 |
|
|||
|
|
| 不可抢占 | 允许抢占资源 | 实现复杂 |
|
|||
|
|
| 循环等待 | 按顺序申请资源 | 限制灵活性 |
|
|||
|
|
|
|||
|
|
**资源有序分配法**：
|
|||
|
|
```c
|
|||
|
|
// 规定所有进程必须按编号顺序申请资源
|
|||
|
|
// 例如：先申请锁1，再申请锁2
|
|||
|
|
|
|||
|
|
pthread_mutex_lock(&mutex1); // 正确
|
|||
|
|
pthread_mutex_lock(&mutex2);
|
|||
|
|
|
|||
|
|
// 而不是
|
|||
|
|
pthread_mutex_lock(&mutex2); // 可能导致死锁
|
|||
|
|
pthread_mutex_lock(&mutex1);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 5. 银行家算法
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
graph TD
|
|||
|
|
A[银行家算法] --> B[检查请求是否安全]
|
|||
|
|
B --> C{安全?}
|
|||
|
|
C -->|是| D[分配资源]
|
|||
|
|
C -->|否| E[等待]
|
|||
|
|
D --> F[更新数据结构]
|
|||
|
|
E --> G[阻塞进程]
|
|||
|
|
|
|||
|
|
style C fill:#fff3e0
|
|||
|
|
style D fill:#e8f5e9
|
|||
|
|
style E fill:#ffcdd2
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**安全状态**：存在一个安全序列，使得所有进程都能顺利完成
|
|||
|
|
|
|||
|
|
**数据结构**：
|
|||
|
|
- `Available[]`：可用资源向量
|
|||
|
|
- `Max[][]`：最大需求矩阵
|
|||
|
|
- `Allocation[][]`：已分配矩阵
|
|||
|
|
- `Need[][]`：还需要的资源矩阵
|
|||
|
|
|
|||
|
|
**算法步骤**：
|
|||
|
|
1. 检查请求是否超过需要
|
|||
|
|
2. 检查请求是否超过可用资源
|
|||
|
|
3. 尝试分配，检查是否安全
|
|||
|
|
4. 如果安全，正式分配；否则等待
|
|||
|
|
|
|||
|
|
### 6. 死锁检测
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
graph TD
|
|||
|
|
A[构建资源分配图] --> B[寻找环路]
|
|||
|
|
B --> C{有环路?}
|
|||
|
|
C -->|是| D[可能存在死锁]
|
|||
|
|
C -->|否| E[无死锁]
|
|||
|
|
D --> F[进一步分析]
|
|||
|
|
|
|||
|
|
style C fill:#fff3e0
|
|||
|
|
style D fill:#ffcdd2
|
|||
|
|
style E fill:#e8f5e9
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**检测算法**：
|
|||
|
|
1. 构建资源分配图
|
|||
|
|
2. 使用深度优先搜索寻找环路
|
|||
|
|
3. 如果存在环路，可能存在死锁
|
|||
|
|
|
|||
|
|
### 7. 死锁恢复
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
graph TD
|
|||
|
|
A[检测到死锁] --> B[选择终止进程]
|
|||
|
|
B --> C[回滚操作]
|
|||
|
|
C --> D[释放资源]
|
|||
|
|
D --> E[唤醒等待进程]
|
|||
|
|
|
|||
|
|
style A fill:#ffcdd2
|
|||
|
|
style E fill:#e8f5e9
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**恢复方法**：
|
|||
|
|
- **终止所有死锁进程**：简单但代价大
|
|||
|
|
- **逐个终止进程**：直到死锁解除
|
|||
|
|
- **资源抢占**：强制剥夺资源
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 💻 动手实践
|
|||
|
|
|
|||
|
|
### 示例1：死锁演示
|
|||
|
|
|
|||
|
|
```c
|
|||
|
|
// deadlock_demo.c - 死锁演示
|
|||
|
|
#include <stdio.h>
|
|||
|
|
#include <stdlib.h>
|
|||
|
|
#include <pthread.h>
|
|||
|
|
|
|||
|
|
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
|
|||
|
|
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;
|
|||
|
|
|
|||
|
|
void *thread1(void *arg) {
|
|||
|
|
pthread_mutex_lock(&mutex1); // 获取锁1
|
|||
|
|
printf("Thread 1: 持有锁1，等待锁2...\n");
|
|||
|
|
sleep(1); // 等待，让线程2获取锁2
|
|||
|
|
pthread_mutex_lock(&mutex2); // 等待锁2（死锁！）
|
|||
|
|
printf("Thread 1: 获取到锁2\n");
|
|||
|
|
|
|||
|
|
pthread_mutex_unlock(&mutex2);
|
|||
|
|
pthread_mutex_unlock(&mutex1);
|
|||
|
|
return NULL;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
void *thread2(void *arg) {
|
|||
|
|
pthread_mutex_lock(&mutex2); // 获取锁2
|
|||
|
|
printf("Thread 2: 持有锁2，等待锁1...\n");
|
|||
|
|
sleep(1); // 等待，让线程1获取锁1
|
|||
|
|
pthread_mutex_lock(&mutex1); // 等待锁1（死锁！）
|
|||
|
|
printf("Thread 2: 获取到锁1\n");
|
|||
|
|
|
|||
|
|
pthread_mutex_unlock(&mutex1);
|
|||
|
|
pthread_mutex_unlock(&mutex2);
|
|||
|
|
return NULL;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int main() {
|
|||
|
|
pthread_t tid1, tid2;
|
|||
|
|
|
|||
|
|
pthread_create(&tid1, NULL, thread1, NULL);
|
|||
|
|
pthread_create(&tid2, NULL, thread2, NULL);
|
|||
|
|
|
|||
|
|
pthread_join(tid1, NULL);
|
|||
|
|
pthread_join(tid2, NULL);
|
|||
|
|
|
|||
|
|
printf("程序正常结束（如果这里能打印说明没有死锁）\n");
|
|||
|
|
return 0;
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**编译运行**：
|
|||
|
|
```bash
|
|||
|
|
gcc -o deadlock deadlock_demo.c -lpthread
|
|||
|
|
./deadlock
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**预期结果**：程序会卡住，无法正常结束（死锁）
|
|||
|
|
|
|||
|
|
### 示例2：避免死锁
|
|||
|
|
|
|||
|
|
```c
|
|||
|
|
// no_deadlock.c - 避免死锁（按顺序获取锁）
|
|||
|
|
#include <stdio.h>
|
|||
|
|
#include <stdlib.h>
|
|||
|
|
#include <pthread.h>
|
|||
|
|
|
|||
|
|
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
|
|||
|
|
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;
|
|||
|
|
|
|||
|
|
void *thread1(void *arg) {
|
|||
|
|
pthread_mutex_lock(&mutex1); // 先获取锁1
|
|||
|
|
printf("Thread 1: 持有锁1\n");
|
|||
|
|
sleep(1);
|
|||
|
|
pthread_mutex_lock(&mutex2); // 再获取锁2
|
|||
|
|
printf("Thread 1: 持有锁1和锁2\n");
|
|||
|
|
|
|||
|
|
pthread_mutex_unlock(&mutex2);
|
|||
|
|
pthread_mutex_unlock(&mutex1);
|
|||
|
|
return NULL;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
void *thread2(void *arg) {
|
|||
|
|
pthread_mutex_lock(&mutex1); // 也先获取锁1（顺序一致）
|
|||
|
|
printf("Thread 2: 持有锁1\n");
|
|||
|
|
sleep(1);
|
|||
|
|
pthread_mutex_lock(&mutex2); // 再获取锁2
|
|||
|
|
printf("Thread 2: 持有锁1和锁2\n");
|
|||
|
|
|
|||
|
|
pthread_mutex_unlock(&mutex2);
|
|||
|
|
pthread_mutex_unlock(&mutex1);
|
|||
|
|
return NULL;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
int main() {
|
|||
|
|
pthread_t tid1, tid2;
|
|||
|
|
|
|||
|
|
pthread_create(&tid1, NULL, thread1, NULL);
|
|||
|
|
pthread_create(&tid2, NULL, thread2, NULL);
|
|||
|
|
|
|||
|
|
pthread_join(tid1, NULL);
|
|||
|
|
pthread_join(tid2, NULL);
|
|||
|
|
|
|||
|
|
printf("程序正常结束\n");
|
|||
|
|
return 0;
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 示例3：银行家算法模拟
|
|||
|
|
|
|||
|
|
```python
|
|||
|
|
# banker.py - 银行家算法模拟
|
|||
|
|
def is_safe(available, max_need, allocation):
|
|||
|
|
"""检查系统是否处于安全状态"""
|
|||
|
|
n = len(allocation) # 进程数
|
|||
|
|
m = len(available) # 资源类型数
|
|||
|
|
|
|||
|
|
# 计算 Need 矩阵
|
|||
|
|
need = [[max_need[i][j] - allocation[i][j] for j in range(m)] for i in range(n)]
|
|||
|
|
|
|||
|
|
# 初始化工作向量和完成标志
|
|||
|
|
work = available.copy()
|
|||
|
|
finish = [False] * n
|
|||
|
|
safe_seq = []
|
|||
|
|
|
|||
|
|
while len(safe_seq) < n:
|
|||
|
|
found = False
|
|||
|
|
for i in range(n):
|
|||
|
|
if not finish[i]:
|
|||
|
|
# 检查是否可以分配
|
|||
|
|
if all(need[i][j] <= work[j] for j in range(m)):
|
|||
|
|
# 模拟分配
|
|||
|
|
for j in range(m):
|
|||
|
|
work[j] += allocation[i][j]
|
|||
|
|
finish[i] = True
|
|||
|
|
safe_seq.append(i)
|
|||
|
|
found = True
|
|||
|
|
|
|||
|
|
if not found:
|
|||
|
|
return False, [] # 不安全
|
|||
|
|
|
|||
|
|
return True, safe_seq
|
|||
|
|
|
|||
|
|
# 测试数据
|
|||
|
|
available = [3, 3, 2]
|
|||
|
|
max_need = [
|
|||
|
|
[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]
|
|||
|
|
]
|
|||
|
|
|
|||
|
|
safe, seq = is_safe(available, max_need, allocation)
|
|||
|
|
if safe:
|
|||
|
|
print(f"系统安全，安全序列: {seq}")
|
|||
|
|
else:
|
|||
|
|
print("系统不安全")
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 🔗 知识关联
|
|||
|
|
- 互斥锁在 [[07_多线程编程]] 中有详细讲解
|
|||
|
|
- 资源分配在 [[05_磁盘空间管理]] 中有类似概念
|
|||
|
|
- 银行家算法在 [[14_分页存储管理]] 中的页面置换有类似思想
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 📝 思考题
|
|||
|
|
|
|||
|
|
1. **为什么需要同时满足四个条件？** 如果只有三个条件满足会怎样？
|
|||
|
|
2. **银行家算法的局限性**：为什么它在实际系统中很少使用？
|
|||
|
|
3. **鸵鸟策略**：为什么有些系统选择忽略死锁问题？
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 📚 扩展阅读
|
|||
|
|
- 《操作系统概念》第7章：死锁
|
|||
|
|
- 《现代操作系统》第6章：死锁
|
|||
|
|
- [死锁检测算法](https://www.geeksforgeeks.org/deadlock-detection-algorithm/)
|