# 死锁的定义
一组进程中，每个进程都无限等待被该组进程中另一进程所占用的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。
# 活锁和饥饿
- 活锁：一组进程既无进展也没有阻塞，由于某些条件不满足导致一直在轮询。
- 饥饿：资源分配策略导致的错误。 ```java public void process_A() { enter_region(&resource_1); enter_region(&resource_2); use_both_resources(); leave_region(&resource_2); leave_region(&resoutce_1); }
public void process_B() { enter_region(&resource_2); enter_region(&resource_1); use_both_resources(); leave_region(&resource_1); leave_region(&resoutce_2); }
<a name="ZcLkQ"></a># # 死锁产生的必要条件产生死锁需要满足四个条件：1. 互斥使用（资源独占）：一个资源每次只能给一个进程使用。1. 占有且等待（请求和保持）：进程在申请新的资源的同时保持对原有资源的占用。1. 不可抢占：资源申请者不能强行的从资源占有者手中夺取资源，资源只能等待占有者自愿释放。1. 循环等待：多个进程组成一个环路，环路中的每个进程都在等待下一个进程所占用的资源。<a name="ZDnbA"></a># # 资源分配图系统由若干类资源构成：- 资源类：某一类资源称为一个资源类，用方框表示；- 资源实例：每个资源类中包含若干个同种资源，称为资源实例；<br />如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。<a name="SHF8v"></a>## | 资源分配图的化简1. 找一个非孤立、且只有分配边的进程结点，去掉分配边，将其变为孤立结点。1. 再把相应的资源分配给一个等待该资源的进程，即将该进程的申请边变为分配边。如果一个图可完全化简（所有的资源和进程都变成孤立的点），则不会产生死锁；如果一个图不可完全化简（即图中还有边存在），则会产生死锁。<a name="zdJJX"></a># # 死锁预防在设计系统时，通过确定资源分配算法，排除发生死锁的可能性。<br />只要防止产生死锁的四个必要条件中的任何一个条件发生即可。<a name="leYqF"></a>## | 破坏“互斥使用”条件把独占资源变为共享资源。例如 SPOOLing 技术把所有用户进程的输出都送入输出井，然后再由输出进程完成打印工作，而输出井在磁盘上，为共享设备。这样，SPOOLing技术就把打印机等独占设备改造成立共享设备。<a name="NS1ab"></a>## | 破坏“占有且等待”条件- 实现方案一：要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。- 问题：资源利用率低，会出现饥饿现象。- 实现方案二：在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。<a name="SIB5Z"></a>## | 破坏“不可抢占”条件当一个进程申请的资源被其他进程占用时，可以通过操作系统抢占这一资源（两个进程的优先级不同）。> 局限性：适用于状态易于保存和恢复的资源，例如内存。<a name="Eq9HX"></a>## | 破坏“循环等待”条件通过定义资源类型的线性顺序实现。把系统中的所有资源编号，进程在申请资源时必须严格按照资源编号的递增次序进行，否则操作系统不予分配。> 通常会按照资源使用的频繁编号。<a name="efIvy"></a># # 死锁避免在系统运行的过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统发生死锁或可能发生死锁，则不予分配，否则予以分配。<a name="eFruu"></a>## | 安全状态如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。<br /><br />例如从图 a 开始出发，先让 B 拥有所需的所有资源（图b），运行结束后释放 B，此时 Free 变为5（图c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 是安全状态。<a name="LvGN4"></a>## | 不安全状态如下图所示，图 b 即为不安全状态，因为它不能满足让后续的进程运行完毕。<br /><a name="CsNej"></a>## | 银行家算法<a name="YPFbT"></a>### * 单个资源条件一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。<br /><br />上图中，图 c 是一个不安全的状态。因为无论如何都不能满足任何一个客户的请求，所以算法会拒绝之前的请求，避免进入不安全状态。<a name="S3Y1j"></a>### * 多个资源条件<br />上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 为三个向量，分别表示：总资源、已分配资源以及可用资源。例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。<br />检查一个状态是否安全的算法如下：- 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。- 如果存在这样一行，将该进程标记为终止，并将其左图中的已分配资源加到 A 中。- 重复以上两步，直到所有进程都标记为终止，则状态时安全的。如果一个状态不是安全的，算法需要拒绝进入这个状态。<a name="T9x4q"></a># # 死锁检测与解除- 允许死锁的发生，但是操作系统会不断监视系统进展情况，判断死锁是否真的发生。- 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。> 检测时机：> 1. 当进程由于资源请求不满足而等待时检测死锁> 1. 定时检测> 1. 系统资源利用率下降时检测死锁<a name="T8UuD"></a>## | 死锁检测<a name="VLwz0"></a>### * 每种类型单个资源的死锁检测判断资源分配图是否满足环路等待条件，具体来说是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。<br /><a name="bDjd6"></a>### * 每种类型多个资源的死锁检测同多个资源条件时的银行家算法。<br /><a name="rNxEG"></a>## | 死锁解除- 利用撤销所有死锁进程解除- 利用抢占解除- 利用回滚再启动解除- 通过杀死进程解除<a name="VZq52"></a># # 鸵鸟算法> 鸵鸟：把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。<br />大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。<a name="kzn7k"></a># # 哲学家进餐问题五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。<br /><br />错误解法：如果所有的哲学家同时拿起了左边的筷子，那么所有哲学家都没有办法拿起右边的筷子，导致死锁。```java#define N 5void philosopher(int i) {while(TRUE) {think();take(i); // 拿起左边的筷子take((i+1)%N); // 拿起右边的筷子eat();put(i);put((i+1)%N);}}
防止死锁发生的解法：
若有收获，就点个赞吧
0 人点赞
