处理机调度与死锁.pptx

第三章 处理机调度与死锁 3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 高级、中级和低级调度高级、中级和低级调度 处理器调度分为三级：高级调度（作业调度）（长程调度）中级调度（中期调度）低级调度（进程调度）（短程调度）第三章 处理机调度与死锁 按某种原则从后备状态挑选作业调入内存运行为作业创建进程为选中作业分配资源1.高级调度高级调度(Low Level Scheduling)第三章 处理机调度与死锁 2.2.中程调度中程调度 决定哪些作业允许参于竞争处理机资源。作用：起到短期调整系统负荷，以平顺系统。方式：“挂起”，“解挂”。第三章 处理机调度与死锁 3.3.低级调度低级调度按某种原则将处理机分配给就绪进程。进程调度属操作系统内核，执行频率很高。进程调度是最基本的一种调度，它可以采用非抢占方式或抢占方式。第三章 处理机调度与死锁 1)非抢占方式非抢占方式(Non-preemptive Mode)在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个：正在执行的进程执行完毕，或因发生某事件而不能再继续执行；执行中的进程因提出I/O请求而暂停执行；在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。第三章 处理机调度与死锁 2)抢占方式抢占方式(Preemptive Mode)抢占的原则有：(1)优先权原则。(2)短作业(进程)优先原则。(3)时间片原则。第三章 处理机调度与死锁 4.处理机三级调度关系处理机三级调度关系 新建新建就绪挂起就绪挂起阻塞挂起阻塞挂起就绪就绪阻塞阻塞运行运行退出退出长程调度长程调度长程调度长程调度中程调度中程调度中程调度中程调度进程调度进程调度调度和进程状态转换调度和进程状态转换第三章 处理机调度与死锁 3.1.2 调度队列模型调度队列模型 1.仅有进程调度的调度队列模型仅有进程调度的调度队列模型 仅具有进程调度的调度队列模型 第三章 处理机调度与死锁 2.具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 具有高、低两级调度的调度队列模型 第三章 处理机调度与死锁(1)就绪队列的形式。(2)设置多个阻塞队列。图 3-2 示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面。第三章 处理机调度与死锁 3.同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 具有三级调度时的调度队列模型 就绪队列进程调度CPU就绪挂起队列中级调度阻塞挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现第三章 处理机调度与死锁 3.2.1作业调度的职能作业调度的职能记录已进入系统的作业情况JCB调度算法：按照某种调度算法从后备状态挑选作业运行。运行准备：为选中作业创建进程，分配主存和外设。结束善后处理：收回资源，输出必要信息。作业进入后备状态建立作业退出系统时撤消 3.2作业调度作业调度第三章 处理机调度与死锁 3.2.2作业控制块作业控制块作业存在唯一标志作业调度的依据记录作业的有关信息，反映作业运行情况内容进入系统时建立退出系统时撤消作业名资源要求资源使用情况类型说明状态第三章 处理机调度与死锁 3.2.3 调度性能的衡量调度性能的衡量平均周转时间：作业k Tk=Tck-Tsk =T等待+T运行 平均周转时间T=1/nTk带权周转时间：作业k Wk=Tk/TRk 平均带权周转时间W=1/n WkK=1nK=1 nTck：作业K完成时间Tsk：作业K提交时间TRk：作业K运行时间第三章 处理机调度与死锁 3.2.4选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则 1.面向用户的准则面向用户的准则(1)周转时间短。(2)响应时间快。(3)截止时间的保证。(4)优先权准则。第三章 处理机调度与死锁 2.面向系统的准则面向系统的准则(1)系统吞吐量高。(2)处理机利用率好。(3)各类资源的平衡利用。第三章 处理机调度与死锁 3.3 调调 度度 算算 法法 先进先服务调度算法先进先服务调度算法短作业优先调度算法短作业优先调度算法高优先权优先调度算法高优先权优先调度算法最高响应比优先最高响应比优先时间片轮转调度算法时间片轮转调度算法最短剩余时间优先调度算法最短剩余时间优先调度算法均衡法均衡法多级反馈队列调度算法多级反馈队列调度算法第三章 处理机调度与死锁 3.3.1先来先服务调度算法先来先服务调度算法其原则按照作业到达系统或进程进入就绪队列先后次序来选择。FIFO是一种非抢占算法。第三章 处理机调度与死锁 例题例题 进程 到达时间 服务时间 优先数 1 0 3 2 2 2 6 5 3 4 4 3 4 6 5 6 5 8 2 1 第三章 处理机调度与死锁 作业1 作业2 作业3 作业4 作业50 3 9 13 18 20T=1/5（3+7+9+12+12）=8.60W=1/5（1+1.17+2.25+2.40+6.00）=2.56第三章 处理机调度与死锁 特点:吞吐量不定、耗费最小、无饥饿、对偏重于I/O进程不利，响应时间很高，尤其是进程执行时间变化很大时第三章 处理机调度与死锁 3.3.2 短作业短作业(进程进程)优先调度算法优先调度算法 短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。第三章 处理机调度与死锁 作业1 作业2 作业5 作业3 作业40 3 9 11 15 20T=1/5（3+7+11+14+3）=7.60W=1/5（1+1.17+2.75+2.80+1.50）=1.84第三章 处理机调度与死锁 SJ(P)F调度算法也存在不容忽视的缺点：(1)该算法对长作业不利，更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。(2)该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。(3)由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。第三章 处理机调度与死锁 特点：吞吐量高、能提供较好的响应时间，对长进程不利、可能产生饥饿第三章 处理机调度与死锁 3.3.3 高优先权优先调度算法高优先权优先调度算法 选择优先级高的进程和作业作为调度对象。按抢占与否优先数可分：非抢占的优先调度算法 可抢占的优先调度算法按静态，动态优先数可分：静态优先数 动态优先数 第三章 处理机调度与死锁 1）非抢占式优先权算法 在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。第三章 处理机调度与死锁 2)抢占式优先权调度算法 在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i时，就将其优先权Pi与正在执行的进程j的优先权Pj进行比较。如果PiPj，原进程Pj便继续执行；但如果是PiPj,则立即停止Pj的执行，做进程切换，使i进程投入执行。显然，这种抢占式的优先权调度算法，能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。第三章 处理机调度与死锁 3)静态优先权 静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，07或0255中的某一整数，又把该整数称为优先数。只是具体用法各异：有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相反。第三章 处理机调度与死锁 确定进程优先权的依据有如下三个方面：(1)进程类型。(2)进程对资源的需求。(3)用户要求。第三章 处理机调度与死锁 4)动态优先权 动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。第三章 处理机调度与死锁 非抢占的优先调度非抢占的优先调度作业1 作业2 作业4 作业3 作业50 3 9 14 18 20 T=1/5（3+7+14+8+12）=8.8W=1/5（1+1.17+3.5+1.6+6）=2.85第三章 处理机调度与死锁 3.3.4高响应比优先调度算法高响应比优先调度算法 优先权的变化规律可描述为：由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：第三章 处理机调度与死锁 (1)如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。(2)当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。(3)对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。第三章 处理机调度与死锁 作业1 作业2 作业3 作业5 作业40 3 9 13 15 20T=1/5（3+7+9+14+7）=8.00W=1/5（1.00+1.17+2.25+2.80+3.5）=2.14最高响应比是一种非抢占算法第三章 处理机调度与死锁 3.3.5时间片轮转调度算法时间片轮转调度算法把CPU的时间分割成时间片，处于就绪状态的进程轮流获得时间片。时间片轮转调度算法是抢占算法。其调度算法的性能取决于时间片Q。第三章 处理机调度与死锁 Q=4（时间片为4）作业1 作业2 作业3 作业4 作业2 作业5 作业40 3 7 11 15 17 19 20T=1/5（3+15+7+14+11）=10.00W=1/5（1.00+2.50+1.75+2.80+5.50）=2.71第三章 处理机调度与死锁 Q=1（时间片为1）1 2 1 2 3 2 4 3 2 5 4 3 2 5 4 3 2 4 40 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 T=1/5（4+16+13+14+7）=10.8 W=1/5（1.33+2.67+3.25+2.80+3.50）=2.71 第三章 处理机调度与死锁 RR算法主要用于分时系统或事务处理系统，可保证对各终端用户的及时响应。但它对偏重CPU的进程和偏重I/O的进程有不同的处理结果，可以采用虚拟时间片轮转(VRR)策略来避免这个问题。新加入的特性是附加一个FCFS策略队列来收集从I/O等待中释放的进程。第三章 处理机调度与死锁 特点：吞吐量在时间片小的时候可能很低，对所有进程公平对待、特别是短进程提供好的响应时间，无饥饿第三章 处理机调度与死锁 3.3.6最短剩余时间优先调度算法最短剩余时间优先调度算法最短剩余时间：从作业当前运行到完成所需时间。最短剩余时间优先调度是抢占算法。用于分时系统其轮转时间最优第三章 处理机调度与死锁 作业1 作业2 作业3 作业5 作业2 作业40 3 4 8 10 15 20T=1/5（3+13+4+14+2）=7.20W=1/5（1.00+2.17+1.00+2.80+1.00）=1.59第三章 处理机调度与死锁 特点：吞吐量高、能提供较好的响应时间，对长进程不利、可能产生饥饿第三章 处理机调度与死锁 3.3.7 均衡法均衡法作业分类AI/O量多B比较适中C占用CPU时间A、C按一定比列搭配。B类不受限制。第三章 处理机调度与死锁 3.3.8多级反馈队列调度算法多级反馈队列调度算法系统中有多个就绪队列各级就绪队列具有不同的时间片各级队列均按FIFO原则排队调度方法：首先调度优先级高的进程，当优先级高的进程为空，才调度下一级。第三章 处理机调度与死锁 Q=1（每级反馈队列每一级时间片为1）1 1 2 1 3 2 4 3 5 4 5 2 3 4 2 3 4 2 4 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20T=1/5（4+18+12+13+3）=10.00W=1/5（1.33+3.00+3.00+2.60+1.50）=2.29 第三章 处理机调度与死锁 Q=2*N（每级反馈队列每一级时间片以2幂次方递增）1 1 2 1 3 2 2 4 5 3 3 4 4 5 2 2 2 3 4 4T=1/5（4+15+14+14+6）=10.06W=1/5（1.33+2.50+3.50+2.80+3.00）=2.63 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20第三章 处理机调度与死锁 特点：吞吐量不定，消耗可能高、有利于偏重I/O进程，可能会饥饿第三章 处理机调度与死锁 多级反馈队列调度算法的性能多级反馈队列调度算法的性能(1)终端型作业用户。(2)短批处理作业用户。(3)长批处理作业用户。第三章 处理机调度与死锁 3.4 实实 时时 调调 度度 3.4.1 实现实时调度的基本条件实现实时调度的基本条件 1.提供必要的信息提供必要的信息(1)就绪时间。(2)开始截止时间和完成截止时间。(3)处理时间。(4)资源要求。(5)优先级。第三章 处理机调度与死锁 2.系统处理能力强系统处理能力强 3.采用抢占式调度机制采用抢占式调度机制4.具有快速切换机制具有快速切换机制(1)对外部中断的快速响应能力。(2)快速的任务分派能力。第三章 处理机调度与死锁 3.4.2 实时调度算法的分类实时调度算法的分类 1.非抢占式调度算法非抢占式调度算法(1)非抢占式轮转调度算法。(2)非抢占式优先调度算法。第三章 处理机调度与死锁 非抢占时间片轮转调度 第三章 处理机调度与死锁 非抢占式优先权调度 第三章 处理机调度与死锁 2.抢占式调度算法抢占式调度算法(1)基于时钟中断的抢占式优先权调度算法。(2)立即抢占(Immediate Preemption)的优先权调度算法。第三章 处理机调度与死锁 基于时钟抢占的优先权抢占调度 第三章 处理机调度与死锁 立即抢占优先权调度 第三章 处理机调度与死锁 3.4.3 常用的几种实时调度算法常用的几种实时调度算法 1.最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)算法算法 根据任务的开始截止时间或完成截止时间来确定任务的优先级，截止时间越早，其优先级越高最早截止时间优先调度算法有抢占式和非抢占式第三章 处理机调度与死锁 1）非抢占式调度用于非周期性实时任务第三章 处理机调度与死锁 2）抢占式调度方式用于周期实时任务假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。第三章 处理机调度与死锁 进程到达时间执行时间完成期限进程到达时间执行时间完成期限A101020B102550A2201040B25025100A3401060A4601080A58010100第三章 处理机调度与死锁 B1A1A2A30 10 20 30 40 50 60 70 80 90 100 B2A4A5A1期限期限 A2期限期限 A3期限期限 A4期限期限 A5期限期限B1期限期限 B2期限期限第三章 处理机调度与死锁 B1期限期限 B2期限期限0 10 20 30 40 50 60 70 80 90 100 A1B1A2B1 A3 B2A1期限期限 A2期限期限 A3期限期限 A4期限期限 A5期限期限B1误期误期A4B2A5 B固定优先级（A优先级高，且可抢占）第三章 处理机调度与死锁 B1期限期限 B2期限期限0 10 20 30 40 50 60 70 80 90 100 B1A2A3B2A5固定优先级（B优先级高）A1期限期限 A2期限期限 A3期限期限 A4期限期限 A5期限期限A1误期误期 A4误期误期第三章 处理机调度与死锁 B1期限期限 B2期限期限0 10 20 30 40 50 60 70 80 90 100 A1B1A2B1A3 B A4B2A5A1期限期限 A2期限期限 A3期限期限 A4期限期限 A5期限期限使用完成期限最早期限调度 都能完成都能完成第三章 处理机调度与死锁 2.最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)算法算法 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。该算法主要用于可抢占调度方式 第三章 处理机调度与死锁 A和B任务每次必须完成的时间 A每隔20MS执行一次，执行时间为10MSB每隔50MS执行一次，执行时间为25MS第三章 处理机调度与死锁 松弛度=必须完成时间-其本身的运行时间-当前时间 第三章 处理机调度与死锁 利用ELLF算法进行调度的情况 t1A1(10)10203040506080t0t1=0B1(15)t2t370A2(10)A3(5)A4(10)t4t5t6t7t8B1(5)B2(20)B2(10)第三章 处理机调度与死锁 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件3.5.1 死锁问题的提出死锁问题的提出1.死锁的定义死锁的定义死锁是指计算机系统和进程所处的一种状态。常定义为：在系统中的一组进程，由于竞争系统资源或由于彼此通信而永远阻塞，我们称这些进程处于死锁状态。第三章 处理机调度与死锁 例例1银行借款银行借款假定某行有一笔法郎可供一批顾客借用，并假定：每个顾客预知他的最大借款总额，且不超过银行拥有可用资金总和。每次借款以一法郎为单位。每当顾客提出借款请求，银行可立即给予，或让顾客等一段时间。只有当顾客达到他的预定最大借款额时，他才在有限时间一次归还。第三章 处理机调度与死锁 死锁的产生：当各顾客借款总额之和大于银行可借用资金总和，而每顾客都未达到他的预定最大借款额。安全状态：如果在某时刻，银行有可能使它当时的所有的顾客在以后有限时间内完成全部成交，则此刻的状态是安全。不安全状态：永远不具有成交的可能，则为不安全。第三章 处理机调度与死锁 C 2 P 4（4）Q 2（1）R 2（7）C 4 P 4（4）R 2（7）C 8 R 2（7）C 10安全状态C 1 P 4（4）Q 2（1）R 3（6）C 3 P 4（4）R 3（6）不安全状态C：借款总额，P，Q，R：顾客第三章 处理机调度与死锁 例2相同类型资源假设内存有M个页面，N个进程，这里M，N满足 2MN，如果分配和回收以页为单位，且每个进程以如下方式申请和释放资源。申请一页申请一页释放一页释放一页第三章 处理机调度与死锁 死锁的产生：各进程的执行次序轮转R1R2R3P1 P2 P3 P4M=3，N=4框：资源圈：进程圈框：分配边框圈：请求边第三章 处理机调度与死锁 例3：不同类型资源假定系统有N种外部设备R1，R2RN，系统又有N个进程P1，P2 PN，它们以这种方式要求资源。P1：申请R1 申请R2 释放R1 释放R2P2：申请R2 申请R3 释放R2 释放R3PN：申请RN 申请R1 释放RN 释放R1第三章 处理机调度与死锁 死锁的产生：各进程的执行次序轮转P3R1 R2P2P1R3第三章 处理机调度与死锁 2.2.产生死锁的原因产生死锁的原因(1)竞争资源。(2)进程间推进顺序非法。第三章 处理机调度与死锁(1)竞争资源引起进程死锁竞争资源引起进程死锁 资源：可以引起一个进程进入等待状态的事物可抢占资源、不可抢占资源共享资源、独享资源可重用资源(永久)、消耗性资源(临时)第三章 处理机调度与死锁（2）进程推进顺序不当引起死锁进程推进顺序不当引起死锁 进程推进顺序合法 图 3-14 进程推进顺序对死锁的影响 第三章 处理机调度与死锁 进程推进顺序非法 若并发进程P1和P2按曲线所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1,P2保持了资源R2,系统处于不安全状态。因为，这时两进程再向前推进，便可能发生死锁。例如，当P1运行到P1:Request(R2)时，将因R2已被P2占用而阻塞；当P2运行到P2:Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁。第三章 处理机调度与死锁 3.产生死锁的必要条件产生死锁的必要条件(1)互斥条件(2)请求和保持条件(3)不剥夺条件(4)环路等待条件 第三章 处理机调度与死锁 3.5.2 处理死锁的基本方法处理死锁的基本方法(1)预防死锁。(2)避免死锁。(3)检测死锁。(4)解除死锁。第三章 处理机调度与死锁 3.6 预防死锁预防死锁 通过设置某些限制条件，以破坏产生死锁的必要条件一个或几个，来防止死锁。预防死锁是一种较可取的方法，但资源的利用率较低。第三章 处理机调度与死锁 3.6.1摒弃“互斥条件”条件互斥是正确使用非共享资源的唯一手段。故不能通过取消互斥来预防死锁。第三章 处理机调度与死锁 3.6.2摒弃“请求和保持”条件 采用资源静态分配：每个进程执行前，一次分配其所有资源允许进程仅当自己未占有资源时才申请资源。第三章 处理机调度与死锁 例1：如果有这样进程，它从读卡机中拷贝磁盘文件，排序磁盘文件，然后将结果打印在打印机上，并将起拷贝到磁带。第三章 处理机调度与死锁 按第一种制约：在进程运行前。为其分配所有资源，读卡机，磁盘文件，打印机，磁带机按第二种制约：先申请读卡机，磁盘文件释放两者申请磁盘文件，打印机释放两者申请磁盘文件，磁带机释放两者。第三章 处理机调度与死锁 3.6.3摒弃“不剥夺”条件适用于状态容易保护，稍后又容易恢复的资源。如CPU，内存。第三章 处理机调度与死锁 3.6.4摒弃“环路等待”条件为使“循环等待”条件不满足，我们把所有资源按类型进行排队，并赋予不同的编号。每个进程 释放 按序号递减次序进行申请 按序号递增次序进行第三章 处理机调度与死锁 优点：资源的申请与分配逐步进行，比预分配策略的资源利用率高；缺点：严格限制资源的顺序性，不允许增加资源请求在使用资源的顺序与系统规定不一致时，资源利用率降低；不能抢占。第三章 处理机调度与死锁 3.7 死锁的避免和银行家算法死锁的避免和银行家算法 3.7.1 安全状态安全状态 在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。所谓安全状态，是指系统能按某种进程顺序(P1,P2,，Pn)(称P1,P2,Pn序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。第三章 处理机调度与死锁 3.7.2 利用银行家算法避免死锁利用银行家算法避免死锁 1.银行家算法中的数据结构银行家算法中的数据结构 Resource:一个长度为m向量,表示系统拥有的资源数目Available：一个长度为m向量，表示每类资源的可用数目 如果Availablej=k，表明Rj类资源有k个。Max：一个mn矩阵，定义每个进程的最大资源需求数 如果Maxi,j=k,表示进程i需要Rj类资源有k个。Allocation：一个mn矩阵，定义当前分配给每个进程每类资源的数目。如果Allocation i,j=k，则表示进程i获得Rj类资源有k个。Need：一个mn矩阵，表示每个进程还需多少资源。如果 Needi,j=k，表示进程i还需要Rj类资源有k个。第三章 处理机调度与死锁 2.银行家算法银行家算法设：Requesti是进程Pi的请求向量当Pi发出资源请求后，系统按如下步骤进行检查：如果Requesti Needi 则go to 2,否则认为出错。如果Requesti Available 则go to 3，否则表示无足够资源，Pi等待。系统进行试探分配，并求该相应数据结构数据 Available：=Available-Requesti Allocationi：=Allocationi+Requesti Needi：=Needi-Requesti系统执行安全性算法：安全，把资源分配给Pi，否则，Pi等待。第三章 处理机调度与死锁 3.安全性算法安全性算法 设Work 和 Finish是长度分别为m,n的向量初试值Work：=Available，Finishi：=False（所有）从进程集合中找到一个能满足下列条件的进程 a.Finishi=False b.Needi Work 如找到go to 3 否则 go to 4 当进程Pi 获得资源后，顺利执行，直至完成，并释放分 配给它的资源。Work：=Work+Allocationi Finishi：=True go to 2如果所有进程的Finishi=True 则表示系统安全，否则为不安全。第三章 处理机调度与死锁 4.银行家算法之例银行家算法之例 假定系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。图 3-15 T0时刻的资源分配表 第三章 处理机调度与死锁(1)T0时刻的安全性：图 3-16 T0时刻的安全序列 第三章 处理机调度与死锁 (2)P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：Request1(1,0,2)Need1(1,2,2)Request1(1,0,2)Available1(3,3,2)系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量，由此形成的资源变化情况如图 3-15 中的圆括号所示。再利用安全性算法检查此时系统是否安全。第三章 处理机调度与死锁 图 3-17 P1申请资源时的安全性检查 第三章 处理机调度与死锁 (3)P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：Request4(3,3,0)Need4(4,3,1);Request4(3,3,0)Available(2,3,0)，让P4等待。(4)P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查：Request0(0,2,0)Need0(7,4,3);Request0(0,2,0)Available(2,3,0);系统暂时先假定可为P0分配资源，并修改有关数据，如图 3-18 所示。第三章 处理机调度与死锁 图 3-18 为P0分配资源后的有关资源数据 第三章 处理机调度与死锁 3.8 死锁的检测与解除死锁的检测与解除 3.8.1 死锁的检测死锁的检测 1.资源分配图资源分配图(Resource Allocation Graph)图 3-19 每类资源有多个时的情况 第三章 处理机调度与死锁 (2)凡属于E中的一个边eE，都连接着P中的一个结点和R中的一个结点，e=pi,rj是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e=rj,pi是资源分配边，由资源rj指向进程pi,它表示把一个单位的资源rj分配给进程pi。第三章 处理机调度与死锁 2.死锁定理死锁定理 图 3-20 资源分配图的简化 第三章 处理机调度与死锁 3.死锁检测中的数据结构死锁检测中的数据结构 (1)可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。(2)把不占用资源的进程(向量Allocation=0)记入L表中，即LiL。(3)从进程集合中找到一个RequestiWork的进程，做如下处理：将其资源分配图简化，释放出资源，增加工作向量Work=Work+Allocationi。将它记入L表中。第三章 处理机调度与死锁 (4)若不能把所有进程都记入L表中，便表明系统状态S的资源分配图是不可完全简化的。因此，该系统状态将发生死锁。Work=Available;L=Li|Allocationi=0Requesti=0 for all Li L do begin for all RequestiWork do begin Work=Work+Allocationi;LiL;end end deadlock =(L=p1,p2,pn);第三章 处理机调度与死锁 3.8.2 死锁的解除死锁的解除(1)剥夺资源。(2)撤消进程。为把系统从死锁状态中解脱出来，所花费的代价可表示为：R(S)min=minCui+minCuj+minCuk+第三章 处理机调度与死锁 图 3-21 付出代价最小的死锁解除方法 第三章 处理机调度与死锁 作业1：假定一个处理机上执行的作业如下：作业提交时间短暂时间段长度优先数 1 0 7 3 2 1 4 1 3 2 2 6 4 3 1 4 5 3 5 2 且规定优先数大优先级别高。试分别用先来先服务，时间片（时间片为2），短作业优先，非抢占优先调度算法调度这些作业，并计算它们的平均周转 时间。第三章 处理机调度与死锁 作业2：设有三个作业，它们到达系统的时间和计算时间如下：J1：8：00到达 计算时间 2个小时J2：8：30到达 计算时间1个小时J3：9：30到达 计算时间0.5小时系统按单道方式运行，采用响应比高者优先调度，在9：30开始调度时，试写出作业调度次序。