一文带你通透理解死锁

待我称王封你为后i 2023-07-25 11:17 139阅读 0赞

## 一文带你通透理解死锁 ##

> 面试的时候，操作系统知识是必备的，而死锁是操作系统知识中重要的一环。
> 
> 所以想找到好工作，通透了解死锁概念是必须的

### 死锁产生的四个条件(必须同时满足) ###

*  **互斥条件**：一个资源一次只能被一个进程占有
 *  **持有并等待**：进程因为请求资源阻塞时，对已获取的资源不释放
 *  **不可抢占**：进程已经获取的资源在使用过程中不能被其他进程抢占，只能使用完后，由该进程自己释放
 *  **环路等待**:多个进程之间形成一种互相循环等待资源的关系
    
     p 1 p1 p1进程持有 R 2 R2 R2，请求 R 1 R1 R1。 p 2 p2 p2进程持有 R 1 R1 R1，请求 R 2 R2 R2
    
    ![Center][]

### 死锁解决方法 → \\rightarrow → 死锁的预防 ###

死锁的预防：不允许死锁发生，可以从破除死锁发生的四个必要条件入手，因为**如果不同时具备**

**上述四个必要条件，那么死锁就一定不会发生**

*  互斥条件，程序并发必不可少的一种机制，难以避免。
 *  持有并等待：**不持有等待**：如果一个进程一次请求获取不了所有资源，那么其不占用任何资源。**持有不等待**：如果资源充足，只要申请请求资源，就分配给其资源，不使其等待。
 *  不可抢占：如果一个进程所请求的资源被另一进程占有，使它可以抢占另一进程占有的资源
 *  环路等待：对资源进行排序，即每个进程访问资源的顺序都是固定的。

### 死锁的解决方法 → \\rightarrow →死锁的避免 ###

死锁防止方法能够防止死锁发生，但必然会降低系统并发性，导致低效的资源利用率。

死锁避免是在程序运行时避免发生死锁。

### 单个资源的银行家算法 ###

一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。（**总共10个资源**）

![img][]

上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。

### 多个资源的银行家算法 ###

![img][img 1]

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

*  查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
 *  假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
 *  重复以上两步，直到所有进程都标记为终止，则状态时安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。

### 死锁解决方法 → \\rightarrow →死锁检测和恢复 ###

**不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复**

*  如果`进程-资源分配图`中无环路，此时系统没有发生死锁
 *  如果`进程-资源分配图`中有环路，分为一下两种情况
    
     *  每种资源类仅有一个资源，则系统发生了死锁
     *  每种资源类中有多个资源，系统未必会发生死锁

#### 死锁检测(针对每种资源类中有多个资源) ####

![img][img 2]

每个资源类用一个方框表示，方框中的原点表示此资源类中的各个资源；

每个进程用一个圆圈来表示，用有向边表示进程申请资源和资源分配情况。

约定方框→圆圈表示资源分配，圆圈→方框表示申请资源。

这种情况下，图3-6 发生了死锁，而图3-7没有发生死锁。

![img][img 3]

#### 死锁恢复 ####

*  **资源剥夺法**：剥夺陷于死锁的进程所占用的资源，但并不撤销此进程，直至死锁解除。
 *  **进程回退法**：根据系统保存的检查点让所有的进程回退，直到足以解除死锁，这种措施要求系统建立保存检查点、回退及重启机制。
 *  **进程撤销法**
 *   *  撤销陷入死锁的所有进程，解除死锁，继续运行。
     *  逐个撤销陷入死锁的进程，回收其资源并重新分配，直至死锁解除。

### 参考文献 ###

[死锁的产生、防止、避免、检测和解除][Link 1]

[操作系统之死锁与死锁的处理][Link 2]

[Center]: /images/20230528/d207932ec7fe44d5877a9779262d4b5a.png
[img]: /images/20230528/e4981cd51baa447a98c52648c10475cb.png
[img 1]: /images/20230528/3d4f8193d4024621b7360e8cfe398471.png
[img 2]: /images/20230528/3c89b9e7e92d4695849831195e6b0fcd.png
[img 3]: /images/20230528/8d073a4f4ff7415c97c9078545d99058.png
[Link 1]: https://zhuanlan.zhihu.com/p/61221667
[Link 2]: https://blog.csdn.net/weiyongle1996/article/details/71511956