第14讲 第4章 处理机调度.ppt

1、,DOS,Windows9X,WindowsNT,Linux,UNIX,WindowsCE,第4章 处理机调度,主讲：曾孝文,本课程内容,第1章 绪论 第2章 操作系统用户界面 第3章 进程管理 第4章 处理机调度 第5章 存储管理 第8章 文件系统 第9章 设备管理,进程调度的算法较多，在设计进程调度算 法时应考虑的因素多，比如：尽量提高资源利 用率，减少处理机的空闲时间，对于用户作业 要较合理的平均响应时间，以及尽可能地增强 CPU的处理能力。,选择调度算法时应考虑的问题,4.4 调度算法,基本要求： 算法应尽可能简单、不让进程长久等待。,一. FCFS(先来先服务调度算法) 最简单的调度

2、原则是先进先出(FIFO) 就绪队列,A,B,C,D,CPU,完成,根据进程到达就绪队列的时间来分配中央处理机，一旦一个进程获得了中央处理机，就一直运行到结束，先来先服务是非剥夺调度。 这种调度从形式上讲是公平的，但它使短作业要等待长作业的完成，重要的作业要等待不重要作业的完成。从这个意义上讲又是不公平的。 先进先出调度使响应时间的变化较小，因此它比其它大多数调度都可预测。由于这种调度方法不能保证良好的响应时间，在处理交互式用户时很少用这种方法。,在当今系统中，先进先出很少作为调度 模式，而是常常嵌套在其它的调度模式中。 例如，许多调度模式根据优先级将处理机分 配给进程，但具有相同优先级的进程

3、却按先 进先出进行分配。,关于平均周转时间和平均带权周转时间的计算与作业中的FCFS的计算一样。,先来先服务(FCFS)算法,先来先服务(FCFS)算法,该算法总是把处理机分配给最先进入就绪队 列的进程，一个进程一旦分得处理机，便执行 下去，直到该进程完成或阻塞时，才释放处理 机。 优点:实现简单。 缺点:没考虑进程的优先级。,二. 循环轮转调度算法 目的：让所有的进程，均衡地使用CPU。 方法： 当CPU空闲时，选取就绪队列首元素，赋予一个时间片，当时间片用完时，该进程转为就绪态并进入就绪队列的末端。 问题：时间片如何定？ (1) 简单循环轮转调度(时间片 q 固定) 即：就绪队列中的所有进

4、程，等速度向前推进。,ti,ti+1,当前的响应时间 : t i=q * n i (n i为当前进程数) ,p1,p1,p4,即：响应时间 t 是变化的，它即随进程数而变化，又受到时间片的影响。 那么时间片应选多大才合适呢？ 时间片q的确定： 设t为响应时间，n为进程数，由tqn 有： q=tmax/n =3000ms/(6 60)= 50 500 ms 问题：q选定后，响应时间是变化的。 太长，用户不满意；太短，浪费切换时间。 例如：设q=0.1秒 当ni=30时： ti=3秒 当nj=3时： tj=0.3秒 ,即：响应时间 t 是变化的，它即随进程数而变化，又受到时间片的影响。,当时间片很

5、大时，每个进程得到比完成该进程多的处理机时间，此时轮转调度模式退化为先进先出模式。 当时间片非常小时，上下文切换开销就成了决定因素，系统性能降低，大多数时间都消耗在处理机的转换上，只有少许用在用户的计算上。,分时系统中常用时间片轮转法,时间片选择问题： 固定时间片 可变时间片 与时间片大小有关的因素(q=tmax/n) 系统响应时间 就绪进程个数 CPU能力,(2)可变时间片循环轮转调度(响应时间T固定) 响应时间T固定为用户所能接受的时间(如3秒)。 每一轮开始前，根据当前的就绪进程数Ni，预先决定该轮的时间片Qi 。即： 不同轮的时间片可能不同；同一轮中各进程的时间片相同。 Qi =T/

6、Ni,进一步的问题：能否同时又考虑进程的优先权呢？ ,P4 P1 P2 P3,P4(等下一轮),3.多重时间片循环轮转调度算法,是优先数和循环轮转调度算法的综合。 根据优先数的分布采用多个就绪队列，进程按优先数 排在相应的就绪队列中。,Windows NT采用类似的结构；UNIX的思想也与此类似。 例： UNIX的进程调度 ,1)简单轮转法的调度模型,2)多队列反馈调度算法,将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间片越小，级别越小，时间片越长，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，.当运行进程用完一个

7、时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列,* 首先系统中设置多个就绪队列； * 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大； * 各个队列按照先进先出调度算法； * 一个新进程就绪后进入第一级队列； * 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列； * 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾； * 当第一级队列空时，就去调度第二级队列，如此类推； * 当时间片到后，进程放弃CPU，回到下一

8、级队列。,多队列反馈调度算法,三.进程优先数调度算法 预先确定各进程的优先级(通常用优先数表示)，系统总是把处理机分配给优先级最高的就绪进程。 .优先数的形式 静态优先数：在进程被创建时按某种策略确定，且在整个进程的运行期间不再改变。 动态优先数：在进程被创建时先给出一个初始的优先数(也称为基本优先数)，而在进程运行中的一些关键时刻，再按某种策略进行调整。 ,2.优先数的确定 基本的策略：占用CPU时间少的进程优先。 静态优先数的确定 根据作业所需使用的资源来估计 (多者优先，为什么？) 根据作业的运行时间来估计 由用户提出 优点：简单，系统开销小。 问题：不准确、不灵活。 , 动态优先数的确

9、定 在进程运行期间，优先数可以改变。常用的策略有： (1)对CPU的时间进行估算，占用少的进程优先。 一种可行的公式为： k n+1 = a * t n + (1 - a) * k n 其中： k n ：本次估计的CPU占用时间 (即本次分配的时间片) t n ：本次实际的CPU占用时间 a 的取值通常为： a = 1： k n+1 = t n 为上一次的实际占用时间 a = 0： k n+1 = k n 估计时间不变(时间片固定) a = 1/2: k n+1 =(k n + t n ) / 2 取平均值 ,(2)因设备请求放弃CPU而等待的进程，唤醒后 优先提高。以提高设备的利用率。 因时

10、间片到而被剥夺CPU的进程，应如何处理呢？ (3) 进程使用CPU超过一定时间后，降低优先级 优先级分配存在的问题： 有的进程可能会长时间等待。 ,四. 短进程优先调度算法 (1) 策略：按进程运行的时间长短进行调度。 (2) 特点： 易实现，系统吞吐量高。 只照顾短进程，而没有考虑长进程的利益。 (3) 讨论周转时间与带权周转时间 进程 提交时间 执行时间 开始时间 完成时间 周转时间 带权周转时间,8.00 9.10 1.10 1 9.10 9.40 0.40 1.33,问题： 长进程可能会饿死。如何解决呢？,1 8.00 .10 2 8.50 0.50 3 9.00 0.30 4 9.5

11、0 0.10,平均周转时间 t = 0 . 825 平均带权周转时间 w = 2 . 532,9.40 9.90 1.40 2.8,9.90 10.00 0.50 5,1.下表给出作业1，2，3的到达时间和运行时间。采用FCFS和SJF调度算法，试问平均周转时间各为多少？是否还有更好的调度策略存在？,1.【解答】 FCFS：10.53 SJF：9.53 未来知识调度（FKS）:6.86,2.一批五个作业A、B、C、D、E几乎同时到达一个计算中心，其运行时间分别为10、6、2、4、8分钟，优先数分别为3、5、2、1、4。对下列每种调度算法，确定诸作业平均周转时间（相互间切换不计开销，都不考虑I/

12、O）： RR(每个时间片为1分钟） 优先级 FCFS SJF,2.【解答】 RR 21.2分钟 优先级 16分钟 FCFS 19.2分钟 SJF 14分钟,思考题：,3.某多道程序设计系统配有一台处理器和两台外设IO1、IO2，现有3个优先级由高到低的作业J1、J2和J3都已装入了主存，它们使用资源的先后顺序和占用时间分别是： J1:IO2(30ms),CPU(10ms),IO1(30ms),CPU(10ms). J2:IO1(20ms),CPU(20ms),IO2(40ms). J3:CPU(30ms),IO1(20ms). 处理器调度采用可抢占的优先数算法，忽略其他辅助操作时间，回答下列问题： （1)分别计算作业J1、J2和J3从开始到完成所用的时