第3章 处理机调度与死锁2

1第3章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除2死锁计算机系统中，多道程序的并发执行可以改善系统的资源利用率，但也可能导致死锁的发生。能否不让死锁发生？何谓死锁?为什么会产生死锁？发生死锁怎么办？死锁的定义产生死锁的原因预防死锁死锁检测与恢复3死锁（deadlock）死锁是指多个进程因竞争系统资源而造成的一种僵局，若无外力作用，这些进程都将永远不能向前推进。一般地说，如果在一组进程的每个进程都在等待只能由该组中的其他一个进程才能引发的事件，则称这组进程处于死锁状态。43.5.1产生死锁的原因一般说来，死锁产生的原因是：◦竞争资源：多个进程竞争资源，而资源又不能同时满足其需求。◦进程推进顺序不当：进程申请资源和释放资源的顺序不当。5资源可剥夺和非剥夺资源◦可剥夺资源是指某进程获得这类资源后，该资源可以被其他进程或系统剥夺。如CPU，存储器。◦非剥夺资源又称不可剥夺资源，是指系统将这类资源分配给进程后，再不能强行收回，只能在进程使用完后主动释放。如打印机、读卡机。6资源（续）永久性资源和临时性资源◦永久性资源：可顺序重复使用的资源。如打印机。◦临时性资源：由一个进程产生，被另一个进程使用短暂时间后便无用的资源，又称为消耗性资源。如消息。7竞争非剥夺资源引起的死锁打印机R1和读卡机R2供进程P1和P2共享。R1R2P1P2假定P1已占用了打印机R1，P2已占用了磁带机R2。此时，若P2继续要求打印机，P2将阻塞；P1若又要求磁带机，P1也将阻塞。8竞争临时性资源引起的死锁进程P1产生消息S1，又要求从P3处接收消息S3；进程P3产生消息S3，又要求从P2接收消息S2；进程P2产生消息S2，又需要接收P1产生的消息S1。如果消息通信按下述顺序进行：P1：…Release(S1)；Reqaest(S3)；…P2：…Release(S2)；Request(S1)；…P3：…Release(S3)；Request(S2)；…并不可能发生死锁，但若改成下述的运行顺序：P1：…Request(S3)；Release(S1)；…P2：…Request(S1)；Release(S2)；…P3：…Request(S2)；Release(S3)；…则可能发生死锁。9进程推进顺序不当引起的死锁当进程P1、P2共享资源A、B时，若推进顺序合法则不会产生死锁，否则会产生死锁。P1:申请A申请B…释放A释放BP2:申请B申请A…释放B释放A10进程推进顺序不当引起的死锁(续)合法的推进路线：①②③不合法的推进线路：④P2释放AP2释放BP2申请AP2申请BP1申请AP1申请BP1释放AP1释放B①②③④113.5.2产生死锁的必要条件互斥条件：在一段时间内某资源仅为一个进程所占有。请求和保持条件：当进程因请求资源被阻塞时，已分配资源保持不放。不可剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。环路等待条件：存在一个循环等待链，其中，每一个进程分别等待它前一个进程所持有的资源，造成永远等待。只要能破坏这四个必要条件之一，死锁就可防止。12注意－关于死锁的一些结论死锁是因资源竞争造成的僵局死锁与部分进程及资源相关◦参与死锁的进程至少有两个◦参与死锁的进程至少有两个已经占有资源◦参与死锁的所有进程都在等待资源◦参与死锁的进程是当前系统中所有进程的子集133.5.3处理死锁的基本方法不考虑此问题（鸵鸟政策）用于处理死锁的方法主要有：◦预防死锁：设置某些限制条件，通过破坏死锁产生的四个必要条件之一来预防死锁。◦避免死锁：在资源的动态分配过程中，用某种方法来防止系统进入不安全状态。◦检测死锁及解除：系统定期检测是否出现死锁，若出现则解除死锁。不让死锁发生让死锁发生14第3章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除153.6.1预防死锁预防死锁。通过破坏产生死锁的四个必要条件中的一个或几个条件，来防止发生死锁。特点：较易实现，广泛使用，但限制较严，资源利用率低。16摒弃“互斥”条件？互斥是设备本身固有的属性，此条件不能破坏。17摒弃“请求和保持条件”要求进程一次申请它所需的全部资源，若有足够的资源则分配给进程，否则不分配资源，进程等待。这种方法称为静态资源分配法。特点：简单、安全且易于实现；但资源利用率低，进程延迟运行。18摒弃“不剥夺”条件一个已保持了某些资源的进程，若新的资源请求得不到满足，则它必须释放已获得的所有资源，待以后需要时再重新申请。特点：实现较复杂，释放已获得资源可能造成前一段工作的失效，重复申请和释放资源会增加系统开销，降低系统吞吐量。只适用于其状态可以保存和恢复的资源，如对主存资源和处理器资源的分配19摒弃“环路等待”条件将所有资源按类型排队，并赋予不同序号，要求进程均严格按照序号递增的次序请求资源，同类资源一次申请完。这种方法称为有序资源分配法。换句话说，要求：当一个进程申请一个资源时，必须释放其占有的序号大于该资源的其它资源。20有序资源分配法的特点特点：比前两种方法资源利用率高，吞吐量大。但要求资源序号相对稳定，从而限制了新设备的增加；使用资源的顺序与系统规定顺序不同，造成资源的浪费；使用资源的次序限制用户编程。21为什么有序资源分配法可以防止死锁假设循环已经出现并且含于环中的进程是p0、…、pn，这意味着pi正占有ri类资源，而请求ri+1类资源，设函数f能获得资源序号，则有f（ri）f（ri+1），故f（r0）f（r1）…f（rn）f（r0）。矛盾，原假设不成立。r1pnp0p1r0…rn223.6.2系统安全状态预防死锁方法一般都对资源的申请使用施加了较强限制条件，而死锁避免对资源的申请使用限制条件较弱，系统性能较好。死锁避免：允许进程动态申请资源，系统在为申请者分配资源前先检查资源分配的安全性。并根据检查结果决定是否分配资源，若分配后系统可能发生死锁（即不安全），则不予分配，否则予以分配。23安全状态死锁避免方法中将系统状态分为安全状态和不安全状态，只要系统始终都处于安全状态便可避免死锁的发生。24安全状态安全状态是指系统能按某种顺序如P1,P2,…,Pn来为每个进程分配其所需的资源，直至最大需求，使每个进程都可以顺利完成，则称此时的系统状态为安全状态，称序列P1,P2,…,Pn为安全序列。即在当前状态下能够找到一个安全序列，则是安全状态。25不安全状态若某一时刻系统中不存在一个安全序列，则称此时的系统状态为不安全状态。进入不安全状态后，便可能进而进入死锁状态；因此避免死锁的本质是使系统不进入不安全状态。26安全状态例进程P1、P2、P3共享某一类资源（共12个），T0时刻，系统资源状态如下：进程最大需求已分配需要可用P110553P2422P3927这时可用资源能满足P2的需要，P2获得运行需要的所有资源并能顺利运行结束。27这时可用资源能满足P1的需要，P1获得运行需要的所有资源并能顺利运行结束。进程最大需求已分配需要可用P110555P2422P3927P2运行结束的系统资源状态安全状态例（续）28因此T0时刻存在一个安全序列P2，P1，P3，系统状态安全。进程最大需求已分配需要可用P1105510P2422P3927这时可用资源能满足P3的需要，P3获得运行需要的所有资源并能顺利运行结束。P2、P1运行结束的系统资源状态安全状态例（续）29安全状态例（续）若在T0之后，P3请求1个资源，如果系统接受其请求将1个资源分配给P3，系统资源状态如下表：进程最大需求已分配需要可用P110552=3-1P2422P393=2+16=7-1此时，不存在安全序列，则系统进入了不安全状态。因此P3的请求不应该接受。30课堂练习T0时刻，系统资源状态如下：进程最大需求已分配需要可用P110553P2422P3927按照死锁避免的思想：以下的哪个申请可以接受？在T0时刻，P2申请1个资源在T0时刻，P3申请1个资源在T0时刻，P1申请1个资源（2个资源）313.6.3利用银行家算法避免死锁最具代表性的死锁避免算法是Dijkstra的银行家算法。假定系统中有n个进程P1、P2、…、Pn，m类资源R1、R2、…、Rm，银行家算法中使用的数据结构如下：321）可用资源向量Available可利用资源向量Available是一个含有m个元素的数组，其中每一个元素代表一类资源的空闲资源数目。如果Available(j)＝k，表示系统中现有空闲的Rj类资源k个。332）最大需求矩阵Max最大需求矩阵Max是一个n×m的矩阵，定义了系统中每个进程对m类资源的最大需求数目。如果Max(i，j)＝k，表示进程Pi需要Rj类资源的最大数目为k。343）分配矩阵Allocation分配矩阵Allocation是一个n×m的矩阵，定义了系统中每一类资源当前已分配给每一个进程的资源数目。如果Allocation(i，j)＝k，表示进程Pi当前已分到Rj类资源的数目为k。Allocationi表示进程Pi的分配向量，由矩阵Allocation的第i行构成。354）需求矩阵Need需求矩阵Need是一个n×m的矩阵，它定义了系统中每一个进程还需要的各类资源数目。如果Need(i，j)＝k，表示进程Pi还需要Rj类资源k个。Needi表示进程Pi的需求向量，由矩阵Need的第i行构成。三个矩阵间的关系：Need(i，j)＝Max(i，j)－Allocation(i，j)36银行家算法设Requesti是进程Pi的请求向量，Requesti(j)＝k表示进程Pi请求分配Rj类资源k个。当Pi发出资源请求后，系统按下述步骤进行检查：37银行家算法描述(1)如果Requesti≤Needi，则转向步骤2；否则出错。(2)如果Requesti≤Available，则转向步骤3；否则Pi等待。(3)试分配并修改数据结构：Available＝Available－Requesti；Allocationi＝Allocationi＋Requesti；Needi＝Needi－Requesti；(4)系统执行安全性算法，检查此次资源分配是否安全。若安全，才正式分配；否则，试分配作废，让进程Pi等待。38安全性算法(1)设置两个向量Work和Finish并置初值：◦Work：m维向量，表示系统可提供给进程继续运行的各类空闲资源数目，算法开始时，Work＝Available；◦Finish：n维向量，表示系统是否有足够的资源分配给进程，使之运行完成，开始时，对每一个i都令Finish(i)＝false；(2)从进程集合中找到一个能满足下述条件的进程：◦Finish(i)=false；◦Needi≤Work；如找到则执行步骤3；否则执行步骤4；39安全性算法(续)(3)当进程Pi获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行：◦Work＝Work＋Allocationi；◦Finish(i)＝true；◦转去执行步骤2；(4)若所有进程的Finish(i)都为true，则表示系统处于安全状态；否则，系统处于不安全状态。40银行家算法例假定系统中有5个进程P0、P1、P2、P3、P4和三种类型的资源A、B、C，数量分别为12、5、9，在T0时刻的资源分配情况如下所示。资源情况进程MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P443300243141T0时刻的安全性利用