17、死锁（操作系统笔记）

2017-02-17 本文已影响226人 yjaal

一、死锁的基本概念

1.1 死锁的定义

一组进程中，每个进程都无限等待被该组进程中另一进程所占用的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。
如果发生死锁，会浪费大量系统资源，甚至导致系统崩溃
注意：
参与死锁的所有进程都在等待资源
参与死锁的进程是当前系统中所有进程的子集

1.2 死锁的产生原因

资源数量有限、锁和信号量错误使用。

资源的使用方式
“申请-分配-使用-释放”模式
可重用资源：可被多个进程多次使用，又可分为可抢占资源与不可抢占资源，如处理器、I/O部件、内存、文件、数据库、信号量等可抢占资源。
可消耗资源：只可使用一次、可创建和销毁的资源。如信号、中断、消息等。

1.3 活锁和饥饿

1
说明：

如图，这里有两个进程都需要使用资源1和资源2，有这样一种情况，比如这两个进程都上cpu执行，但是进程A执行到第二句的时候需要使用资源2，而进程B执行到第二句的时候需要资源1，但是此时恰好都不能获得各自的资源，这样就进入忙等待（进入轮询看资源是否可用），这就是活锁，也就是先加锁再轮询，这样导致两个进程既无进展也没有阻塞。这和死锁的概念的区别在于死锁的时候进程不能进入cpu去执行。
饥饿：资源分配策略决定

1.4 产生死锁的必要条件

互斥使用（资源独占）：一个资源每次只能给一个进程使用
占有且等待（请求和保持，部分分配）：进程在申请新的资源的同时保持对原有资源的占有。
不可抢占（不可剥夺）：资源申请者不能强行的从资源占有着手中多去资源，资源只能由占有着自愿释放
循环等待
存在一个进程等待队列｛P1，P2，......，Pn｝，其中P1等待P2占有的资源，P2等待P3占有的资源，......，Pn等待P1占有的资源，形成一个进程等待环路。

二、资源分配图（RAG：Resource Allocation Graph）

用有向图描述系统资源和进程的状态

2.1 资源分配图画法说明

系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例。
资源类：用方框表示。资源实例：用方框中的黑圆点表示。进程：用圆圈中加进程名表示。

3
分配边：资源实例-->进程；申请边：进程-->资源类

2.2 死锁定理

如果资源分配图中没有环路，则系统中没有死锁；如果图中存在还礼则系统中可能存在死锁。
如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。例如：

3

2.3 资源分配图化简

化简步骤：

1、找一个非孤立、且只有分配边的进程结点，去掉分配边，将其变为孤立结点
2、再把相应的资源分配给一个等待该资源的进程，即将该进程的申请边变为分配边。
3、重复上述步骤直到找不到资源分配结点。完成之后如果所有结点都变为孤立结点则表示系统中没有死锁，否则系统存在死锁。

三、死锁预防

3.1 解决死锁的方法

不考虑此问题（鸵鸟算法）
不让死锁发生
- 死锁预防。这是一种静态策略：即设计合理的资源分配算法，不让死锁发生
- 死锁避免。这是一种动态策略：以不让死锁发生为目标，跟踪并评估资源分配过程，根据评估结构决策是否分配
让死锁发生
死锁检测和解除

3.2 死锁预防（Deadlock Prevention）

定义：在设计系统时，通过确定资源分配算法，排除发生死锁的可能性
具体做法：防止产生死锁的四个必要条件中任何一个条件的发生

3.2.1 破坏“互斥使用/资源独占”条件

资源转换技术：把独占资源变为共享资源
SPooling技术的引入，解决不允许任何进程直接占有打印机的问题。设计一个“守护进程/线程”负责管理打印机，进程需要打印时，将请求发给该daemon，由它完成打印任务。

3.2.2 破坏“占有且等待”条件

实现方案1：要求每个进程在运行前必须一次性申请它所有求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。当然，这种方案的资源利用率较低，容易出现“饥饿”现象。
实现方案2：在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。

3.2.3 破坏“不可抢占”条件

实现方案
当一个进程申请的资源被其他进程占用时，可以通过操作系统抢占这一资源（两个进程优先级不同）
局限性：适用于状态易于保存和恢复的资源。如cpu和内存等。

3.2.4 破坏“循环等待”条件

通过定义资源类型的线性顺序实现
实施方案：资源有序分配法
把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。
实现时要考虑什么问题？
如何进行编号？这里我们一般根据资源使用的频繁性来进行编号。例如解决哲学家就餐问题。
为什么资源有序分配法不会产生死锁？
起始就是进程申请的资源编号必须是递增的，比如进程P1申请了资源1、3、9，而进程P2需要资源1、2、5，那么进程P2在申请时必须按照1、2、5的顺序来申请，这样就破坏了环路条件，因为在申请到资源1之前，后面的资源是申请不到的。

四、死锁避免

定义：在系统运行过程中，对进程发出的每一个系统能满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统发生死锁或可能发生死锁（不是安全状态），则不予分配，否则（安全状态）予以分配。
安全状态：如果系统中存在一个所有进程构成的安全序列P1，P2，......，Pn，则称系统处于安全状态。安全状态表示系统一定没有发生死锁。
安全序列
一个进程序列｛P1，P2，......，Pn｝是安全的，如果对于每个进程Pi(1<= i <= n)：它以后还需要的资源数量不超过系统当前剩余资源量与所有进程Pj(j < i)当前占有资源量只和。
不安全状态：系统中不存在一个安全序列。一定会导致死锁。

五、死锁避免算法：银行家算法

这是Dijkstra在1965年提出的，是仿照银行发放贷款时采取的控制方式而设计的一种死锁避免算法。

应用条件
1、在固定数量的进程中共享数量固定的资源。
2、每个进程预先指定完成工作所需的最大资源数量。
3、进程不能申请比系统中可用资源总数还多的资源。
4、进程等待资源的时间是有限的。
5、如果系统满足了进程对资源的最大需求，那么，进程应该在有限的时间内使用资源，然后归还给系统。

4

当进程Pi提出资源申请时，系统执行下列步骤：
（1）若Request[i] <= Need[i]，转（2）；否则，报错返回。
（2）若Request[i] <= Available，转（3）；否则，报错返回。
（3）假设系统分配了资源，则有：

Available = Available - Request[i];
Allocation[i] = Allocation[i] + Request[i];
Need[i] = Need[i] = Request[i]

若系统新状态是安全的，则分配完成；若系统新状态是不安全的，则恢复原来状态，进程等待。

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

Work : ARRAY[1...m] of integer;
Finish : ARRAY[1...n] of Boolean;

安全性检查的步骤：
（1）Work = Available； Finish = false；
（2）寻找满足条件的i：

a. Finish[i] == false
b. Need[i] <= Work;

如果不存在，则转（4）
（3）

Work = Work + Allocation[i] ;
Finish[i] = true

转（2）
（4）若对所有i，Finish[i] == true，则系统处于安全状态，否则，系统处于不安全状态。

六、死锁检测与解除

死锁检测
允许死锁发生，但是操作系统会不断监视系统进展情况，判断死锁是否真的发生。一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。
检测时机
1、当进程由于资源请求不满足而等待时检测死锁。这里缺点是系统开销较大。
2、定时检测
3、系统资源利用率下降时检测死锁

6.1 一个简单的死锁检测算法

6.2 死锁的解除

发生死锁后重要的是以最小的代价恢复系统的运行。方法如下：

撤销所有死锁进程，代价较大。
进程回退再启动，代价也较大
按照某种原则逐一死锁进程，直到不发生死锁
按照某种原则逐一抢占资源（资源被抢占的进程必须回退到之前的对应状态），直到不发生死锁。

七、哲学家就餐问题

问题描述：

有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子。
每个哲学家的行为是思考，感到饥饿，然后吃通心粉。
为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子（筷子的互斥使用、不能出现死锁现象）

问题模型：
应用程序中并发线程执行时，协调处理共享资源。

7.1 第一种方案

6
说明：这里将筷子当作一个信号量来处理，饥饿的时候会申请筷子（P操作），当同时等待拿某只筷子的时候会发生死锁。

为防止死锁发生可采取的措施：

最多允许四个哲学家同时坐在桌子周围
仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子。
给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家反之。

7.2 第二种方案

7
说明：这里增加了一个信号量room，即这个桌子上最多允许坐四个人，这样就不会发生死锁。

7.3 第三种方案

9
说明：这里使用管程来解决，即哲学家拿筷子的动作是由管程管理，一次只能拿两只筷子。