定义
- 两个或多个进程相互等待对方释放资源，导致所有相关进程都无法继续执行
- 若无外力作用，死锁进程将永远处于阻塞状态
死锁示例
- 交通死锁：四个方向的车互不相让，形成环路
- 哲学家就餐问题：5 个哲学家同时拿起左边筷子，循环等待右边筷子
重点 死锁产生的四个必要条件
- 互斥（Mutual Exclusion）：资源一次只能被一个进程使用
- 请求与保持（Hold and Wait）：进程已持有一个资源，又请求新的资源
- 不可剥夺（No Preemption）：资源在未使用完前不能被强行夺走
- 循环等待（Circular Wait）：存在进程 - 资源的循环等待链
重点 死锁处理策略对比
| 策略 | 方法 | 特点 |
|---|
| 死锁预防 | 破坏四个必要条件之一 | 实现简单，资源利用率低 |
| 死锁避免 | 银行家算法，动态检查安全性 | 资源利用率较高，需预知最大需求 |
| 死锁检测与恢复 | 检测到死锁后强行恢复 | 适用于容易回滚的系统 |
死锁预防（破坏必要条件）
- 破坏互斥：非共享设备不能破坏（如打印机不能共享）
- 破坏请求与保持：一次性申请所有资源（静态分配），资源利用率低
- 破坏不可剥夺：资源可被系统抢占，但可能导致进程回退
- 破坏循环等待：资源有序分配（给资源编号，必须按编号顺序申请）
重点 银行家算法（死锁避免）
基本思想
- 系统维护各进程所需资源的最大量，每次分配前检查是否处于安全状态
- 安全状态：存在安全序列使得所有进程最终能完成
单资源示例
- 10 个可用资源，3 个进程 P、Q、R，分别最多需要 8、4、9
- 当前已分配：P=5, Q=2, R=2（Available=1）
- 安全序列：Q → P → R（Q 还需 2，可得 1 + 后续回收）
数据结构（5 进程 3 资源类型）
| 矩阵 | 描述 |
|---|
| Available | 每类资源当前可用数量 |
| Max | 每个进程最多需要各类资源的数量 |
| Allocation | 每个进程当前已分配的资源数量 |
| Need | 每个进程还需要资源数量（Need = Max - Allocation） |
安全性检查算法
Work = Available，Finish[i] = false- 找满足
Finish[i] = false 且 Need[i] ≤ Work 的进程 i
Work = Work + Allocation[i]，Finish[i] = true，重复步骤 2- 如果所有
Finish[i] = true，则系统安全
示例：T0 时刻 5 进程 3 资源
假设资源 A=10, B=5, C=7，当前系统处于安全状态，存在安全序列 P1→P3→P4→P2→P0 等
资源分配图（RAG）
- 圆形节点 = 进程，矩形节点 = 资源类
- 资源 → 进程（分配边），进程 → 资源（请求边）
- 死锁检测：化简 RAG，如果存在不可化简的进程，则系统存在死锁
- 连续化简所有不阻塞的进程，最终仍阻塞的进程是死锁进程
死锁检测与恢复
检测
- 类似安全性检查算法，检测当前是否存在死锁进程
- 周期性检测或资源请求失败时触发
恢复方法
| 方法 | 描述 | 缺点 |
|---|
| 重启系统 | 强制重启所有进程 | 简单粗暴，所有工作丢失 |
| 终止死锁进程 | 终止部分或全部死锁进程 | 可能丢失数据 |
| 剥夺资源 | 从死锁进程处剥夺资源给其他进程 | 可能导致进程回退 |
| 进程回滚 | 将死锁进程回滚到某个安全检查点 | 需系统支持 checkpoint |