1、6.2Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n基本概念基本概念n调度准则调度准则n调度算法调度算法n多处理器调度多处理器调度n实时调度实时调度n算法评估算法评估n总结总结6.3Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005nCPU调度（进程调度）是多任务操作系统的基础。调度（进程调度）是多任务操作系统的基础。n通过多道程序设计得到通过多道程序设计得到CP
2、U的最高利用率的最高利用率nCPU-I/O脉冲周期脉冲周期(CPUI/O Burst Cycle)-进程的执行包括进程在进程的执行包括进程在CPU上执行和等待上执行和等待I/O6.4Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,20056.5Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,20056.6Silberschatz,Galvin and Gagne 2005Opera
3、ting System Concepts 7th Edition,Feb 8,2005n选择内存中的就绪进程，并分配选择内存中的就绪进程，并分配CPU给其中之一给其中之一nCPU调度可能发生在当一个进程调度可能发生在当一个进程:1.从运行转到等待从运行转到等待.2.从运行转到就绪从运行转到就绪.3.从等待转到就绪从等待转到就绪.4.终止运行终止运行.n发生在发生在1、4两种情况下的调度称为非抢占式调度两种情况下的调度称为非抢占式调度(nonpreemptive).n其他情况下发生的调度称为抢占式调度其他情况下发生的调度称为抢占式调度(preemptive).6.7Silberschatz,Ga
4、lvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n进程调度进程调度(分派程序分派程序)模块负责将对模块负责将对CPU的控制权转交给由的控制权转交给由CPU调度调度程序，包括程序，包括:l切换上下文切换上下文l切换到用户态切换到用户态l跳转到用户程序的适当位置并重新运行之跳转到用户程序的适当位置并重新运行之n调度时间、分派延迟调度时间、分派延迟(Dispatch latency)调度程序终止一个进程调度程序终止一个进程的运行并启动另一个进程运行所花的时间的运行并启动另一个进程运行所花的时间.6.8Silbers
5、chatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005nCPU利用率利用率 使使CPU尽可能的忙碌尽可能的忙碌n吞吐量吞吐量 单位时间内运行完的进程数单位时间内运行完的进程数n周转时间周转时间 进程从提交到运行结束的全部时间进程从提交到运行结束的全部时间,带权周转时间带权周转时间周转时间周转时间/运行时间运行时间n等待时间等待时间 进程在就绪队列中等待调度的时间片总和进程在就绪队列中等待调度的时间片总和 n响应时间响应时间 从进程提出请求到从进程提出请求到 首次被响应首次被响应而不是输出结果而不是输
6、出结果的的时间段时间段在分时系统环境下在分时系统环境下 6.9Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n最大的最大的CPU利用率利用率n最大的吞吐量最大的吞吐量n最短的周转时间最短的周转时间n最短的等待时间最短的等待时间n最短的响应时间最短的响应时间6.10Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n举例举例:进程进程区间时间区间时间P124P2 3
7、P33 n假定进程到达顺序如下假定进程到达顺序如下:P1,P2,P3 该调度的该调度的Gantt图为图为:n等待时间：等待时间：P1 =0;P2 =24;P3=27n平均等待时间平均等待时间:(0+24+27)/3=17P1P2P324273006.11Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n假定进程到达顺序如下假定进程到达顺序如下 P2,P3,P1.n该调度的该调度的Gantt图为图为:n等待时间等待时间:P1=6;P2=0;P3=3n平均等待时间平均等待时间:(6+
8、0+3)/3=3n比前例好得多比前例好得多n此种结果（护航效果此种结果（护航效果convoy effect）产生是由于长进程先于短进程到达）产生是由于长进程先于短进程到达P1P3P2633006.12Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,20056.13Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n关联到每个进程下次运行的关联到每个进程下次运行的CPU脉冲长度
9、，调度最短的进程脉冲长度，调度最短的进程n两种模式两种模式:l非抢占式调度非抢占式调度 nonpreemptive 一旦进程拥有一旦进程拥有CPU，它的，它的使用权限只能在该使用权限只能在该CPU 脉冲结束后让出脉冲结束后让出.l抢占式调度抢占式调度 Preemptive 发生在有比当前进程剩余时间片更发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度短的进程到达时，也称为最短剩余时间优先调度Shortest-Remaining-Time-First(SRTF).nSJF是最优的是最优的 对一组指定的进程而言，它给出了最短的平均等对一组指定的进程而言，它给出了最短的平均等
10、待时间待时间6.14Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005进程进程到达时间到达时间区间时间区间时间P10.07 P22.04 P34.01 P45.04nSJF(non-preemptive)n平均等待时间平均等待时间=(0+6+3+7)/4=4P1P3P273160P48126.15Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005进程进程到达时间到达时间
11、区间时间区间时间P10.07 P22.04 P34.01 P45.04nSJF(preemptive)n平均等待时间平均等待时间=(9+1+0+2)/4=3P1P3P242110P457P2P1166.16Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,20056.17Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n其长度只能估计其长度只能估计.n可以通过先前的可以通过先
12、前的CPU脉冲长度及计算指脉冲长度及计算指 数均值进行数均值进行:Define 4.10 ,3.burst CPU next the for value predicted 2.burst CPU of lenght actual 1.1nthnnt.1 1nnnt6.18Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,20056.19Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8
13、,2005n =0l n+1=nl近来历史没有影响近来历史没有影响n =1l n+1=tnl只有最近的只有最近的CPU区间才重要区间才重要n如果扩展公式，得到如果扩展公式，得到:n+1=tn+(1-)tn-1+(1-)j tn-j+(1-)n+1 0n由于由于 和和(1-)都小于或等于都小于或等于1，所以后面项的权比前面项的权小，所以后面项的权比前面项的权小6.20Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n每个进程都有自己的优先数每个进程都有自己的优先数整数整数nCPU分
14、配给最高优先级的进程分配给最高优先级的进程假定最小的整数假定最小的整数 最高的优先级最高的优先级.lPreemptive（抢占式）（抢占式）lNonpreemptive（非抢占式）（非抢占式）nSJF是以下一次是以下一次CPU脉冲长度为优先数的优先级调度脉冲长度为优先数的优先级调度.n问题问题 饥饿饥饿 低优先级的可能永远得不到运行低优先级的可能永远得不到运行.n解决方法解决方法 老化老化 视进程等待时间的延长提高其优先数视进程等待时间的延长提高其优先数.6.21Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Ed
15、ition,Feb 8,2005进程进程优先级优先级区间时间区间时间P1310 P211 P332 P441 P525n平均等待时间平均等待时间=(0+5+16+18+1)/4=10P2P3P51160P4618P1196.22Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n每个进程将得到小单位的每个进程将得到小单位的CPU时间时间时间片时间片，通常为，通常为10-100毫毫 秒秒。时间片用完后，该进程将被抢占并插入就绪队列末尾。时间片用完后，该进程将被抢占并插入就绪队列末尾.
16、n假定就绪队列中有假定就绪队列中有n个进程、时间片为个进程、时间片为q,则每个进程每次得到则每个进程每次得到1/n的、不超过的、不超过q单位的成块单位的成块CPU时间，没有任何一个进程的等待时时间，没有任何一个进程的等待时间会超过间会超过(n-1)q单位单位.n特性特性lq 大大 FIFOlq 小小 q相对于切换上下文的时间而言必须足够长，否则将相对于切换上下文的时间而言必须足够长，否则将导致系统开销过大导致系统开销过大.6.23Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005进
17、程进程区间时间区间时间P153 P2 17 P368 P4 24nGantt图如下图如下:n典型的说，典型的说，RR的平均周转时间比的平均周转时间比SJF长，但响应时间要短一些长，但响应时间要短一些.P1P2P3P4P1P3P4P1P3P302037577797117121 134154 1626.24Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,20056.25Silberschatz,Galvin and Gagne 2005Operating System Concepts 7t
18、h Edition,Feb 8,20056.26Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,20056.27Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n就绪队列分为就绪队列分为:l前台前台交互式交互式l后台后台批处理批处理n每个队列有自己的调度算法每个队列有自己的调度算法 前台前台 RR后台后台 FCFSn调度须在队列间进行调度须在队列间进行.l固定优先级调度，即
19、前台运行完后再运行后台。有可能产生饥饿固定优先级调度，即前台运行完后再运行后台。有可能产生饥饿.l给定时间片调度，即每个队列得到一定的给定时间片调度，即每个队列得到一定的CPU时间，进程在给定时间内时间，进程在给定时间内执行；如，执行；如，80%的时间执行前台的的时间执行前台的RR调度，调度，20%的时间执行后台的的时间执行后台的FCFS调度调度6.28Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,20056.29Silberschatz,Galvin and Gagne 2005Op
20、erating System Concepts 7th Edition,Feb 8,2005n进程能在不同的队列间移动；可实现老化进程能在不同的队列间移动；可实现老化.n多级反馈队列调度程序由以下参数定义多级反馈队列调度程序由以下参数定义:l队列数队列数l每一队列的调度算法每一队列的调度算法l决定进程升级的方法决定进程升级的方法l决定进程降级的方法决定进程降级的方法l决定需要服务的进程将进入哪个队列的方法决定需要服务的进程将进入哪个队列的方法6.30Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,F
21、eb 8,20056.31Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n三个队列三个队列:lQ0 时间片为时间片为8毫秒毫秒lQ1 时间片为时间片为16毫秒毫秒lQ2 FCFSn调度调度l新的作业进入新的作业进入FCFS的的Q0队列，它得到队列，它得到CPU时能使用时能使用8毫秒，毫秒，如果它不能在如果它不能在8毫秒内完成，将移动到队列毫秒内完成，将移动到队列Q1.l作业在作业在Q1仍将作为仍将作为FCFS调度，能使用附加的调度，能使用附加的16毫秒，如果毫秒，如果它还不能完
22、成，将被抢占，移至队列它还不能完成，将被抢占，移至队列Q2.6.32Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n多个多个CPU可用时，可用时，CPU调度将更为复杂调度将更为复杂.n多处理器内的同类处理器多处理器内的同类处理器.n负载共享负载共享n对称多处理器对称多处理器(SMP)每个处理器决定自己的调度方案每个处理器决定自己的调度方案.n非对称多处理器非对称多处理器(ASMP)仅一个处理器能处理系统数据结构，这仅一个处理器能处理系统数据结构，这就减轻了对数据的共享需求就减轻
23、了对数据的共享需求6.33Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n硬实时系统硬实时系统(hard real-time)用于实现要求在给定的时间内执行完用于实现要求在给定的时间内执行完关键进程的场合关键进程的场合 n软实时计算软实时计算(soft real-time)当要求临界进程得到比其他进程更高当要求临界进程得到比其他进程更高的优先级时使用的优先级时使用6.34Silberschatz,Galvin and Gagne 2005Operating System Con
24、cepts 7th Edition,Feb 8,2005n局部调度局部调度(Local Scheduling)线程库怎样决定将哪个线程列入有线程库怎样决定将哪个线程列入有效的轻量级进程效的轻量级进程LWPn全局调度全局调度(Global Scheduling)内核怎样决定下一个运行的内核内核怎样决定下一个运行的内核线程线程6.35Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,20056.36Silberschatz,Galvin and Gagne 2005Operating Syst
25、em Concepts 7th Edition,Feb 8,2005n确定性建模法确定性建模法 精确预定作业量，并定义该作业量在每个算法上执精确预定作业量，并定义该作业量在每个算法上执行的情况行的情况n排队模型排队模型n模拟模拟6.37Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,20056.38Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,20056.39Silberscha
26、tz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,20056.40Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005 CPU 调度是多道程序操作系统的基础。通过在进程间切换调度是多道程序操作系统的基础。通过在进程间切换CPU，操，操作系统能够提高计算机的生产效率。本章中，我们介绍了基本调度作系统能够提高计算机的生产效率。本章中，我们介绍了基本调度概念，并展示了多个不同的概念，并展示了多个不同的CPU调度算法。还研究了为特定系统选调度算法。还研究了为特定系统选择算法的问题。择算法的问题。FCFS,SJF,RR,PR和其他调度算法应该为同学们和其他调度算法应该为同学们所掌握。这是第一次接触资源分配和调度，因此理解如何这些算法所掌握。这是第一次接触资源分配和调度，因此理解如何这些算法如何运行很重要的。如何运行很重要的。6.41Silberschatz,Galvin and Gagne 2005Operating System Concepts 7th Edition,Feb 8,2005n P163 5.4 5.5 5.9
