《四章调度.ppt》由会员分享，可在线阅读，更多相关《四章调度.ppt（24页珍藏版）》请在三一文库上搜索。
1、第4章 调 度,操作系统中离不开调度。所谓调度，就是选出待分派的作业或进程。 处理机调度分为作业调度（高级调度）、进程挂起与对换（中级调度）和进程调度（低级调度）三级。,4.1 调 度 类 型,一般来说，作业从进入系统到最后完成，可能要经历三级调度： 高级调度、中级调度和低级调度。这是按调度层次进行分类的。,4.2 作 业 调 度,4.2.1 作业状态 提交状态。 后备状态。 执行状态。 完成状态。,4.2.2 作业控制块和作业调度的功能,记录系统中各个作业的情况 按照某种调度算法从后备作业队列中挑选作业。 为选中的作业分配内存和外设等资源。 为选中的作业建立相应的进程，并把该进程放入就绪队列
2、中。 作业结束后进行善后处理工作。 3常用作业调度算法 先来先服务法（First-Come First-Served），短作业优先法（Shortest Job First）和最短剩余时间优先法（Shortest Remaining Time Next）。,4.3 进 程 调 度,4.3.1 进程调度的功能 （1）保存现场 （2）挑选进程 （3）恢复现场,4.3.2 进程调度的时机, 创建进程。 进程终止。 等待事件。 中断发生。 运行到时。,4.3.4 交互式系统中常用的调度算法,轮转法 优先级法 多级队列法 短进程优先法 高响应比优先法 多级反馈队列法 公平共享法等,4.3.5 两级调度模型
3、,作业调度是宏观调度 进程调度是微观调度,图4-3 两级调度简化队列图,4.4.2 调度性能评价准则,1CPU利用率 2吞吐量 3周转时间 从作业提交到作业完成的时间间隔就是周转时间。 Ti= tci - tsi tsi表示作业i的提交时间 tci表示作业i的完成时间。,4.4.2 调度性能评价准则,系统中n个作业的平均周转时间为： 带权周转时间W W = T/R W =T为周转时间，R为实际运行时间。 平均带权周转时间： 4就绪等待时间 5响应时间,4.5 调 度 算 法,4.5.1 先来先服务法 排队买票 设有三个作业，编号分别为1, 2, 3。各作业分别对应一个进程。各作业依次到达，相差
4、一个时间单位。,图4-4 先来先服务调度算法示意图,表4-1 FCFS调度算法性能,所谓作业的长短是指作业要求运行时间的多少。当分派CPU时，SJF算法就把CPU优先分给最短的作业。 例如，考虑表4-2给出的一组作业（它们同时提交到系统）。,4.5.2 短作业优先法,表4-2 一组作业列表,4.5.2 短作业优先法,采用短作业优先法在实现上有困难。 这种算法的一个缺点是对长作业很不利。,图4-5 作业执行顺序,图4-6 短作业优先法执行情况,4.5.3 最短剩余时间优先法,当新进程加入就绪队列时，如果它需要的运行时间比当前运行的进程所需的剩余时间还短，则执行切换。,图4-7 最短剩余时间优先法
5、调度结果,表4-3 进程列表,4.5.4 优先级法,优先级调度算法是从就绪队列中选出优先级最高的进程，让它在CPU上运行。 非抢占式优先级法。 抢占式优先级法。 一般来说，进程优先级可由系统内部定义或由外部指定。 确定进程优先级的方式有静态方式和动态方式两种。 静态优先级是在创建进程时就确定下来的，而且在进程的整个运行期间保持不变。 优先数 本书采用“优先数小、优先级高”的表示方式。 动态优先级是随着进程的推进而不断改变的。,4.5.4 优先级法,表4-4 一组进程列表,图4-8 优先级调度算法执行顺序,4.5.5 轮转法,时间片轮转法（Round-Robin, RR）主要用于分时系统中的进程
6、调度。 时间片是一个小的时间单位，通常为10100 ms数量级。,图4-9 轮转法q=1和q=4时进程运行情况,4.5.5 轮转法,表4-5 RR调度算法的性能指标,4.5.5 轮转法,进程的周转时间也依赖于时间片的大小。,图4-10 平均周转时间随时间片的变化,4.5.5 轮转法,时间片的长短通常由以下四个因素确定： 系统的响应时间。 就绪队列进程的数目。 进程的转换时间。 CPU运行指令速度。,4.5.6 多级队列法,多级队列（Multilevel Queue）调度算法把就绪队列划分成几个单独的队列（见图4-11），一般根据进程的某些特性，如占用内存大小、进程优先级和进程类型，永久性地把各个进程分别链入不同的队列中，每个队列都有自己的调度算法。,图4-11 多级队列调度,4.5.7 多级反馈队列法,图4-12 多级反馈队列调度算法, 系统中设置多个就绪队列，每个队列对应一个优先级。 各就绪队列中进程的运行时间片不同，高优先级队列的时间片小，低优先级队列的时间片大。 新进程进入系统后，先放入第1个队列的末尾。 系统先运行第1个队列中的进程 这种调度算法基于抢占式，使用动态优先级机制。,4.5.8 高响应比优先法,高响应比优先法是一种非抢占方式。它为每个进程计算一个响应比RR： RR=W+S/S w是进程等待处理机所用的时间；s是进程要求的服务时间。,