计算机操作系统原理教程第6章 CPU调度

韩都衣舍官方旗舰店

韩都衣舍女装您值得拥有

/

好狗友

/

广东韩都衣舍批发

/

韩都衣舍旗舰店

/

1第6章CPU调度主要内容基本概念调度准则调度算法多处理器调度实时调度算法评估进程调度模型26.1基本概念1、CPU-I/O区间周期进程的观测属性：进程执行由CPU执行和I/O等待周期组成。CPU区间－I/O区间－CPU区间－I/O区间－……－CPU区间通常具有大量短CPU区间和少量长CPU区间2、CPU调度程序当CPU变为空闲时，操作系统必须从就绪队列中选择一个进程来执行，进程选择是由CPU调度程序来执行的，又称为短期调度程序（short-termscheduler）就绪队列可实现为FIFO队列、优先队列、树或无序链表等形式33、可抢占式调度CPU调度决策发生的环境当一个进程从运行状态切换到等待状态当一个进程从运行状态切换到就绪状态当一个进程从等待状态切换到就绪状态当一个进程终止时非抢占（nonpreemptive）调度（1、4情况）可抢占（preemptive）调度（2、3情况）可抢占调度的代价共享数据的不一致性问题影响操作系统内核的设计44、分派程序分派程序负责将CPU的控制交给由短期调度程序所选择的进程，其功能包括：切换上下文切换到用户模式跳转到用户程序的合适位置以重新启动这个程序分派延迟（dispatchlatency）：分派程序停止一个进程而启动另一个进程执行所要花费的时间56.2调度准则常用的调度准则CPU使用率：CPU实际使用时间与总占用时间之比吞吐量：一个时间单元内所完成进程的数量周转时间：从进程提交到进程完成的时间间隔等待时间：在就绪队列中等待所花时间之和响应时间：从提交请求到产生第一响应的时间希望最大化CPU使用率和吞吐量，最小化周转时间、等待时间和响应时间绝大多数情况下，要优化平均度量值有时需要优化最小值或最大值本书使用平均等待时间来度量（有时用平均周转时间）66.3调度算法1、先到先服务调度（first-come,first-served,FCFS）先请求CPU的进程被首先分配到CPU，可用FIFO队列来实现平均等待时间通常相当长非抢占调度例

进程

区间时间P124P23P33P1P2P30242730平均等待时间(0+24+27)/3=17P2P3P103630平均等待时间(0+3+6)/3=372、最短作业优先调度（shortest-job-first,SJF）当CPU可用时，赋给具有最短后续CPU区间（最短下一个CPU区间）的进程；如果两个进程具有同样长度的CPU区间，可使用FCFS调度来处理SJF调度算法最佳，平均等待时间最短困难：如何确定下一个CPU请求的长度指数平均（exponentialaverage）n+1=tn+(1-)n常用于长期调度，短期调度很难实现SJF算法可能是抢占或非抢占的，可抢占SJF调度有时称为最短剩余时间优先（shortest-remaining-time-first）调度8非抢占调度例：进程

区间时间P16P28P37P43抢占调度例：进程

到达时间

区间时间P108P214P329P435P4P1P3P2P1P2P4P1P30391624平均等待时间：(3+16+9+0)/4=7015101726平均等待时间：((10-1)+(1-1)+(17-2)+(5-3))/4=7.7591、设作业J1和J2的运行时间t1<=t2，当采用短作业优先时，调度顺序为J1、J2，平均周转时间为(t1+(t1+t2))/2=(2t1+t2)/2。不采用短作业优先时，调度顺序为J2、J1，平均周转时间为(t2+(t2+t1))/2＝(t1+2t2)/2。显然，得证。2、假设当n=k时成立，则当n=k+1时，J1，J2，……，Jk，Jk+1，它们的运行时间分别为：t1，t2，……，tk，

tk+1。(ti<=

ti+1)当采用短作业优先时，调度顺序为J1，J2，……，Jk，Jk+1，所有作业的平均周转时间为：T=[T1+T2+…+Tk+Tk+1]/n=

[t1+(t1+t2)+…+(t1+t2+…+tk)+(t1+t2+…+tk+tk+1)]/n不采用短作业优先时，假设调度顺序为J1,J2,…,Jk+1,Jk。

所有作业的平均周转时间为：T’=[T1+T2+…+Tk+1+Tk]/n=

[t1+(t1+t2)+…+(t1+t2+…+tk+1)+(t1+t2+…+tk+1+tk)]/n则：T’-T=[(tk+1+tk+1+tk)-(tk+tk+tk+1)]/n=(tk+1-tk)/n>=0。

得证。证明：采用SJF调度算法可以使平均周转时间最少。10补充：最高响应比优先算法响应比R=周转时间/执行时间=（执行时间＋等待时间）/执行时间每次调度前计算响应比，选值最高的调度执行，例：A运行完，计算BCD的响应比：B=(70+50)/50=2.4；C=(60+10)/10=7；D=(10+20)/20=1.5。调度C。C运行完，计算BD的响应比：B=(80+50)/50=2.6；D=(20+20)/20=2。先调度B后调度D。进程提交时间执行时间A8:00120B8:5050C9:0010D9:5020开始时间结束时间等待时间周转时间8:0010:00012010:1011:008013010:0010:10607011:0011:207090平均52.5102.5113、优先权调度（priority-schedulingalgorithm）每个进程都有一个优先权与其关联，具有最高优先权的进程会被分配到CPU。具有相同优先权的进程按FCFS顺序调度低数字表示高优先权优先权定义：内部或外部优先权调度可以是抢占或非抢占优先权调度的一个主要问题：无穷阻塞（indefiniteblocking）或称为饥饿（starvation），即低优先权进程可能无穷等待饥饿的解决方案：老化（aging）即逐渐增加在系统中等待很长时间的进程的优先权，例如UNIX系统中，每秒计算一次优先权：

p_pri=min{127,(p_cpu/16+PUSER+p_nice)}

每过一个时钟嘀嗒加1用户优先权基数调节参数12优先权调度例:进程

区间时间

优先权P1103P211P324P415P552P2P5P1P3P4016161819平均等待时间：(6+0+16+18+1)/5=8.213优先权调度练习进程到达时间CPU区间时间优先级

P1833P2911P31023P41114P51242注：抢占和非抢占两种情况141）抢占式P1P2P1P5P3P4891012161819平均等待时间:[(0+(10-9))+0+(16-10)+(18-11)+0]/5=2.8进程到达时间CPU区间时间优先级

P1833P2911P31023P41114P51242152）非抢占式P1P2P5P3P481112161819平均等待时间:[(0+(11-9))+(16-10)+(18-11)+0]/5=3进程到达时间CPU区间时间优先级

P1833P2911P31023P41114P51242164、轮转法调度（round-robin,RR）类似于FCFS调度，但通过为每个进程分配时间量（timequantum）或称为时间片，增加抢占以在进程间切换CPU调度程序循环就绪队列，为每个进程分配不超过一个时间片间隔的CPU平均等待时间通常相当长RR调度算法是可抢占的性能很大程度上依赖于时间片的大小例(时间片为4ms)：

进程

区间时间P124P23P33P1P2P3P1P1P1P1P1047101418222630平均等待时间:[(0+(10-4))+4+7]/3=5.6617轮转法调度练习（时间片为2、5）进程CPU区间时间

P110P21P32P41P55181）时间片为2P1P2P3P4P5P1P5P1P5P1P1023568101214151819平均等待时间:{[(0+(8-2))+(12-10)+(15-14)]+2+3+5+[6+(14-12)+(10-8)]}/5=5.8进程CPU区间时间

P110P21P32P41P55192）时间片为5P1P2P3P4P5P1056891419平均等待时间:[(0+(14-5))+5+6+8+9]/5=7.4进程CPU区间时间

P110P21P32P41P55205、多级队列调度

（multilevelqueue-schedulingalgorithm）根据进程的某些属性，将其永久的分配到一个队列，每个队列有自己的调度算法队列之间通常采用固定优先权可抢占调度来实现也可以在队列之间划分时间片216、多级反馈队列调度（multilevelfeedbackqueuescheduling）多级队列调度算法中，进程进入系统后，被永久的分配到一个队列，优点是低调度开销，缺点是不够灵活多级反馈队列调度允许进程在队列之间移动，根据不同CPU区间特点以区分进程定义时需要考虑的参数队列数量每个队列的调度算法用以确定何时升级到较高优先权队列的方法用以确定进程何时降级到较低优先权队列的方法用以确定进程在需要服务时应进入哪个队列的方法最通用的CPU调度算法，但也是最复杂的22常用调度算法小结先来先处理（FCFS）——非抢占最短作业优先（SJF）优先权抢占或非抢占时间片轮转（RR）——抢占多级队列多级反馈队列236.4多处理器调度限定同构系统，即处理器功能相同任何可用处理器可用于运行队列内的任何进程通用内存访问（uniformmemoryaccess,UMA）负载分配（loadsharing）为每个处理器提供独立的队列使用一个共同就绪队列针对2）的两种调度方法每个处理器自我调度主－从结构，即选择一个处理器为其他处理器进行调度非对称多处理（asymmetricmultiprocessing）：主服务器246.5实时调度实时计算分为硬实时（hardreal-time）和软实时（softreal-time）实现软实时功能要求系统必须有优先权调度，且实时进程必须有最高的优先权分派延迟必须小为了让分派延迟保持很小，需要允许系统可抢占，实现方法有在长时间系统调用内插入抢占点（preemptionpoint）－内核安全位置使整个内核可抢占－同步机制保护内核数据结构254、实时调度策略优先级+时间片轮转调度：获得秒级的响应时间基于优先权的非抢占调度：数秒~数百毫秒级的响应时间基于优先权的固定点抢占调度：数十毫秒级基于优先权的立即抢占调度：获得毫秒级的响应时间时限调度算法时限要求最近的任务优先占用处理机最少裕度调度算法：选择裕度（laxity）最少的进程执行裕度=截止时间-(就绪时间+计算时间)266.7进程调度模型Solaris2：基于优先级的、可抢占的进程调度Windows2000：基于优先权的、可抢占的调度算法Linux分时：优先权的、基于信用度的调度算法实时：先到先处理（FCFS）和轮转（RR）每一次定时器中断，信用减1，当信用减为0时，暂停该进程，其它进程抢占若无可运行进程有信用，重新计算所有进程的信用：信用=信用/2+优先级每次调度选择信用多的进程27综合练习题进程到达时间CPU区间时间优先级

P10202P25153P31051P415104

FCFS、SJF（抢占、非抢占）、优先级（抢占、非抢占）、RR（时间片＝5）281、FCFSP1P2P3P4020354050平均等待时间:[0+(20-5)+(35-10)+(40-15)]/4=65/4=16.25进程到达时间CPU区间时间优先级

P10202P25153P31051P415104292、SJF（非抢占）P1P3P4P2020253550平均等待时间:[0+(35-5)+(20-10)+(25-15)]/4=50/4=12.5进程到达时间CPU区间时间优先级

P10202P25153P31051P415104302、SJF（抢占）P1P3P1P4P201015253550平均等待时间:[(0+(15-10))+(35-5)+(10-10)+(25-15)]=45/4=11.25进程到达时间CPU区间时间优先级

P10202P25153P31051P415104313、优先级（非抢占）P1P3P2P4020254050平均等待时间:[0+(25-5)+(20-10)+(40-15)]/4=55/4=13.75进程到达时间CPU区间时间优先级

P10202P2