04. 死锁
死锁
基本概念
死锁定义
死锁：多个进程因竞争资源而造成的一种互相等待的现象，若无外力作用，这些进程都将无法向前推进。
死锁特征：
- 互斥条件：资源不能被多个进程同时使用
- 请求和保持条件：进程在等待其他资源时，不释放已占有的资源
- 不可剥夺条件：资源不能被强制剥夺
- 循环等待条件：存在进程等待链，形成循环
死锁示例
经典死锁场景：
进程A持有资源R1，请求资源R2
进程B持有资源R2，请求资源R1
资源分配图：
R1 -----> P1
| |
| v
| P2
| |
R2 <------|
死锁预防
破坏互斥条件
策略：使用可共享的资源，避免互斥访问。
方法：
- 使用只读资源
- 使用虚拟化技术
- 使用资源池
示例：
// 使用共享内存而不是互斥锁
shared_memory *data = get_shared_memory();
// 多个进程可以同时读取
read_data(data);
破坏请求和保持条件
策略：进程必须一次性申请所有需要的资源。
方法：
- 资源预分配：进程开始执行前申请所有资源
- 资源释放：申请新资源前释放所有已占有的资源
示例：
// 一次性申请所有资源
void process() {
acquire_all_resources();
// 执行任务
release_all_resources();
}
破坏不可剥夺条件
策略：允许资源被强制剥夺。
方法：
- 设置资源优先级
- 实现资源抢占机制
- 使用超时机制
示例：
// 资源抢占
void resource_preemption() {
if (high_priority_process_needs_resource()) {
preempt_resource_from_low_priority_process();
allocate_resource_to_high_priority_process();
}
}
破坏循环等待条件
策略：对资源进行编号，进程只能按编号顺序申请资源。
方法：
- 资源有序分配
- 资源编号策略
- 资源层次结构
示例：
// 资源编号：R1=1, R2=2, R3=3
void ordered_resource_allocation() {
// 只能按编号顺序申请
acquire_resource(1); // R1
acquire_resource(2); // R2
acquire_resource(3); // R3
// 不能先申请R3再申请R1
}
死锁避免
银行家算法
原理：在分配资源前检查是否会导致不安全状态，只有在安全状态下才分配资源。
数据结构：
int available[RESOURCES]; // 可用资源
int maximum[PROCESSES][RESOURCES]; // 最大需求
int allocation[PROCESSES][RESOURCES]; // 已分配
int need[PROCESSES][RESOURCES]; // 需求
安全状态检查：
bool is_safe_state() {
int work[RESOURCES];
bool finish[PROCESSES];
// 初始化
for (int i = 0; i < RESOURCES; i++)
work[i] = available[i];
for (int i = 0; i < PROCESSES; i++)
finish[i] = false;
// 查找可以完成的进程
for (int count = 0; count < PROCESSES; count++) {
bool found = false;
for (int i = 0; i < PROCESSES; i++) {
if (!finish[i] && can_allocate(i, work)) {
// 分配资源给进程i
for (int j = 0; j < RESOURCES; j++)
work[j] += allocation[i][j];
finish[i] = true;
found = true;
}
}
if (!found) return false; // 不安全状态
}
return true; // 安全状态
}
资源分配算法：
bool request_resources(int process_id, int request[]) {
// 检查请求是否超过需求
for (int i = 0; i < RESOURCES; i++) {
if (request[i] > need[process_id][i])
return false;
}
// 检查是否有足够资源
for (int i = 0; i < RESOURCES; i++) {
if (request[i] > available[i])
return false;
}
// 尝试分配资源
for (int i = 0; i < RESOURCES; i++) {
available[i] -= request[i];
allocation[process_id][i] += request[i];
need[process_id][i] -= request[i];
}
// 检查是否安全
if (is_safe_state()) {
return true; // 分配成功
} else {
// 恢复原状态
for (int i = 0; i < RESOURCES; i++) {
available[i] += request[i];
allocation[process_id][i] -= request[i];
need[process_id][i] += request[i];
}
return false; // 分配失败
}
}
资源分配图算法
原理：使用有向图表示资源分配情况，检测是否存在环路。
图的构成：
- 节点：进程和资源
- 边：资源分配和请求关系
检测算法：
bool detect_deadlock() {
// 简化资源分配图
while (存在可以简化的节点) {
// 找到可以简化的进程节点
for (每个进程节点P) {
if (P的所有请求都能满足) {
// 删除P的所有边
remove_all_edges_from(P);
// 标记P为可简化
mark_as_simplified(P);
}
}
}
// 检查是否还有边
if (图中还有边)
return true; // 存在死锁
else
return false; // 不存在死锁
}
死锁检测
资源分配图
图的表示：
- 圆形节点：进程
- 方形节点：资源
- 实线箭头：资源分配（资源 → 进程）
- 虚线箭头：资源请求（进程 → 资源）
示例：
R1(1) -----> P1
| |
| v
| P2
| |
R2(1) <------|
检测算法
简化算法：
- 找到没有请求边的进程节点
- 删除该节点的所有分配边
- 重复步骤 1-2，直到无法简化
- 如果图中还有边，则存在死锁
实现：
bool detect_deadlock_using_graph() {
// 构建资源分配图
build_resource_allocation_graph();
// 简化图
while (true) {
bool simplified = false;
// 查找可以简化的进程
for (每个进程P) {
if (P没有请求边) {
// 删除P的所有分配边
remove_allocation_edges(P);
simplified = true;
}
}
if (!simplified) break;
}
// 检查是否还有边
return has_remaining_edges();
}
检测时机
检测策略：
- 定期检测：每隔一定时间检测一次
- 按需检测：当进程请求资源时检测
- 资源耗尽检测：当某种资源耗尽时检测
检测开销：
- 时间复杂度：O(n²)，n 为进程数
- 空间复杂度：O(n×m)，m 为资源类型数
死锁恢复
进程终止
策略：终止部分或全部死锁进程。
方法：
- 终止所有死锁进程：简单但损失大
- 逐个终止死锁进程：选择代价最小的进程终止
选择标准：
- 进程优先级
- 进程已运行时间
- 进程剩余时间
- 进程使用的资源数量
示例：
void terminate_deadlocked_processes() {
// 计算每个进程的终止代价
for (每个死锁进程P) {
cost[P] = calculate_termination_cost(P);
}
// 选择代价最小的进程终止
while (存在死锁) {
process = find_minimum_cost_process();
terminate_process(process);
release_resources(process);
}
}
资源抢占
策略：从某些进程抢占资源，分配给其他进程。
方法：
- 选择牺牲进程：选择代价最小的进程
- 回滚到安全状态：将进程回滚到某个检查点
- 重新分配资源：将抢占的资源分配给其他进程
回滚机制：
void resource_preemption() {
// 选择牺牲进程
victim = select_victim_process();
// 回滚到检查点
rollback_to_checkpoint(victim);
// 释放资源
release_resources(victim);
// 重新分配资源
redistribute_resources();
}
检查点机制
原理：定期保存进程状态，发生死锁时可以回滚。
实现：
// 保存检查点
void save_checkpoint(int process_id) {
checkpoint[process_id] = {
.registers = get_process_registers(process_id),
.memory = get_process_memory(process_id),
.resources = get_process_resources(process_id)
};
}
// 回滚到检查点
void rollback_to_checkpoint(int process_id) {
restore_process_state(process_id, checkpoint[process_id]);
}
死锁处理策略比较
策略选择
| 策略 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 预防 | 完全避免死锁 | 资源利用率低 | 实时系统 |
| 避免 | 资源利用率较高 | 需要预知资源需求 | 批处理系统 |
| 检测 | 资源利用率最高 | 检测和恢复开销大 | 通用系统 |
| 忽略 | 实现简单 | 可能导致系统挂起 | 开发环境 |
实际应用
操作系统选择：
- Windows：主要使用死锁检测和恢复
- Linux：主要使用死锁预防和避免
- 实时系统：主要使用死锁预防
选择考虑因素：
- 系统类型：实时系统、分时系统、批处理系统
- 资源特性：资源数量、资源类型、资源分配模式
- 性能要求：响应时间、吞吐量、资源利用率
- 可靠性要求：系统稳定性、故障恢复能力
死锁案例分析
案例 1：哲学家进餐问题
问题描述：
- 5 个哲学家围坐在圆桌旁
- 每个哲学家需要两根筷子才能进餐
- 筷子放在哲学家之间
死锁情况：
所有哲学家同时拿起左边的筷子
然后等待右边的筷子
形成循环等待
解决方案：
// 使用资源有序分配
void philosopher(int i) {
int left = i;
int right = (i + 1) % 5;
// 总是先申请编号小的筷子
if (left < right) {
acquire_chopstick(left);
acquire_chopstick(right);
} else {
acquire_chopstick(right);
acquire_chopstick(left);
}
eat();
release_chopstick(left);
release_chopstick(right);
}
案例 2：数据库死锁
问题描述：
- 事务 A 持有锁 L1，请求锁 L2
- 事务 B 持有锁 L2，请求锁 L1
解决方案：
-- 使用超时机制
SET LOCK_TIMEOUT 5000; -- 5秒超时
-- 使用死锁检测
SET DEADLOCK_PRIORITY LOW; -- 设置死锁优先级
-- 使用资源有序分配
-- 总是按固定顺序申请锁
BEGIN TRANSACTION;
UPDATE table1 SET column1 = value1 WHERE id = 1;
UPDATE table2 SET column2 = value2 WHERE id = 1;
COMMIT;