搜索
第三章处理机调度和死锁Review实时调度算法EDFLLF截止时间（完成截止时间和开始截止时间）松弛度的定义：松弛度=必须完成时间-运行时间-当前时刻竞争资源进程推进顺序不当产生死锁的原因竞争非剥夺性资源竞争临时资源本章主要内容3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除①互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只供一个进程占用。如果此时其他进程请求该资源，请求者只能等待—（资源独占）②请求和保持：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占用，此时请求进程阻塞，但又对自己已获得的其它资源保持不放—（部分分配，占有申请）产生死锁的必要条件死锁的发生具备下列四个必要条件：必要条件:如果能从命题B推出命题A,条件A是条件B的必要条件。如果无A必无B，有A可能有B也可能没有B，则A是B的必要条件。产生死锁的必要条件③不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放；④环路等待条件：指在发生死锁时，必然存在一个进程—资源的环形链，即进程集合{P0，P1，P2，…,Pn}中的P0正等待一个P1占用的资源，P1正等待一个P2占用的资源，…，Pn正等待已被P0占用的资源。①②③④输入设备输出设备BA输入设备输出设备A在干什么？B在干什么？①②③④输入设备输出设备BA输入设备输出设备处理死锁的基本方法不考虑此问题：（鸵鸟政策）预防死锁该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量的降低。避免死锁发生也是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的四个必要条件。而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁。常用的算法是银行家算法。检测死锁不须事先采取限制性措施，也不必检查系统是否进入不安全区，而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；然后采用适当的措施从系统中将已发生的死锁清除掉。解除死锁与检测死锁相配套的一种措施。检测到系统中已发生死锁时，将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。本章主要内容3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除1、预防死锁定义：在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的必要条件之一（互斥条件是不能破坏的）1）摒弃“请求和保持”条件---资源的静态分配要求每个进程在运行前必须一次性申请它所要求的所有资源，当且仅当该进程所要资源均可满足时才给予一次性分配缺点：资源严重浪费。进程申请到资源后，整个运行期间一直占用；进程延迟运行，只有当进程获得了其所需的所有资源后，才能开始运行，可能因某些资源长期被其他进程占用而致使等待进程迟迟不能运行。优点：简单、易于实现且很安全。2）摒弃“不可剥夺”条件在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。代价：①以前的工作失效②反复申请释放使进程无限期推迟③系统开销大缺点：①为系统中各类资源所分配（确定）的序号必须相对稳定，这就限制了新设备的添加；②尽管在为资源的类型分配序号时，已经考虑到大多数作业在实际使用这些资源时的顺序，但也经常发生这种情况：即作业（进程）使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。如：某进程先用磁带机，再用打印机。但按系统规定，该进程应先申请打印机而后申请磁带机，致使先获得的打印机被长时间闲置。③为方便用户，系统对用户在编程时所施加的限制条件应尽量少。然而这种按规定次序申请的方法，必然会限制用户简单、自主地编程。3）摒弃“环路等待”条件采用资源有序分配法：①把系统中所有资源顺序编号：r1，r2，…，rn②各进程按资源编号递增次序申请资源系统安全状态在预防死锁的方法中，都施加了较强的限制条件；在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。该方法中把系统的状态分为安全状态和不安全状态，只要使系统始终都处于安全状态，便可避免发生死锁。ＲP1安全吗？ＲP1安全吗？安全不安全系统安全状态在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程，否则，令进程等待。所谓安全状态，是指系统能按某种进程顺序（P1,P2,…,Pn），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。安全状态之例Eg:系统中有进程P1、P2、P3和12台磁带驱动器，各进程对此资源的需求和分配情况如下表所示，此时按照安全序列P2,P1,P3分配资源可以保证各进程都顺利完成进程最大需求已分配可用P11053P242P392安全状态向不安全状态的转换分配资源时若不按照安全序列的顺序，可能会导致OS由安全状态进入不安全状态eg：在上例中，为进程P3分配一台磁带机，系统进入不安全状态，此时再也找不到一个安全序列进程最大需求已分配可用P11052P242P393银行家算法假定某银行家有一笔资金可供一批顾客借用，并假定：每个顾客预知他的最大借款总额，且不超过银行家拥有的可用资金总和。每当顾客提出借款请求，银行家可立即给予，或让顾客等一段时间。只有当顾客达到他的预定最大借款额时，他才在有限时间依次归还。•死锁的产生：当各顾客借款总额之和大于银行可借用资金总和，而每顾客都未达到他的预定最大借款额。•安全状态：如果在某时刻，银行有可能使它当时的所有的顾客在以后有限时间内完成全部成交，则此刻的状态是安全。•不安全状态：永远不具有成交的可能，则为不安全。银行家算法概念（P109～P111）把这种算法比作银行家，银行家占有有限的资金（资源），把进程比作借款人，如果借出去的款能收回则出借（分配资源），否则拒绝贷款。算法原理：每次分配检查系统是否存在一个进程安全序列，存在一个安全序列则分配，反之，拒绝分配，让申请的进程阻塞。如果系统无法找到这样的一个安全序列，则称系统处于不安全状态。例：有三个进程共享某类资源，最大需求为（10，4，9），资源总数为：12最大需求数已分配数当前需求下限可用数P110553P2422P3927{P1，P2，P3}{P1，P3，P2}{P2，P1，P3}{P2，P3，P1}{P3，P1，P2}{P3，P2，P1}√√√对安全序列的物理含义的说明:(0,0,0)(0,0,7)(5,0,7)(5,2,7)(10,4,9)尚需P3P1P2安全完成3(12)(0,0,9)(0,0,7)t40(10)(10,0,2)(5,0,0)t31(5)(5,4,2)(0,2,0)t23(5,2,2)(5,2,2)t112（0,0,0)（0,0,0)t0可用数P1,P2,P3分配P1,P2,P3申请各时刻系统状态都是安全的，因为每个时刻都存在一个进程安全序列，保证各进程顺利完成。P1,P2,P3最大需求为（10，4，9）最大需求数已分配数当前需求可用数P110552P2422P3936{P1，P2，P3}{P1，P3，P2}{P2，P1，P3}{P2，P3，P1}{P3，P1，P2}{P3，P2，P1}如果进程P3再请求并分配一个资源:不存在安全序列(5,0,6)(5,0,6)(5,0,6)(5,2,6)(5,2,7)尚需P3阻塞P1阻塞P2不安全安全完成4(5,0,3)(0,0,6)t54(5,0,3)(5,0,0)t40(4)(5,4,3)(0,2,0)t32(5,2,3)(0,0,1)t23(5,2,2)(5,2,2)t1可用数P1,P2,P3分配P1,P2,P3申请不安全状态，最终推进到死锁。银行家算法就是要排除这种不安全状态的存在不安全状态，最终推进到死锁。最大需求仍然为（10，4，9）P1,P2,P3申请P1,P2,P3分配可用数完成t1(5,2,2)(5,2,2)3安全t2(0,0,1)(5,2,2)3t3(2,0,0)(5,2,2)3t4(0,2,0)(5,4,2)1t5(5,0,0)(10,0,2)0t6（0,0,7）（0,0,9）3××P3阻塞P1阻塞P2完成P1完成P3完成(5)(10）(12)最大需求仍然为（10，4，9）银行家算法n：系统中进程的总数；m：资源种类可用资源向量Available:ARRAY[1..m]ofinteger;最大需求矩阵Max:ARRAY[1..n,1..m]ofinteger;已分配矩阵Allocation:ARRAY[1..n,1..m]ofinteger;需求矩阵（各进程的需求下限）Need:ARRAY[1..n,1..m]ofinteger;请求向量Request:ARRAY[1..n,1..m]ofinteger;银行家算法符号简记：Available、Max[i]Allocation[i]Need[i]、Request[i]当进程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]若系统新状态是安全的，则分配完成若系统新状态是不安全的，则恢复原状态，进程等待银行家算法安全性检查定义数据结构：工作向量Work:ARRAY[1..m]ofinteger;结束向量Finish:ARRAY[1..n]ofBoolean;•安全性检查的步骤：(1)Work:=Available;Finish:=false;(2)寻找满足条件的i：①Finish[i]=false;②Need[i]≤Work;如果不存在，则转(4)(3)Work:=Work+Allocation[i];Finish[i]:=true;转(2)(4)若对所有i,Finish[i]=true,则系统处于安全状态，否则处于不安全状态银行家算法之例（P110）进程P0,1,2,3,4共享A、B、C三类资源{A，B，C}={10，5，7}T0时刻，资源的分配情况如下图所示。（1）该状态是否安全？若安全，请找出安全序列。（2）在此基础上，P1申请（1，0，2）能否分配？为什么？（3）P4申请（3，3，0）能否分配？为什么？（4）P0申请（0，2，0）能否分配？为什么？MaxABCAllocationABCNeedABCAvailableABCP0P1P2P3P4753322902222433010200302211002743122600011431332True1057302600755P2True755010743745P0True745002431743P4True743211011532P3False302600532P2True532200122332P1False010743332P0finishiWork+allocallocneedwork√√√√√•有P1,P3,P4,P0,P2安全序列，T0时刻分配合法•注意：安全序列