死锁的概念

指多个进程在运行过程中因争夺资源而造成的一种僵局（deadly-Embrace)，若无外力作用，这些进程都将无法向前推进。

注意：

  • 参与死锁的进程数至少为2

  • 参与死锁的所有进程均等待资源

  • 参与死锁的进程至少有两个占有资源

  • 参与死锁的进程是系统中当前正在运行进程的一部分。

产生死锁的条件和处理

资源分类

​ 操作系统管理着系统内所有资源，它负责分配不同类型的资源给进程使用，系统中的资源从不同角度可分：

根据资源本身的性质

  • 可剥夺资源：如主存、CPU

  • 不可剥夺资源：如驱动器、打印机等

    根据资源使用期限

  • 永久性资源：可再次使用，如所有硬件。

  • 临时性资源：消耗性的资源，如消息、信号和数据

产生死锁的原因

竞争非剥夺性资源

竞争临时性资源

进程推进顺序不当

422

551

死锁的必要条件

互斥条件（资源独占）

一个资源每次只能给一个进程使用

请求和保持条件（部分分配，占有申请）

（部分分配，占有申请）

一个进程在申请新的资源的同时保持对原有资源的占有

（只有这样才是动态申请，动态分配）

非剥夺条件（不可强占）

资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放

循环等待条件

存在一个进程等待队列

{P1 , P2 , … , Pn},

其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路

四种基本处理方法

预防死锁

指通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。

避免死锁

指在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。

检测死锁

允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。

解除死锁

当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来

死锁的预防

破坏互斥条件

（不可行）

即允许多个进程同时访问资源。但由于资源本身固有特性限制，有的资源根本不能同时访问，只能互斥访问，所以不可能用破坏互斥条件来预防死锁。

破坏请求和保持条件

​ 可采用预先静态分配方法，即要求进程在运行之前一次申请它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦运行后，这些资源全归其占有，同时它也不再提出其它资源要求，这样可以保证系统不会发生死锁。

​ 此方法虽简单安全，但降低了资源利用率，同时必须预知进程所需要的全部资源。

破坏不可剥夺条件

一个已经获得某些资源的进程，若又请求新的资源时不能得到满足，则它必须释放出已获得的所有资源，以后需要资源时再请求。即一个进程已获得的资源在运行过程中可被剥夺。从而破坏了“不剥夺”条件。

这种方法实现较复杂，会增加系统开销，降低系统吞吐量。

破坏环路条件

​ 可采用有序资源分配方法，即将系统中的所有资源都按类型赋予一个编号，要求每一个进程均严格按照编号递增的次序来请求资源，同类资源一次申请完。也就是，只要进程提出请求资源Ri，则在以后的请求中，只能请求Ri后面的资源，这样不会出现几个进程请求资源而形成环路。

​ 该方法虽提高了资源的利用率，但编号难，加重进程负担及因使用资源顺序与申请顺序不同而造成资源浪费。

死锁的避免

定义

定义

定义:系统运行过程中， 允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待。

安全序列和安全状态

指在某一时刻，系统能按某种进程顺序(P1,P2,…，Pn)来为每个进程Pi分配其资源,直到满足每个进程对资源的最大需求,使每个进程都可顺利地完成，称此时的系统状态为安全状态，称序列(P1,P2,…，Pn)为安全序列。

若某一时刻系统中不存在这样一个安全序列，则称此时的系统状态为不安全状态。

在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可以避免死锁的发生。

死锁和安全/不安全的关系

在死锁避免的方法中，允许进程动态申请资源，系统在进行资源分配之前，先计算资源分配的安全性，若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。

  • 如果一个系统在安全状态，就没有死锁

  • 如果一个系统处于不安全状态，就有可能死锁

  • 避免死锁的实质：确保系统不进入不安全状态

银行家算法

具有代表性的避免死锁算法，是Dijkstra给出的银行家算法。

数据结构

实现银行家算法，须设置若干数据结构。假定系统中有n个进程（P1，P2，…，Pn），m类资源（R1，R2，…，Rm），银行家算法中使用的数据结构如下：

  • 可利用资源向量：available[j]=k, 资源Rj类有k个可用**

  • 最大需求矩阵：Max[i,j]=k,进程Pi最大请求k个Rj类资源

  • 分配矩阵：Allocation[i,j]=k,进程Pi分配到k个Rj类资源

  • 需求矩阵：Need[i,j]=k,进程Pi还需要k个Rj类资源**

  • 请求向量： Requesti,是进程Pi的请求向量。Requesti [j] =k，表示进程Pi请求分配Rj类资源k个。

三个矩阵的关系：

Need [i,j] = Max[i,j] – Allocation [i,j]

安全性检查

当进程Pi 发出资源请求后，系统按如下步骤进行检查：

(1)如Requesti[j]≤Need[i,j],转(2);否则出错，因为进程申请资源量超过它声明的最大量。

(2)如Requesti[j] ≤Available[j],转(3);否则表示资源不够，需等待。

(3)系统试分配资源给进程Pi，并作如下修改：

Available[j]:= Available[j]- Requesti[j]

Allocation[i,j]:= Allocation[i,j]+ Requesti[j]

Need[i,j]:= Need[i,j]- Requesti[j]

(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，则正式进行分配，否则恢复原状态，让进程Pi等待。

为了进行安全性检查，需要定义如下数据结构

  • int Work[m] 工作变量，记录可用资源。开始时， Work:= Available

  • boolean Finish[n] 工作变量，记录进程是否执行完。开始时， Finish[i]=false;当有足够资源分配给进程Pi时，令Finish[i]=true。

例

3326

死锁的检测和解除

如果在一个系统中，既未采用死锁预防方法，也未采用死锁避免方法，而是直接为进程分配资源，则系统中便有可能发生死锁。一旦死锁发生，系统应能将其找到并加以消除，为此需提供死锁检测和解除的手段。

资源分配图

检测死锁的基本思想: 在操作系统中保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。为此，将进程和资源间的申请和分配关系描述成一个有向图—-资源分配图。

资源分配图又称进程-资源图，它描述了进程和资源间的申请和分配关系，该图是一个有向图，具有以下定义和限制：

一个结点集合N和边集合E

结点N被分为两个互斥子集

  • 进程结点子集 P = {P1,P2,…,Pn}

  • 资源结点子集 R = {R1,R2 , … ,Rm}

  • N=PUR={P1,P2,…,Pn}U{R1,R2,…,Rm}

圆圈表示一进程，方框表示一类资源，其数目由方框中的小圆圈数表示

边E

  • 请求边：直接 $P_i\to R_j$ 即 $e=(P_i,R_j)$

  • 分配边：$P_i\leftarrow R_j$即$e=(R_j,P_i)$

3999

如果一个图中没有环路（也称回路），则系统中不存在死锁；若有环路，系统可能存在死锁。

即可说，环路是死锁的必要条件，但不是充分条件。

资源分配图的化简

​ 可以通过对资源分配图进行化简，来判断系统是否处于死锁状态。资源分配图中的约简方法如下：

（1）寻找一个既不阻塞又非孤立的进程结点Pi，若无，则算法结束；

（2）去除Pi的所有分配边和请求边，使Pi成为一个孤立节点；

（3）转步骤（1）。

在进行一系列化简后，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；反之，称该图是不可完全简化的。

4418

死锁定理

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

化简步骤

①先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞（“不阻塞”即：系统有足够的空闲资源分配给它）的

②接着把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来

③这样，系统剩余的空闲资源便多了起来，接着又去看看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点。

④最后，所有的资源和进程都变成孤立的点。这样的图就叫做“可完全简化”。

例1

4881

第一步：分析资源 R1。它有三个向外的箭头，表示已向进程分配了 3 个资源实例，此时 R1 已无可用资源。

第二步：分析资源 R2。它有一个向外的箭头，表示已分配 1 个资源实例，此时 R2 还剩余 1 个空闲资源。

第三步：分析进程 P2。P2 正在申请 1 个 R1 资源，但 R1 已全部分配完毕。因此，进程 P2 因资源不足进入阻塞状态，无法被简化为孤立节点。

5249

第四步：分析进程 P1。P1 申请 1 个 R2 资源，而此时 R2 尚有 1 个可用资源，因此该请求可以被满足。P1 在获得所需资源后即可顺利执行，并在执行完毕后释放其占有的所有资源。在资源分配图中，这意味着可以移除所有与 P1 相连的边，使其成为一个孤立节点，如图 2 所示。

5569

第五步：进程P1运行完后，释放其所占有的资源（2个R1资源和1个R2资源），系统回收这些资源后，空闲的资源便变成2个R1资源和1个R2资源，由于进程P2一直在申请一个R1资源，所以此时，系统能满足它的申请。这样，进程P2便得到了它的全部所需资源，所以它不会进入阻塞状态，可以一直运行，等它运行完后，我们再把它的所有的资源释放。相当于：可以把P2的所有的边都去掉，化成一个孤立的点，变成图3

例2

5946

一、资源状态分析

首先，分析系统中各类资源的初始分配情况：

  • R1：共有 1 个实例，且已分配。当前可用数量为 0。
  • R2：共有 2 个实例，均已分配。当前可用数量为 0。
  • R3：共有 2 个实例，其中 1 个已分配，尚有 1 个可用。
  • R4：共有 1 个实例，且已分配。当前可用数量为 0。

综上，当前系统中仅有 R3 尚余 1 个可用资源实例。

二、进程请求分析

接下来，分析各进程的资源请求是否能被满足：

  • 进程 P1：请求资源 R1。由于 R1 已无可用实例，P1 进入阻塞状态。
  • 进程 P2：请求资源 R4。由于 R4 已无可用实例，P2 进入阻塞状态。
  • 进程 P3：请求资源 R2 和 R3。尽管 R3 有可用实例，但由于 R2 已全部分配，P3 的请求同样无法被满足，进入阻塞状态。

三、结论

分析可知，所有进程（P1, P2, P3）均因请求的资源无法得到满足而处于阻塞状态。因此，资源分配图中不存在任何可以首先执行完毕并释放资源的进程，导致该图无法被完全简化。

这表明系统已经产生了死锁。

死锁的综合处理策略