《3处理机调度与死锁培训教材》由会员分享，可在线阅读，更多相关《3处理机调度与死锁培训教材（111页珍藏版）》请在金锄头文库上搜索。
1、第三章 处理机调度与死锁,3.1 处理机调度的基本概念 3.2 作业调度 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除,3.1 处理机调度的基本概念,3.1.1 高级、中级和低级调度,处理器调度分为三级： 高级调度（作业调度）（长程调度） 中级调度（中期调度） 低级调度（进程调度）（短程调度）,按某种原则从后备状态挑选作业调入内存运行 为作业创建进程 为选中作业分配资源,1. 高级调度(Low Level Scheduling),3.低级调度 按某种原则将处理机分配给就绪进程。 进程调度属操作系统内核，执行频率很高。 进
2、程调度是最基本的一种调度，它可以采用非抢 占方式或抢占方式。,1) 非抢占方式(Non-preemptive Mode) 在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个： 正在执行的进程执行完毕， 或因发生某事件而不能再继续执行； 执行中的进程因提出I/O请求而暂停执行； 在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。,2) 抢占方式(Preemptive Mode),抢占的原则有：,优先权原则。 (2) 短作业(进程)优先原则。 (3) 时间片原则
3、。,4.处理机三级调度关系,新建,就绪挂起,阻塞挂起,就绪,阻塞,运行,退出,长程调度,长程调度,中程调度,中程调度,进程调度,调度和进程状态转换,3.1.2 调度队列模型,1. 仅有进程调度的调度队列模型,仅具有进程调度的调度队列模型,2. 具有高级和低级调度的调度队列模型,具有高、低两级调度的调度队列模型,就绪队列的形式。 (2) 设置多个阻塞队列。,图 3-2 示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面。,3. 同时具有三级调度的调度队列模型,具有三级调度时的调度队列模型,3.2.1作业调度的职能,记录已进入系统的作业情况JCB 调度算法：按照某种
4、调度算法从后备状态挑选作业运行。 运行准备：为选中作业创建进程，分配主存和外设。 结束善后处理：收回资源，输出必要信息。,作业进入后备状态建立 作业退出系统时撤消,3.2作业调度,3.2.2作业控制块,作业存在唯一标志 作业调度的依据 记录作业的有关信息，反映作业运行情况 内容,进入系统时建立 退出系统时撤消,作业名 资源要求 资源使用情况 类型说明 状态,3.2.3 调度性能的衡量,平均周转时间： 作业k Tk=Tck-Tsk =T等待+T运行 平均周转时间T=1/nTk 带权周转时间： 作业k Wk=Tk/TRk 平均带权周转时间W=1/n Wk,K=1,n,K=1,n,Tck：作业K完成
5、时间 Tsk：作业K提交时间 TRk：作业K运行时间,3.2.4选择调度方式和调度算法的若干准则,1. 面向用户的准则,周转时间短。 响应时间快。 (3) 截止时间的保证。 (4) 优先权准则。,2. 面向系统的准则,系统吞吐量高。 (2) 处理机利用率好。 (3) 各类资源的平衡利用。,3.3 调 度 算 法,先进先服务调度算法 短作业优先调度算法 高优先权优先调度算法 最高响应比优先 时间片轮转调度算法 最短剩余时间优先调度算法 均衡法 多级反馈队列调度算法,3.3.1先来先服务调度算法,其原则按照作业到达系统或进程进入就绪队 列先后次序来选择。 FIFO是一种非抢占算法。,例题,进程 到
6、达时间 服务时间 优先数 1 0 3 2 2 2 6 5 3 4 4 3 4 6 5 6 5 8 2 1,作业1 作业2 作业3 作业4 作业5 0 3 9 13 18 20 T=1/5（3+7+9+12+12）=8.60 W=1/5（1+1.17+2.25+2.40+6.00）=2.56,特点:吞吐量不定、耗费最小、无饥饿、对偏重 于I/O进程不利，响应时间很高，尤其是进程执 行时间变化很大时,3.3.2 短作业(进程)优先调度算法,短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法，是从后备队列中选
7、择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。,作业1 作业2 作业5 作业3 作业4 0 3 9 11 15 20 T=1/5（3+7+11+14+3）=7.60 W=1/5（1+1.17+2.75+2.80+1.50）=1.84,SJ(P)F调度算法也存在不容忽视的缺点： (1) 该算法对长作业不利， 更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来
8、的)短作业(进程)，将导致长作业(进程)长期不被调度。 (2) 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。 (3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。,特点：吞吐量高、 能提供较好的响应时间，对 长进程不利、可能产生饥饿,3.3.3 高优先权优先调度算法,选择优先级高的进程和作业作为调度对象。 按抢占与否优先数可分： 非抢占的优先调度算法 可抢占的优先调度算法 按静态，动态优先数可分： 静态优先数 动态优先数,1）非抢占式优先权算法 在这种
9、方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成； 或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。,2) 抢占式优先权调度算法 在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i时，就将其优先权Pi与正在执行
10、的进程j的优先权Pj进行比较。如果PiPj，原进程Pj便继续执行；但如果是PiPj, 则立即停止Pj的执行，做进程切换，使i进程投入执行。显然，这种抢占式的优先权调度算法，能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中， 以及对性能要求较高的批处理和分时系统中。,3) 静态优先权 静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，07或0255中的某一整数， 又把该整数称为优先数。只是具体用法各异：有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相反。,确定进程优先权的依据有如下三个
11、方面： 进程类型。 (2) 进程对资源的需求。 (3) 用户要求。,4) 动态优先权 动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。当采用抢占式优先权调度算法时，如果再规定当前进程的
12、优先权以速率b下降，则可防止一个长作业长期地垄断处理机。,非抢占的优先调度,作业1 作业2 作业4 作业3 作业5 0 3 9 14 18 20 T=1/5（3+7+14+8+12）=8.8 W=1/5（1+1.17+3.5+1.6+6）=2.85,3.3.4高响应比优先调度算法,优先权的变化规律可描述为：,由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：,(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。 (2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，
13、因而它实现的是先来先服务。 (3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机。,作业1 作业2 作业3 作业5 作业4 0 3 9 13 15 20 T=1/5（3+7+9+14+7）=8.00 W=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
14、 作业4 0 3 7 11 15 17 19 20 T=1/5（3+15+7+14+11）=10.00 W=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 4 0 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
15、/O的进程有不同的处理结果，可以 采用虚拟时间片轮转(VRR)策略来避免这个问题。 新加入的特性是附加一个FCFS策略队列来收集从 I/O等待中释放的进程。,特点：吞吐量在时间片小的时候可能很低，对所 有进程公平对待、特别是短进程提供好的响应时 间，无饥饿,3.3.6最短剩余时间优先调度算法,最短剩余时间：从作业当前运行到完成所需时间。 最短剩余时间优先调度是抢占算法。 用于分时系统 其轮转时间最优,作业1 作业2 作业3 作业5 作业2 作业4 0 3 4 8 10 15 20 T=1/5（3+13+4+14+2）=7.20 W=1/5（1.00+2.17+1.00+2.80+1.00）=1
16、.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 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 T=1/5（4+18
