3处理机调度与死锁.ppt

第三章 处理机调度与死锁,3.1 处理机调度的基本概念 3.2 作业调度3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除,3.1 处理机调度的基本概念,3.1.1 高级、中级和低级调度,,处理器调度分为三级：高级调度（作业调度）（长程调度）中级调度（中期调度）低级调度（进程调度）（短程调度）,,按某种原则从后备状态挑选作业调入内存运行为作业创建进程为选中作业分配资源,1. 高级调度(Low Level Scheduling),,2.中程调度 决定哪些作业允许参于竞争处理机资源 作用：起到短期调整系统负荷，以平顺系统 方式：“挂起”，“解挂”3.低级调度按某种原则将处理机分配给就绪进程进程调度属操作系统内核，执行频率很高进程调度是最基本的一种调度，它可以采用非抢占方式或抢占方式1) 非抢占方式(Non-preemptive Mode) 在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个：① 正在执行的进程执行完毕， 或因发生某事件而不能再继续执行； ② 执行中的进程因提出I/O请求而暂停执行；③ 在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。

这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境2) 抢占方式(Preemptive Mode),抢占的原则有：,优先权原则2) 短作业(进程)优先原则 (3) 时间片原则4.处理机三级调度关系,,新建,就绪挂起,阻塞挂起,就绪,阻塞,,,,,,,运行,退出,,,,长程调度,长程调度,中程调度,中程调度,进程调度,调度和进程状态转换,3.1.2 调度队列模型,1. 仅有进程调度的调度队列模型,仅具有进程调度的调度队列模型,2. 具有高级和低级调度的调度队列模型,具有高、低两级调度的调度队列模型,就绪队列的形式 (2) 设置多个阻塞队列图 3-2 示出了具有高、低两级调度的调度队列模型该模型与上一模型的主要区别在于如下两个方面3. 同时具有三级调度的调度队列模型,具有三级调度时的调度队列模型,3.2.1作业调度的职能,记录已进入系统的作业情况JCB调度算法：按照某种调度算法从后备状态挑选作业运行运行准备：为选中作业创建进程，分配主存和外设结束善后处理：收回资源，输出必要信息作业进入后备状态建立作业退出系统时撤消,3.2作业调度,3.2.2作业控制块,作业存在唯一标志作业调度的依据记录作业的有关信息，反映作业运行情况内容,,进入系统时建立退出系统时撤消,,作业名资源要求资源使用情况类型说明状态,3.2.3 调度性能的衡量,平均周转时间： 作业k Tk=Tck-Tsk =T等待+T运行 平均周转时间T=1/nTk带权周转时间： 作业k Wk=Tk/TRk 平均带权周转时间W=1/n Wk,K=1,n,K=1,n,Tck：作业K完成时间Tsk：作业K提交时间TRk：作业K运行时间,3.2.4选择调度方式和调度算法的若干准则,1. 面向用户的准则,周转时间短。

响应时间快 (3) 截止时间的保证 (4) 优先权准则2. 面向系统的准则,系统吞吐量高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进行比较如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi＞Pj, 则立即停止Pj的执行，做进程切换，使i进程投入执行。

显然，这种抢占式的优先权调度算法，能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中， 以及对性能要求较高的批处理和分时系统中3) 静态优先权 静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变一般地，优先权是利用某一范围内的一个整数来表示的，例如，0~7或0~255中的某一整数， 又把该整数称为优先数只是具体用法各异：有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相反确定进程优先权的依据有如下三个方面：进程类型 (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的时间分割成时间片，处于就绪状态的进程轮流获得时间片。

时间片轮转调度算法是抢占算法其调度算法的性能取决于时间片QQ=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等待中释放的进程。