【操作系统】处理死锁的方法

旧城等待， 2022-07-14 10:58 309阅读 0赞

破坏死锁的四个必要条件中的一个或几个。

# 预防死锁 #

*  破坏互斥条件
 *  破坏请求和保持条件
 *  破坏不可剥夺条件
 *  破坏环路等待条件

## 破坏互斥条件 ##

即允许多个进程同时访问资源。但由于资源本身固有特性的限制，此方法不可行。

## 破坏请求和保持条件 ##

### 第一种协议 ###

全分配，全释放: 采用预先静态分配方法，即要求进程在运行之前一次性申请它所需要的全部资源，在它的资源未满足前，不把它投入运行。

若系统有足够的资源，便可把进程需要的所有资源分配给它，在整个运行期间便不会再提出资源要求，从而摒弃了请求条件。在该进程的等待期间，它并未占有任何资源，因而也摒弃了保持条件，这样可以保证系统不会发生死锁。

简单安全，但资源浪费严重，可能有饥饿现象，同时必须**预知进程所需要的全部资源。**

### 第二种协议 ###

允许一个进程只获得运行初期所需的资源后，便开始运行。

摒弃保持条件：进程运行过程中必须释放已分配给自己的且已经用完的全部资源，然后才能再请求新的所需资源。

第二种协议能使进程更快地完成任务，提高设备利用率，还可减少进程饥饿的几率。

## 破坏不可剥夺条件 ##

### 实施方案 1 ###

在允许进程动态申请资源前提下，规定一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。

### 实施方案 2 ###

进程申请的资源被其他进程占用时，可以通过操作系统抢占这一资源（适用于状态易于保存和恢复的资源） 。

破坏不可剥夺条件的方法实现较复杂，需付出很大的代价。会增加系统开销，降低系统吞吐量，且进程前段工作可能失效。

## 破坏环路等待条件 ##

采用有序资源分配方法，即将系统中所有资源都按类型赋予一个编号，要求每个进程均严格按照资源序号递增的次序来请求资源, 从而保证任何时刻的资源分配图不出现环路。

例如：系统把所有资源按类型进行排队。如输入机 =1，打印机 =2，磁带机 =3，磁盘机 =4。

如果一个进程已经分配了序号为 i 资源，它接下来请求的资源只能是那些排在 i 之后的资源。

当 `i<j`时，进程 A 获得 Ri，可以请求 Rj，而进程 B 获得 Rj 再请求 Ri不可能发生，因为资源 Ri 排在 Rj 前面。

在采用这种策略时，总有一个进程占据了较高序号的资源，此后它继续申请的资源必然是空闲的，因而进程可以一直向前推进。

有序资源分配方法的缺点：新增资源不便（原序号已排定） ，用户不能自由申请资源，加重了进程负担。使用资源顺序与申请顺序不同可能造成资源浪费。

# 避免死锁 #

不需要事先采取限制措施破坏产生死锁的必要条件（死锁预防）; 在资源的动态分配过程中, 采用某种策略防止系统进入不安全状态, 从而避免发生死锁。

在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。

## 系统的安全状态 ##

安全状态指在某一时刻，系统能按某种进程顺序(p1,p2,…，pn) 来为每个进程 Pi 分配其资源，**直到满足每个进程对资源的最大需求**，使每个进程都可顺利地完成，则称此时的系统状态为安全状态，称序列(p1,p2,…，pn) 为安全序列。若某一时刻系统中不存在这样一个安全序列，则称此时的系统状态为不安全状态。

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

### 死锁状态空间 ###

如果一个系统处于安全状态，就不会死锁。

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

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

![图示][SouthEast]

### 安全状态实例 ###

例：假定系统中有三个进程 P1、P2 和 P3，共有 12 台打印机，三个进程对打印机的需求和占有情况如下表所示：

![图示][SouthEast 1]

T0 时刻，存在一个安全序列（P2，P1，P3） ，所以系统是安全的。

> 安全序列可能不唯一

### 由安全状态向不安全状态的转换 ###

上例中，若 P3 再申请一台，则进入不安全状态。

![图示][SouthEast 2]

在 P3 请求资源时，尽管系统中尚有可用的打印机，但却不能分配给它，必须让 P3 一直等待到 P1 和 P2 完成，释放出资源后再将足够的资源分配给 P3。

## 银行家算法（Banker’s Algorithm） ##

银行家算法是最具代表性的避免死锁算法（Dijkstra 于1965 年提出）

银行家算法的实质：设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。

检查是否有足够的剩余资金满足一个距最大请求最近的客户。如果有，这笔贷款被认为是能够收回的。继续检查下一个客户，如果所有投资最终都被收回，那么该状态是安全的，最初的请求可以批准。

银行家算法执行的前提条件：要求进程必须预先提出自己的最大资源请求数量，这一数量不能超过系统资源的总量，系统资源的总量是一定的。

### 银行家算法中的数据结构 ###

假定系统中有 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 类资源

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

### 银行家算法描述（资源分配算法） ###

假定进程 Pi 请求分配 Rj 类资源 k 个，设 Request\[i,j\]=k。当进程Pi 发出资源请求后，系统按如下步骤进行检查：

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

2 如果 Request\[i,j\] ≤Available\[j\] ，转 (3)；否则表示资源不够，需等待。

3 系统试分配资源给进程 Pi，并作如下修改：  
Available\[j\]= Available\[j\] - Request\[i,j\]  
Allocation\[i,j\]= Allocation\[i,j\] + Request\[i,j\]  
Need\[i,j\]= Need\[i,j\] - Request\[i,j\]

4 系统执行安全性算法。若安全，则正式进行分配，否则恢复原状态让进程 Pi 等待。

### 银行家算法描述（安全性算法） ###

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

1 工作变量 work\[m\]：记录可用资源。开始时，Work=Available。

2 finish\[n\]：记录系统是否有足够的资源分配给进程，使之运行完成。开始时，finish\[i\]=false；当有足够资源分配给进程 Pi 时，令finish\[i\]=true。

![图解][SouthEast 3]

### 银行家算法例题1 ###

例：假定系统中有 5 个进程 P0 到 P4，3 类资源及数量分别为 A(10 个） ，B（5 个） ，C（7 个） ，T0 时刻的资源分配情况如下：

![图示][SouthEast 4]

![过程图][SouthEast 5]

P1 发出请求向量 Request1(1,0,2)  
已知 Need1 (1,2,2)，Available (3,3,2)  
系统按银行家算法进行检查：

Request1 (1,0,2) ≤ Need1 (1,2,2)  
Request1 (1,0,2) ≤ Available (3,3,2)  
系统试为 P1 分配资源，并修改相应的向量Available、Need、Allocation

![图示][SouthEast 6]

![图示][SouthEast 7]

P4 发出请求向量 Request4(3,3,0)，系统按银行家算法进行检查：

Request4(3,3,0) ≤ Need4 (4,3,1)  
Request4 (3,3,0) > Available (2,3,0)

资源不够，让 P4 等待

P0 请求资源 Request0(0,2,0)

P0 发出请求向量 Request0(0,2,0)，系统按银行家算法进行检查：

Request0(0,2,0) ≤ Need0 (7,4,3)  
Request0 (0,2,0) ≤ Available (2,3,0)

系统试为 P0 分配资源，并修改相应的向量  
Available、Need、Allocation

![图示][SouthEast 8]

![图示][SouthEast 9]

### 银行家算法例题2 ###

T0 时刻的资源分配情况如下：

![图示][SouthEast 10]

剩余资源向量为：Available = （2, 3, 3）

1.T0 时刻是否为安全状态？若是，请给出安全序列。

![图示][SouthEast 11]

2.在 T0 时刻若进程 P2 请求资源（0，3，4） ，是否能实施资源分配？

因为 Request2（0, 3, 4）> Available （2, 3, 3）所以不能满足进程 P2 的请求。

3.若进程 P4 请求资源（2，0，0） ，是否可以资源分配？

Request4（2, 0, 0）≤ Need4 (2, 0, 1)  
且 Request4（2, 0, 0）< Available（2, 3, 3）  
试分配后，则 Need4 =(0, 0, 1), Allocation4 =(4, 0, 4)  
新的剩余向量 Available = （0, 3, 3）

![图示][SouthEast 12]

### 银行家算法流程图 ###

![图示][SouthEast 13]

## 死锁避免小结 ##

优点

*  比死锁预防限制少。
 *  无死锁检测方法中的资源剥夺, 进程重启。

缺点

*  必须事先声明每个进程的最大资源请求。
 *  考虑的进程必须是无关的, 也就是说, 它们执行的顺序没有任何同步要求的限制。
 *  进程的数量保持固定不变，且分配的资源数目必须是固定的。

# 死锁的检测和解除 #

如果在一个系统中，既未采用死锁预防方法，也未采用死锁避免方法，而是直接为进程分配资源，则系统中便有可能发生死锁。

一旦死锁发生，系统应能将其找到并加以消除，为此需提供死锁检测和解除死锁的手段。

检测死锁的基本思想：在操作系统中保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。

## 资源分配图 ##

资源分配图又称进程 -资源图，它是描述进程和资源间的申请和分配关系的一种有向图。

圆圈表示进程节点 P，方框表示资源节点 R，方框中的小黑点数表示资源数。

请求边：Pi →Rj 分配边：Pi ←Rj

![图示][SouthEast 14]

![图示][SouthEast 15]

上图中：r2中有两个资源，分别分配给了p1和p2，然后p1请求r1，而r1中就1个资源，分配给了p2，所以此时p1阻塞，p2请求r3，而r3中的那个资源分配给了p3，所以此时p2也阻塞，r4中的一个资源分配给了p3，所以，待p3运行完毕，释放r3，p2阻塞解除，运行完毕后释放r1，然后p1执行。下面也都同样的分析思路，此处不再详解。

![图示][SouthEast 16]

重要结论：**如果资源分配图中不存在环路，则系统中不存在死锁；反之，如果资源分配图中存在环路，则系统中可能存在死锁，也可能不存在死锁。**

## 死锁定理 ##

资源分配图的化简方法  
1 寻找一个既不阻塞又不孤立的进程结点 Pi，若无则算法结束；  
2 去除 Pi 的所有分配边和请求边，使 Pi 成为一个孤立结点；  
3 转步骤（1） 。

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

孤立结点：没有请求边和分配边与之相连。

阻塞结点：有请求边但资源无法满足其要求。

**死锁定理:出现死锁状态的充分条件是资源分配图不可完全简化。**

![图示][SouthEast 17]

![图示][SouthEast 18]

![图示][SouthEast 19]

## 死锁的检测 ##

死锁检测算法的思想

死锁检测算法的思想是基于资源分配图化简和死锁定理来检测死锁。

死锁检测的原因

系统没有采取任何预先限制死锁的措施。资源分配时不检查系统是否会进入不安全状态, 被请求的资源都被授予给进程。需要周期性检测是否出现死锁。

检测时机

*  在每个资源请求时都进行（相当于死锁避免） 。
 *  定时检测。
 *  系统资源利用率下降时检测死锁。

死锁检测中的数据结构类似于银行家算法的数据结构：

![图示][SouthEast 20]

## 死锁检测流程 ##

![图示][SouthEast 21]

## 检测算法练习题 ##

![图示][SouthEast 22]

![图示][SouthEast 23]

## 死锁的解除 ##

一旦检测出系统中出现了死锁，就应将陷入死锁的进程从死锁状态中解脱出来，常用的解除死锁方法有两种:

资源剥夺法: 当发现死锁后，从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。

*  撤消进程法: 采用强制手段从系统中撤消一个/一部分死锁进程，并剥夺这些进程的资源供其它死锁进程使用。
 *  撤消全部死锁进程。
 *  按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。

基于最小代价原则一次只终止一个进程直到取消死锁循环为止。

撤消进程选择原则

*  已消耗 CPU 时间最少
 *  到目前为止产生的输出量最少
 *  预计剩余的时间最长
 *  目前为止分配的资源总量最少
 *  优先级最低

[SouthEast]: /images/20220714/cc7a6a22cfe24a45811ab5d66bec55f5.png
[SouthEast 1]: /images/20220714/47be862d165a44c8918b99adbe2e1362.png
[SouthEast 2]: /images/20220714/83f79b0783f94897974b95e48db13d87.png
[SouthEast 3]: /images/20220714/3a9dbaf6d6114660bb6cabc5f57329fd.png
[SouthEast 4]: /images/20220714/b1194f6986804ce89131f993fa0afa3e.png
[SouthEast 5]: /images/20220714/122fee95f2144dada941a76797cc30eb.png
[SouthEast 6]: /images/20220714/c138322ef8794eef8bb523dba81caad9.png
[SouthEast 7]: /images/20220714/a3fd5fdb3aed43a191b1eb0b9edf5f29.png
[SouthEast 8]: /images/20220714/23c1222bfbd14d878a5b04bc6c762c5c.png
[SouthEast 9]: /images/20220714/88f8d88888be4d3cabf1bc47f69c51d5.png
[SouthEast 10]: /images/20220714/66fecee85a9f44f2bfb1327721ab45bd.png
[SouthEast 11]: /images/20220714/36d119eb2ec24e3fb174235ef62d9b4b.png
[SouthEast 12]: /images/20220714/6fd63a0fa0ad495a84f3b2f641e8d5ec.png
[SouthEast 13]: /images/20220714/3db1c9dee87f41d99905554bfe90b445.png
[SouthEast 14]: /images/20220714/01feaa87b6c947c78f039ba5febe567a.png
[SouthEast 15]: /images/20220714/49f8bd57cfbb434faddc860e40c48cf9.png
[SouthEast 16]: /images/20220714/84f3f94364364a6f8e33c9ce8ece8c8c.png
[SouthEast 17]: /images/20220714/fb75879689d64f3e9b45eaf38574d360.png
[SouthEast 18]: /images/20220714/7fa4620176494566a0119a2da2977d3f.png
[SouthEast 19]: /images/20220714/c8596c44621544928434260761e47384.png
[SouthEast 20]: /images/20220714/35fb13e6aa064b26966951c1ccb3821b.png
[SouthEast 21]: /images/20220714/5c0a145e1a9d465395f95361a977cf01.png
[SouthEast 22]: /images/20220714/150459c8401d4ccda3c8eb2ae4eac30f.png
[SouthEast 23]: /images/20220714/60210890f9284d95b7c904aedd45587e.png