第05讲_进程调度.ppt

1、2.6 进程调度,在多道系统当中，往往有多个进程同时在内存中运行。在任何时刻，一个进程只可能是以下三种状态之一： 运行状态：该进程正在CPU上运行，每个CPU 上最多只能有一个进程在运行； 就绪状态：进程已经就绪，随时可以运行； 阻塞状态：如在某个信号量上被阻塞，等待I/O,与此相对应，操作系统会维护相应的状态队列。,就绪队列和各种I/O设备队列,（本图摘自Silberschatz, Galvin and Gagne： “Operating System Concepts”）,在操作系统中，负责去做这个选择的那 部分程序，称为调度程序(scheduler)； 调度程序在决策过程中所采用的算法，

2、 称为是调度算法； 调度程序是CPU资源的管理者； 调度的对象是进程，也可以是线程，大 多数的调度问题对两者都是适用的。,2.6.1 关于调度的若干问题,1. 要解决的问题,WHEN：何时分配CPU 调度的时机 WHAT：按什么原则分配CPU 调度算法 HOW： 如何分配CPU 进程的上下文切换,2. 进程的行为,进程的执行过程：CPU执行（CPU burst）和等待I/O操作（I/O burst）交替进行。,fpResult = fopen(szResult, w); if(fpResult=NULL) printf(“cant open file); flag = 0; while(1)

3、str10 = 0; fgets(str1, MAX_LEN, fpOut); if(str10 = 0) str20 = 0; fgets(str2, MAX_LEN, fpStd); if(str20 = 0) flag = 1;break; .,CPU繁忙（CPU-bound）的进程：大部分时间 处于运行和就绪状态； I/O繁忙（I/O-bound）的进程：大部分时间处 于阻塞状态。,CPU繁忙与I/O繁忙,CPU繁忙,I/O繁忙,while(ch != EOF) putchar(ch); ch = fgetc(fp); ,内部因素：进程自身的功能决定了它的各种工作量。例如，矩阵相乘进程

4、的计算量大，文件管理进程的I/O需求很大； 外部因素：计算机系统的运行速度决定了完成这些工作量所需要的时间长短。工作量和工作时间是两回事，判断一个进程是属于CPU繁忙还是属于输入输出繁忙，主要看它的计算时间和输入输出时间； I/O设备的运行速度较慢，CPU的运行速度较快，而且更新换代的速度快，将来进程都趋向于I/O繁忙。,CPU繁忙还是I/O繁忙？,VCD播放软件； WORD文字编辑器； 磁盘碎片整理工具defrag。,CPU繁忙还是I/O繁忙？（续）,3. 何时调度？,当一个新的进程被创建时，是执行新进程还是继续执行父进程？ 当一个进程运行完毕时； 当一个进程由于I/O、信号量或其他的某个原

5、因被阻塞时； 当一个I/O中断发生时，表明某个I/O操作已经完成，而等待该I/O操作的进程转入就绪状态； 在分时系统中，当一个时钟中断发生时。,不可抢占调度方式：一个进程若被选中，就一直运行下去，直到它被阻塞（I/O，或正在等待其他的进程），或主动地交出CPU。以上的情形13均可发生调度； 可抢占调度方式：当一个进程在运行时，调度程序可以打断它。以上的情形15均可发生调度，另外，在其他的一些情形下，如就绪队列中有进程的优先级高于当前运行进程的优先级，也可能立即进行调度。,两种调度方式,4. 调度算法的类别,不同的OS有不同的目标，对调度程序有不同的 要求，因此需要不同类型的调度算法。 批处理系

6、统：无须及时的用户响应，采用不可抢占的调度方式，或时间间隔很长的可抢占调度方式，从而允许进程能长时间运行，减少进程的切换次数，提高系统的性能； 交互式系统：及时的用户响应非常重要，必须采用可抢占的调度方式。以防单个进程占用太多CPU时间，影响到其他进程的运行。 实时系统：对响应时间要求苛刻，每个进程运行时间很短，可采用可抢占的调度方式。,5. 调度算法的目标,算法调度的目标是多元的，有些是可以共存的， 也有些是相互牵制的，对于一个实际的调度算法 来说，有一个综合权衡的过程。,所有系统普遍适用的目标： 公平：每个进程都能进展，不会“饥饿”； 对已制订的调度策略必须能贯彻执行； 均衡：尽可能使整个

7、系统的各部分都忙起来， 提高系统资源的使用效率。,用户关心的评价指标： 周转时间（Turnaround time）：一个作业从提交到完成（得到结果）所经历的时间。包括：在CPU上执行，在就绪队列和阻塞队列中等待，结果输出等待； 平均周转时间：一批作业的周转时间的平均值； 平均带权周转时间：权值是实际执行时间的倒数; 等待时间（Waiting Time）：在就绪队列中的等待时间。 响应时间（Response Time）：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间。响应时间越短越好，优先考虑交互式进程。,周转时间：,（Ei表示作业i完成时间， Si表示作业i提交时间）,平均周

8、转时间：,(N表示作业的个数),平均带权周转时间：,(ri表示作业i的实际执行时间),系统关心的评价指标（考虑系统各部分的利用率） 吞吐量（Throughput）：单位时间内所完成的作业数，与作业本身特性和调度算法有关； CPU的利用率：大中型主机的CPU较贵，所以要让它时刻不停地转着。 各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙的作业搭配。,2.6.2 批处理系统中的调度算法,1. 先来先服务,先来先服务（First Come First Served，FCFS；First In First Out，FIFO）：按照作业到达的先后次序进行调度； 不可抢占方式：当前进程一直占用CPU，

9、直到执行完或被阻塞，才让出CPU给另一个进程； 在进程被唤醒后（如I/O完成），并不立即恢复执行，而是放在就绪队列的末尾； 优点：简单、公平，易于理解也易于实现。现实生活中应用广泛：排队。,问题1. 平均周转时间取决于各作业到达的顺序，若短作业位于长作业之后，将增大平均周转时间。,例如，三个作业A、B、C的运行时间为24、3、3,问题2. 无法充分利用CPU繁忙的作业与I/O繁忙的作业之间的互补关系。如果CPU繁忙的作业独占很长时间的CPU，使得I/O设备空闲，也使得I/O繁忙的作业无法运行。,2. 短作业优先,短作业优先（Shortest Job First，SJF），设计 目标是改进FCF

10、S算法，减少平均周转时间； SJF算法要求作业在开始执行时预计执行时间， 对预计执行时间短的作业优先分派处理器； 两种实现方案： 不可抢占方式：当前作业在运行时不会被打 断，只有运行完毕或阻塞时，才让出CPU； 可抢占方式：如果一个新的短作业到来，其 运行时间小于当前正在运行作业的剩余时间， 则抢占CPU运行，称为SRTF（Shortest Remaining Time First）。,可以证明：对于一组同时到达的作业，采用SJF 算法将得到一个最小的平均周转时间。,D,时间,A,C,a a+b a+b+c a+b+c+d,例如，考察4个作业A、B、C、D，其运行时间分别为a、b、c、d,B,

11、A、B、C、D的周转时间分别为a、a+b、a+b+c和 a+b+c+d，因此平均周转时间为：(4a+3b+2c+d)/4 显然，当a b c d时，平均周转时间最小。,是否万事大吉了？,取得最优解的前提之一：这组作业必须同时到达；,例如：,SJF（不可抢占）：,P1,P3,P2,P4,0,3,7,8,12,16,平均周转时间：(7 + 10 + 4 + 11) / 4 = 8 平均等待时间：(0 + 6 + 3 + 7) / 4 = 4若按P2,P3,P4,P1顺序, 平均周转和等待时间7.75, 3.75,进程,到达时间,运行时间,P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0

12、 4,SJF（可抢占）：,P1,P3,P2,P4,P2,P1,0,2,7,4,11,16,5,平均周转时间：(16 + 5 + 1 + 6) / 4 = 7 平均等待时间：(9 + 1 + 0 + 2) / 4 = 3,前提条件之二：需要事先估计作业的运行时间,如何知道作业的运行时间？,该时间只可能是一个估计值； 让提交该作业的用户来提供。不太实用； 使用前面的CPU运行时间来预测后面的CPU运 行时间，通过过去的行为来预测将来的行为。 如果一个作业已经运行很长时间了，那它可能 还会运行更长的时间； 使用指数平均值函数来预测下一段CPU时间;,2.6.3 交互式系统中的调度算法,1. 时间片轮

13、转法,在时间片轮转算法（Round-Robin，RR）中，将所有的就绪进程按照FCFS原则，排成一个队列； 每次调度时将处理器分派给队首进程，让其执行一小段CPU时间（时间片）； 在一个时间片结束时，如果进程还没有执行完的话，在时钟中断中，进程调度程序将暂停当前进程的执行，并将其送到就绪队列的末尾，然后执行当前的队首进程； 如果一个进程在它的时间片用完之前就已结束或被阻塞，那么立即让出CPU。,开始时，进程B位于队列之首，因此被调度执行。当它的时间片用完后，就把它送到就绪队列的末尾。同时，进程F成为队首进程，被调度运行。,（本图摘自Andrew S. Tanenbaum： “Modern Op

14、erating Systems” ）,Round robin, too.,优点： 公平性：各个就绪进程平均地分配CPU的使用 时间。假设有n个就绪进程，时间片大小为q， 那么每个进程将得到1/n的CPU时间； 活动性：每个进程最多等待(n-1)q时间就能够 再次得到CPU去运行； 一般来说，平均周转时间较SJF算法为长，但 能够得到较短的平均响应时间； 缺点：q的大小难以确定（一般在2050ms）。 q太大：退化为FCFS算法，进程在一个时间片 内执行完或被阻塞，响应时间长。如q=100ms； q太小：每个进程需要更多时间片才能处理完， 进程切换次数增加(1ms)，增大系统开销。如q=4ms,

15、时间片轮转法的特点,进程CPU时间 P153 P2 17 P368 P4 24,一个例子：时间片长度q20,0 20 37 57 77 97 117 121 134 154 162,平均周转时间：,(134 + 37 + 162 + 121) / 4113.5,SJF的平均周转时间：,(94 + 17 + 162 + 41) / 478.5,2. 优先级算法,轮转法有一个缺省的前提，即各进程同等重要； “人人生而平等”？ 恐怕不太现实！同样，并 不是每个进程都同等重要， 怎么办？分等级！ 优先级算法（Priority Scheduling）：给每个进 程设置一个优先级，然后在所有就绪进程中选择

16、 优先级最高的那个进程去运行； SJF就是一个优先级算法，每个进程的优先级是 它的CPU运行时间（时间越短，优先级越高）； 分为可抢占和不可抢占两种方式；各进程优先级 的确定方式可分为静态和动态两种。,静态优先级方式,确定优先级的依据： 进程类型（系统进程优先级高于用户进程，交互式进程高于批处理进程）； 对系统资源的需求（对CPU和内存需求较少的进程，优先级较高）； 用户要求（用户级别和付费情况，如军用电脑、商用电脑）。 静态方式的缺点：高优先级的进程一直占用CPU，低优先级的进程“饥饿”。,静态优先级方式是指在创建进程时确定进程优先级，并保持不变到进程结束。,动态优先级方式,为防“饥饿”,

17、根据运行时间和等待时间调整优先级 进程每执行一个时间片就降低其优先级。当一个进程持续执行时，其优先级降低到让出CPU； 在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行。 为了让I/O忙起来，可提高I/O繁忙进程的优先级。但如何判定一个进程是I/O繁忙的？可把进程优先级设为1/f，f是在上一个时间片中所用的时间比例,动态优先级方式是指在创建进程时赋予给进程的优先级，在进程运行过程中可以动态改变，以便获得更好的调度性能。,优先级类别,（本图摘自Andrew S. Tanenbaum： “Modern Operating Systems”

18、 ）,可以把进程按照不同的优先级别分组，然后在不同级别之间使用优先级算法，而在同一级别的各个进程之间使用时间片轮转法。,优先级反转,T1 优先级高、T2 优先级低 T2 获得了锁 L. 场景 1: T1 试图去获取 L, 失败, 循环等待； T2 无法运行； 场景 2: T1 试图去获取 L, 失败, 被阻塞. T3 进入系统，其优先级高于T2、低于T1。 T2 无法运行。,3. 多级队列算法,多级队列算法（Multilevel Queue）引入多个就绪队列，通过各个队列的区别对待，达到一个综合的调度目标。 根据进程的性质或类型的不同，将就绪队列再分 为若干个子队列，如系统进程、用户交互进程、

19、 批处理进程等； 不同的队列可以有不同的优先级； 不同的队列可以采用各自不同的调度算法，如前 台的交互式进程可采用RR算法，后台的批处理进 程可采用FCFS算法。,在各个队列之间也必须进行调度： 固定优先级调度：按照各种类型的进程的优先 级别从高到低地进行，先运行最高优先级的所 有进程，再运行次一级所有进程，依此类推。 问题：可能导致“饥饿”； 时间片方法：把CPU时间按比例分配给不同的 队列，然后再由各个队列的调度算法去调度， 如80给前台的交互式进程队列（RR算法）， 20给后台的批处理进程队列（FCFS）。,（本图摘自Silberschatz, Galvin and Gagne： “Op

20、erating System Concepts”）,多级队列算法的一个例子,1-20,21-99,100-199,200-255,256-1024,Time slice,100,200,300,400,500,4. 多级反馈队列算法,多级队列算法把每个进程按照它的类型固定在一 个队列中，但问题是如何来确定进程的类型？ 而且有的进程其类型可能动态变化，怎么办？ “路遥知马力，日久见人心”！ 多级反馈队列算法 (Multilevel Feedback Queue) 即根据一个进程的运行反馈信息，动态地调整它 所在的队列。 反馈（Feedback）：即进程在运行当中的表 现，例如，它是否需要整个的时

21、间片用于计 算，或者它是否经常地执行I/O操作？,如何实现多级反馈队列算法？需要确定以下的一 些参数： 队列的个数； 每个队列所用的调度算法； 用来确定何时给一个进程“升级”的方法； 用来确定何时给一个进程“降级”的方法； 用来确定一个进程的初始队列的方法；,多级反馈队列算法的一个例子,三种优先级别，3最高、1最低，三个就绪队列。时间片长度 分别为N、2N和4N； 新进程进入内存后，优先级为3，加入队列3的末尾，按FCFS 算法调度；若一个时间片内未能执行完，则优先级降为2，加 入到队列2的末尾，同样按FCFS算法调度；依此类推。 如果进程在时间片用完之前即被阻塞，则增加它的优先级； 仅当较高

22、优先级的队列为空，才调度较低优先级的队列中的进 程执行。若进程执行时有新进程进入较高优先级的队列，则抢 先执行新进程。,多级反馈队列算法是时间片轮转算法和优先级算法 的综合和发展。其特点是： 为提高系统吞吐量和缩短平均周转时间而照顾短进程：新进程一进来即赋予最高优先级。 为获得较好的I/O设备利用率和缩短响应时间而照顾了I/O繁忙的进程： I/O繁忙进程：让其进入最高优先级队列，以及时启动I/O操作。通常只需一个小时间片，即可处理完一次I/O请求，然后转入到阻塞队列。 CPU繁忙进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。 不必估计进程的执行时间，动态调节

23、，能够适应一个进程在不同时间段的不同运行特点。,优先级和时间片都会根据进程的特点而发生变化。,low,high,high,priority,timeslice,I/O bound jobs,CPU bound jobs,2.6.4 实时系统中的调度算法,在实时系统中，对时间的要求是非常严格的。典 型的例子是：一个或多个外部的物理设备定期或 不定期地生成激励信号，而计算机必须在一定的 时间期限内做出恰当的反应。 硬实时：有一个绝对的时间期限，计算机的反应 动作必须在此期限之前完成，如核电站的控制系 统；软实时：偶尔错过一次期限虽然是令人不快 的，但也是可以容忍的，如VCD的播放系统； 实时调度算法可以是静态的或动态的，前者在系 统开始运行之前即已做好调度决策；而后者是在 运行中做出调度决策。,2.6.5 线程调度,在进程调度中，如果每个进程都带有多个的 线程，那么我