操作系统5-死锁.pptx

12024/8/9周五第第第第3 3章章章章 进程管理进程管理进程管理进程管理 3.1 进程的引入进程的引入 3.2 进程的结构进程的结构 3.3 进程控制进程控制 3.4 进程的同步与互斥进程的同步与互斥 3.5 进程间通信进程间通信 3.6 进程调度进程调度 3.7 死锁死锁 3.8 线程线程22024/8/9周五死锁的概念死锁的概念死锁的概念死锁的概念死锁举例死锁举例产生死锁的原因产生死锁的原因 产生死锁的必要条件产生死锁的必要条件 处理死锁的基本方法处理死锁的基本方法 32024/8/9周五死锁现象死锁现象死锁现象死锁现象42024/8/9周五死锁举例死锁举例死锁举例死锁举例 【例例 】设设系系统统有有打打印印机机、扫扫描描仪仪各各一一台台，被被进进程程1 1和和P2P2共共享享。两两个个进进程程并并发发执执行行，按按下下列列次次序请求和释放资源：序请求和释放资源：P1：申请打印机申请打印机申请扫描仪申请扫描仪使用使用释放打印机释放打印机释放扫描仪释放扫描仪P2：申请扫描仪申请扫描仪申请打印机申请打印机使用使用释放打印机释放打印机释放扫描仪释放扫描仪52024/8/9周五死锁定义死锁定义死锁定义死锁定义死锁死锁是指是指多个多个进程在运行过程中因争夺资源而造成的一种僵持进程在运行过程中因争夺资源而造成的一种僵持局面。即，一组进程中，每个进程都无限等待被该组进程局面。即，一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到该资源，这中另一进程所占有的资源，因而永远无法得到该资源，这种现象称为种现象称为死锁死锁，这一组进程就称为死锁进程。，这一组进程就称为死锁进程。关于死锁的一些结论关于死锁的一些结论参与死锁的进程最少是两个（两个以上进程才会出现死锁）参与死锁的进程最少是两个（两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。如果没有外力作用，死锁是无法解除的。如果没有外力作用，死锁是无法解除的。62024/8/9周五产生死锁的原因产生死锁的原因产生死锁的原因产生死锁的原因竞争资源（系统内的资源数量不足）竞争资源（系统内的资源数量不足）进程推进的顺序不当进程推进的顺序不当进程推进顺序合法进程推进顺序合法 不会造成死锁的进程推进顺序不会造成死锁的进程推进顺序进程推进顺序非法进程推进顺序非法 会造成死锁的进程推进顺序会造成死锁的进程推进顺序72024/8/9周五产生死锁的必要条件产生死锁的必要条件产生死锁的必要条件产生死锁的必要条件互斥条件互斥条件（资源本身的性质）（资源本身的性质）涉涉及及的的资资源源是是非非共共享享的的，必必须须存存在在需需要要互互斥斥使使用用的资源。的资源。请求和保持条件请求和保持条件（进程的行为）（进程的行为）进程在等待一新资源时继续占有已分配的资源。进程在等待一新资源时继续占有已分配的资源。不剥夺条件不剥夺条件（系统规定）（系统规定）不能强行剥夺进程拥有的资源。不能强行剥夺进程拥有的资源。环路等待条件环路等待条件（进程（进程/资源之间的关系）资源之间的关系）存在一个进程等待队列存在一个进程等待队列 P P1 1,P,P2 2,Pn,Pn,其中其中P P1 1等待等待P P2 2占有的资源，占有的资源，P P2 2等待等待P P3 3占有的资源，占有的资源，PnPn等待等待P P1 1占有的资源，形成一个进程等待环路。占有的资源，形成一个进程等待环路。82024/8/9周五处理死锁的基本方法处理死锁的基本方法处理死锁的基本方法处理死锁的基本方法预防死锁预防死锁避免死锁避免死锁检测死锁检测死锁解除死锁解除死锁92024/8/9周五预防死锁预防死锁预防死锁预防死锁 通通过过设设置置某某些些限限制制条条件件，去去破破坏坏死死锁锁四四个必要条件中的一个或多个，来防止死锁。个必要条件中的一个或多个，来防止死锁。优点优点较易实现较易实现缺点缺点由于所施加的限制往往太严格，可能导致系统资由于所施加的限制往往太严格，可能导致系统资源利用率和系统吞吐量的降低。源利用率和系统吞吐量的降低。102024/8/9周五避免死锁避免死锁避免死锁避免死锁 不不事事先先采采取取限限制制去去破破坏坏产产生生死死锁锁的的条条件件，而而是是在在资资源源的的动动态态分分配配过过程程中中，用用某某种种方方法法去去防防止止系系统统进进入入不不安安全全状状态态，从从而而避免死锁的发生。避免死锁的发生。优点优点只需要较弱的限制条件，可获得较高的资源利只需要较弱的限制条件，可获得较高的资源利用率和系统吞吐量用率和系统吞吐量。缺点缺点实现较难实现较难112024/8/9周五检测死锁检测死锁检测死锁检测死锁 事事先先并并不不采采取取任任何何限限制制，也也不不检检查查系系统统是是否否进进入入不不安安全全区区，允允许许死死锁锁发发生生，但但可可通通过过检检测测机机构构及及时时检检测测出出死死锁锁的的发发生生，并并精精确确确确定定与与死锁有关的进程和资源。死锁有关的进程和资源。122024/8/9周五解除死锁解除死锁解除死锁解除死锁 与与检检测测死死锁锁相相配配套套，用用于于将将进进程程从死锁状态解脱出来。从死锁状态解脱出来。优点优点可获得较高的资源利用率和系统吞吐量可获得较高的资源利用率和系统吞吐量。缺点缺点实现难度大实现难度大 132024/8/9周五死锁的预防死锁的预防死锁的预防死锁的预防 死锁的预防一般是从破坏导致发生死锁的必要条件着手，死锁的预防一般是从破坏导致发生死锁的必要条件着手，只要能使四个必要条件其中的任何一个不成立，就可防止死只要能使四个必要条件其中的任何一个不成立，就可防止死锁。锁。破坏互斥条件：破坏互斥条件：改变把独享资源变为共享资源；改变把独享资源变为共享资源；破坏请求和保持条件：破坏请求和保持条件：采用静态分配策略；采用静态分配策略；破坏不可剥夺条件：破坏不可剥夺条件：主动释放资源策略和强行剥夺策略；主动释放资源策略和强行剥夺策略；破坏循环等待条件：破坏循环等待条件：采用资源的有序申请策略；采用资源的有序申请策略；142024/8/9周五破坏破坏破坏破坏“请求和保持请求和保持请求和保持请求和保持”条件条件条件条件采用采用静态分配资源静态分配资源策略策略 要求每个进程在运行前必须一次性申请它所要求的要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。一次性分配。优点优点：简单、安全：简单、安全缺点：缺点：资源利用率低；资源利用率低；使进程延迟运行使进程延迟运行 152024/8/9周五破坏破坏破坏破坏“不可剥夺不可剥夺不可剥夺不可剥夺”条件条件条件条件破坏不可剥夺条件破坏不可剥夺条件 一一个个已已拥拥有有资资源源的的进进程程，若若它它再再提提出出新新资资源源要要求求而而不不能能立立即即得得到到满满足足时时，它它必必须须释释放放已已经经拥拥有有的的所所有有资资源。以后需要时再重新申请。源。以后需要时再重新申请。缺点缺点这种方法比较复杂且系统开销大。这种方法比较复杂且系统开销大。在剥夺资源时，需要保存中间信息，但也会使进程在剥夺资源时，需要保存中间信息，但也会使进程前后两次运行的信息不连续。前后两次运行的信息不连续。所以，临界资源不宜剥夺。所以，临界资源不宜剥夺。162024/8/9周五破坏破坏破坏破坏“循环等待循环等待循环等待循环等待”条件条件条件条件采用采用资源有序分配策略资源有序分配策略 事事先先把把系系统统中中的的所所有有资资源源按按大大多多数数进进程程使使用用资资源源的的顺顺序序由由小小到到大大进进行行编编号号，每每个个进进程程只只能能按按资资源源编编号号递递增增的的顺顺序序申申请资源。请资源。例子例子 多多个个进进程程之之间间只只可可能能存存在在占占据据较较低低序序号号资资源源的的进进程程等等待待占占据据较较高高序序号号资资源源的的进进程程释释放放资资源源的的情情况况，但但不不可可能能存存在在反反向的等待，因此，它们之间绝对不会形成向的等待，因此，它们之间绝对不会形成循环等待环路循环等待环路 缺点缺点资源的编号不容易合理化资源的编号不容易合理化限制了用户简单自主的编程限制了用户简单自主的编程当当系系统统增增加加新新设设备备类类型型时时，要要重重新新对对系系统统资资源源进进行行合合理理编编号号172024/8/9周五资源按序分配示例资源按序分配示例资源按序分配示例资源按序分配示例 系系统统中中有有下下列列 设设备备：输输入入机机（1），打打印印机机（2），穿穿孔孔机机（3），磁磁带带机机（4），磁磁盘盘（5）。有有一一进进程程要要先先后后使使用用输输入入机机、磁磁盘盘、打打印印机机，则则它它申申请请设设备备时时要要按按输入机、打印机、磁盘的顺序申请。输入机、打印机、磁盘的顺序申请。例如：例如：1 1，2 2，3 3，5 5P1：申请申请1申请申请5申请申请21 ，2，5182024/8/9周五死锁的避免死锁的避免死锁的避免死锁的避免避免死锁的基本思想避免死锁的基本思想 允许进程动态申请资源，但在每次分配资源时，都允许进程动态申请资源，但在每次分配资源时，都要通过判断要通过判断系统状态系统状态来决定是否分配资源，若分配后系来决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。统可能发生死锁，则不予分配，否则予以分配。系统状态系统状态安全状态安全状态 在某一时刻，如果系统能按某种顺序（如在某一时刻，如果系统能按某种顺序（如P1，P2，,Pn,称称为为安全序列安全序列）为每个进程分配其所需的资源，直至所有进程都）为每个进程分配其所需的资源，直至所有进程都能运行完成，称系统处于能运行完成，称系统处于安全状态安全状态。不安全状态不安全状态 若不存在这样一个安全序列称系统处于若不存在这样一个安全序列称系统处于不安全状态不安全状态。192024/8/9周五安全序列安全序列安全序列安全序列 在某在某一时刻，存在一个进程序列一时刻，存在一个进程序列P1，Pn，对，对每个进程每个进程Pi(1in），如果满足它以后尚需要的资源量），如果满足它以后尚需要的资源量不超过系统当前剩余资源量与所有进程不超过系统当前剩余资源量与所有进程Pj(j i)当前占当前占有资源量之和，即有资源量之和，即Needi则则 Available+Allicationj(1 j i-1)，则称，则称P1，Pn为安全序列。为安全序列。安全状态一定是安全状态一定是 没有死锁发生的没有死锁发生的不安全状态一定不安全状态一定 导致死锁导致死锁?202024/8/9周五安全状态示例安全状态示例安全状态示例安全状态示例有三个进程有三个进程P1,P2,P3，有，有12台磁带机台磁带机P1共要求共要求10台台P2共要求共要求4台台P3共要求共要求9台台在在T0时刻，时刻，P1,P2,P3分别获得分别获得5、2、2台，尚有台，尚有3台空闲台空闲分析分析经分析，在经分析，在T0时刻，系统是安全的。因为存在一个安全时刻，系统是安全的。因为存在一个安全序列序列P2(23)、P1(5=3+2)、P3(7=3+2+2)。见下图。见下图进程进程最大需求最大需求已分配已分配还需还需可用可用P1105P242P392进程进程最大需求最大需求已分配已分配还需还需可用可用P11055 3P2422P3927212024/8/9周五由安全状态向不安全状态的转换由安全状态向不安全状态的转换由安全状态向不安全状态的转换由安全状态向不安全状态的转换如果不按安全序列分配资源，则系统可能会由安全如果不按安全序列分配资源，则系统可能会由安全状态进入不安全状态。如在状态进入不安全状态。如在T0以后，以后，P3要求要求1台磁带机台磁带机，若系统分给它一台，则系统进入不安全状态。若系统分给它一台，则系统进入不安全状态。因为其余因为其余2台分给台分给P2，P2完成后，只能释放完成后，只能释放4台，这台，这既不能满足既不能满足P1（5台），也不能满足台），也不能满足P3（6台）。将导致台）。将导致死锁。可见当死锁。可见当P3申请资源时，尽管系统中有资源也不能申请资源时，尽管系统中有资源也不能分给它。分给它。系统进入不安全状态：系统进入不安全状态：进程进程最大需求最大需求已分配已分配还需还需可用可用P11055（3）2P2422P39（2）3（7）6222024/8/9周五利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁利用银行家算法避免死锁银行家算法银行家算法银行家拥有一笔周转资金银行家拥有一笔周转资金客客户户要要求求分分期期贷贷款款，如如果果客客户户能能够够得得到到各各期期贷贷款款，就一定能够归还贷款，否则就一定不能归还贷款就一定能够归还贷款，否则就一定不能归还贷款银行家应谨慎的贷款，防止出现坏帐银行家应谨慎的贷款，防止出现坏帐用银行家算法避免死锁用银行家算法避免死锁操作系统（银行家）操作系统（银行家）操作系统管理的资源操作系统管理的资源(周转资金周转资金)进程（要求贷款的客户）进程（要求贷款的客户）最有代表性的避免死锁算法，由最有代表性的避免死锁算法，由Dijkstra提出。提出。232024/8/9周五 银行家算法的数据结构银行家算法的数据结构银行家算法的数据结构银行家算法的数据结构(1)(1)(1)(1)可利用资源向量可利用资源向量Available。它是一个含有它是一个含有m个元素的数组，其中每个元个元素的数组，其中每个元素代表一类可利用资源的数目。素代表一类可利用资源的数目。int Availablem-1;如：如：ABC523242024/8/9周五 银行家算法的数据结构银行家算法的数据结构银行家算法的数据结构银行家算法的数据结构(2)(2)(2)(2)最大需求矩阵最大需求矩阵Max：n*m矩阵，表示矩阵，表示n个进程的个进程的每一个对每一个对m类资源的最大需求。类资源的最大需求。int Maxn-1m-1;ABCP1562P2331P3425P4332252024/8/9周五 银行家算法的数据结构银行家算法的数据结构银行家算法的数据结构银行家算法的数据结构(3)(3)(3)(3)分配矩阵分配矩阵Allocation：n*m矩阵，表示每个进矩阵，表示每个进程已分配的资源数。程已分配的资源数。int Allocationn-1m-1ABCP1212P2121P3222P4132262024/8/9周五 银行家算法的数据结构银行家算法的数据结构银行家算法的数据结构银行家算法的数据结构(4)(4)(4)(4)需求矩阵需求矩阵Need：n*m矩阵，表示每个进程还需矩阵，表示每个进程还需要各类资源数。要各类资源数。int Needn-1m-1ABCP1352P2211P3223P4232272024/8/9周五 银行家算法的数据结构银行家算法的数据结构银行家算法的数据结构银行家算法的数据结构(5)(5)(5)(5)进程申请资源向量进程申请资源向量Request：它是一个含有它是一个含有m个元素的数组，其中每个个元素的数组，其中每个元素代表进程申请资源的数目。元素代表进程申请资源的数目。int Requestm-1;如：如：ABC312282024/8/9周五银行家算法描述银行家算法描述银行家算法描述银行家算法描述 当进程当进程PiPi提出资源申请时，系统执行下列步骤：提出资源申请时，系统执行下列步骤：(1)若若RequestiNeedi,转（转（2）；否则错误返回）；否则错误返回(2)若若RequestiAvailable,转（转（3）；否则进程等待）；否则进程等待(3)假设系统分配了资源，则有：假设系统分配了资源，则有：Available=Available-Requesti;Allocationi=Allocationi+Requesti;Needi=Needi-Requesti(4)执行执行安全性算法安全性算法，若系统新状态是安全的，则分配，若系统新状态是安全的，则分配 完成，若系统新状态是不安全的，则恢复原状态，完成，若系统新状态是不安全的，则恢复原状态，进程等待。进程等待。292024/8/9周五安全性算法安全性算法安全性算法安全性算法定义数据结构定义数据结构int Workm-1;bool Finishn-1;m代表资源的数量，代表资源的数量，n代表进程的数量代表进程的数量安全性算法步骤安全性算法步骤(1)Work=Available;Finishi=false;(2)寻找满足下列条件的寻找满足下列条件的i：a.Finishi=false;b.NeediWork;如果不存在，则转如果不存在，则转(4)(3)Work=Work+Allocationi;Finishi=true;转转(2)(4)若对所有若对所有i,Finishi=true,则系统处于安全状态，否则处于不安全状态则系统处于安全状态，否则处于不安全状态302024/8/9周五银行家算法示例银行家算法示例银行家算法示例银行家算法示例(1)(1)设系统有五个进程设系统有五个进程P0,P1,P2,P3,P4和三类资源和三类资源A,B,C，每类资源分别有每类资源分别有10、5、7，在，在T0时刻资源分配情况如图时刻资源分配情况如图312024/8/9周五银行家算法示例银行家算法示例银行家算法示例银行家算法示例(2)(2)T0时刻可以找到一个安全序列时刻可以找到一个安全序列P1,P3,P4,P2,P0，系统是，系统是安全的：安全的：（T0时刻安全性检查）时刻安全性检查）322024/8/9周五银行家算法示例银行家算法示例银行家算法示例银行家算法示例(3)(3)T0时刻，时刻，P1发出请求发出请求Request(1,0,2)，执行银行家算法执行银行家算法332024/8/9周五银行家算法示例银行家算法示例银行家算法示例银行家算法示例(4)(4)可以找到一个安全序列可以找到一个安全序列p1,p3,p4,p0,p2系统是安全的，系统是安全的，可以将可以将P1的请求分配给它。的请求分配给它。执行安全性算法执行安全性算法342024/8/9周五银行家算法示例银行家算法示例银行家算法示例银行家算法示例(5)(5)P4发出请求发出请求Request(3,3,0),执行银行家算法执行银行家算法 Available=(2,3,0)不能通过算法第不能通过算法第2步（步（RequestiAvailable），），所以所以P4等待等待。352024/8/9周五银行家算法示例银行家算法示例银行家算法示例银行家算法示例(5)(5)P0请求资源请求资源Request（0，2，0），执行银行家算法），执行银行家算法进行安全性检查：进行安全性检查：Available(2,1,0)已不能满足任何进程需已不能满足任何进程需要，所以系统进入不安全状态，要，所以系统进入不安全状态，P0的请求不能分配的请求不能分配362024/8/9周五死锁检测死锁检测 允许死锁发生，操作系统不断监视系统进展情况，允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生判断死锁是否发生;一旦死锁发生则采取专门的措施，一旦死锁发生则采取专门的措施，解除死锁解除死锁并以最小的代价恢复操作系统运行并以最小的代价恢复操作系统运行检测时机检测时机当进程等待时检测死锁当进程等待时检测死锁,其缺点是系统的开销大其缺点是系统的开销大定时检测定时检测系统资源利用率下降时检测死锁系统资源利用率下降时检测死锁死锁的检测和解除死锁的检测和解除死锁的检测和解除死锁的检测和解除372024/8/9周五进程进程进程进程-资源分配图资源分配图资源分配图资源分配图PRAGPRAGPRAGPRAG构成构成二元组二元组G=G=（V V，E E）V V：结点集，分为：结点集，分为P P，R R两部分两部分 P=p1,p2,P=p1,p2,pn,pn R=r1,r2,R=r1,r2,rm,rmE E：边的集合，其元素为有序二元组：边的集合，其元素为有序二元组或或表示法表示法资源类：用方框表示资源类：用方框表示资源实例：用方框中的黑圆点（圈）表示资源实例：用方框中的黑圆点（圈）表示进程：进程：用圆圈中加进程名表示用圆圈中加进程名表示分配边：资源实例分配边：资源实例进程的一条有向边进程的一条有向边请求边：进程请求边：进程资源类的一条有向边资源类的一条有向边382024/8/9周五资源分配图示例资源分配图示例资源分配图示例资源分配图示例392024/8/9周五死锁定理（死锁定理（死锁定理（死锁定理（1 1 1 1）如果进程如果进程-资源分配图中资源分配图中无环路无环路，则此时系统没有发，则此时系统没有发生死锁。生死锁。如果进程如果进程-资源分配图中资源分配图中有环路有环路，且每个资源类中仅，且每个资源类中仅有有一个一个资源，则系统中发生了死锁，此时，环路是系资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程。统发生死锁的充要条件，环路中的进程便为死锁进程。例例如果进程如果进程-资源分配图中资源分配图中有环路有环路，且涉及的资源类中，且涉及的资源类中有有多个多个资源，则环路的存在只是产生死锁的必要条件资源，则环路的存在只是产生死锁的必要条件而不是充分条件。而不是充分条件。例例402024/8/9周五有环有死锁有环有死锁有环有死锁有环有死锁P1P2R1R2412024/8/9周五有环有死锁有环有死锁有环有死锁有环有死锁422024/8/9周五有环无死锁有环无死锁有环无死锁有环无死锁432024/8/9周五死锁定理（死锁定理（死锁定理（死锁定理（2 2 2 2）资源分配图简化资源分配图简化（1 1）找出所有只有分配边的非孤立点进程结点，）找出所有只有分配边的非孤立点进程结点，去掉分配边，将其变为孤立结点去掉分配边，将其变为孤立结点（2 2）找一个非孤立点进程结点）找一个非孤立点进程结点PiPi，PiPi的请求边均的请求边均能立即满足。能立即满足。（3 3）若找到了这样的）若找到了这样的PiPi，则将与，则将与PiPi相连的边全部相连的边全部删去（包括分配边），转（删去（包括分配边），转（2 2）若所有进程结点成为若所有进程结点成为孤立结点孤立结点，称该图是，称该图是可完全可完全简化的简化的，否则称该图是，否则称该图是不可完全简化的不可完全简化的。系统为死锁状态的充分条件是：当且仅当该状态的进系统为死锁状态的充分条件是：当且仅当该状态的进程程-资源分配图是不可完全简化的，该充分条件称为资源分配图是不可完全简化的，该充分条件称为死锁定理死锁定理。442024/8/9周五资源分配图化简实例资源分配图化简实例资源分配图化简实例资源分配图化简实例例例P1P4P3P2P1P4P3P2P1P4P3P2可完全化简图可完全化简图452024/8/9周五资源分配图化简实例资源分配图化简实例资源分配图化简实例资源分配图化简实例例例不可完全化简不可完全化简P1P3P2P1P3P2462024/8/9周五死锁的解除死锁的解除死锁的解除死锁的解除重新启动重新启动 立立即即结结束束所所有有进进程程的的执执行行，并并重重新新启启动动操操作作系系统统。方法简单方法简单,但以前工作全部作废但以前工作全部作废,损失可能很大。损失可能很大。撤消进程撤消进程 撤消陷于死锁的所有进程撤消陷于死锁的所有进程,解除死锁继续运行；逐个解除死锁继续运行；逐个撤销陷于死锁的进程撤销陷于死锁的进程,回收其资源回收其资源,直至死锁解除。直至死锁解除。剥夺资源剥夺资源 剥剥夺夺陷陷于于死死锁锁的的进进程程占占用用的的资资源源，但但并并不不撤撤销销它它,直至死锁解除。直至死锁解除。进程回退进程回退 根据系统保存的根据系统保存的checkpoint,checkpoint,让所有进程回退让所有进程回退,直到直到足以解除死锁。足以解除死锁。