本文共 5286 字，大约阅读时间需要 17 分钟。

一、概念与原因

1、死锁的概念

• 多道程序系统环境下，进程可以并发执行，这些并发的进程会争夺系统资源，极端情况下可能出现所有的进程互相等待，此种情形便称为死锁，因为一旦出现这种情况，若无外力作用，这些进程都将无法向前推进，系统也有可能因此奔溃。
  例子
  计算机系统中有一台打印机和一台输入设备，进程 P1 正在占用输入设备，同时又提出使用打印机的要求，但打印机正被进程 P2 占用，而 P2 在未释放打印机的时候有请求使用输入设备，这样一来，两个进程便彼此等待，造成死锁。

2、死锁出现的原因

1）资源竞争

• 系统中拥有的不可剥夺资源数量不足以满足多个进程运行的需求，导致进程争夺资源出现僵局。反观，系统的可剥夺资源不会造成死锁现象。

2）进程推进顺序非法

• 进程运行过程中请求资源和释放资源的顺序不正确，也会导致死锁现象；信号量使用不当也会造成死锁；进程将彼此相互等待对方发来的消息也会导致进程间无法向前推进。

3）死锁产生的必要条件

• 出现死锁必须同时满足互斥条件、不剥夺条件、请求并保持条件和循环等待条件这四个条件，只要其中任何一个不满足，就不会发生死锁。
• ① 互斥条件：进程要求所分配的资源进行排他控制，在一段时间内不允许其他进程占用，任何后来的想用该资源的进程只能等待。
• ② 不剥夺条件：进程所获得的资源在未使用完之前，不能被其他进程强行夺走，只能由占用该资源的进程自己主动释放。
• ③请求并保持条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源正被其他进程占用，此时请求进程被阻塞，当对自己已获得的资源保持不放。
• ④ 循环等待条件：存在一种进程资源的循环等待链，链中每个进程都已获得资源的同时被链中的下一个进程所请求。

二、死锁处理策略

• 根据死锁出现的原因中的四个必要条件，只要破坏其中一个，就能打破死锁；或者允许死锁出现，但当四所发生时能检测出死锁，并有能力实现恢复。因此有三大类死锁处理策略：死锁预防、避免死锁和死锁检测及解除。
• 死锁预防主要是通过设置某些限制条件，破坏产生死锁的四个必要条件中的一个或多个，从而达到防止死锁；避免死锁则是采取某种方法防止系统进入不安全状态，来达到避免死锁；死锁的检测和解除，不用任何限制条件，也允许进程运行过程中出现死锁，但系统有检测死锁发生并解除死锁的能力。
• 前两种都属于事先预防策略，预防死锁的限制条件比较严格，易于实现，但往往导致系统效率低、资源利用率低；避免死锁的限制条件较为宽松，资源分配后需要通过算法判断是否进入不安全状态，实现起来较为复杂。
  

1、死锁预防

1.1、破坏互斥条件

• 若允许系统资源都能共享使用，则系统不会进入死锁状态。但是有些资源，如打印机是不可能同时访问的，只能互斥使用，所以这种策略的局限性很大。

1.2、破坏不可剥夺条件

• 当一个已保持了某些不可剥夺资源的进程请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。该策略具有一定的实现难度，因为释放已经获得的资源可能造成前一阶段工作的失效，反复的申请和释放资源增加系统开销，降低系统吞吐量。
• 此策略常用于状态易于保存和恢复的资源，如 CPU 的寄存器及内存资源，一般不能用于打印机之类的资源。

1.3、破坏请求并保持条件

• 实现该策略的思路，就是采用预先静态分配方法，在进程开始运行之前一次申请完所需要的全部资源，在资源未满足之前不得运行，一旦运行则这些资源为其所占用，不再提出其他资源请求。
• 该策略实现简单，但是系统资源浪费严重，其中有些资源可能仅在运行初期或快运行结束时才使用，甚至根本不使用；还有可能导致“饥饿”现象，因为个别资源被其他进程长期占用。

1.4、破坏循环等待条件

• 采用顺序资源分配法：首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完，即若进程提出申请分配资源 Ri，则该进程在以后的资源申请中只能申请编号大于 Ri 的资源。
• 此策略存在的问题是，编号必须稳定，意味着限制了新类型设备的增加；有可能出现所也是用资源的顺序与系统规定的顺序不同的情况，造成资源浪费；还会给用户的编程带来麻烦。

2、死锁避免

2.1、系统安全状态

• 避免死锁的方法中，运行进程动态申请资源，但系统进行资源分配前，应先计算此次分配的安全性；若此次分配不会导致系统进入不安全状态，则允许分配；否则让进程等待。
• 所谓安全状态，指系统能按某种进程推进顺序（P1,P2,……,Pn）为每个进程分配所需的资源，直到满足每个进程对资源的最大需求，使每个进程都顺序完成，此时称P1,P2,……,Pn为安全序列；若系统找不到一个安全序列，则称系统处于不安全状态。
  
• 并非所有的不安全状态都是死锁，但可以肯定的是系统进入不安全状态后发生死锁的概率，远比没有进入不安全状态的要大很多。

2.2、银行家算法

• 该算法是著名的死锁避免算法，其思想是：把操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用于向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。进程运行前先声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源是否满足该进程尚需的最大资源量，能则按当前的申请分配，否则推迟分配。

1）数据结构描述

• 可利用资源向量 Available：含有 m 个元素的数组，每个元素代表一类可用资源数目，Available[j]=K 表示该系统现有 Rj 类资源 K 个。

• 最大需求矩阵 Max：n*m 矩阵，定义系统中 n 个进程的每个进程对 m 类资源的最大需求；一行代表一个进程，一列代表一类资源，Max[i,j]=K 表示进程 i 需要 Rj 类资源最大数目为 K。

• 分配矩阵 Allocation：n*m 矩阵，定义系统中每类资源当已分配给每个进程的资源数；同样行表示进程，列表示一类资源。

• 需求矩阵 Need：n*m 矩阵，表示每个进程接下来最多还需要多少资源。

• 上述三个矩阵的关系：

  Need = Max - Allocation

2）银行家算法描述

• 设 Request_i 是进程 Pi 的请求向量，Request_i[j] = K 表示进程 Pi 需要 j 类资源 K 个。当 Pi 发出资源请求后，系统按以下步骤进行检查：
  ① 若 Request_i[j]<=Need[i,j]，则转向步骤②；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
  ② 若 Request_i[j]<=Available[j]，则转向步骤③；否则，表示尚无足够的资源，Pi 进程需要等待。
  ③ 系统试探着把资源分配给进程 Pi，并修改相应数据结构中的数值：
  Available = Available - Request_j；
  Allocation[i,j]=Allocation[i,j] + Request_i[j]；
  Need[i,j] = Need[i,j] - Request_i[j]；
  ④ 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态；若安全，才正式将资源分配给进程 Pi，以完成本次分配；否则，将本次试探分配作废，恢复原来资源分配状态，让进程 Pi 等待。

3）安全性算法

• 设工作向量 Work，有 m 个元素，表示系统中剩余可用资源数目。在安全性算法开始时，Work=Available。

  ① 初始时安全序列为空。
  ② 从Need 矩阵找出符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于等于 Work 向量，找到后，把对应的进程加入安全序列；若找不到，则执行步骤④。
  ③ 进程 Pi 进入安全序列后，可顺利执行直到完成，并释放分配给它的资源，因此应执行 Work = Work + Allocation[i]，返回步骤②.
  ④ 若此时安全序列中已有所有进程，则系统处于安全状态，否则系统处于不安全状态。

• 例子：

• 假设系统有五个进程{P0,P1,P2,P3,P4}和三类资源{A，B，C}，T0 时刻资源分配情况如下：

  

• 由题意获得 Max 矩阵和 Allocation 矩阵以及 Need 矩阵：

  
  ①将 Work 向量与 Need 矩阵各行进行比较，找出 Work 矩阵小的行，例如初始时：
  (3,3,2)>(1,2,2)
  (3,3,2)>(0,1,1)
  对应P1 进程和 P3 进程，选择 P1 暂时加入安全序列。释放 P1 所占的资源，也就是把 P1 对应的 Allocation 矩阵中的一行与 Work 向量相加：
  (3,3,2)+(2,0,0)=(5,3,2)=Work
  更新需求矩阵，去掉 P1
  
  用更新后的 Work 向量和 Need 矩阵重复①，最后得到一个安全序列{P1,P3,P4,P2,P0}

• 银行家算法举例：

• 在上述例子的基础上，进一步用银行家算法分析。

  1）P1 请求资源：P1 发出请求向量 Request1(1,0,2)，系统按银行家算法进行检查：
  Request1(1,0,2)<=Need(1,2,2)
  Request1(1,0,2)<=Available1(3,3,2)
  系统先假定可为 P1 分配资源，并修改
  Available = Available - Request1 = (2,3,0)
  Allocation1 = Allocation1 + Request1 = (3,0,2)
  Need1 = Need1 - Request1 = (0,2,0)
  令 Work= Available=（2，3，0），再利用安全性算法检查此时系统是否安全，如下表：
  

• 有前面的安全性算法分析可以知，可找到一个安全序列{P1,P3,P4,P2,P0}，因此系统是安全的，可以立即将 P1 所申请的资源分配给它，分配后的系统中资源情况如下：

  
  2）P4 请求资源：P4 发出请求向量 Request4(3,3,0)，系统按银行家算法检查：
  Request4(3,3,0)<=Need4(4,3,1);
  Request4(3,3,0)>=Available(2,3,0), 让 P4 等待。
  3）P0 请求资源：P0 发出请求向量 Request0(0,2,0)，系统仍旧按照银行家算法检查：
  Request0(0,2,0)<=Need0(7,4,3);
  Request0(0,2,0)<=Available(2,3,0)
  系统暂时假定可为 P0 分配资源，修改有关数据：
  Available = Available - Request0 = (2,1,0)
  Allocation0 = Allocation0 + Request0 = (0,3,0)
  Need0 = Need0 -Request0 = (7,2,3)
  如下表：
  

• 进行安全性检查：可用资源 Available(2,1,0) 已不能满足任何进程的需要，因此系统进入不安全状态，因此拒绝 P0 请求并让 P0 等待，将 Available、Allocation0 和 Need0 恢复为之前的值。

3、死锁检测和解除

3.1、资源分配图

• 圆圈代表一个进程，框代表一类资源，框中的圆表示某类资源的一个资源；从进程到资源有向边称为请求，意义是表示该进程申请一个单位的该类资源；从资源到进程的有向边称为分配边，表示将该类资源分配给进程。

3.2、死锁定理

• 简化分配图可检测系统状态 S 是否为死锁状态，简化方法和步骤如下：

• 1）在资源分配图中，找出既不阻塞又不孤点的进程 Pi；也就是找出一条有向边与它向量，且该有向边对应资源的申请数量小于等于该系统已有的空闲资源数量。然后消去它所有的请求边和分配边，使之成为孤立点。

• 注意：判断某种资源是否有空间，应当用它的资源数量减去它在资源分配图中的出度。

• 2）进程 Pi 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。根据 1） 中的方法进行一系列简化后，若能消去图中所有的边，则称该图是完全可简化的。

  

• S 为死锁的条件当且仅当 S 状态的资源分配图是不可完全简化的，该条件为死锁定理。

3.2、死锁解除

• 一旦检出死锁，就立即采取相应的措施来解除死锁。解除死锁的主要方法有资源剥夺法、撤销进程法和进程回退法。

1）资源剥夺法

• 挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他死锁进程。但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。

2）撤销进程法

• 强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。

3）进程回退法

• 让一个或多个进程回退到足以回避死锁的地步，进程回退时资源释放资源而非剥夺。要求系统保持进程的历史信息，设置还原点。·

转载地址：http://wqqgn.baihongyu.com/