操作系统第3章-5 死锁

12020/2/9第3章进程管理3.1进程的引入3.2进程的结构3.3进程控制3.4进程的同步与互斥3.5进程间通信3.6进程调度3.7死锁3.8线程22020/2/9死锁的概念死锁举例产生死锁的原因产生死锁的必要条件处理死锁的基本方法32020/2/9死锁现象42020/2/9死锁举例【例】设系统有打印机、扫描仪各一台，被进程Ｐ1和P2共享。两个进程并发执行，按下列次序请求和释放资源：P1：…申请打印机申请扫描仪使用释放打印机释放扫描仪…P2：…申请扫描仪申请打印机使用释放打印机释放扫描仪…52020/2/9死锁定义死锁是指多个进程在运行过程中因争夺资源而造成的一种僵持局面。即，一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到该资源，这种现象称为死锁，这一组进程就称为死锁进程。关于死锁的一些结论参与死锁的进程最少是两个（两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。如果没有外力作用，死锁是无法解除的。62020/2/9产生死锁的原因竞争资源（系统内的资源数量不足）进程推进的顺序不当进程推进顺序合法不会造成死锁的进程推进顺序进程推进顺序非法会造成死锁的进程推进顺序72020/2/9产生死锁的必要条件互斥条件（资源本身的性质）涉及的资源是非共享的，必须存在需要互斥使用的资源。请求和保持条件（进程的行为）进程在等待一新资源时继续占有已分配的资源。不剥夺条件（系统规定）不能强行剥夺进程拥有的资源。环路等待条件（进程/资源之间的关系）存在一个进程等待队列{P1,P2,…,Pn},其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路。82020/2/9处理死锁的基本方法预防死锁避免死锁检测死锁解除死锁92020/2/9预防死锁通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。优点较易实现缺点由于所施加的限制往往太严格，可能导致系统资源利用率和系统吞吐量的降低。102020/2/9避免死锁不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。优点只需要较弱的限制条件，可获得较高的资源利用率和系统吞吐量。缺点实现较难112020/2/9检测死锁事先并不采取任何限制，也不检查系统是否进入不安全区，允许死锁发生，但可通过检测机构及时检测出死锁的发生，并精确确定与死锁有关的进程和资源。122020/2/9解除死锁与检测死锁相配套，用于将进程从死锁状态解脱出来。优点可获得较高的资源利用率和系统吞吐量。缺点实现难度大132020/2/9死锁的预防死锁的预防一般是从破坏导致发生死锁的必要条件着手，只要能使四个必要条件其中的任何一个不成立，就可防止死锁。●破坏互斥条件：改变把独享资源变为共享资源；●破坏请求和保持条件：采用静态分配策略；●破坏不可剥夺条件：主动释放资源策略和强行剥夺策略；●破坏循环等待条件：采用资源的有序申请策略；142020/2/9破坏“请求和保持”条件采用静态分配资源策略要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。优点：简单、安全缺点：①资源利用率低；②使进程延迟运行152020/2/9破坏“不可剥夺”条件破坏不可剥夺条件一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，它必须释放已经拥有的所有资源。以后需要时再重新申请。缺点这种方法比较复杂且系统开销大。在剥夺资源时，需要保存中间信息，但也会使进程前后两次运行的信息不连续。所以，临界资源不宜剥夺。162020/2/9破坏“循环等待”条件采用资源有序分配策略事先把系统中的所有资源按大多数进程使用资源的顺序由小到大进行编号，每个进程只能按资源编号递增的顺序申请资源。例子多个进程之间只可能存在占据较低序号资源的进程等待占据较高序号资源的进程释放资源的情况，但不可能存在反向的等待，因此，它们之间绝对不会形成循环等待环路缺点资源的编号不容易合理化限制了用户简单自主的编程当系统增加新设备类型时，要重新对系统资源进行合理编号172020/2/9资源按序分配示例系统中有下列设备：输入机（1），打印机（2），穿孔机（3），磁带机（4），磁盘（5）。有一进程要先后使用输入机、磁盘、打印机，则它申请设备时要按输入机、打印机、磁盘的顺序申请。例如：1，2，3，…，5P1：申请1申请5申请2…1，2，5182020/2/9死锁的避免避免死锁的基本思想允许进程动态申请资源，但在每次分配资源时，都要通过判断系统状态来决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。系统状态安全状态在某一时刻，如果系统能按某种顺序（如P1，P2，…,Pn,称为安全序列）为每个进程分配其所需的资源，直至所有进程都能运行完成，称系统处于安全状态。不安全状态若不存在这样一个安全序列称系统处于不安全状态。192020/2/9安全序列在某一时刻，存在一个进程序列{P1，…，Pn}，对每个进程Pi(1≤i≤n），如果满足它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj(ji)当前占有资源量之和，即Needi则Available+Allicationj(1ji-1)，则称{P1，…，Pn}为安全序列。安全状态一定是没有死锁发生的不安全状态一定导致死锁???202020/2/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进程最大需求已分配还需可用P110553P2422P3927212020/2/9由安全状态向不安全状态的转换如果不按安全序列分配资源，则系统可能会由安全状态进入不安全状态。如在T0以后，P3要求1台磁带机，若系统分给它一台，则系统进入不安全状态。因为其余2台分给P2，P2完成后，只能释放4台，这既不能满足P1（5台），也不能满足P3（6台）。将导致死锁。可见当P3申请资源时，尽管系统中有资源也不能分给它。系统进入不安全状态：进程最大需求已分配还需可用P11055（3）2P2422P39（2）3（7）6222020/2/9利用银行家算法避免死锁银行家算法银行家拥有一笔周转资金客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款银行家应谨慎的贷款，防止出现坏帐用银行家算法避免死锁操作系统（银行家）操作系统管理的资源(周转资金)进程（要求贷款的客户）最有代表性的避免死锁算法，由Dijkstra提出。232020/2/9银行家算法的数据结构(1)可利用资源向量Available。它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。intAvailable[m-1];如：ABC523242020/2/9银行家算法的数据结构(2)最大需求矩阵Max：n*m矩阵，表示n个进程的每一个对m类资源的最大需求。intMax[n-1][m-1];ABCP1562P2331P3425P4332252020/2/9银行家算法的数据结构(3)分配矩阵Allocation：n*m矩阵，表示每个进程已分配的资源数。intAllocation[n-1][m-1]ABCP1212P2121P3222P4132262020/2/9银行家算法的数据结构(4)需求矩阵Need：n*m矩阵，表示每个进程还需要各类资源数。intNeed[n-1][m-1]ABCP1352P2211P3223P4232272020/2/9银行家算法的数据结构(5)进程申请资源向量Request：它是一个含有m个元素的数组，其中每个元素代表进程申请资源的数目。intRequest[m-1];如：ABC312282020/2/9银行家算法描述当进程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](4)执行安全性算法，若系统新状态是安全的，则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待。292020/2/9安全性算法定义数据结构intWork[m-1];boolFinish[n-1];m代表资源的数量，n代表进程的数量安全性算法步骤(1)Work=Available;Finish[i]=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,则系统处于安全状态，否则处于不安全状态302020/2/9银行家算法示例(1)设系统有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C}，每类资源分别有10、5、7，在T0时刻资源分配情况如图312020/2/9银行家算法示例(2)T0时刻可以找到一个安全序列{P1,P3,P4,P2,P0}，系统是安全的：（T0时刻安全性检查）322020/2/9银行家算法示例(3)T0时刻，P1发出请求Request(1,0,2)，执行银行家算法332020/2/9银行家算法示例(4)可以找到一个安全序列{p1,p3,p4,p0,p2}系统是安全的，可以将P1的请求分配给它。执行安全性算法342020/2/9银行家算法示例(5)P4发出请求Request(3,3,0),执行银行家算法Available=(2,3,0)不能通过算法第2步（Request[i]≤Available），所以P4等待。352020/2/9银行家算法示例(5)P0请求资源Request（0，2，0），执行银行家算法进行安全性检查：Available(2,1,0)已不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配362020/2/9死锁检测允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生;一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行检测时机当进程等待时检测死锁,其缺点是系统的开销大定时检测系统资源利用率下降时检测死锁死锁的检测和解除372020/2/9进程-资源分配图PRAG构成二元组G=（V，E）V：结点集，分为P，R两部分P={p1,p2,…,pn}R={r1,r2,…,rm}E：边的集合，其元素为有序二元组pi,rj或rj,pi表示法资源类：用方框表示资源实例：用方框中的黑圆点（圈）表示进程：用圆圈中加进程名表示分配边：资源实例进程的一条有向边请求边：进程资源类的一条有向边382020/2/9资源分配图示例392020/2/9死锁定理（1）如果进程-资源分配图中无环路，则此时系统没有发生死锁。如果进程-资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程。例如果进程-资源分配图中有环路，且涉及的资源类中有多