OS第3章死锁(MR)

1、操作系统操作系统第3章 死锁本章教学内容v3.1 3.1 资源资源v3.2 3.2 死锁概念死锁概念v3.3 3.3 死锁的预防死锁的预防v3.4 3.4 死锁的避免死锁的避免v3.5 3.5 死锁的检测和恢复死锁的检测和恢复v3.6 3.6 处理死锁的综合方式处理死锁的综合方式v3.7 3.7 本章小结本章小结3.1 资源3.1.1 3.1.1 资源使用模式资源使用模式 申请申请 使用使用 释放释放3.1.2 可剥夺资源与不可剥夺资源按占有方式划分：按占有方式划分： 可剥夺资源可剥夺资源 当该资源被某进程拥有后，其它进程仍可当该资源被某进程拥有后，其它进程仍可以把它剥夺过去为己所用，并且不会

2、产生任以把它剥夺过去为己所用，并且不会产生任何不良影响。例如，内存就是可剥夺资源。何不良影响。例如，内存就是可剥夺资源。 不可剥夺资源不可剥夺资源 该资源一旦被某进程占有，则其它进程不该资源一旦被某进程占有，则其它进程不能强行抢占，必须由拥有者自动释放，否则能强行抢占，必须由拥有者自动释放，否则会引起相关计算的失效。如光盘刻录机。会引起相关计算的失效。如光盘刻录机。 死锁和不可剥夺资源有关死锁和不可剥夺资源有关 3.2 死锁概念v什么是死锁什么是死锁v死锁的条件死锁的条件v资源分配图资源分配图v处理死锁的方法处理死锁的方法3.2 死锁概念 3.2.1 3.2.1 什么是死锁什么是死锁 1 1死

3、锁示例死锁示例汽车过窄桥时的冲突汽车过窄桥时的冲突在计算机系统中，涉及软件、硬件资源的进在计算机系统中，涉及软件、硬件资源的进程都可能发生死锁程都可能发生死锁 DijkstraDijkstra在在19651965年提出了死锁。年提出了死锁。死锁的概念v 产生死锁的原因产生死锁的原因: :多个并发进程因多个并发进程因竞争资源而造成的一种僵局，若无竞争资源而造成的一种僵局，若无外力的作用，这些进程将都不能再外力的作用，这些进程将都不能再继续执行。继续执行。 v死锁：死锁：是指在一个进程集合中的每个进程是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能都在等待仅由该集合中的另一个进程

4、才能引发的事件而无限期地僵持下去的局面。引发的事件而无限期地僵持下去的局面。v计算机系统产生死锁的根本原因就是计算机系统产生死锁的根本原因就是资源资源有限有限且且操作不当操作不当v死锁的危害死锁的危害 系统瘫痪系统瘫痪 资源浪费资源浪费 死锁的概念 什么是死锁v有两个进程有两个进程A A和和B B，竞争两个资源，竞争两个资源R R和和S S，这两个资源，这两个资源都是不可剥夺资源。都是不可剥夺资源。 进程进程A A 进程进程B B 申请并占用申请并占用R R 申请并占用申请并占用S S 申请并占用申请并占用S S 申请并占用申请并占用R R 释放释放R R 释放释放S S 释放释放S S 释放

5、释放R R 什么是死锁进程推进顺序对引发死锁的影响进程推进顺序对引发死锁的影响死锁的概念v 产生死锁有四个必要条件：产生死锁有四个必要条件：（1 1）互斥条件。）互斥条件。 （2 2）不剥夺条件。）不剥夺条件。（3 3）部分分配（请求和保持条件）部分分配（请求和保持条件）（4 4）环路等待条件。）环路等待条件。 只要有一个必要条件不满足，则死锁就只要有一个必要条件不满足，则死锁就可以排除。可以排除。3.2.3 资源分配图1 1资源分配图的构成资源分配图的构成v由由结对结对组成：组成： G G = (= (V V, , E E) ) V V是是顶点顶点的集合，的集合，E E是是边边的集合。的集合

6、。 顶点集合可分为两部分：顶点集合可分为两部分： P P=p p1 1, , p p2 2, , , , p pn n 由系统中所有活动进程组成由系统中所有活动进程组成 R R=r r1 1, , r r2 2, , , , r rm m 由系统中全部资源类型组成由系统中全部资源类型组成v有向边有向边p pi i r rj j称为称为申请边申请边 有向边有向边r rj j p pi i 称为称为赋给边赋给边v在资源分配图中，通常用圆圈表示每个进程，用方在资源分配图中，通常用圆圈表示每个进程，用方框表示每种资源类型。框表示每种资源类型。2 2资源分配图示例资源分配图示例（1 1）集合）集合P P

7、, , R R和和E E如下：如下： P P=p p1, 1, p p2, 2, p p33 R R=r r1, 1, r r2, 2, r r3, 3, r r44 E E=p p11r r1, 1, p p22r r3, 3, r r11p p2, 2, r r22p p2, 2, r r22p p1, 1, r r33p p33（2 2）资源数量）资源数量 分别为分别为1 1，2 2，1 1，3 3（3 3）进程状态）进程状态 该图不含环路，没有死锁该图不含环路，没有死锁 资源分配图示例资源分配图示例3.2.3 资源分配图3 3环路与死锁环路与死锁 如果每类资源的实体都只有一个，如果每类

8、资源的实体都只有一个，那么图中出现环路就说明死锁了。那么图中出现环路就说明死锁了。3.2.3 资源分配图 环路与死锁 如果每类资源的实体不止一个，那么资源分配图如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。中出现环路并不表明一定出现死锁。 资源分配图中存在环路是死锁产生的必要条件，资源分配图中存在环路是死锁产生的必要条件，但不是充分条件。但不是充分条件。3.2.4 处理死锁的方法利用某些协议预防或避免死锁，保证系利用某些协议预防或避免死锁，保证系统不会进入死锁状态。统不会进入死锁状态。允许系统进入死锁状态，然后设法发现允许系统进入死锁状态，然后设法发现并克服它。并克

9、服它。完全忽略这个问题，好像系统中从来也完全忽略这个问题，好像系统中从来也不会出现死锁。不会出现死锁。3.3 死锁的预防3.3.1 3.3.1 破坏互斥条件破坏互斥条件3.3.2 3.3.2 破坏占有且等待条件破坏占有且等待条件 预分资源策略：预分资源策略：静态分配静态分配 “空手空手”申请资源策略：申请资源策略：不占有资源时才可不占有资源时才可以申请资源以申请资源 存在以下存在以下4 4个主要缺点个主要缺点 不可预测不可预测 利用率低利用率低 降低并发性降低并发性 “饥饿饥饿” ” 现象现象3.3.3 破坏非抢占条件v隐式抢占方式（申请资源失败释放隐式抢占方式（申请资源失败释放所有资源）所有

10、资源） v抢占等待者资源抢占等待者资源3.3.4 破坏循环等待条件资源有序分配策略资源有序分配策略 资源编号资源编号 设设R R=r r1 1, , r r2 2, , , , r rm m ，表示一组资源，表示一组资源 定义一对一的函数定义一对一的函数F F：R RN N，N N是一组自然数是一组自然数 如：如：F F（磁带机）（磁带机）= 1= 1，F F（磁盘机）（磁盘机）= 5= 5，F F（打（打印机）印机）= 12= 12 依序分配依序分配 约定：所有进程对资源的申请严格按照序号约定：所有进程对资源的申请严格按照序号递增的次序进行。递增的次序进行。 破坏循环等待条件先弃大，再取小先

11、弃大，再取小 一个进程申请资源一个进程申请资源r rj j，它应释放所有满足，它应释放所有满足F F( (r ri i)F F( (r rj j) ) 关系的资源关系的资源r ri i 这两种办法都是可行的，都可排除环路等待条件这两种办法都是可行的，都可排除环路等待条件 优点：优点：资源利用率和系统吞吐量都有很大提高资源利用率和系统吞吐量都有很大提高缺点：缺点：v资源请求受限，合理编号困难，增加系统开销。资源请求受限，合理编号困难，增加系统开销。v暂不使用的资源也需提前申请，增加资源占用时暂不使用的资源也需提前申请，增加资源占用时间。间。3.4 3.4 死锁的避免死锁的避免排除死锁的排除死锁的

12、动态策略。动态策略。关键是确定资源分配的安关键是确定资源分配的安全性全性 3.4.1 3.4.1 安全状态安全状态v在当前分配状态下，进程的安全序列在当前分配状态下，进程的安全序列 P P1 1, , P P2 2, , , P Pn n 是：是：若对于每一个进程若对于每一个进程P Pi i（11i in n），它需要的附加资源可被系统中），它需要的附加资源可被系统中当前可用资源与所有进程当前可用资源与所有进程P Pj j（j ji i）当前当前占有资源之和所满足，则占有资源之和所满足，则 P P1 1, , P P2 2, , , P Pn n 为一个安全序列。为一个安全序列。 这时系统处于

13、安全状态。这时系统处于安全状态。存在安全序列时一定不会有死锁发生存在安全序列时一定不会有死锁发生 死锁是不安全状态中的特例死锁是不安全状态中的特例 安全状态安全状态时时 刻刻已占有台数已占有台数最大需求台数最大需求台数当前可用台当前可用台数数进程进程P1进程进程P2进程进程P3进程进程P1进程进程P2进程进程P3T03229473T13429471T2302975T3307970T430097T59001T600010 不安全状态示意不安全状态示意时刻时刻已占有台数已占有台数最大需求台数最大需求台数当前当前可用可用台数台数进程进程P1进程进程P2进程进程P3进程进程P1进程进程P2进程进程P3

14、T03229473T14229472T24429470T3402974v若不按照安全序列分配资源，则系统可能会由安全若不按照安全序列分配资源，则系统可能会由安全状态转换为不安全状态状态转换为不安全状态 死锁的避免死锁的避免死锁状态是不安全状态。死锁状态是不安全状态。如果系统处于不安全状态，并不意味着它就如果系统处于不安全状态，并不意味着它就在死锁状态，而是表示存在导致死锁的危机。在死锁状态，而是表示存在导致死锁的危机。 如果一个进程申请的资源当前是可用的，但如果一个进程申请的资源当前是可用的，但为了避免死锁，该进程也可能必须等待。此时为了避免死锁，该进程也可能必须等待。此时资源利用率会下降。资

15、源利用率会下降。练习练习: :假定系统中有三个进程假定系统中有三个进程P P1 1、P P2 2和和P P3 3，共有，共有1212台磁带机。进程台磁带机。进程P P1 1总共要求总共要求1010台磁带机，台磁带机，P P2 2和和P P3 3分别要求分别要求9 9台和台和4 4台。假设在台。假设在T T0 0时刻，进程时刻，进程P P1 1、P P2 2和和P P3 3已分别获得已分别获得5 5台、台、2 2台和台和2 2台磁带机，尚有台磁带机，尚有3 3台空闲未分配台空闲未分配。求安全序列。求安全序列。 进进 程程 最大需求最大需求 已分配已分配 可用可用 P P1 1P P2 2P P3

16、 310109 94 45 52 22 2死锁的排除方法死锁的排除方法3.4.2 资源分配图算法资源分配图算法v资源类资源类 单体资源类单体资源类 多体资源类多体资源类v单体资源类的资源分配图单体资源类的资源分配图 除申请边和赋给边之外，还要有一种称为除申请边和赋给边之外，还要有一种称为“要求边要求边”的新的新边。要求边边。要求边 p pi i r rj j表示进程表示进程p pi i能够申请能够申请资源资源r rj j，有时用虚线表示。，有时用虚线表示。资源分配图示例资源分配图示例3.4.3 银行家算法银行家算法v“银行家算法银行家算法”（BankerBankers Algorithms A

17、lgorithm）针对多体资源类针对多体资源类 v设计思想：设计思想： 当用户申请一组资源时，系统必须做出判断：当用户申请一组资源时，系统必须做出判断：如果把这些资源分出去，系统是否还处于安全如果把这些资源分出去，系统是否还处于安全状态。若是，就可以分出这些资源；否则，该状态。若是，就可以分出这些资源；否则，该申请暂不予满足。申请暂不予满足。银行家算法数据结构银行家算法数据结构令令n n表示系统中进程的数目，表示系统中进程的数目，m m表示资源分类数。表示资源分类数。 AvailableAvailable是一个长度为是一个长度为m m的向量，它表示每类资源可的向量，它表示每类资源可用的数量。用

18、的数量。AvailableAvailablej j=k k，表示，表示r rj j类资源可用的数类资源可用的数量是量是k k。 MaxMax是一个是一个n nm m矩阵，它表示每个进程对资源的最大矩阵，它表示每个进程对资源的最大需求。需求。MaxMaxi i, , j j=k k，表示进程，表示进程p pi i至多可申请至多可申请k k个个r rj j类资类资源单位。源单位。 AllocationAllocation是一个是一个n nm m矩阵，它表示当前分给每个进矩阵，它表示当前分给每个进程的资源数目。程的资源数目。Allocation Allocation i i, , j j=k k，表

19、示进程，表示进程p pi i当当前分到前分到k k个个r rj j类资源。类资源。 NeedNeed是一个是一个n nm m矩阵，它表示每个进程还缺少多少资矩阵，它表示每个进程还缺少多少资源。源。Need Need i i, , j j=k k，表示进程，表示进程pipi尚需尚需k k个个r rj j类资源才类资源才能完成其任务。能完成其任务。3.4.3 银行家算法银行家算法1 1资源分配算法资源分配算法v令令RequestRequesti i表示进程表示进程pipi的申请向量。的申请向量。RequestRequesti i j j= = k k，表示进程表示进程p pi i需要申请需要申请k

20、 k个个r rj j类资源。当进程类资源。当进程p pi i申请资源时申请资源时，就执行下列动作：，就执行下列动作： 若若RequestRequesti iNeedNeedi i，表示出错，表示出错， 如果如果RequestRequesti iAvailableAvailable，则，则p pi i等待。等待。 假设系统把申请的资源分给进程假设系统把申请的资源分给进程p pi i，则应对有关数据，则应对有关数据结构进行修改：结构进行修改： AvailableAvailable：= Available Request= Available Requesti i Allocation Alloca

21、tioni i：= Allocation= Allocationi i + Request+ Requesti i Need Needi i：= Need= Needi i Request Requesti i 系统执行安全性算法，查看此时系统状态是否安全。系统执行安全性算法，查看此时系统状态是否安全。如果是安全的，就实际分配资源，满足进程如果是安全的，就实际分配资源，满足进程p pi i 的此次的此次申请；否则，若新状态是不安全的，则申请；否则，若新状态是不安全的，则p pi i等待，对所申等待，对所申请资源暂不予分配，并且把资源分配状态恢复成之前请资源暂不予分配，并且把资源分配状态恢复成之

22、前的情况。的情况。2 2安全性算法安全性算法 令令WorkWork和和FinishFinish分别表示长度为分别表示长度为m m和和n n的向量，最初，的向量，最初，置置Work= AvailableWork= Available，FinishFinishi i=false=false，i i=1, 2, =1, 2, n n 搜寻满足下列条件的搜寻满足下列条件的i i值：值： FinishFinishi i=false=false，且，且NeedNeedi iWorkWork。 若没有找到，则转向。若没有找到，则转向。 修改数据值：修改数据值： WorkWork：=Work+ Allocat

23、ion=Work+ Allocationi i（pipi释放所占的全部释放所占的全部资源）资源） FinishFinishi i=true=true 转向。转向。 若若FinishFinishi i=true=true对所有对所有i i都成立（任一进程都可能是都成立（任一进程都可能是p pi i），则系统处于安全状态；否则，系统处于不安全状），则系统处于安全状态；否则，系统处于不安全状态。态。v假定系统中有假定系统中有4 4个进程个进程A, B, C, DA, B, C, D和三类资源和三类资源R R1 1, , R R2 2和和R R3 3，各自的数量分别为，各自的数量分别为9, 39, 3

24、和和6 6个单位。个单位。进程进程AllocationMaxNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A100322222112B511613102C211314103D002422420 资源资源情况情况3算法应用示例 资源资源 情情况况WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3B112102511623trueA623222100723trueC723103211934trueD934420002936true进程3算法应用示例v 假定系统中有假定系统中有4 4个进程个进程A

25、, B, C, DA, B, C, D和三类资源和三类资源R R1 1, , R R2 2和和R R3 3，各自，各自的数量分别为的数量分别为9, 39, 3和和6 6个单位。个单位。v （1 1）T T0 0时刻是安全的，存在一个安全序列时刻是安全的，存在一个安全序列B, A, C, DB, A, C, D v假定系统中有假定系统中有4 4个进程个进程A, B, C, DA, B, C, D和三类资源和三类资源R R1 1, , R R2 2和和R R3 3，各自的数量分别为，各自的数量分别为9, 39, 3和和6 6个单位。个单位。v进程进程A A请求资源，进程请求资源，进程A A发出请求

26、发出请求Request(1, 0, 1)Request(1, 0, 1) 进程进程AllocationMaxNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A100322222112B511613102C211314103D002422420资源资源情况情况 资源情资源情况况进进 程程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A322201121011B613511102C314211103011D422002420系统进入不安全的状态系统进入不安全的状态 不能为进程不能为进程A A分配所申请的资源分配所申请的

27、资源 3算法应用示例v 假定系统中有假定系统中有4 4个进程个进程A, B, C, DA, B, C, D和三类资源和三类资源R R1 1, , R R2 2和和R R3 3，各自，各自的数量分别为的数量分别为9, 39, 3和和6 6个单位。个单位。v 进程进程A A请求资源，进程请求资源，进程A A发出请求发出请求Request(1, 0, 1)Request(1, 0, 1) 银行家算法银行家算法v优点优点： 限制条件少限制条件少 资源利用程度提高资源利用程度提高 v缺点：缺点： 难以保证进程数固定不变难以保证进程数固定不变 未考虑实时进程快速响应未考虑实时进程快速响应 增加了系统开销增

28、加了系统开销 进程进程 AllocationMaxNeedAvailableP1 0，1，0 7，5，3 P2 2，0，0 3，2，2 P3 3，0，2 9，0，2 P4 2，1，12，2，2 P5 0，0，24，3，3 v假设某系统中有假设某系统中有3类资源类资源(R1、R2、R3)，每一种资源的可用量，每一种资源的可用量为（为（10，5，7）：）：（1）当前系统是否安全）当前系统是否安全 （2）进程）进程P1发出请求向量发出请求向量Request1（2，0，4），系统能否将资），系统能否将资源分配给它？源分配给它？（3）如果进程）如果进程P3发出请求向量发出请求向量Request3（4，0

29、，0），系统能否），系统能否将资源分配给它？将资源分配给它？（4）如果此刻进程）如果此刻进程P2发出请求向量发出请求向量Request2（1，0，2），系统），系统能否将资源分配给它？能否将资源分配给它？（5）在（在（4）的基础上）的基础上如果又有进程如果又有进程P5发出请求向量发出请求向量Request5（2，2，0），系统能否将资源分配给它？），系统能否将资源分配给它？3.5 死锁的检测和恢复死锁的检测和恢复v 死锁检测与恢复是指系统设有专门的死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，且能通过外到死锁发生的位

30、置和原因，且能通过外力破坏死锁发生的必要条件，从而使并力破坏死锁发生的必要条件，从而使并发进程从死锁状态中解脱出来。发进程从死锁状态中解脱出来。3.5.1 3.5.1 对单体资源类的死锁检测对单体资源类的死锁检测等待图等待图资源分配图的变形资源分配图的变形 从资源分配图中去掉表示资源类的节点，且把相应从资源分配图中去掉表示资源类的节点，且把相应边折叠在一起得到的边折叠在一起得到的资源分配图和对应的等待图资源分配图和对应的等待图3.5.2 3.5.2 对多体资源类的死锁检测对多体资源类的死锁检测v采用若干随时间变化的数据结构，与银行家算采用若干随时间变化的数据结构，与银行家算法相似法相似 Ava

31、ilableAvailable是一个长度为是一个长度为m m的向量的向量 AllocationAllocation是一个是一个n nm m的矩阵的矩阵 RequestRequest是一个是一个n nm m的矩阵，的矩阵，RequestRequesti i, , j j=k k，表示进程，表示进程p pi i正申请正申请k k个个r rj j类资源类资源 仍把矩阵仍把矩阵AllocationAllocation和和RequestRequest的行作为向量的行作为向量对待，并分别表示为对待，并分别表示为AllocationAllocationi i和和RequestRequesti i 对多体资源

32、类的死锁检测对多体资源类的死锁检测检测算法：检测算法： 简单地调查尚待完成的各个进程所有可能的分配序列简单地调查尚待完成的各个进程所有可能的分配序列 令令WorkWork和和FinishFinish分别表示长度为分别表示长度为m m和和n n的向量，初始化的向量，初始化 Work=AvailableWork=Available；对于；对于i i=1, 2, =1, 2, n n 如果如果AllocationAllocationi i00，则，则FinishFinishi i=false=false；否则；否则FinishFinishi i=true=true。 寻找一个下标寻找一个下标i i，

33、它应满足条件：，它应满足条件： FinishFinishi i=false=false且且RequestRequesti iWorkWork 若找不到这样的若找不到这样的i i，则转到。，则转到。 修改数据值：修改数据值： Work=Work+AllocationWork=Work+Allocationi i Finish Finishi i=true=true 转向。转向。 若存在某些若存在某些i i（11i in n），），FinishFinishi i=false=false，则系统处于死，则系统处于死锁状态。此外，若锁状态。此外，若FinishFinishi i=false=false

34、，则进程，则进程p pi i处于死锁环中。处于死锁环中。 对多体资源类的死锁检测对多体资源类的死锁检测v设系统中有设系统中有5 5个进程个进程p p1 1, , p p2 2, , p p3 3, , p p4 4和和p p5 5，有，有3 3类资源类资源R R1 1, , R R2 2和和R R3 3 ，每类资源的个数分别为，每类资源的个数分别为7, 2, 67, 2, 6。 AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p1010000000p2200202p3303000p4211100p5002002资源情况资源情况进程进程假定，进程假定，进程

35、p p3 3现在申请一个单位的现在申请一个单位的R R3 3资源资源AllocationRequestAvailableR1R2R3R1R2R3R1R2R3p1010000000p2200202000p3303001p4211100p5002002 由于对所有由于对所有i i=1, 2,=1, 2, 5, 5，AllocationAllocationi i00，所以，所以FinishFinishi i=false=false。 资源情况资源情况进程进程3.5.3 3.5.3 从死锁中恢复从死锁中恢复v通过抢占资源实现恢复通过抢占资源实现恢复v通过回退执行实现恢复通过回退执行实现恢复 发生死锁的某个进程或某些进程回退到它发生死锁的某个进程或某些进程回退到它取得另外某个资源之前的一个检查点取得另外某个资源之前的一个检查点 系统中应保存一系列检查点的文件系统中应保存一系列检查点的文件 要确定这个进程后退多远要确定这个进程后退多远 “全体全体”回退方式回退方式v通过杀掉进程实现恢复通过杀掉进程实现恢复 终止所有的死锁进程。终止所有的死锁进程。 一次终止一个进程，直至消除死锁环路。一次终止一个进程，直至消除死锁环路。3.5.4 3.5.4 “饥饿饥饿”状态状态v在某些策略下，系统会出