操作系统之死锁

操作系统的几种资源

可重用性资源和消耗性资源

• 可重用性资源

  • 定义：可供用户重复使用的资源
  • 性质：
    1. 可重用性资源的单元只能同一时间只能分配给一个进程，不允许共享
    2. 进程使用可重用性资源，需要一定顺序使用1）请求资源2）使用资源3）释放资源
    3. 操作系统中每一类可重用性资源的单元数目是固定的，进程在使用资源的过程不可创建或删除重用性资源
  • 操作系统中的大多数资源都属于可重用性资源

• 消耗性资源

  • 定义：与可重用性资源相对，消耗性资源是在进程运行过程中，由进程动态的创建和消耗的资源，又称为临时性资源
  • 性质：
    1. 在进程运行过程中，消耗性资源的单元数目是可以不断变化的
    2. 进程运行过程中，可以创造消耗性资源
    3. 进程运行过程中，进程可以消耗一定数目的消耗性资源，而不再将该资源返回给资源类

可抢占性资源和不可抢占性资源

• 可抢占性资源
  • 定义：某进程在获得这类资源后，该资源可以随时被其他进程或系统抢占
• 不可抢占性资源
  • 定义：与不可抢占性资源相对，某进程获得这类资源后，该资源不能被其他进程或系统抢占，只有等进程用完之后自行释放该资源。

死锁的起因

• 竞争不可抢占性资源引起死锁
• 竞争可消耗性资源引起死锁
• 进程推进顺序不当引起死锁

死锁的定义、必要条件及处理方法

死锁的定义

如果一组进程中的每一个进程都在等待仅有该组进程中的其他进程才能引发的事件，则称该组进程是死锁的。

产生死锁的四个必要条件

产生死锁的原因有多种，但都是具备了一定的条件才形成死锁，产生死锁必须满足四个条件：

• 互斥条件：进程对分配到的资源进行排他性使用，不共享
• 请求和保持条件：进程在请求被其他进程所占有的资源，成阻塞状态时，保持自己所占有的资源不放
• 不可抢占条件：进程的资源不可抢占，只能等执行完毕后自行释放
• 循环等待条件：进程组每一个进程都在等待另一个进程所占用的资源，形成一个循环链

处理死锁的方法

• 预防死锁：破坏必要条件
• 避免死锁：防止进程进入不安全状态
• 检测死锁：可通过检测出死锁，从而采取一定措施
• 解除死锁：若检测到死锁，便采取措施解除死锁，通常是撤销一些进程

四种方法从上到下对于死锁的防范程度不断减弱，但资源利用率不断提高

预防死锁

预防死锁通常是通过破坏死锁的四个必要条件中的后三个来避免产生死锁。

破坏“请求和保持”条件

可通过两个不同的协议来保证：当一个进程在请求资源时，该进程不能持有不可抢占资源。从而破坏“请求和保持”条件

• 第一种协议
  • 内容：所有进程在运行之前，必须一次性申请其整个运行过程中需要的所有资源
  • 优点：简单易行、安全
  • 缺点：
    1. 资源被严重浪费
    2. 使进程经常出现饥饿现象
• 第二种协议
  • 内容：允许进程在只获得运行初期所需要的资源时，便开始运行。在运行过程中逐步释放自己所占有的，且使用完毕的资源。然后再去请求下一运行阶段所需要的资源
  • 优点：提高了资源的利用率，减少发生饥饿现象的几率

破坏“不可抢占”条件

通过一种协议来破坏“不可抢占条件”

• 协议：
  • 协议内容：当一个已经保持了某些不可抢占资源的进程，提出新的资源请求而得不到满足时，该进程必须释放它保持的所有资源，待以后需要时再申请。可以理解为这些资源被抢占了
  • 优点：破坏了不可抢占条件
  • 缺点：
    1. 方法比较复杂，实现代价大
    2. 可能造成前一阶段工作的浪费，延长了进程的周转时间，降低系统的吞吐量。

破坏“循环等待”条件

对系统的各类资源类型进行线性排序，并赋予不同的序号。

• 协议：
  • 内容：规定每个进行必须按序号递增的顺序请求资源。如果需要多个同类资源，必须一起请求。假如某进程申请到了序号较高的资源又想申请序号较低的资源时，必须先释放序号较高的资源，再去申请序号较低的资源
  • 优点：
    1. 避免资源分配途中出现环路，从而破坏了“循环等待”条件
    2. 提高了资源利用率，系统的吞吐量
  • 缺点：
    1. 各类资源的序号必须相对稳定，从而限制了新类型设备的增加
    2. 在实际中，可能会出现某些作业使用各类资源的顺序与系统规定的顺序不同，从而造成资源的浪费。
    3. 按固定次序去申请资源，限制了用户自主得进行编程。

避免死锁

与预防死锁相比，避免死锁也属于事前预防的措施，但并不是通过破坏形成死锁的必要条件来实现，而是通过在资源动态分配过程中，防止系统进入不安全状态，来避免死锁。

安全状态与不安全状态：

• 安全状态：安全状态，指系统能按某种进程推进顺序$(P_1,P_2,...,P_n)$为每个进程分配所需的资源，直至满足进程的所有需求，使每个进程都可顺利完成。该推进顺序称为安全序列
• 不安全状态：与安全状态相对，如果不存在进程推进顺序，使得每个进程都可顺利完成，则称系统处在不安全状态中。
• 需要注意的是：系统处于安全状态，则一定不会出现死锁。而如果系统处于不安全状态，可能会出现死锁，并不是一定会出现死锁。

避免死锁的方法即为，在系统进行资源分配之前，先计算此次资源分配的安全性，如果此次分配不会导致系统进入不安全状态，则执行分配，而如果此次分配会导致系统进入不安全状态，则不执行分配。

银行家算法（避免死锁算法）

银行家算法：当一个新进程进入系统时，该进程必须申明在运行过程中所需要的每种资源的最大数目，且该数目不能超过系统拥有的资源总量。当进程请求某组资源时，系统必须先确定系统中是否有足够的该类资源供以分配给该进程。若有，通过安全性算法来计算，将资源分配给该进程后，是否会使系统处于不安全状态，如果不会处于安全状态，则将资源分配给该进程，否则让进程等待。若没有，进程等待。

• 数据结构

  实现银行家算法，必须有四种数据结构，用以描述系统中可使用的资源数目、所有进程对于各类资源的最大需求、系统中已分配资源的情况、各进程还需要多少资源的情况

  • 可利用资源向量$Available$，$Available[j]=K$ 表示系统中现有可利用的$R_j$类资源$K$个
  • 最大需求矩阵$Max$，$Max[i,j]=K$ 表示进程$i$需要$R_j$类资源的最大数目为$K$个
  • 分配矩阵$Allocation$，$Allocation[i,j]=K$ 表示进程$i$已分得$R_j$类资源$K$个
  • 需求矩阵$Need$，$Need[i,j]=K$ 表示进程$i$还需要$R_j$类资源$K$个

  有关系：
  $$Need[i,j]=Max[i,j]-Allocation[i,j]$$

• 银行家算法描述

​ 设$Reques{t}_i[j]$是进程$i$的请求向量，$Requese{t}_i[j]=K$表示进程$i$请求K个$R_j$类资源。当进程发出资源请求后，算法执行步骤如下：

1. ​ 如果 $Reques{t}_i[j]\le Need[i,j]$，跳至步骤2；否则，认为出错，因为请求的超过它所需要的。

2. ​ 如果$Reques{t}_i[j]\le Available[i,j]$，跳至步骤3；否则，认为系统暂时满足不了该进程的需求，进程等待

3. ​ 系统尝试着将请求的资源分配给该进程，并修改数据结构中的数值：
   $$\begin{gathered} Available[i,j]=Available[i,j]-Reques{t}_i[j] \\ Allocation[i,j]=Allocation[i,j]+Reques{t}_i[j] \\ Need[i,j]=Need[i,j]-Reques{t}_i[j] \end{gathered}$$

4. 执行安全性算法，判断如此分配后，系统是否处于安全状态，如果处于安全状态，则执行分配；否则，本次尝试分配作废，进程等待。

• 安全性算法描述：

  1. 设置两个向量

     • 工作向量$Work$，表示系统可提供给进程继续运行的各类资源数目，算法执行之前，令$Work=Available$
     • $Finish$：表示系统是否有足够的资源分配给进程，使进程完成。开始时令$Finish[i]=False$，如果有足够的资源分配给进程，则令$Finish[i]=True$

  2. 从进程集中寻找满足下列条件的进程：

     1. $Finish[i]=False$
     2. $Need[i,j]\le Work[j]$

     若找到，跳至步骤3，否则执行步骤4

  3. 更新数据结构的数值。进程$i$获得资源后，执行，直至完成进程，并释放他占有的资源，即：
     $$\begin{gathered} Work[j]=Work[j]+Allocation[i,j] \\ Finish[i]=True \\ gotostep2 \end{gathered}$$

  4. 如果所有的进程都满足$Finish[i]=True$，表示分配资源后系统将处于安全状态，执行分配。否则，尝试分配作废，进程等待。
     

死锁的检测与解除

如果系统中并没有预防死锁和避免死锁的措施，那么很可能会出现死锁，这时就需要利用死锁检测算法和死锁解除算法来解除死锁。

死锁的检测

资源分配图

资源分配图：由一个结点集$N$和一个边集$E$组成的对偶$G=(N,E)$，它具有下述定义：

1. 将$N$划分为两个互斥的结点集，进程结点集 P = { P 1 , P 2 , . . . , P n } P=\{P_1,P_2,...,P_n\} P={P1​,P2​,...,Pn​}以及资源结点集 R = { R 1 , R 2 , . . . , R n } R=\{R_1,R_2,...,R_n\} R={R1​,R2​,...,Rn​}，满足$N=P\cup R$
2. 边集$E$中的每一条边都连接$P$中的一个结点与$R$中的一个结点，
   • e = { P i , R j } e=\{P_i,R_j\} e={Pi​,Rj​}为资源请求边，由进程结点指向资源结点，表示进程$P_i$请求一个单位的资源$R_j$
   • e = { R j , P i } e=\{R_j,P_i\} e={Rj​,Pi​}为资源分配边，由资源结点指向进程结点，表示把一个单位的资源$R_j$分配给进程$P_i$

资源分配图如图所示：

死锁定理

死锁定理：系统处于S状态，S为死锁状态的充分条件为 当且仅当S状态的资源分配图为不可完全简化的。

• 资源分配的简化方法如下：
  1. 在资源分配图中，找出一个既不阻塞也非独立的进程结点$P_1$。如果在顺利的情况下，$P_i$可获得所需资源，完成执行，则去掉$P_i$的所有请求边和分配边，使之成为一个孤立结点
  2. 按照步骤1，不断简化资源分配图
  3. 如果可以通过一系列简化，消去资源分配图中的所有边，使所有进程结点孤立，则称该图是可完全简化的。即该状态不为死锁状态

死锁中的数据结构

• 可利用资源向量$Available$，表示系统中每类资源的可用数目
• 把不占用资源的进程记入$L$表中，即$L=L\cup P_i$
• 从进程集合中找到一个满足$Reques{t}_i\le Work$的进程，做以下处理：
  • 将资源分配图简化，释放资源，令$Work=Work+Allocatio{n}_i$
  • 将该进程记入$L$表中
• 如不能将所有的进程都记入$L$表中，则表明此状态下资源分配图不可简化，即系统处于死锁状态。

死锁的解除

当检测出死锁时，需要采取一定措施，来解除死锁状态。常用的方法有：

1. 抢占资源。从若干个进程中抢占足够的资源，分配给死锁进程，以解除死锁状态
2. 终止进程。终止若干个死锁进程，使系统从死锁状态中摆脱出来。
   • 终止进程的方法有：
     • 终止所有死锁进程：进程运行周期变长
     • 逐个终止进程：执行死锁检测算法代价大，不易于实际操作。
   • 付出代价最小的死锁解除算法：从所有逐个终止进程的序列中找出代价最小的。是一种不太实际的算法。

定措施，来解除死锁状态。常用的方法有：

1. 抢占资源。从若干个进程中抢占足够的资源，分配给死锁进程，以解除死锁状态
2. 终止进程。终止若干个死锁进程，使系统从死锁状态中摆脱出来。
   • 终止进程的方法有：
     • 终止所有死锁进程：进程运行周期变长
     • 逐个终止进程：执行死锁检测算法代价大，不易于实际操作。
   • 付出代价最小的死锁解除算法：从所有逐个终止进程的序列中找出代价最小的。是一种不太实际的算法。

所以说，预防是最好的治疗。