操作系统-11-死锁

引言

计算机的某些资源同一时间只能一个进程或线程使用，比如打印机，如果两个进程同时使用打印机便会出问题。所以需要使用锁来控制进程并发的使用某些资源，但是不恰当的使用锁会造成一个严重的问题。举个例子，进程A申请扫描仪，A获得扫描仪；进程B申请刻录仪，B获得刻录仪，此时进程A需要申请刻录仪，而进程B要申请扫描仪，因为进程A、B都需要有扫描仪和刻录仪才能完成工作，因此这个过程将一直等待下去，这就叫做死锁。

死锁可以发生在各种各样的场景，比如数据库，接下来学习死锁的发生和死锁的检查以及死锁的避免和解决

资源

大部分的死锁都和资源有关，先来了解一下资源

资源定义

根据时间推移，能够获得、使用、释放的任何东西

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

• 可抢占资源：可以从拥有它的进程中拿走资源，不会有副作用（比如：内存）
• 不可抢占资源：无法从拥有它的进程中拿走资源而不引起计算失败
• 可抢占资源死锁解决方案：重新分配资源即可解决
• 资源申请和使用顺序抽象
  1. 申请资源：如果进程申请时资源不可用，那么进程强制等待
  2. 使用资源
  3. 释放资源

死锁检测和恢复

• 死锁的书面定义：如果一个进程集合中，每一个进程都在等待只能由该集合中的进程才能引发的事件，那么该进程集合就产生了死锁

死锁的条件

• 互斥条件：每个资源在同一时间只能分配给一个进程

• 持有和等待条件：每个进程持有之前申请的资源并可以申请新的资源

• 不可抢占条件：每个进程持有的之前申请的资源不可以被强制抢占，必须由申请并持有的进程释放

• 环路等待条件：如果发生死锁，肯定有两个或更多的进程组成了一个环路，每一个环路中的进程都在等待下一个进程持有的资源

  上述四个条件很重要，因为死锁发生时，四个条件必定同时满足，如果有一个条件不满足，死锁就不会发生。这也是如何避免死锁的关键

死锁建模

• 模型描述图示

  

  • a持有资源，A持有R资源
  • b申请资源，B申请S资源
  • c死锁，C持有U申请T，D持有T申请U

• 举个例子：假设有三个进程A、B、C申请三个资源R、S、T，如下图

  

  • 进程A需要的资源为R和S，顺序为申请R->申请S->释放R->释放S
  • 进程B需要的资源为S和T，顺序为申请S->申请T->释放S->释放T
  • 进程C需要的资源为T和R，顺序为申请T->申请R->释放T->释放R
  • 假设进程A、B、C申请资源的顺序
    • A申请R->B申请S->C申请T->A申请S->B申请T>C申请R，最终A、B、C进程获取资源和持有资源的示意图如上图(e->j)，会发生死锁
    • A申请R->C申请T->A申请S->C申请R->A释放R>A释放S，最终A、B、C进程获取资源和持有资源的示意图如上图(l->q)，不会发生死锁

• 死锁处策略

  • 忽略(鸵鸟算法，很形象，像鸵鸟一样，把头埋进沙子，假装什么事也没发生)
  • 检测和恢复，让死锁发生，检测它并解决死锁
  • 小心分配资源避免死锁发生
  • 破坏死锁四个条件之一，防止死锁发生

死锁检测

不防止死锁的发生，而是通过死锁检测的方式解决死锁

• 各类型一个资源的死锁检测

  • 这种方式各类型的资源只有一个，因此这种类型检测死锁可以构建一个进程获取资源和申请资源的图，如果检测到一个或多个环，那么就出现了死锁

  • 如何确定哪些进程发生死锁，在环中的进程是发生死锁的进程，如下图所示，D、E、G。D持有U申请T；E持有T申请V；G持有V申请U，因此产生了死锁

    

  • 有向图环路检测算法在图算法中有很多，下面举一个简单的例子（图深度优先遍历），这个算法并非最优的

    1. 初始化一个列表L为空，清除所有节点有向边的标记
    2. 将当前节点加入到L尾部，判断是否出现了两次，如果出现了两次，那么存在环
    3. 从给定的节点检查是否还有没有标记的边，如果存在，执行第4步，否则执行第5步
    4. 随机选择一条并标记，指向的节点作为新的当前节点执行第2步
    5. 如果该节点为初始节点，说明，图中不存在环，否则说明该节点没有后续节点，弹出该节点，返回前一个节点作为当前节点执行第2步

• 各类型多个资源的死锁检测

  • 这种场景因为资源有多个，所以用图是否有环算法不能处理这种场景，因此需要另外一种算法

  • 死锁检测建模数据结构

    1. $E$向量代表拥有各类型资源的数量，比如$E_1$代表类型1的数量，其向量表示为

       $$E=\begin{bmatrix} E_1 & E_2 &... &E_m \\ \end{bmatrix}$$

    2. $A$向量代表当前可用的各类型资源的数量，比如$A_1$代表类型的当前剩余可用的资源数，其向量表示为

       $$A = \begin{bmatrix} A_1 & A_2 & ... & A_m \end{bmatrix}$$

    3. $C$矩阵表示当前各进程拥有各类型资源的数量，矩阵的每一行代表一个进程，比如$C_i$代表第i个进程拥有的资源向量，$C_{i,j}$代表进程i拥有资源类型j的数量，矩阵表示如下

       $$\begin{bmatrix} C_{1,1} & C_{1,2} & \cdots & C_{1,m} \\ C_{2,1} & C_{2,2} & \cdots & C_{2, m} \\ \vdots & \vdots & \vdots & \vdots \\ C_{n,1} & C_{n,2} & \cdots & C_{n,m} \end{bmatrix}$$

    4. R矩阵表示当前进程完成任务还需要申请的各类型资源，矩阵的每一行代表一个进程，比如$R_i$代表第i个进程还需要申请的资源向量，$R_{i,j}$代表进程i还需要申请的资源类型j的数量

       $$\begin{bmatrix} R_{1,1} & R_{1,2} & \cdots & R_{1,m} \\ R_{2,1} & R_{2,2} & \cdots & R_{2, m} \\ \vdots & \vdots & \vdots & \vdots \\ R_{n,1} & R_{n,2} & \cdots & R_{n,m} \end{bmatrix}$$

    5. 资源数量之间关系

       $$\sum_{i=1}^nC_{i,j} + A_j = E_j$$

  • 死锁检测算法

    1. 查找一个未标记的进程，比较$R_{i}$行是否小于等于向量$A$
    2. 如果找到这样一个进程，那么标记当前进程，将$R_i$加到向量$A$然后返回第一步
    3. 如果没有这样的一个进程，则发生了死锁

  • 简单的例子

    

    • 首先找到第三个进程，因此$A$累计$C_{3}$，因此$A$为$\begin{bmatrix} 2 & 2 & 2 & 0 \end{bmatrix}$
    • 然后第二个进程满足条件，$A$累计$C_2$，因此$A$为$\begin{bmatrix} 4 & 2 & 2 & 1 \end{bmatrix}$
    • 最后是第一个进程，因此不会发生死锁

死锁恢复

• 通过抢占恢复，这种方法要根据资源的类型来确定，通常比较困难或者不可行
• 利用回滚恢复，这种方式需要存储进程的各种状态包括获得的资源，叫做进程检查点，新的检查点并不会覆盖之前的检查点，一旦发生死锁，进程可以选择之前的检查点来回滚到未获得该资源的状态，因此在该检查点之后的工作是无效的
• 通过杀死进程恢复，如果可能，杀死一个在死锁环中的一个进程来打破死锁。选择杀死进程要非常小心，最好选择那种重新执行进程不会产生副作用的进程

死锁避免

上边讨论了死锁的检测和恢复，其没有考虑避免死锁发生，而是从检测和解决死锁考虑。是否能有方法每次资源分配时做出正确的选择避免死锁？接下来讲述如果避免死锁发生

资源轨迹图

• 通过对资源轨迹的描述，来判断两个进程是否进入死锁状态，如下图，横坐标代表A进程需要的资源和时间点，纵坐标代表进程B需要的资源和时间点，虚线代表调度器调度进程A、B运行的时间，比如p->q调度A运行，q->r是进程B运行

  

  阴影区域是我们关注的区域，因为这两个区域内两个进程运行同时需要该资源，因此如果进入该区域便会产生死锁，为了避免死锁，B进程会被挂起直到进程A申请并释放Plotter

安全和不安全状态

• 如果直到各进程需要某一个资源的最大需求，并且进程存在某种调度顺序能完成任务，不会发生死锁，那么就称为安全状态，比如下图，总共资源有10个，如图a已分配的资源为7个还剩余3个，所以可以先调度B进程运行如图b，然后调度C进程运行，资源刚好，最后调度A不会发生死锁

  

• 不安全状态，比如下图，a为初始状态，但是A进程申请了一个资源如b，此时我们无法找到一个顺序能完成任务，因此b为不安全状态。注意，不安全状态并不是死锁

  

单资源银行家算法

• 定义：银行家算法，Dijkstra提出的一种避免死锁的算法，思想来源于银行家贷款，所以叫银行家算法。该算法在请求资源时，会判断同意该请求会不会导致不安全状态，如果是，则该请求会等待，如果不会，则会同意

• 一个简单的例子，假设有四个客户A、B、C、D需要的贷款总共为22单位，但是客户并不是一次性就需要所有贷款，所以银行并不需要22个单位的金额，假设现在银行有10个单位的金额，a是状态安全的；b也是状态安全的因为剩余2单位贷款可以满足客户C，C获得资源后可以满足B、D客户，最后可以满足A客户；但是c不是安全的因为不能满足任何一个客户的贷款

  

• 缺点：进程运行前需要知道需要的资源

多资源银行家算法

• 和单资源银行家算法类似，多资源是多个资源，因此这里用两个矩阵，一个表示进程已分配各资源的矩阵，一个是进程还需要的资源数，还有3个向量分别为$E$、$P$、$A$分别表示各资源总数量、已分配数量和可使用资源数量，如下图

  

• 检查一个状态是否安全的算法执行步骤，和多资源死锁检测算法类似

  1. 找到一个进程，其还需要的资源向量小于或等于可用资源向量$A$，如果没有这样一个进程，说明最终会发生死锁
  2. 假设这个进程获得其所需要的所有资源，并完成其工作，因此其释放其已拥有的资源累加到向量$A$上，将该进程标记为终止
  3. 重复执行上述两步，直到所有的进程都标记完成，那么初始状态是安全的；否则，初始状态是不安全的，最终会发生死锁

• 小结：银行家算法虽然很有意义，但是缺乏使用价值，因为很少有进程在运行前就事先知道运行需要的资源，而且进程数量也不是固定的会一直变化

死锁预防

通过上述的死锁避免方法学习，我们知道了死锁避免从本质上是不可行的。所以回到文章开始提到的四个死锁条件，可以从这四个条件入手，通过打破这些条件来预防死锁

破坏互斥条件

• 定义：避免分配那些不是绝对必须的资源，尽量做到尽可能少得进程可以访问真正的资源
• 一个例子：假脱机打印机技术，进程需要打印并不是直接控制物理打印机，只有打印机守护进程可以控制物理打印机，并且打印机守护进程不会申请其他资源，因此不会产生死锁

破坏持有并等待条件

• 第一种方法：进程一次性获取了其所需要的所有资源在执行任务直到任务完成，如果有一个资源或多个不可用，那么进程什么资源也不会分配。该方法的问题是和银行家算法，在进程执行前很难知道进程需要的资源，并且还有一个问题资源得不到充分利用
• 第二种方法：另一个方法是，进程每次申请一个资源时，先释放其持有的所有资源，然后再一次性申请它们

破坏不可抢占条件

• 如前所述，某一些资源可以通过虚拟化技术来使其可以变成可抢占的，比如打印机的虚拟化技术假脱机

破坏环路等待条件

• 第一种方法：一个进程同一时刻只能持有一个资源，要申请另一个资源时必须释放其当前持有的资源。但是这种方法会导致某些复杂需要多个资源的任务不可接受，比如将一个磁盘上的大文件打印
• 第二种方法：对所有资源统一编号，进程可以在任何时候提出资源申请，但是必须是按资源编号升序顺序申请。该方法还有一个优化，就是不强制要求升序，而只是要求不能申请比进程持有资源编号低的资源。这种方法的缺点是几乎找不出一种让任何进程都满足的排序编号

其他问题

两阶段锁

数据库领域适用的一种加锁方式，在第一阶段，进程对某一记录加锁，如果第一阶段加锁成功，那就执行第二阶段更新操作，然后释放锁。如果进程发现需要加锁的记录已经加锁，释放它已经获得的锁重新开始第一阶段

该算法并不能通用，只有在程序员确定在第一阶段随时都可以停下来，然后重启并且不产生错误，该算法才可用

活锁

• 一个可以造成活锁的例子，A,B进程在获得2,1资源时失败，同时释放已经持有的锁，并且等待相同的时间，然后会重复上述过程
• 解决办法：在获取锁失败后随机等待一段时间，而不是所有进程等待固定的时间

饥饿

• 某个进程因为资源访问策略限制，而迟迟得不到资源。比如，打印机的策略是先打印小文件，假设有一个大文件需要打印，每次都是优先打印小文件，那么大文件就得不到打印的机会
• 解决办法：使用先到先服务的策略