王道操作系统笔记（六）—— 死锁的处理策略

太过爱你忘了你带给我的痛 2023-10-11 20:37 6阅读 0赞

#### 文章目录 ####

*  一、死锁的概念
 *   *  1.1 死锁的定义
     *  1.2 死锁、饥饿、死循环的区别
     *  1.3 死锁产生的必要条件
     *  1.4 死锁发生的时机
 *  二、死锁的处理策略
 *   *  2.1 死锁预防
     *  2.2 死锁避免
     *   *  2.2.1 系统安全状态
         *  2.2.2 银行家算法
         *  2.2.3 典型例题
     *  2.3 死锁的检测和解除
     *   *  2.3.1 资源分配图
         *  2.3.2 死锁定理
         *  2.3.3 死锁解除
     *  2.4 补充：常见题型
     *   *  2.4.1 资源数已知，进程数未知
         *  2.4.1 进程数已知，资源数未知

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

## 一、死锁的概念 ##

### 1.1 死锁的定义 ###

在并发环境下，各进程因竞争资源而造成的一种 互相等待对方手里的资源，导致各进程都阻塞待对方手里的资源，导致各进程都阻塞，都无法向前推进，都无法向前推进的现象，就是死锁。发生死锁后若无外力干涉，这些进程都将无法向前推进。

### 1.2 死锁、饥饿、死循环的区别 ###

![在这里插入图片描述][e19b4b897d5a4a379d3858a27360abaa.png_pic_left]

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

### 1.3 死锁产生的必要条件 ###

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

> ① 互斥条件：只有对必须 互斥使用的资源的争抢 才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。  
> ② 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。  
> ③ 请求和保持条件：进程已经 保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。  
> ④ 循环等待条件：存在一种进程资源的 循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

注：发生死锁时一定有循环等待，但是发生循环等待时未必死锁，即 循环等待是死锁的必要不充分条件。  
![在这里插入图片描述][8d5f352afa3940b1a3e13deab4bd1e7f.png_pic_left]  
  如果同类资源数大于1，则即使有循环等待，也未必发生死锁（如上图 Pn 可以同时请求 P1 或者 Pk 的资源，得到 Pk 资源后，不会发生死锁）。 但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。

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

### 1.4 死锁发生的时机 ###

1.  **对系统资源的竞争。** 各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的。
2.  **进程推进顺序非法。** 请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2 分别申请并占有了资源 R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
3.  **信号量的使用不当也会造成死锁。** 如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。

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

## 二、死锁的处理策略 ##

死锁的处理策略有三种：死锁预防、避免死锁和死锁的检测和解除。  
其中，死锁预防、死锁避免 两种策略 不允许死锁发生，死锁的检测和解除 策略 允许死锁发生。

![在这里插入图片描述][241b5bccade14529a4f30db375632a0a.png_pic_left]

### 2.1 死锁预防 ###

死锁的产生必须满足四个必要条件，只要其中一个或者几个条件不满足，死锁不会发生。

1.  **`破坏互斥条件`**  
    把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。如: SPOOLing技术。使用 SPOOLing 技术可以把 独占设备在逻辑上改造成共享设备。
    
    **策略的缺点：** 不是所有的资源都可以改造成可共享使用的资源。并且互斥性对于系统安全很重要。因此，很多时候都无法破坏互斥条件。
2.  **`破坏不剥夺条件`**  
    提供两种方案：① 申请资源得不到时，主动释放所占有资源。② 申请资源被其他进程占用时，由 OS 协助剥夺。
    
    **策略的缺点：** 实现起来比较复杂； 释放已获得的资源可能造成前一阶段工作的失效；反复地申请和释放资源会增加系统开销，降低系统吞吐量；方案 ① 可能导致进程饥饿。
3.  **`破坏破坏请求和保持条件`**  
    采用 静态分配方法，即进程 在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。
    
    **策略的缺点：** 进程在整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有 可能导致某些进程饥饿。
4.  **`破坏循环等待条件`**  
    采用 顺序资源分配法。首先给系统中的资源编号，要求进程只能按编号递增顺序请求资源。
    
    **原理分析：** 一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象(类比拓扑排序)。  
    **策略的缺点：** 不方便增加新的设备，因为可能需要重新分配所有的编号；进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费；必须按规定次序申请资源，用户编程麻烦。  
      
    ![在这里插入图片描述][dac72c1e166b4f3294dc151c3689394e.png_pic_left]

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

### 2.2 死锁避免 ###

死锁的避免是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。

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

#### 2.2.1 系统安全状态 ####

系统在资源分配之前，应 先计算 此次分配的安全性，若此次分配不会导致系统进入 不安全状态，则允许分配，否则让系统等待。安全状态 是指系统能按某种进程的 推进顺序 为每个进程 Pi 分配其所需的资源，使每个进程都可顺序完成。所谓的推进顺序就是安全序列。

简而言之：观察系统是否存在安全序列。如果存在，系统则处于安全状态；如果不存在系统则处于不安全状态。

**安全序列的计算方法：**  
  已知现有三个进程的资源分配表如下(可用代表系统还剩有 3 个资源)，现假设可用资源每次分配都是全部分配，并且分配给进程的资源总数应满足进程最多还需求的资源数目(如：可用资源有 3 个，由于 P2 进程还需要 2 个资源，因此只能满足 P2)，分配完后回收该进程所拥有的全部资源。

![在这里插入图片描述][a8fd403d874141cfbece5486934dc73a.png_pic_left]  
计算步骤如下：  
![在这里插入图片描述][9241e0fb8dfa413d807a6f11194279f0.png_pic_left]  
因此得到安全序列是 \{P2, P1, P3\}。

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

如果计算到 P3 时，可用资源无法满足 P3 的最大需求，即还需要的资源数目多于可用资源数目，那么就不存在安全序列。  
![在这里插入图片描述][a1fbffe7bdad4cc99de2dd8f1d28e8f4.png_pic_left]

注：死锁状态一定是不安全状态，不安全状态不一定是死锁状态，即：死锁状态 ⇒ 不安全状态。  
如：A 进程需 10 个资源，而可用资源有 5 个。若 A 还未提出申请，则不会进入死锁状态。  
系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统变可避免进入死锁。

`当系统处于安全状态时，系统中一定无死锁。(✓) 当系统处于不安全状态时，系统一定会出现死锁进程。(×) (来源：2013年408真题)`

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

#### 2.2.2 银行家算法 ####

**核心思想：** 在分配资源前，预先判断这次分配是否会导致系统进入不安全状态，以此来决定是否答应资源分配请求，从而使得系统避免死锁。

*  **数据结构描述：**  
    ① 可利用资源向量  A v a i l a b l e Available Available（一维数据）、② 最大需求矩阵  M a x Max Max、③ 分配矩阵  A l l o c a t i o n Allocation Allocation、④ 需求矩阵  N e e d Need Need  
    以上三个矩阵间存在的关系：  N e e d = M a x − A l l o c a t i o n Need = Max - Allocation Need=Max−Allocation
    
    ![在这里插入图片描述][c49ba6619b9b4d5aa0a933ee740b8493.png_pic_left]  
    注： A v a i l a b l e ( A , B , C ) = ( 3 , 3 , 2 ) Available(A,B,C)=(3,3,2) Available(A,B,C)=(3,3,2) 代表可用的 A 类资源数目有 3 个，B 类资源数目有3个，C 类资源数目有 2 个。
 *  **银行家算法描述（只需看蓝字）：**
    
    设  R e q u e s t i Request\_i Requesti 是进程  P i Pi Pi 的请求向量， R e q u e s t i \[ j \] = K Request\_i\[j\]=K Requesti\[j\]=K 表示进程  P i Pi Pi 需要  j j j 类资源  K K K个。  
    ① 若  R e q u e s t i \[ j \] ≤ N e e d \[ i , j \] Request\_i\[j\]≤Need\[i,j\] Requesti\[j\]≤Need\[i,j\]，检查此次申请是否超过最多还需求数。  
    ② 若  R e q u e s t i \[ j \] ≤ A v a i l a b l e \[ j \] Request\_i\[j\]≤Available\[j\] Requesti\[j\]≤Available\[j\]，检查系统的可用资源是否还能满足此次需求。  
    ③ 系统 试探着 把资源分配给  P i Pi Pi，并修改下面数据结构的数值：  
     A v a i l a b l e = A v a i l a b l e − R e q u e s t i Available = Available - Request\_i Available=Available−Requesti，修改 i 进程剩余可用资源数  
     A l l o c a t i o n \[ i , j \] = A l l o c a t i o n \[ i , j \] + R e q u e s t i \[ j \] Allocation\[i,j\] = Allocation\[i,j\]+Request\_i\[j\] Allocation\[i,j\]=Allocation\[i,j\]\+Requesti\[j\]，i 进程已分配资源数加上本次请求资源数  
     N e e d \[ i , j \] = N e e d \[ i , j \] − R e q u e s t i \[ j \] Need\[i,j\]=Need\[i,j\]-Request\_i\[j\] Need\[i,j\]=Need\[i,j\]−Requesti\[j\]，i 进程还需的资源数减去本次请求的资源数  
    ④ 执行安全性算法，检查系统是否处于安全状态，即检查当前系统是否存在安全序列。  
    若系统安全，才正式将资源分配给  P i Pi Pi；否则此次试探分配作废，恢复原来分配状态。  
    注：安全性算法是银行家算法的核心。
 *  **安全性算法描述：**
    
    设置工作向量  W o r k Work Work，表示系统中剩余可用资源数目。算法执行开始时， W o r k = A v a i l a b l e Work=Available Work=Available。  
    ① 初始时安全序列为空。  
    ② 检查当前的剩余资源是否能满足某个进程的最大需求。如果可以就将它加入安全序列；若找不到执行步骤 ④   
    ③ 把该进程持有资源全部回收，返回步骤 ②  
    ④ 若此时安全序列中已有所有进程，则系统处于安全状态，否则处于不安全状态。

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

#### 2.2.3 典型例题 ####

假设当前系统中资源分配和剩余情况如下表所示，现  P 1 P\_1 P1 发出请求向量  R e q u e s t 1 ( 1 , 0 , 2 ) Request\_1(1,0,2) Request1(1,0,2)，判断此次请求是否分配成功。  
![在这里插入图片描述][c49ba6619b9b4d5aa0a933ee740b8493.png_pic_left]

① 系统按银行家算法进行检查：

R e q u e s t 1 ( 1 , 0 , 2 ) ≤ N e e d 1 ( 1 , 2 , 2 ) ， R e q u e s t 1 ( 1 , 0 , 2 ) ≤ A v a i l a b l e ( 3 , 2 , 2 ) Request\_1(1,0,2)≤Need\_1(1,2,2)，Request\_1(1,0,2)≤Available(3,2,2) Request1(1,0,2)≤Need1(1,2,2)，Request1(1,0,2)≤Available(3,2,2)  
此次申请未超过P1进程最多还需求数，并且当前可用资源数可满足此次申请，则可试探的为P1分配资源，并修改：  
 A v a i l a b l e = A v a i l a b l e − R e q u e s t 1 = ( 2 , 3 , 0 ) Available=Available-Request\_1=(2,3,0) Available=Available−Request1=(2,3,0)  
 A l l o c a t i o n 1 = A l l o c a t i o n 1 + R e q u e s t 1 = ( 3 , 0 , 2 ) Allocation\_1= Allocation\_1+Request\_1=(3,0,2) Allocation1=Allocation1\+Request1=(3,0,2)  
 N e e d 1 = N e e d 1 − R e q u e s t 1 = ( 0 , 2 , 0 ) Need\_1=Need\_1-Request\_1=(0,2,0) Need1=Need1−Request1=(0,2,0)

![在这里插入图片描述][8fe6c5cad74c4e598da0d01b2a5f4054.png_pic_left]  
② 系统执行安全性算法检查安全状态：

令  W o r k = A v a i l a b l e = ( 2 , 3 , 0 ) Work=Available=(2,3,0) Work=Available=(2,3,0)，执行安全性算法，如下表所示：  
![在这里插入图片描述][9bab9019c27e4561adcb1d022b605be9.png_pic_left]  
由安全性检查而知，可以找到一个安全序列 \{ P1, P3, P4, P0, P2 \}，因此系统是安全的，可以将P1所申请的资源分配给他。

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

### 2.3 死锁的检测和解除 ###

如果系统既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供死锁检测和解除的手段。

#### 2.3.1 资源分配图 ####

系统死锁可利用 资源分配图 来描述。圆代表一个进程，框代表一类资源，框中一个圆代表一类资源中的一个资源。从进程到资源的有向边称为请求边，表示进程想申请几个资源，每条边代表一个。从资源到进程的边称为分配边，表示已经为进程分配了几个资源，每条边代表一个。

![在这里插入图片描述][ad8c5ea4cdbd48d99508aeb1f00065a8.png_pic_left]  
如上图，进程 P1 已经分得了两个 R1 资源，并又请求了一个 R2 资源；进程 P2 分得了一个 R1 资源和一个 R2资源，并又请求了一个 R1 资源。

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

#### 2.3.2 死锁定理 ####

简化资源分配图可检测系统状态是否为死锁状态。简化方法如下：

① 在资源分配图中，找出 既不阻塞又不是孤点的进程 Pi。

*  不阻塞：表示进程申请的资源可以被满足，如 P1 进程。由于 R2 资源除分配给 P2 进程一个资源外，还剩有一个资源，因此 P1 进程申请的 R2 资源可以被满足。相反，P2 进程申请 R1 资源则不会被满足，由于 R1 资源全部被分配完。
 *  不是孤点：表示与该进程节点至少一个边相连。

② 消去进程所有的请求边和分配变，使之称为孤点。  
 在下图中，P1 是满足这一条件的进程结点，于是将P1的所有边消去。

重复以上步骤，若能消去图中所有的边，则称该图是可完全简化的。

![在这里插入图片描述][cda1e353f29f4499baeed8c070096631.png_pic_left]  
注：并不是系统中所有的进程都是死锁状态，用死锁检测算法 化简资源分配图后，还连着边的那些进程就是死锁进程。

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

#### 2.3.3 死锁解除 ####

一旦检测出死锁的发生，就应该立即解除死锁。解除死锁的主要方法有：

1.  **`资源剥夺法`**  
    挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是 应防止被挂起的进程长时间得不到资源而饥饿。
2.  **`撤销进程法`**  
    又称终止进程法，强制撤销部分甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
3.  **`进程回退法`**  
    让一个或多个死锁进程回退到足以避免死锁的地步。进程回退时，自愿释放资源而非剥夺。这就要求系统要记录进程的历史信息，设置还原点。

注：撤销进程法中参考的优先级，应考虑：进程优先级、已执行多长时间、还要多久能完成、进程已经使用了多少资源、进程是交互式的还是批处理式的等因素。

`死锁的避免方法需要进程运行所需资源的总量信息，而死锁的检测方法不需要。(✓) 解析：死锁的避免应用银行家算法，需要资源的使用情况等信息。而应用死锁定理检测死锁，只需通过资源分配图化简情况来检测死锁，不需要资源的总量信息(资源分配图中包含进程使用资源的情况)。 (来源：2015年408真题)`

![在这里插入图片描述][21400358088a4c9aa92736f337bcf8de.png_pic_left]

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

### 2.4 补充：常见题型 ###

#### 2.4.1 资源数已知，进程数未知 ####

![在这里插入图片描述][e883d145a68c4ca391be4f6aa2455e4e.png_pic_left]  
注：可能发生死锁参考上文，如：A 进程需 10 个资源，而可用资源有 5 个。若 A 还未提出申请，则不会进入死锁状态。

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

> **例1：** 某系统中共有 11 台磁带机，X 个进程共享此磁带机设备，每个进程最多请求使用 3 台，则系统必然不会死锁的最大 X 值是( B )。  
>    A.4    B.5    C.6    D.7  
> **解析：**每个进程分配 2 台设备后还剩 1 个资源，则至少有一个进程可执行，一定不会死锁。因此系统只要满足：2X+1 ≤ 11 这个条件就不会发生死锁，求得 X=5。假设 6 个进程的分配情况是：2 2 2 2 2 1，则可能发生死锁。

> **例2：**【来源：2009年408真题】某计算机系统中有 8 台打印机，由 K 个进程竞争使用，每个进程最多需要 3 台打印机。该系统可能会发生死锁的 K 的最小值是( C )。  
>    A.2    B.3    C.4    D.5  
> **解析：** 同上，当每个进程分配 2 台打印机后，还剩 1 个资源，则系统一定不会死锁，即 2K+1 ≤ 8 这个条件就不会发生死锁。解得系统不会死锁的 K 的最大值为 3，因此系统可能死锁的最小值等于 3 + 1 = 4。

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

#### 2.4.1 进程数已知，资源数未知 ####

![在这里插入图片描述][655b832333fd4939bafaeae9c1c620b2.png_pic_left]

> **例3：** 某系统中有三个并发进程都需要四个同类资源，则该系统必然不会发生死锁的最少资源是( B )  
>    A.9    B.10     C.11    D.12  
> **解析：** N 个进程，每个进程需要 K 个资源，最大发生死锁的资源数：N×(K-1)，不发生死锁的最少资源数：N×(K-1)+1。因此，不会发生死锁的最少资源是：3×(4-1)+1 = 10。

> **例4：**【来源：2014年408真题】某系统有n台互斥使用的同类设备，三个并发进程分别需要3、4、5台设备，可确保系统不发生死锁的设备数n最小为( B )  
>    A.9    B.10     C.11    D.12  
> **解析：**当三个进程被分配 2、3、4 个资源，还剩一个资源时，系统一定不会发生死锁。因此，不发生死锁的设备数最小为 2+3+4+1 = 10

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

注：以上两种类型的考题的关键在于 找到临界条件。

[e19b4b897d5a4a379d3858a27360abaa.png_pic_left]: https://img-blog.csdnimg.cn/e19b4b897d5a4a379d3858a27360abaa.png#pic_left
[8d5f352afa3940b1a3e13deab4bd1e7f.png_pic_left]: https://img-blog.csdnimg.cn/8d5f352afa3940b1a3e13deab4bd1e7f.png#pic_left
[241b5bccade14529a4f30db375632a0a.png_pic_left]: https://img-blog.csdnimg.cn/241b5bccade14529a4f30db375632a0a.png#pic_left
[dac72c1e166b4f3294dc151c3689394e.png_pic_left]: https://img-blog.csdnimg.cn/dac72c1e166b4f3294dc151c3689394e.png#pic_left
[a8fd403d874141cfbece5486934dc73a.png_pic_left]: https://img-blog.csdnimg.cn/a8fd403d874141cfbece5486934dc73a.png#pic_left
[9241e0fb8dfa413d807a6f11194279f0.png_pic_left]: https://img-blog.csdnimg.cn/9241e0fb8dfa413d807a6f11194279f0.png#pic_left
[a1fbffe7bdad4cc99de2dd8f1d28e8f4.png_pic_left]: https://img-blog.csdnimg.cn/a1fbffe7bdad4cc99de2dd8f1d28e8f4.png#pic_left
[c49ba6619b9b4d5aa0a933ee740b8493.png_pic_left]: https://img-blog.csdnimg.cn/c49ba6619b9b4d5aa0a933ee740b8493.png#pic_left
[8fe6c5cad74c4e598da0d01b2a5f4054.png_pic_left]: https://img-blog.csdnimg.cn/8fe6c5cad74c4e598da0d01b2a5f4054.png#pic_left
[9bab9019c27e4561adcb1d022b605be9.png_pic_left]: https://img-blog.csdnimg.cn/9bab9019c27e4561adcb1d022b605be9.png#pic_left
[ad8c5ea4cdbd48d99508aeb1f00065a8.png_pic_left]: https://img-blog.csdnimg.cn/ad8c5ea4cdbd48d99508aeb1f00065a8.png#pic_left
[cda1e353f29f4499baeed8c070096631.png_pic_left]: https://img-blog.csdnimg.cn/cda1e353f29f4499baeed8c070096631.png#pic_left
[21400358088a4c9aa92736f337bcf8de.png_pic_left]: https://img-blog.csdnimg.cn/21400358088a4c9aa92736f337bcf8de.png#pic_left
[e883d145a68c4ca391be4f6aa2455e4e.png_pic_left]: https://img-blog.csdnimg.cn/e883d145a68c4ca391be4f6aa2455e4e.png#pic_left
[655b832333fd4939bafaeae9c1c620b2.png_pic_left]: https://img-blog.csdnimg.cn/655b832333fd4939bafaeae9c1c620b2.png#pic_left