操作系统之死锁概述——引起死锁的原因、死锁的四个必要条件、死锁的预防、避免、检测及解除

死锁概述

文章目录

• 死锁概述
• • 可重用性资源和消耗性资源
  • 可抢占性资源和不可抢占性资源
  • 计算机系统中的死锁
  • • 引起死锁的原因
    • 死锁的定义、必要条件和处理方法
    • 产生死锁的必要条件
    • 处理死锁的方法
    • 预防死锁
    • 避免死锁
    • 死锁的检测和解除

系统中有许多不同类型的资源，其中可以引起死锁的主要是需要采用互斥访问、不可被抢占的资源，即临界资源；

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

1. 可重用性资源是指可供用户重复使用多次的资源，它具有以下特点：

   1. 每一个可重用性资源中的单元只能分配给一个进程使用，不允许多个进程共享；
   2. 使用可重用性资源时需要按照以下顺序进行：请求资源、使用资源、释放资源；
   3. 系统中每一类可重用性资源中的单元数目相对固定，进程在运行期间不能创建也不能删除它；

   对资源的请求和释放通常是通过系统调用完成的；

2. 消耗性资源又称为临时性资源，它是在进程运行期间由进程动态创建和消耗的，它具有以下特点：

   1. 可消耗性资源的数目在进程运行期间是不断变化的；
   2. 进程可以不断创造可消耗性资源，将其放置在该类资源的缓冲区中；
   3. 进程在运行过程中可以申请多个可消耗资源单元，用于自己进程的消耗，不再将其归还。

   可消耗性资源通常由创建者进程创建，由消耗者进程使用；

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

1. 可抢占性资源是指，该资源在被进程使用时可以被优先级更高的进程抢夺；常见的可抢占性资源包括处理机和内存；当内存资源比较紧张时，可以将一些进程暂时移到外存中去，其实就是对内存资源的一种抢占；
2. 不可抢占性资源是指，在该类资源使用过程中，其拥有者不会发生变化；例如打印机、刻录机等设备；

计算机系统中的死锁

引起死锁的原因

死锁的起因通常是对多个资源的争夺，不仅对不可抢占资源的争夺会引起死锁，对可消耗资源的争夺也会引起死锁

1. 竞争不可抢占资源引起死锁：比如两个写文件的进程A和B分别操作文件F1和F2，某一时刻，A请求了F1,B请求了F2并且都得到允许；此时如果A请求F2，B请求F1，那么AB两个进程都会被阻塞，即死锁；
2. 竞争可消耗资源引起死锁：这种情况的死锁通常是因为使用资源的顺序不当，比如A需要x才发出y；而B需要y才发出x；这样就形成了一种互相等待；
3. 进程的不当推进引起死锁：进程的不当推进引起死锁通常是因为对资源的请求和释放的顺序是否合法，不当的推进顺序可能造成A持有X，但是A却在使用完Y后才释放X；B持有Y，但是B只有在使用完X后才释放Y，这样由于释放和申请的顺序也会造成死锁现象；

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

死锁，可以定义为一组进程中的每一个进程都在等待只有这组进程中的进程才能触发的事件；

产生死锁的必要条件

1. 互斥条件：进程对分配给它的资源进行排它性使用，即在一段时间内某一个资源只能由一个进程使用。如果其他进程申请使用该资源则必须等待，直到拥有者释放该资源；
2. 请求和保持条件：进程已经只少保持了一个资源，但是又提出了新的资源请求，该资源又被其他进程占用，此进程被阻塞，但是并没有释放自己拥有的资源；
3. 不可抢占条件：分配给进程的资源，除非进程自己释放，否则其他进程不可抢占；
4. 循环等待：发生死锁时，必然存在一个进程-资源的循环链；

只要破坏四个条件中的一个，就能阻止死锁情况的发生；

处理死锁的方法

处理死锁的方法一般分为四种

1. 预防死锁：通过设置某些条件，破坏产生死锁的四个条件之一来预防死锁，死锁的预防比较容易实现，被广泛采用；
2. 避免死锁：同样属于预先防范策略，但它不是通过各种限制条件以破坏四个必要条件，而是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁；
3. 检测死锁：事先无需采用任何限制性措施，允许进程在运行过程中出现死锁，但是通过死锁检测机构及时地检测出死锁的发生，然后采取适当的条件，将进程从死锁中解救出来；
4. 接触思索：当检测到系统出现死锁时，采用相应策略，将进程从死锁状态解救出来，通常是撤销一些进程，回收它们的资源，然后将其分配给其他进程；

上述四种方法，从上到下对死锁的防范程度越来越低，但是对应的资源利用率越来越高，以及进程因资源因素被阻塞的频度越来越低（即并发程度提高）；

预防死锁

预防死锁通常是破坏死锁产生的必要条件之一；由于互斥是并发状态下对临界资源的访问方式，不但不能破坏还必须遵守，所以只能破坏后面三个条件；

1. 破坏“请求和保持条件”

   为了能破坏该条件，需要保证当进程在请求资源时，它不能持有不可抢占资源；通常有两种方法：

   1. 第一协议：所有进程在开始运行之前，必须一次性申请它在运行时需要用到的资源，只要有一个资源不满足，那么它就不能获得任何资源；这样，如果系统有足够的资源，那么进程在运行之前就可以获得需要的全部资源，运行中自然也就不请求其他资源了，即破坏了请求条件；如果进程需要的资源不能被满足，那么它就不能获得任何资源，这样当进程在等待状态时自然有就没有“持有”任何资源了；

      优点是简单、易行；这种方式的缺点很明显：首先资源被严重浪费，一个进程可能长期拥有一个只使用一小会的资源或者在开始就拥有一个只有到结束才可能用到的资源，这于资源来讲是极大的浪费；进程会经常发生饥饿现象，由于某些资源被其他进程长期占用，所以即便该资源对于某一个进程来说只有最后才会用到，该进程也不得不一直阻塞；

   2. 第二协议：进程一开始可以不必获得所有的资源才能运行，但是在进程的运行过程中需要逐步释放分配给自己的且已使用完毕的资源，然后才能继续申请其他所需要的新资源；这样做的好处是，不仅能更快地完成任务，提高设备的利用率，还可以避免进程发生饥饿现象；但是该方法实现比较复杂。

2. 破坏“不可抢占条件”

   当一个进程在申请某一资源时，如果该请求不能被满足，那么该进程则释放自己已持有的所有资源；这种方法不但实现比较复杂，而且可能会因为反复申请和释放资源导致一些进程的执行无限期推迟，不仅延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量；

3. 破坏“循环等待条件”

   一个能保证“循环等待条件”不满足的策略是：对所有系统资源类型进行编号并线性排序，进程按照序列号递增的顺序申请资源；当进程所持有的最大资源号为x时，当且仅当A资源的序号y>x时该进程才能申请A资源；如果进程申请A资源，但是y<x，那么进程就需要释放自己持有的所有序号大于y的资源；采用这种资源分配方式所形成的资源分配图中不可能出现环路，所以也就破坏了循环等待的条件；

   采用这种资源分配方式，一个问题就是对资源类型的编号需要符合大多数进程使用资源的顺序，比如依据输入-计算-输出这一顺序，输入设备应该具有较低的类型号；此种方法相比其他几种方法来说，系统资源利用率和系统吞吐量均得到提高，但是也存在以下问题：1、扩充资源类型不便；2、存在一些进程，使用资源的顺序与系统规定的资源类型序号的策略不同，这样可能造成资源的浪费；3、这种方法对于编程增加了额外的限制；

避免死锁

避免死锁也是一种预防策略，但是并不是事先采取某种措施，破坏死锁的必要条件，而是在进行资源分配时防止系统进入不安全状态以避免产生死锁现象。由于这种方法所施加的限制条件较弱，所以系统有较好的性能，目前普遍采用这种方式；

在死锁避免方法中，系统有两种状态：安全状态和不安全状态；当系统处于安全状态时，可以避免进入死锁；当系统处于不安全状态时，有可能进入死锁；

安全状态与非安全状态：所谓安全状态，是指系统能按照某种进程推进方式（某个进程序列）为每个进程分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利地完成；如果找到这样一个序列，则系统是处于安全状态；否则系统处于不安全状态；虽然系统处于不安全状态时不一定进入死锁，但是是存在这个可能的；因此避免死锁的实质在于，系统进行资源分配时，应使系统不进入不安全状态；

在建立了系统安全状态的概念之后，便可知避免死锁的基本思想就是确保系统始终处于安全状态；当有进程请求一个可用资源时，系统需要对该进程的请求进行计算，如果将资源分配给进程之后，系统仍然处于安全状态，那么该资源才可以分配给进程；否则不进行分配；

避免死锁的最有代表性的算法就是DijKstra的银行家算法。该算法涉及的数据结构以及伪算法如下：

1. 银行家算法涉及的数据结构：

   1. 可用资源向量Available。Available[j]=k；表示编号为j的资源系统一共有k个；
   2. 最大需求矩阵Max。Max[n，j]=k；表示进程n对编号为j的资源的最大需求是k个；
   3. 分配矩阵Allocation。Allocation[n，j]=k；表示进程n已经获得编号为j的资源已经获得k个；
   4. 当前需求矩阵Need。Need[n，j]=k；表示进程n当前对资源编号为j的资源还需要k个；

2. 银行家算法的伪算法：

   设request是编号为x的进程的请求向量；如果request[j]=k，表示进程x对编号为j的资源请求量为k；

   1. 如果request[j]<=need[x，j]，转向2；否则请求出错，因为它申请的资源数量超过当前它需要的数量，认为这是一个失败的请求；

   2. 如果request[j]<=Available[j]，转向3；否则表示系统当前没有足够的资源可以分配，x进程需要等待；

   3. 试着将编号为j的资源分配给进程x，更新相关数据结构：

      Available[j]=Available[j]-request[j];

      Allocation[x,j]=Allocation[x,j]+request[j];

      Need[x,j]=Need[x,j]-request[j];

   4. 进入安全性检测程序（该程序试图找到一个安全序列；如果找到，说明这次分配之后系统仍然是安全的，否则这次分配无效，因为系统进入了不安全状态）

3. 安全性检测程序数据结构及其伪算法

   1. 设置两个向量：工作向量Work，表示系统可提供给进程继续运行所需的各类资源数目；初始值为Available；Finish[j]表示编号为j的进程是否有足够资源，使之完成运行；初始值为false；当有足够资源时设置为true；

   2. 从进程中找到一个满足下述条件的进程：

      1） Finish[j]=false;2）Need[x,j]<=work[j]；如果找到执行步骤3；否则执行4；

   3. 当进程x获得资源后，可顺利执行完毕，所以将归还分配给它的资源，所以执行：

      Work[j]=Work[j]+Allocation[x,j];

      Finish[x]=true;

      go to 2;

   4. 如果所有进程的Finish[j]=true，则表示系统处于安全状态；则上次的资源分配可以进行；否则，不行啊；

   到这里我就想到一个问题，如果2中满足条件的有多个，那么是否可以任意选择呢？正当我码这些字的时候，我想通了：是可以的！因为一旦选择完一个进程后，就假设该进程执行完毕，那么它就要归还系统资源，即系统资源是不减的！也就是说，如果在某一次查找中，有x个进程满足条件，那么任意选择一个进程并且执行完3后再回到2时，原来满足条件的进程现在一定还是满足的，原来不满足的进程由于资源的不减，也有可能满足，所以，是可以任意选择的！

死锁的检测和解除

如果系统中既没有死锁预防措施也没有死锁避免措施，那么系统很有可能发生死锁；在这种情况下，需要系统提供以下两种算法：死锁检测算法和死锁解除算法；

1. 死锁检测算法：为实现死锁检测算法，需要系统记录各种资源的使用情况以及进程对资源的请求情况，并且系统需要能根据这些信息检测系统是否进入死锁状态；一种常见的死锁检测方法是利用资源分配图。

   资源分配图是这样的有向图：它包含两类节点（资源节点和进程节点）和两类边（资源请求边，由进程节点出发，指向资源节点；资源分配边，由资源节点指向进程节点）；利用资源图分配图检测死锁的原理如下：

   在资源分配图中找到一个既不阻塞也不独立的进程节点，然后为其分配所需的全部资源，使其得以运行结束，再释放其所占有的全部资源，这相当于消去所有经过该进程节点的边使之成为一个独立的点，然后更新资源数量；然后重复这个步骤；如果经过一系列简化后，所有边都被消去，即所有节点都是孤立的，那么系统就没有死锁；否则系统就是死锁状态；这一定理也被称为死锁定理；

   这里，不同的简化顺序最后得到的简化图是一样的，道理同上面提到的一样，因为每简化一次，资源数目是不减的；

2. 死锁解除算法：死锁解除常使用两种方法：抢占资源和终止进程；

   终止进程的方法有一次性终止所有死锁进程，效果立竿见影，但是也意味着功亏一篑：许多进程都需要从头再来，并且有些情况下，数据可能无法还原，从而造成极大的破坏；还有就是逐个终止进程，释放资源，直到打破循环等待，将系统从死锁中解决出来；但是这里存在一个问题，该如何选择要终止的进程？常常需要考虑以下几点：

   1. 进程的优先级；
   2. 进程的运行时间以及还需要多少时间完成执行；
   3. 进程在运行中使用了多少资源以及还需要多少资源；
   4. 进程的性质是交互式还是批处理式；

   一种最小代价的死锁解除算法是：对于死锁状态的每一个进程，都计算一遍终止该进程所产生的代价，然后选择代价最小的一个进程终止，然后如果系统还处于死锁，那么重复前一个步骤；但是计算选择代价最小的进程这一步骤可能会有较大的代价！总体来说，还是让系统别进入死锁的好！对吧！把死锁扼杀在摇篮里！