第四章-死锁及其对策课件

第四章死锁及其对策4.1死锁的基本概念4.2死锁原理及对策4.3鸵鸟算法4.4死锁的检测和恢复4.5死锁预防4.6死锁避免今天日期：9/18/20231第四章死锁及其对策第四章死锁及其对策4.1死锁的基本概念今天日期：8/4.1死锁的基本概念在计算机系统中，产生死锁的直接原因是多个进程的并发执行。多个进程的并发执行改善了系统资源的利用率，提高了系统的处理能力，但由于每个系统资源都由多个进程共享，有些资源本身又要求互斥的使用，所以如果处理不当就可能产生死锁。今天日期：9/18/20232第四章死锁及其对策4.1死锁的基本概念在计算机系统中，产生死锁的直接原因是4.1.1资源依资源的性质：可剥夺和非可剥夺资源

可剥夺资源：处理机和内存

非可剥夺资源：磁带和打印机依资源的使用方式：共享资源和独享资源

共享资源：处理机、内存、磁盘等

独享资源：磁带机、读卡机和打印机等依资源的使用期限：永久资源和临时资源

永久资源：硬资源和可重入的纯代码过程

临时资源：进程同步和通信过程中出现的消息、信号的数据。在进行资源分配时，一定要先认清相应资源的特性，以便选择合适的分配策略，在竞争非剥夺资源和临时性资源时都可能产生死锁。在并发进程的活动中，若选择一种合理的推进顺序就可以避免死锁的发生。今天日期：9/18/20233第四章死锁及其对策4.1.1资源今天日期：8/6/20233第四章死4.1.2死锁的定义死锁是计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争系统资源而出现的一种互相等待的现象。此时，每个进程都“占用”一些其他进程正在等待的资源，而用，每个进程都没有完全得到所有的资源，结果所有这些进程互相等待，谁也无法继续，我们称这些进程是死锁的，相应的计算机系统处于死锁状态。今天日期：9/18/20234第四章死锁及其对策4.1.2死锁的定义今天日期：8/6/20234第四章4.1.3产生死锁的原因系统竞争临界资源。当系统所拥有的某种临界资源个数比各个进程要求该资源的总数要少时，则有可能引起多个并发进程对资源的竞争而产生死锁。进程推进顺序不当，进程运行过程中，由于请示和释放资源的顺序不当，而产生死锁。今天日期：9/18/20235第四章死锁及其对策4.1.3产生死锁的原因今天日期：8/6/20235第四1、竞争临界资源引起的死锁

竞争非剥夺性资源引起的死锁竞争临时性资源引起的死锁竞争同一类资源引起的死锁2、进程推进顺序不当引起的死锁今天日期：9/18/20236第四章死锁及其对策1、竞争临界资源引起的死锁今天日期：8/6/20236第四章0G1G2G3A1B1C1D1P1进展P2进展A2B2C2D2占用R2占用R21DN2占用R1占用R23占用R1占用R1R2(读卡机)R1（打印机）今天日期：9/18/20237第四章死锁及其对策0G1G2G3A1B1C1D1P1进展P2进展A2B2C2D4.2死锁原理及对策4.2.1死锁原理及产生死锁的必要条件

死锁是与时间有关的一种现象，它涉及到多进程的并发，并发进程对一些特殊资源的共享，以及具体进行并发进程资源调度的时机等。综上所述，产生死锁的四个必要条件如下：互斥条件、不可剥夺条件、部分分配条件、环路等待条件今天日期：9/18/20238第四章死锁及其对策4.2死锁原理及对策4.2.1死锁原理及产生死锁的必要4.2.2死锁的描述1、资源分配图P2P1R1R2今天日期：9/18/20239第四章死锁及其对策4.2.2死锁的描述P2P1R1R2今天日期：8/6/22、死锁举例竞争非剥夺性资源引起的死锁竞争临时性资源引起的死锁竞争同一类资源引起的死锁R1P1R2P2S1P1S3P3P2S2P1P2P3今天日期：9/18/202310第四章死锁及其对策2、死锁举例竞争非剥夺性资源引起的死锁竞争临时性资源引起的死4.2.3解决死锁的方法1.预防死锁：为了使系统不发生死锁现象，在系统设计初期即选择一些限制条件，来破坏产生死锁的四个必要条件之一或其中几个。这样，系统中就不会出现死锁现象。2.避免死锁：一方面预防死锁的方法会降低系统资源利用率；另一方面死锁的必要条件在存在未必就一定会使系统发生死锁。因此为提高系统资源的利用率，避免死锁并不严格限制死锁必要条件的存在，而是在资源的动态分配过程中，使用某种方法去防止系统进入不安全状态，从而避免死锁的最终出现。今天日期：9/18/202311第四章死锁及其对策4.2.3解决死锁的方法今天日期：8/6/202311第3.检测和解除死锁：在一些相对简单的系统中，为节省预防和避免死锁而增加的系统开销，又因为死锁产生的概率总是比较小的，所以系统中允许出现死锁状态。在这种系统中，专门设置了一个检测机构，可以随时检测出死锁的发生，并能确定与死锁有关的进程和资源，然后采用适当的方法解除系统中的死锁状态。常用的方法有：一是强制性的撤销一些死锁进程，并剥夺它们的资源给其余进程；一是使用一个有效的挂起和解除挂起机构来挂起一些进程，以便从被挂起的进程中剥夺一些资源用来解除死锁。今天日期：9/18/202312第四章死锁及其对策3.检测和解除死锁：在一些相对简单的系统中，为节省预防和避免4.4死锁的检测与恢复检测系统中是否存在死锁产生的必要条件：环路等待4.4.1利用资源分配图描述系统状态1、死锁状态的推断思想封锁进程：是指某个进程由于请求了超过系统中现有的未分配资源数目的资源，而被系统封锁的进程。非封锁进程：没有被系统封锁的进程今天日期：9/18/202313第四章死锁及其对策4.4死锁的检测与恢复检测系统中是否存在死锁产生的必要条2、资源分配图的化简

假设某个资源分配图中存在一个进程Pi，此刻Pi是非封锁进程，那么可对此资源分配图作以下化简：当Pi有请求边时，首先将其请求边变成分配边，即满足Pi进程的相应资源请求，而一旦Pi进程的所有资源请求都得到满足，Pi进程就能在有限时间内运行结束，并释放它所占用的所有资源。所以此时Pi只有分配边，可以将所有这些分配边删去。

总之，对非封锁进程Pi的化简即删除资源分配图中与Pi连接的所有有向边，使Pi成为孤立结点。P2P1R1R2P2P1R1R2P2P1R1R2(a)(b)(c)今天日期：9/18/202314第四章死锁及其对策2、资源分配图的化简总之，对非封锁进程Pi的化简即删除假如一个资源分配图可以被其上的所有进程所化简，则称该图为完全可化简的。反之，若一个资源分配图不能被其上的任一进程化简，则称其为不可化简的。若某个资源分配图只能被其上的一些进程所化简，则该图为非完全可化简的。P2P1R1R2图完全可化简的资源分配图P2P1R1R2图不可化简的资源分配图今天日期：9/18/202315第四章死锁及其对策假如一个资源分配图可以被其上的所有进程所化简，则称该图为完全3、死锁定理：当一个资源分配图是完全可化简时，该资源分配图能被其上所有的进程所化简。也就是此时系统中存在一个进程序列，按此安全序列的顺序运行，可使每个进程都顺利完成，所以此时系统处于安全状态，即系统不会发生死锁。反之当某资源分配图是非完全可化简的时候，说明该资源分配图不能被中的一些进程所化简。也就是此刻系统中出现了一些互相等待的封锁进程，系统中不存在一个进程的安全序列。这些互相等待的封锁进程永远无法运行到终点，所以此时系统处于死锁状态。资源分配图中不能化简的进程即为死锁进程。死锁定理：系统中某个时刻S为死锁状态的充分必要条件是，S时刻系统的资源分配图是非完全可化简的。今天日期：9/18/202316第四章死锁及其对策3、死锁定理：当一个资源分配图是完全可化简时，该资源分配图能4.4.2死锁检测中的数据结构假设系统中的N个进程P1,P2,…,Pn，有M种资源，R1,R2,…,Rm，则请求矩阵和分配矩阵都是一个N×M的二维数组：(1)请求矩阵Re：是一个N×M的二维数组，每行代表一个进程当前对各类资源的请求数目。若Re(i,j)=k,则代表第i个进程Pi请求了Rj类资源k个分配单位。(2)分配矩阵Al：是一个N×M的二维数组，代表某个时刻系统中资源的分配情况。若Al(i,j)=k,则代表第i个进程Pi已分配到了Rj类资源k个分配单位。P1PnP2R1R2Rm今天日期：9/18/202317第四章死锁及其对策4.4.2死锁检测中的数据结构(3)可利用资源向量Av，是一个长度为M的一维数组，表示系统中各类资源的可利用数目。

(4)工作向量Work：是一个长度为M的一维数组，动态的反映系统中可让进程运行的各类资源的数目。(5)进程向量L：是一个集合，所有已运行结束的进程都送入L中，若最后L中包括了所有的N个进程，则说明系统处于安全状态。今天日期：9/18/202318第四章死锁及其对策(3)可利用资源向量Av，是一个长度为M的一维数组，表示4.4.3死锁检测算法1、在某个时刻T，j从1到M执行Work(j)=Av(j)。2、检查Al矩阵和Re矩阵，是否存在某个i(i从1到M)使Al矩阵第i行中所有的Al(i,j)和Re矩阵第i行中所有的Re(i,j)均为零。若存在这个i说明在资源分配图中Pi进程已成为孤立结点，将Pi进程送入进程向量L中。3、在系统中除已送入L之外的所有进程中逐个寻找，若某个i使Re(i,j)<=Work(j)，(j的取值从1到M)，则执行：1)j从1到M，Work(j)=Work(j)+Al(i,j)2)j从1到M，令所有的Al(i,j)=0，所有的Re(i,j)=03)将当前的这个进程也送入进程向量L中这样反复执行，直到所有L以外的进程中再没有满足上述条件为止。4、检查L向量，若N个进程都在L中，说明系统中不会发生死锁，反之，系统中存在死锁，那些没能进入L向量的进程均为死锁进程。今天日期：9/18/202319第四章死锁及其对策4.4.3死锁检测算法今天日期：8/6/202319第四章由于当系统中有了新的请求，而这种请求又不能立即满足时才可能发生死锁。所以在一个非死锁状态的前提下，要判断下一个状态是否为死锁，只需要在某个进程执行新的进程请求而又不能立即满足时，进行死锁检测，由于死锁检测算法执行时间长、系统开销大，可以在较长时间间隔后，执行一次检测算法。今天日期：9/18/202320第四章死锁及其对策由于当系统中有了新的请求，而这种请求又不能立即满足时才可4.4.4死锁的恢复强制性地从系统中撤销一些死锁进程，并剥夺它们的资源给其余进程。使用一个有效的挂起和解除机构来挂起一些进程，以便从被挂起的进程中剥夺一些资源用来解除死锁1、撤销进程：为了保证系统所受到的影响最小，可以逐个撤销进程，直到死锁不复存在为止。一般依次选择撤销代价最小的进程。撤销代价包括：进程的优先数、运行代价（从重新启动该进程并运行到此撤销时刻所需要的时间）、该进程对应作业的外部代价。2、挂起进程今天日期：9/18/202321第四章死锁及其对策4.4.4死锁的恢复今天日期：8/6/202321第四章4.5死锁的预防4.5.1打破“不剥夺”条件强迫那些请求新资源而没有立即得到满足的进程释放它已保持的其它资源，即一个进程已占用的资源在运行过程中可能要暂时释放。实现复杂，只适用于CPU和内存。4.5.2打破“部分分配”条件对某进程所要求的资源一次性地分配完毕，又称预先静态分配法。4.5.3打破“环路等待”条件在资源的分配过程中，对资源的请求作出某种限制，使环路不可能出现。今天日期：9/18/202322第四章死锁及其对策4.5死锁的预防4.5.1打破“不剥夺”条件今天日期：具体的方法是：为系统中每种资源规定一个唯一的序号，例如，输入机为1，打印机为2，穿孔机为3，磁带机为4，磁盘机为5等，而且要求每个进程都要严格按照递增的顺序请求资源。若能认真的安排资源序号，将各作业经常使用的、比较普通的资源安排成低序号，不常使用的资源、比较繁重的资源安排成高序号，便能提高资源的利用率。但在各资源的序号安排好后，不能经常变动。今天日期：9/18/202323第四章死锁及其对策具体的方法是：为系统中每种资源规定一个唯一的序号，例如，输入4.6死锁避免4.6.1系统状态的安全性1、安全状态：是指系统能按照某种顺序为每个进程分配所需的资源，使每个进程都能顺利完成。当且仅当系统中存在此安全序列时，系统处于安全状态。假设系统中有3个进程，10个可供分配的资源单位进程已分配资源还需申请的资源P144P222P3272、不安全状态：某个时刻系统中不存在一个安全序列，能使所有的进程都顺利完成。不安全状态不是死锁状态，进入不安全状态的进程有可能进入死锁。今天日期：9/18/202324第四章死锁及其对策4.6死锁避免4.6.1系统状态的安全性假设系统中有

银行家算法是最有代表性的避免死锁算法，由Dijkstrn提出。1、银行家算法中的数据结构(1)可利用资源向量Av

它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。例如：Av数组4.6.2银行家算法

前提条件：假设分配资源的单位是固定的，请求资源的进程数也固定不变，而且每个进程必须先告诉系统对某类资源的最大需求量，当某个进程要求的资源数量小于系统所拥有的该类资源的最大量时，系统会在有限的时间内满足进程的要求。今天日期：9/18/202325第四章死锁及其对策银行家算法是最有代表性的避免死锁算法，由Dijkstrn(2)最大需求矩阵Max

n×m矩阵，表示n个进程对m类资源的最大需求。例如：假设n=5,m=3Max矩阵为：今天日期：9/18/202326第四章死锁及其对策(2)最大需求矩阵Maxn×m矩阵，表示n个进程对m类(3)分配矩阵Al

n×m矩阵，表示每个进程已经分配到的资源的数目。例如：设n=5,m=3Al矩阵为：今天日期：9/18/202327第四章死锁及其对策(3)分配矩阵Aln×m矩阵，表示每个进程已经分配到(4)需求矩阵Need

n×m矩阵，表示每个进程还需要各类资源的数目。例如：n=5,m=3Need矩阵为：今天日期：9/18/202328第四章死锁及其对策(4)需求矩阵Needn×m矩阵，表示每个进程还需要2.银行家算法描述当进程Pi提出资源申请时，系统执行下列步骤：所有Re(i,j)<=Need(i,j)？(j=1,2,…,m)所有Re(i,j)<=Av(j)？(j=1,2,…,m)Av(j)=Av(j)-Re(i,j)Al(i,j)=Al(i,j)+Re(i,j)Need(i,j)=Need(i,j)-Re(i,j)(j=1,2,…,m)Av(j)=Av(j)+Re(i,j)Al(i,j)=Al(i,j)-Re(i,j)Need(i,j)=Need(i,j)+Re(i,j)(j=1,2,…,m)出错处理系统是否处于安全状态？断定分配可以进行否否是是是否结束Pi必须等待执行安全性算法恢复分配前资源状态Re：请求矩阵Need：需求矩阵Av：可利用资源向量Al：分配矩阵Max：最大需求矩阵今天日期：9/18/202329第四章死锁及其对策2.银行家算法描述当进程Pi提出资源申请时，系统执行下列步骤3.安全性算法Work(j)=Av(i,j)(j=1,2,…,m)Finish(i)=False(i=1,2,…,n)找能满足Finish(i)=False(i=1,2,…,n)且Need(i,j)<=Work(j)(j=1,2,…,m)的进程PiWork(j)=Work(j)+Al(i,j)(j=1,2,…,m)令Finish(i)=True说明系统处于不安全状态即、至少有一个Pi，使Finish(i)=False所有的Finish(i)=True？(i=1,2,…,n)则系统为安全状态安全性算法结束找到是找不到否今天日期：9/18/202330第四章死锁及其对策3.安全性算法Work(j)=Av(i,j)Finish(4.6.3银行家算法举例

设系统有五个进程和三类资源，每类资源分别有10、5、7。在T1时刻资源分配情况如下图：Al矩阵：Need矩阵：Av数组：今天日期：9/18/202331第四章死锁及其对策4.6.3银行家算法举例设系统有五个进程和三类资源１．假设T1时刻初始状态为Work(j)=[332]Finish(i)=[FFFFF]的话。首先，判断它是否处于安全状态：①由于i=2时，存在一个P2，使Finish(2)=F，且故由Work(j)=Work(j)+Al(2,j)得到Work(J)=[532]Finish(i)=[FTFFF]②由于i=4时，存在一个P4，使Finish(4)=F，且故由Work(j)=Work(j)+Al(4,j)得到Work(J)=[743]Finish(i)=[FTFTF]③由于i=5时，存在一个P5，使Finish(5)=F，且故由Work(j)=Work(j)+Al(5,j)得到Work(J)=[745]Finish(i)=[FTFT

T]<=Work(j)=[332]<=Work(j)=[532]<=Work(j)=[743]Need=今天日期：9/18/202332第四章死锁及其对策１．假设T1时刻初始状态为Work(j)=[33④由于i=3时，存在一个P3，使Finish(3)=F，且故由Work(j)=Work(j)+Al(3,j)得到Work(J)=[1047]Finish(i)=[FT

T

T

T]⑤由于i=1时，存在一个P1，使Finish(1)=F，且故由Work(j)=Work(j)+Al(1,j)得到Work(J)=[1057]Finish(i)=[T

T

T

T

T]

此时、安全标志为真，存在一个安全序列（P2,P4,P5,P3,P1）,所以系统是安全的。<=Work(j)=[745]<=Work(j)=[1047]今天日期：9/18/202333第四章死锁及其对策<=Work(j)=[745]<=Work(j)=[２.假设T2时刻P2请求资源，即Re(2,j)=[102]的话，使用银行家算法来判断，此时i=2，Need(2,j)=[122]AlR1R2R3NeedR1R2R3AvR1R2R3ReR1R2R3P1P2P3P4P5010

200302211002743

122600011431

332

…

102………①满足Re(j)<=Need(2,j)②满足Re(j)<=Av(j)AlR1R2R3NeedR1R2R3AvR1R2R3ReR1R2R3P1P2P3P4P5010

302302211002743

020600011431

230

…

102………③执行Av(j)=Av(j)-Re(2,j)Al(2,j)=Al(2,j)+Re(2,j)Need(2,j)=Need(2,j)-Re(2,j)(j=1,2,…,m)今天日期：9/18/202334第四章死锁及其对策２.假设T2时刻P2请求资源，即Re(2,j)=[102然后，对T2时刻进行安全性检查，方法同T1时刻。检查结果，可以找到一个安全序列（P2,P4,P5,P1,P3)。可以得出P2的请求不会导致系统进入不了安全状态。所以可以将P2申请的资料分配给他。今天日期：9/18/202335第四章死锁及其对策然后，对T2时刻进行安全性检查，方法同T1时刻。检查结果，可3.假设T3时刻P5请求资源，即Re(5,j)=[330]的话，使用银行家算法来判断，此时i=5，Need(5,j)=[431]AlR1R2R3NeedR1R2R3AvR1R2R3ReR1R2R3P1P2P3P4P5010302302211002743020600011

431

230

…………330①满足Re(j)<=Need(5,j)②Re(j)<=Av(j)不满足所以P5必须等待今天日期：9/18/202336第四章死锁及其对策3.假设T3时刻P5请求资源，即Re(5,j)=[3304.假设T4时刻P1请求资源，即Re(1,j)=[020]的话，使用银行家算法来判断，此时i=1，Need(1,j)=[743]AlR1R2R3NeedR1R2R3AvR1R2R3ReR1R2R3P1P2P3P4P5

010

302302211002

743

020600011431

230

020…………①满足Re(j)<=Need(1,j)②满足Re(j)<=Av(j)AlR1R2R3NeedR1R2R3AvR1R2R3ReR1R2R3P1P2P3P4P5

030302302211002