2.5操作系统（预防死锁避免死锁检测和解除死锁）

﹏ヽ暗。殇╰゛Y 2023-10-01 21:36 31阅读 0赞

**目录**

1.死锁

1.什么是死锁？

2.死锁、饥饿、死循环的区别

3.死锁产生的必要条件

4.什么时候会发生死锁

5.死锁的处理策略

2.死锁的处理策略——预防死锁

1.破坏互斥条件

2.破坏不剥夺条件

3.破坏请求和保持条件

4.破坏循环等待条件

3.死锁的处理策略——避免死锁

1.什么是安全序列

2.安全序列、不安全状态、死锁的联系

3.银行家算法

1. 实现步骤

2. 银行家算法示例（手算）

3. 代码实现

4.死锁的处理策略——检测和解除

1.死锁的检测

2. 死锁的解除

--------------------

> ![6c077b7a8d9e4ee8a2176b4d2f267b7e.png][] 个人主页：[个人主页][Link 1]  
> ![78ebf3e975d74a4ab1d20c57ee7b2791.png][] 系列专栏：[操作系统][Link 2]

##  ##

## 1.死锁 ##

### 1.什么是死锁？ ###

哲学家进餐问题中，如果5位哲学家进程并发执行，都拿起了左手边的筷子…

![在这里插入图片描述][f3e48696195f405b9b72f9f676e60a94.png_pic_center]

在并发环境下，各进程因竞争资源而造成的一种**互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进**的现象，就是**“死锁”**。

发生死锁后若无外力干涉，这些进程都将无法向前推进。

> 哲学家问题后续专栏会讲  
> ![78ebf3e975d74a4ab1d20c57ee7b2791.png][] 系列专栏：[操作系统][Link 2]

### 2.死锁、饥饿、死循环的区别 ###

**死锁**：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

**饥饿**：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先（SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。

**死循环**：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑 bug 导致的，有时是程序员故意设计的

![在这里插入图片描述][00c14d6d9703475087f804a4bf251a77.png_pic_center]

### 3.死锁产生的必要条件 ###

产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生。

**互斥条件** ：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。

**不剥夺条件** ：进程所获得的资源在未使用完之前，**不能由其他进程强行夺走**，只能主动释放。

**请求和保持条件** ：进程**已经保持了至少一个资源**，但又提出了新的资源**请求**，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源**保持**不放。

**循环等待条件** ：存在一种进程**资源的循环等待链**，链中的每一个进程已获得的资源同时被下一个进程所请求。

**注意！发生死锁时一定有循环等待，但是发生循环等待时未必死锁**（循环等待是死锁的必要不充分条件）

**如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了**

### 4.什么时候会发生死锁 ###

**对系统资源的竞争**。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的。

**进程推进顺序非法**。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2 分别申请并占有了资源 R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。

**信号量的使用不当也会造成死锁**。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）

**总之，对不可剥夺资源的不合理分配，可能导致死锁。**

### 5.死锁的处理策略 ###

**预防死锁**。破坏死锁产生的四个必要条件中的一个或几个。

**避免死锁**。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）

**死锁的检测和解除**。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。

## 2.死锁的处理策略——预防死锁 ##

![cb2cb520908043379e9b361c68986140.png][]

### 1.破坏互斥条件 ###

> **互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。**
> 
> 如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如: SPOOLing技术。操作系统可以采用 SPOOLing 技术把独占设备在逻辑上改造成共享设备。比如，用SPOOLing技术将打印机改造为共享设备…

> ![在这里插入图片描述][232716f8562a435aa18ffd832093c65b.png_pic_center]
> 
> 该策略的**缺点**：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，**很多时候都无法破坏互斥条件**。

###  2.破坏不剥夺条件 ###

> **不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。**
> 
> 破坏不剥夺条件：
> 
> ①、方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。  
> ②、方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）  
> 该策略的**缺点****：**  
> ①、实现起来比较复杂。  
> ②、释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
> 
> ③、反复地申请和释放资源会增加系统开销，降低系统吞吐量。  
> ④、若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

### 3.破坏请求和保持条件  ###

> **请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。**
> 
> 可以**采用静态分配方法**，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。
> 
> 该策略实现起来简单，但也有明显的**缺点**：  
> 有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，**资源利用率极低**。另外，该策略也有**可能导致某些进程饥饿**。
> 
> ![在这里插入图片描述][8d3aad3e7cb747ba93463fc21e5593f3.png_pic_center]

### 4.破坏循环等待条件  ###

> **循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。**
> 
> 可**采用顺序资源分配法**。首先给系统中的资源编号，规定每个进程**必须按编号递增的顺序请求资源**，同类资源（即编号相同的资源）一次申请完。
> 
> 原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。
> 
> ![在这里插入图片描述][50ced48b6ba54219a23380f487c95435.png_pic_center]
> 
> 该策略的**缺点**：  
> ①、不方便增加新的设备，因为可能需要重新分配所有的编号；  
> ②、进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费；  
> ③、必须按规定次序申请资源，用户编程麻烦

![852001bc526e47dd96e4b75e1a01adfb.png][]

## 3.死锁的处理策略——避免死锁  ##

![f8a7134598ba400883c25f4e8136e52c.png][]

###  1.什么是安全序列 ###

![在这里插入图片描述][0a965d597ed240caaa2cc9912011f87e.png_pic_center]

![在这里插入图片描述][ff6e9c526cdf435c9426ea48a03c596a.png_pic_center]

![在这里插入图片描述][ecf1991217544d7b87238105c8c5dcff.png_pic_center]

![在这里插入图片描述][af6a20a6dc714b58bbc676e94e9e058a.png_pic_center]

### 2.安全序列、不安全状态、死锁的联系 ###

![在这里插入图片描述][1f97c74fcd714765975dd611d90f46e5.png_pic_center]

> 所谓**安全序列**，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是**安全状态**。当然，**安全序列可能有多个。**
> 
> 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了**不安全状态**。这就意味着之后**可能**所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那**系统也有可能重新回到安全状态**，不过我们在分配资源之前总是要考虑到最坏的情况。**【比如A 先归还了10亿，那么就有安全序列T→B → A】**
> 
> 如果系统处于**安全状态**，就**一定不会**发生**死锁**。如果系统进入**不安全状态**，就**可能**发生**死锁**（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）
> 
> 因此可以**在资源分配之前预先判断这次分配是否会导致系统进入不安全状态**，以此决定是否答应资源分配请求。这也是“**银行家算法**”的核心思想。

### 3.银行家算法  ###

> 银行家算法是荷兰学者 Dijkstra 为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于**避免死锁**。
> 
> **核心思想**：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

![在这里插入图片描述][5e365aea51ec4b7cb49020981a44005d.png_pic_center]

####  1. 实现步骤 ####

![在这里插入图片描述][24ffffbe5f5640aa9794cf3dc67acf09.png_pic_center]  
![在这里插入图片描述][4ae333821375475baff298fa9f1c4211.png_pic_center]  
![在这里插入图片描述][54f42fa668f84df29775379988d95347.png_pic_center]

> 以此类推，共五次循环检查即可将5个进程都加入安全序列中，最终可得一个安全序列。该算法称为**安全性算法**。可以很方便地用代码实现以上流程，每一轮检查都从编号较小的进程开始检查。实际做题时可以更快速的得到安全序列。

#### 2. 银行家算法示例（手算） ####

**银行家算法示例（手算）**

![在这里插入图片描述][bd48e62856aa44f4a14b985712a1249d.png_pic_center]

**手算（找不到安全系列）**

![在这里插入图片描述][0c1c697e08684b1681b230384e74bbd5.png_pic_center]

#### 3. 代码实现 ####

> 假设**系统中有 n 个进程，m 种资源**
> 
> 每个进程在运行前先声明对各种资源的最大需求数，则可用一个 `n*m` 的矩阵（可用二维数组实现）表示所有进程对各种资源的**最大需求数**。不妨称为最大需求矩阵 `Max`，`Max[i, j]=K` 表示进程 `Pi` 最多需要 `K` 个资源`Rj`。同理，系统可以用一个 `n*m` 的**分配矩阵 Allocation**表示对所有进程的资源分配情况。`Max – Allocation =Need` 矩阵，表示各进程最多还需要多少各类资源。
> 
> 另外，还要用一个**长度为m的一维数组 Available** 表示当前系统中还有多少可用资源。
> 
> 某进程Pi向系统申请资源，可用一个**长度为m的一维数组 Requesti**表示本次申请的各种资源量。

![在这里插入图片描述][c80c8a3842be4aa8bdadbff60f6d9320.png_pic_center]  
![在这里插入图片描述][a3cedef958844322b6a563546f5ce145.png_pic_center]

> 数据结构：  
> ①、长度为 m 的一维数组 Available 表示还有多少可用资源  
> ②、n\*m 矩阵 Max 表示各进程对资源的最大需求数  
> ③、n\*m 矩阵 Allocation 表示已经给各进程分配了多少资源  
> ④、Max – Allocation = Need 矩阵表示各进程最多还需要多少资源  
> ⑤、用长度为 m 的一位数组 Request 表示进程此次申请的各种资源数  
> 银行家算法步骤：  
> ①、检查此次申请是否超过了之前声明的最大需求数  
> ②、检查此时系统剩余的可用资源是否还能满足这次请求  
> ③、试探着分配，更改各数据结构  
> ④、用安全性算法检查此次分配是否会导致系统进入不安全状态  
> 安全性算法步骤：  
> ①、检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。  
> ②、不断重复上述过程，看最终是否能让所有进程都加入安全序列。
> 
> **系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。**

## 4.死锁的处理策略——检测和解除  ##

![在这里插入图片描述][0dbc2d479dd74b558024a0666d58cb2c.png_pic_center]

> 如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很**可能发生死锁**。在这种情况下，系统应当提供两个算法：  
> **①死锁检测算法**：用于检测系统状态，以确定系统中是否发生了死锁。  
> **②死锁解除算法**：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

### 1.死锁的检测  ###

> 为了能对系统是否已发生了死锁进行检测，必须：  
> ①用**某种数据结构**来保存资源的请求和分配信息；  
> ②提供**一种算法**，利用上述信息来检测系统是否已进入死锁状态。

![在这里插入图片描述][2d7e2b0dfab74ec6819ae61e8f52df6e.png_pic_center]

> 如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。
> 
> 如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程…

![在这里插入图片描述][298befd829ab4bf3959e576518d62506.png]

> 如果按上述过程分析，最终**能消除所有边**，就称这个图是**可完全简化的**。此时**一定没有发生死锁**（相当于能找到一个安全序列）

![在这里插入图片描述][ed479d77d27448fe907dc7e13e961a0a.png_pic_center]

> 如果最终**不能消除所有边**，那么此时就是**发生了死锁**
> 
> **最终还连着边的那些进程就是处于死锁状态的进程。**

![在这里插入图片描述][4506f6a5894d4b59b7142fd46ae54947.png_pic_center]

### 2. 死锁的解除 ###

> 一旦检测出死锁的发生，就应该立即解除死锁。
> 
> 补充：并不是系统中所有的进程都是死锁状态，用死锁检测算法**化简资源分配图后，还连着边的那些进程就是死锁进程**
> 
> 解除死锁的主要方法有：  
> ①、**资源剥夺法**。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
> 
> ②、 **撤销进程法（或称终止进程法）** 。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
> 
> ③、 **进程回退法**。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

![在这里插入图片描述][e625ecfa096948278358766ae1fbceac.png_pic_center]

[6c077b7a8d9e4ee8a2176b4d2f267b7e.png]: https://img-blog.csdnimg.cn/6c077b7a8d9e4ee8a2176b4d2f267b7e.png
[Link 1]: https://blog.csdn.net/Javascript_tsj?type=blog
[78ebf3e975d74a4ab1d20c57ee7b2791.png]: https://img-blog.csdnimg.cn/78ebf3e975d74a4ab1d20c57ee7b2791.png
[Link 2]: https://blog.csdn.net/javascript_tsj/category_11676356.html?spm=1001.2014.3001.5482
[f3e48696195f405b9b72f9f676e60a94.png_pic_center]: https://img-blog.csdnimg.cn/f3e48696195f405b9b72f9f676e60a94.png#pic_center
[00c14d6d9703475087f804a4bf251a77.png_pic_center]: https://img-blog.csdnimg.cn/00c14d6d9703475087f804a4bf251a77.png#pic_center
[cb2cb520908043379e9b361c68986140.png]: https://img-blog.csdnimg.cn/cb2cb520908043379e9b361c68986140.png
[232716f8562a435aa18ffd832093c65b.png_pic_center]: https://img-blog.csdnimg.cn/232716f8562a435aa18ffd832093c65b.png#pic_center
[8d3aad3e7cb747ba93463fc21e5593f3.png_pic_center]: https://img-blog.csdnimg.cn/8d3aad3e7cb747ba93463fc21e5593f3.png#pic_center
[50ced48b6ba54219a23380f487c95435.png_pic_center]: https://img-blog.csdnimg.cn/50ced48b6ba54219a23380f487c95435.png#pic_center
[852001bc526e47dd96e4b75e1a01adfb.png]: https://img-blog.csdnimg.cn/852001bc526e47dd96e4b75e1a01adfb.png
[f8a7134598ba400883c25f4e8136e52c.png]: https://img-blog.csdnimg.cn/f8a7134598ba400883c25f4e8136e52c.png
[0a965d597ed240caaa2cc9912011f87e.png_pic_center]: https://img-blog.csdnimg.cn/0a965d597ed240caaa2cc9912011f87e.png#pic_center
[ff6e9c526cdf435c9426ea48a03c596a.png_pic_center]: https://img-blog.csdnimg.cn/ff6e9c526cdf435c9426ea48a03c596a.png#pic_center
[ecf1991217544d7b87238105c8c5dcff.png_pic_center]: https://img-blog.csdnimg.cn/ecf1991217544d7b87238105c8c5dcff.png#pic_center
[af6a20a6dc714b58bbc676e94e9e058a.png_pic_center]: https://img-blog.csdnimg.cn/af6a20a6dc714b58bbc676e94e9e058a.png#pic_center
[1f97c74fcd714765975dd611d90f46e5.png_pic_center]: https://img-blog.csdnimg.cn/1f97c74fcd714765975dd611d90f46e5.png#pic_center
[5e365aea51ec4b7cb49020981a44005d.png_pic_center]: https://img-blog.csdnimg.cn/5e365aea51ec4b7cb49020981a44005d.png#pic_center
[24ffffbe5f5640aa9794cf3dc67acf09.png_pic_center]: https://img-blog.csdnimg.cn/24ffffbe5f5640aa9794cf3dc67acf09.png#pic_center
[4ae333821375475baff298fa9f1c4211.png_pic_center]: https://img-blog.csdnimg.cn/4ae333821375475baff298fa9f1c4211.png#pic_center
[54f42fa668f84df29775379988d95347.png_pic_center]: https://img-blog.csdnimg.cn/54f42fa668f84df29775379988d95347.png#pic_center
[bd48e62856aa44f4a14b985712a1249d.png_pic_center]: https://img-blog.csdnimg.cn/bd48e62856aa44f4a14b985712a1249d.png#pic_center
[0c1c697e08684b1681b230384e74bbd5.png_pic_center]: https://img-blog.csdnimg.cn/0c1c697e08684b1681b230384e74bbd5.png#pic_center
[c80c8a3842be4aa8bdadbff60f6d9320.png_pic_center]: https://img-blog.csdnimg.cn/c80c8a3842be4aa8bdadbff60f6d9320.png#pic_center
[a3cedef958844322b6a563546f5ce145.png_pic_center]: https://img-blog.csdnimg.cn/a3cedef958844322b6a563546f5ce145.png#pic_center
[0dbc2d479dd74b558024a0666d58cb2c.png_pic_center]: https://img-blog.csdnimg.cn/0dbc2d479dd74b558024a0666d58cb2c.png#pic_center
[2d7e2b0dfab74ec6819ae61e8f52df6e.png_pic_center]: https://img-blog.csdnimg.cn/2d7e2b0dfab74ec6819ae61e8f52df6e.png#pic_center
[298befd829ab4bf3959e576518d62506.png]: https://img-blog.csdnimg.cn/298befd829ab4bf3959e576518d62506.png
[ed479d77d27448fe907dc7e13e961a0a.png_pic_center]: https://img-blog.csdnimg.cn/ed479d77d27448fe907dc7e13e961a0a.png#pic_center
[4506f6a5894d4b59b7142fd46ae54947.png_pic_center]: https://img-blog.csdnimg.cn/4506f6a5894d4b59b7142fd46ae54947.png#pic_center
[e625ecfa096948278358766ae1fbceac.png_pic_center]: https://img-blog.csdnimg.cn/e625ecfa096948278358766ae1fbceac.png#pic_center