产生死锁的根本原因是系统资源分配不足和进程推进顺序非法。
死锁和饥饿
共同点
死锁和饥饿都是进程无法顺利向前推进的现象。
不同点
- 发生饥饿的进程只可以有一个；而发生死锁的进程必然大于等于 2 个
- 发生饥饿的进程可以处于就绪态（因为长期没有被调度到），也可能处于阻塞态（长期没有获得所需的 I/O 设备）；而发生死锁的进程必定处于阻塞态
死锁产生的必要条件
- 互斥条件。进程要求对所分配的资源（如打印机）进行互斥使用
- 不可剥夺条件。进程获得的资源未用完不能被其他进程强行夺走
- 请求并保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求
- 循环等待条件。存在一个进程资源的循环等待链
死锁的处理策略
| 资源分配策略 | 各种可能模式 | 主要优点 | 主要缺点 | |
|---|---|---|---|---|
| 死锁预防 | 保守，宁可资源闲置 | 一次请求所有资源；资源剥夺；资源按序分配 | 适用于突发式处理的进程，不必进行剥夺 | 效率低，初始化时间延长；剥夺次数过多；不便灵活申请新资源 |
| 死锁避免 | 是预防和检测的折中（在运行时判断是否可能死锁） | 寻找可能的安全序列 | 不必进行剥夺 | 必须知道将来的资源需求；进程不能被长时间阻塞 |
| 死锁检测 | 宽松，只要允许就分配资源 | 定期检查死锁是否已经发生 | 不延长进程初始化时间；允许对死锁进行现场处理 | 通过剥夺解除死锁，造成损失 |
1. 死锁预防
设置某些限制条件，破环死锁的 4 个必要条件中的一个或几个。
(1) 破环互斥条件
将只能互斥使用的资源改造为允许共享使用。但是如打印机之类的资源肯定不可能共享访问，而且为了系统安全，很多时候要保护这种互斥性。（SPOOLing 技术是模拟成共享设备，实际还是互斥的）
(2) 破环不可剥夺条件
当一个已经保持了某些不可剥夺资源的进程，请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要再重新申请。
缺点
- 该策略实现起来比较复杂。释放已获得资源可能造成前一阶段工作的失效，因此这种方法常用于状态易于保存和恢复的资源，如 CPU 寄存器及内存资源，一般不用于打印机之类的资源
- 反复地申请和释放资源既影响进程推进速度，又增加系统开销，进而降低系统吞吐量
(3) 破环请求并保持条件
要求进程在请求资源时不能持有不可剥夺资源，可以通过两种方法实现：
- 采用预先静态分配方法。进程在运行前一次申请完它所需要得全部资源。缺点是系统资源严重浪费，还可能导致“饥饿”现象
- 允许进程只获得运行初期所需的资源后，便可开始运行。进程在运行过程中再逐步释放已分配给自己且已使用完毕的全部资源后，才能请求新的资源
(4) 破环循环等待条件
采用顺序资源分配法。首先给系统中的各类资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（编号相同的资源）一次申请完。
缺点
- 编号相对稳定，因此不利于增加新设备
- 实际使用的顺序可能和编号的次序不一致，造成资源的浪费
- 必须按规定次序申请资源，会给用户变成带来麻烦
2. 避免死锁
在资源的动态分配过程中，用某种方法防止系统进入不安全状态。
死锁一定是不安全状态；不安全状态可能进入死锁，但不是一定。
银行家算法
数据结构描述
Allocation：每个进程已分配到的各类资源数。 Need：每个进程还需要的各类资源数。 Available(Work)：还剩余可用的各类资源数。 Max：需要的最大资源数。Max=Need+Allocation
| Process | Allocation | Need | Available |
|---|---|---|---|
| P 0 | (0,0,3,2) | (0,0,1,2) | (1,6,2,2) |
| P 1 | (1,0,0,0) | (1,7,5,0) | |
| P 2 | (1,3,5,4) | (2,3,5,6) | |
| P 3 | (0,3,3,2) | (0,6,5,2) | |
| P 4 | (0,0,1,4) | (0,6,5,6) |
当 Available 大于进程的 Need 时，回收所有的 Allocation 到 Available 中，也就是完成该进程后，Available=Work+Allocation。
| Process | Work(Available) | Need | Allocation | Work+Allocation |
|---|---|---|---|---|
| P 0 | (1,6,2,2) | (0,0,1,2) | (0,0,3,2) | (1,6,5,4) |
| P 3 | (1,6,5,4) | (0,6,5,2) | (0,3,3,2) | (1,9,8,6) |
| P 1 | (1,9,8,6) | (1,7,5,0) | (1,0,0,0) | (2,9,8,6) |
| P 2 | (2,9,8,6) | (2,3,5,6) | (1,3,5,4) | (3,12,13,10) |
| P 4 | (3,12,13,10) | (0,6,5,6) | (0,0,1,4) | (3,12,14,14) |
若进程 P 2提出 Request (1,2,2,2) ，如果 Request<Need 且 Request<Available，则可以将资源分配给 P 2，分配完成后，Allocation+=Request，Need-=Request，Available-=Request
3. 死锁的检测及解除
死锁定理
- 如果资源分配图中没有环路，则系统中没有死锁
- 如果图中存在环路则系统中可能存在死锁
- 如果每个资源类中只包含一个资源，则环路是死锁存在的充分必要条件。
每种类型多个资源的死锁检测
不采用限制措施，在死锁发生后，才用某种措施接触死锁。
上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。
找到一个资源 P，如果 P 所请求的资源数量足够，则分配给 P，然后 P 归还所有的已获取的资源。用这个方法，对所有进程的出边和入边进行化简，若最后能消去所有边（也就是只剩进程结点和资源结点），则该图是可完全简化的，不存在死锁。
每种类型一个资源的死锁检测
每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。
死锁的解除
- 资源剥夺法。挂起某些死锁进程，并抢占它的资源
- 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源
- 进程回退法。让一个或多个死锁进程回退到足以回避死锁的地步。这要求系统保持进程的历史信息，设置还原点。