有时，一个进程申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变状态，这种情况称为死锁。
互斥
至少有一个资源必须处于非共享模式
占有并等待
一个进程应占有至少一个资源，并等待另一个资源，而该资源为其他进程占有
非抢占
资源不能被抢占，只能在任务完成后自愿释放
循环等待
资源的等待关系成循环。即有一组等待进程，P0等待资源为P1占有，P1等待的为P2占有，…，Pn等待的为P0占有
P集合：所有活动进程的集合；R集合：所有资源类型的集合；申请边：Pi→Rj；分配边：Rj→Pi
如果分配图没有环，那么系统一定没有进程死锁；如果有环则可能存在进程死锁
整体上有三种思路：
破坏死锁的4个必要条件中的一个。
很难破坏互斥条件。因为许多资源固有地就是非共享的。
保证进程申请一个资源时，没有占有其他资源。
如果一个进程在申请一个不能立即分配的资源，那么它已分配到的资源都可被抢占（隐式释放）。只有当它分配到该资源并且恢复被抢占的资源后，才能重新执行。
适合于状态可保存和恢复资源（如寄存器、内存），不适合其他资源（如信号量、互斥锁）。
对所有资源类型进行完全排序，要求每个进程按递增顺序来申请资源，申请多个同类资源时应一起申请。
每次分配前检测安全状态，安全则分配，不安全则暂缓分配。
只有存在一个安全序列，系统才处于安全状态。
安全序列是指一个进程序列<P1, P2, …, Pn> ，Pi仍然可以申请的资源数小于当前可用资源加上所有j<i的进程锁占有的资源，即当所有Pj完成时，Pi可得到所需的资源来完成自己。
安全状态一定不是死锁状态，死锁状态是非安全状态，但非安全状态不一定产生死锁。
适合于每种资源类型只有一个实例的情况。
除了申请边和分配边外，引入需求边Pi→Rj，用虚线，表示Pi可能在将来某个时刻申请Rj。当申请完成时，申请边反向，变为分配边。
如果在尝试满足一个申请，即将申请边转为分配边后，边成环，就是进入了非安全状态，不应进行此分配。
适合于每种资源类型有多个实例的情况。
进程进入系统时，声明可能需要的每种资源的实例的最大数量（不能超过系统资源总和）；用户申请资源时，系统应确定分配会不会让系统进入非安全状态。
n：进程数；m：资源种类数
Available：长度为m的向量，表示每种资源可用实例数量
Max：n×m矩阵，表示每个进程的最大需求
Allocation：n×m矩阵，表示每个进程目前获得的分配
Need：n×m矩阵，表示每个进程还需要的分配
性质：Need = Max - Allocation
安全算法：确定系统是否处于安全状态
Work：长度为m的向量，工作向量，初始化Work=Available
Finish：长度为n的向量，表示任务是否完成，初始化全false
- 找一个未完成的i，满足Need[i]≤Work（即当前工作向量能满足完成的需求）
- Finish[i]=true，即将它完成；Work += Allocation[i]，即交还分配，转第一步
- 如果第一步没有找到i，则检查Finish是否均为true，是的话即处于安全状态
资源请求算法：如何进行安全的资源请求
- 确认Request[i] ≤ Need[i]，否则该进程进行了过量需求
- 确认Request[i] ≤ Available，否则该进程要等待
- 修改状态：
- Available -= Request[i]，即进行分配
- Allocation += Request[i]，记录当前分配
- Need[i] -= Request[i]，削减需求
- 检查当前是否在安全状态，如果不，则恢复
使用wait-for图。在资源分配图中删去所有资源，适当合并边，即得到wait-for图。当且仅当在wait-for图中有一个环，系统发生死锁。
Work：长度为m的向量，工作向量，初始化Work=Available
Finish：长度为n的向量，表示任务是否完成，如果Allocation[i]不为0则false，否则true（当前没分到，等效于已经完成）
- 找一个未完成的i，满足Request[i]≤Work（即当前工作向量能满足完成的需求）
- Finish[i]=true，即将它完成；Work += Allocation[i]，即交还分配，转第一步
- 如果第一步没有找到i，则检查Finish，如果Finish[i]为false则系统死锁、进程i死锁
如果任意时间地检测，那么资源图可能有多个环，难以确定哪个进程造成了死锁。
不断地抢占一些进程的资源给其他进程使用，直到死锁循环被打破。
原文：https://www.cnblogs.com/zxuuu/p/12958117.html