1、2.62.6处理机调度处理机调度2.6.1 处理机调度层次2.6.2 选择调度算法的原则2.6.3 作业管理与调度2.6.4 低级调度功能和类型2.6.5 作业调度和低级调度算法引言引言在多道系统当中，往往有在多道系统当中，往往有多个进程多个进程同时同时在内存中在内存中运行运行。在任何时刻，一个进程只可能是以下三种。在任何时刻，一个进程只可能是以下三种状态之一：状态之一：运行状态：该进程正在运行状态：该进程正在CPU上运行，每个上运行，每个CPU 上最多只能有一个进程在运行；上最多只能有一个进程在运行；就绪状态：进程已经就绪，随时可以运行；就绪状态：进程已经就绪，随时可以运行；阻塞状态：如在某
2、个信号量上被阻塞，等待阻塞状态：如在某个信号量上被阻塞，等待I/O。与此相对应，与此相对应，操作系统会维护相应的状态队列操作系统会维护相应的状态队列。就绪队列和各种就绪队列和各种I/O设备队列设备队列（本图摘自Silberschatz,Galvin and Gagne：“Operating System Concepts”）选择谁去运行？在操作系统中，负责去做这个选择的那在操作系统中，负责去做这个选择的那 部分程序，称为部分程序，称为调度程序调度程序(scheduler)；调度程序在决策过程中所采用的算法，调度程序在决策过程中所采用的算法，称为是称为是调度算法调度算法；调度程序是调度程序是CP
3、U资源的管理者资源的管理者；调度的对象调度的对象是是进程进程，也可以是，也可以是线程线程，大，大 多数的调度问题对两者都是适用的。多数的调度问题对两者都是适用的。几个基本概念几个基本概念处理器调度要解决的问题WHENWHEN：何时分配CPU 调度的时机WHATWHAT：按什么原则分配CPU 调度算法HOWHOW：如何分配CPU 进程的上下文切换2.6.1 处理机调度层次作业调度（高级调度）作业调度（高级调度）交换调度（中级调度）交换调度（中级调度）进程调度（低级调度）进程调度（低级调度）注：注：进程调度频率最高，约进程调度频率最高，约10100 ms进行一次，进行一次，因而进程调度算法不能太复
4、杂，以免占用太多因而进程调度算法不能太复杂，以免占用太多CPU时间。时间。作业调度作业调度对象：外存上后备队列中的作业对象：外存上后备队列中的作业其它其它作业作业成批进入成批进入输入井输入井输出井输出井内存内存CPU动作：调入内存、创建进程、分配资源、新进程进入就绪队列动作：调入内存、创建进程、分配资源、新进程进入就绪队列决策内容：接纳作业量、作业类型决策内容：接纳作业量、作业类型作业调度作业调度（2）低级调度）低级调度:进程调度进程调度对象：就绪队列中的进程对象：就绪队列中的进程其它其它作业作业成批进入成批进入输入井输入井输出井输出井内存内存CPU动作：决定由哪个进程获得动作：决定由哪个进程
5、获得CPU调度方式：调度方式：非抢占式非抢占式抢占式抢占式进程调度进程调度CPU就绪队列就绪队列交互用户交互用户123*进程调度对象：就绪队列中的进程进程调度对象：就绪队列中的进程进程调度进程调度进程调度进程调度*进程调度功能及过程进程调度功能及过程:纪录当前进程的状态、保存纪录当前进程的状态、保存CPU现场现场;选取适当的就绪进程选取适当的就绪进程 分配处理机：恢复选取进程的现场分配处理机：恢复选取进程的现场;进程调度的方式：进程调度的方式：现运行进程的现运行进程的CPU使用权不能被中途强行剥夺使用权不能被中途强行剥夺除非进程主动放弃除非进程主动放弃.系统按照某种原则剥夺现行进程的系统按照某
6、种原则剥夺现行进程的CPU使用权使用权将将CPU使用权分配给其他进程使用权分配给其他进程.*抢占原则抢占原则:优先权原则优先权原则时间片原则时间片原则短进程优先原则短进程优先原则进程调度进程调度作业调度与进程调度的关系作业调度与进程调度的关系 进程调度进程调度运行就绪等待输入状态后备状态完完成成状状态态预输预输入完入完成成作业控制作业调度(选中并创建进程)作业调度(作业终止并撤离)SPOOLingSPOOLing作业预输入作业预输入SPOOLingSPOOLing作作业缓输出业缓输出交换调度交换调度对象：外存中因暂时不能运行而被挂起的进程对象：外存中因暂时不能运行而被挂起的进程.动作：将外存挂
7、起的进程激活调入内存，进入就绪队列动作：将外存挂起的进程激活调入内存，进入就绪队列.目的：提高内存利用率目的：提高内存利用率.交换调度交换调度（3）中级调度）中级调度:调度队列模型调度队列模型1交互用户交互用户进程调度是最基本的调度，进程调度是最基本的调度，必须配置必须配置1 1、单级调度模型、单级调度模型CPU就绪队列就绪队列阻塞队列阻塞队列时间片完时间片完阻塞阻塞唤醒唤醒后备队列后备队列在批处理或类似系统中在批处理或类似系统中需要从外存后备队列中调入作业需要从外存后备队列中调入作业2 2、二级调度模型、二级调度模型调度队列模型调度队列模型2CPU就绪队列就绪队列阻塞队列阻塞队列时间片完时间
8、片完阻塞阻塞唤醒唤醒后备队列后备队列挂起挂起挂起挂起事件出现事件出现外存阻塞队列外存阻塞队列外存就绪队列外存就绪队列配置中级配置中级调度机制调度机制可以提高可以提高内存利用率内存利用率进程调度进程调度作业调度作业调度中级中级调度调度1 1、三级调度模型、三级调度模型调度队列模型调度队列模型3CPU就绪队列就绪队列阻塞队列阻塞队列交互用户交互用户阻塞阻塞唤醒唤醒进程调度进程调度1.现进程运行完毕现进程运行完毕2.现进程阻塞现进程阻塞3.优先权高的进程进入就绪队列优先权高的进程进入就绪队列4.现进程现进程“超时超时”进程调度时机进程调度时机时间片完时间片完从多个目标中选取一个从多个目标中选取一个*
9、算法准则算法准则面向用户面向用户面向系统面向系统周转时间周转时间响应时间响应时间截止时间截止时间优先权优先权系统吞吐量系统吞吐量处理机利用率处理机利用率各类资源的利用各类资源的利用短短快快保证保证可设置可设置大大高高平衡平衡2.6.2 选择调度算法原则选择调度算法原则吞吐量吞吐量（Throughput）：）：单位时间内所完成单位时间内所完成的作业数，与作业的作业数，与作业本身特性和调度算本身特性和调度算法有关。法有关。周转时间：iiiSET（Ei表示作业i完成时间，Si表示作业i提交时间）平均周转时间：NiiTNT11(N表示作业的个数)平均带权周转时间：NiiirTNW11(ri表示作业i的
10、实际执行时间)周转时间周转时间*算法类型算法类型简单的调度算法简单的调度算法先来先服务算法先来先服务算法短进程优先短进程优先轮转法轮转法等时间片轮转等时间片轮转不等时间片轮转不等时间片轮转优先权法优先权法抢占式优先权抢占式优先权非抢占式优先权非抢占式优先权静态优先权静态优先权动态优先权动态优先权多级反馈队列算法多级反馈队列算法2.6.5 调度算法调度算法最短剩余时间优先算法最短剩余时间优先算法最高响应比算法最高响应比算法1、先来先服务算法、先来先服务算法FCFS（First Come First Served）按照就绪进程进入就绪队列的先后次序进行调度；按照就绪进程进入就绪队列的先后次序进行调
11、度；不可抢占方式：当前进程一直占用不可抢占方式：当前进程一直占用CPU，直到执，直到执行完或被阻塞，才让出行完或被阻塞，才让出CPU给另一个进程。给另一个进程。利于长进程利于长进程，CPU繁忙型作业繁忙型作业 不利于短进程不利于短进程FCFS算法算法 在进程被唤醒后（如在进程被唤醒后（如I/O完成），并不立即恢复完成），并不立即恢复执行，而是放在就绪队列的末尾；执行，而是放在就绪队列的末尾；问题问题1.平均周转时间取决于各作业到达的顺序，若平均周转时间取决于各作业到达的顺序，若短作业位于长作业之后，将增大平均周转时间。短作业位于长作业之后，将增大平均周转时间。例如，三个作业例如，三个作业A、B
12、、C的运行时间为的运行时间为24、3、3时间时间 24 27 30ABC平均周转时间平均周转时间(24+27+30)/327平均等待时间平均等待时间(0+24+27)/317时间时间 3 6 30ABC平均周转时间平均周转时间(3+6+30)/313平均等待时间平均等待时间(0+3+6)/33问题问题2.无法充分利用无法充分利用CPU繁忙的作业与繁忙的作业与I/O繁忙的繁忙的作业之间的互补关系。如果作业之间的互补关系。如果CPU繁忙的作业独占很繁忙的作业独占很长时间的长时间的CPU，使得，使得I/O设备空闲，也使得设备空闲，也使得I/O繁忙繁忙的作业无法运行。的作业无法运行。作业A作业BCPU
13、I/O作业A作业B时间t0t1 t2t3t42、最短作业优先算法（、最短作业优先算法（Shortest Job First）对系统服务时间需求短的作业优先被调度对系统服务时间需求短的作业优先被调度.短进程估算：依赖于前一周期的实际短进程估算：依赖于前一周期的实际CPU时间和估计时间时间和估计时间系统性能改善，平均带权周转时间优于系统性能改善，平均带权周转时间优于FCFS.不利于长作业不利于长作业，不保证及时性不保证及时性，甚至可能得不到调度，甚至可能得不到调度.（不断有短进程到达不断有短进程到达）其中其中 为估计的第为估计的第n个个CPU 周期。周期。tn 为实际值。为实际值。为控制值，为控制
14、值，0 1，常取常取 0.5nn+1nnt（1 ）SJF算法算法 短作业优先短作业优先设计目标是改进设计目标是改进FCFS算法，算法，减少平均周转时减少平均周转时间间；SJF算法要求作业在开始执行时预计执行时间算法要求作业在开始执行时预计执行时间,对预计执对预计执行时间短的作业优先分派处理器；行时间短的作业优先分派处理器；两种实现方案：两种实现方案：不可抢占方式：当前作业在运行时不会被打断，只有不可抢占方式：当前作业在运行时不会被打断，只有运行完毕或阻塞时，才让出运行完毕或阻塞时，才让出CPU；可抢占方式：如果一个新的短作业到来，其运行时间可抢占方式：如果一个新的短作业到来，其运行时间小于当前
15、正在运行作业的剩余时间，则抢占小于当前正在运行作业的剩余时间，则抢占CPU运行运行，称为，称为SRTF（Shortest Remaining Time First）.SJF算法算法 可以证明：对于一组同时到达的作业，采用可以证明：对于一组同时到达的作业，采用SJF 算法将得到一个算法将得到一个最小最小的平均周转时间。的平均周转时间。D时间时间ACa a+b a+b+c a+b+c+d 例如，考察例如，考察4个作业个作业A、B、C、D，其运行时间分，其运行时间分别为别为a、b、c、dBA、B、C、D的周转时间分别为的周转时间分别为a、a+b、a+b+c和和a+b+c+d，因，因此平均周转时间为：
16、此平均周转时间为：(4a+3b+2c+d)/4.显然，当显然，当a b c d时，平均周转时间最小。时，平均周转时间最小。是否万事大吉了？是否万事大吉了？取得最优解的前提之一：这组作业必须同时到达；取得最优解的前提之一：这组作业必须同时到达；例如：进程到达时间运行时间P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4SJF（不可抢占）：（不可抢占）：P1P3P2P403781216平均周转时间：平均周转时间：(7+10+4+11)/4=8平均等待时间：平均等待时间：(0+6+3+7)/4=4若按若按P2,P3,P4,P1顺序顺序,平均周转和等待时间平均周转和等待时间7.75,3.
17、75进程到达时间运行时间P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4SJF（可抢占）：（可抢占）：P1P3P2P4P2P1027411165平均周转时间：平均周转时间：(16+5+1+6)/4=7平均等待时间：平均等待时间：(9+1+0+2)/4=3前提条件之二：需要事先估计作业的运行时间前提条件之二：需要事先估计作业的运行时间如何知道作业的运行时间？如何知道作业的运行时间？该时间只可能是一个估计值；该时间只可能是一个估计值；让提交该作业的用户来提供，不太实用；让提交该作业的用户来提供，不太实用；使用前面的使用前面的CPU运行时间来预测后面的运行时间来预测后面的CPU运行时
18、间，通过运行时间，通过过去的行为来预测将来的行为。过去的行为来预测将来的行为。如果一个作业已经运行很长时间了，那它可能如果一个作业已经运行很长时间了，那它可能 还会运行更长的时间；还会运行更长的时间；使用指数平均值函数来预测下一段使用指数平均值函数来预测下一段CPU时间。时间。例：例：A请求系统服务时间请求系统服务时间5s，B请求系统服务时间请求系统服务时间为为100s，设第，设第0到第到第5秒前，秒前，CPU运行运行C进程。第进程。第1秒时秒时B进入系统，第进入系统，第2秒时秒时A进入内存，进入内存，当当CPU空空闲，需要调度进程时选择闲，需要调度进程时选择A或或B。A：周转时间为：周转时间
19、为 3+58，带权周转时间为，带权周转时间为8/5 1.6先来先服务先来先服务短作业优先短作业优先B：周转时间为：周转时间为 4+5100109，带权周转时间为带权周转时间为109/100 1.09平均带权周转时间为（平均带权周转时间为（1.6 1.09）2 1.345A：周转时间为：周转时间为 3+100+5108，带权周转时间为，带权周转时间为108/5 21.6B：周转时间为：周转时间为 4100104，带权周转时间为带权周转时间为104/100 1.04平均带权周转时间为（平均带权周转时间为（21.6 1.04）2 11.32SRTF把把SJF算法改为抢占式算法改为抢占式的。一个新作业
20、进入就绪的。一个新作业进入就绪状态，如果新作业需要的状态，如果新作业需要的CPU时间比当前正在执行的时间比当前正在执行的作业剩余下来还需的作业剩余下来还需的CPU时间短，时间短，SRTF强行赶走当前强行赶走当前正在执行作业。称最短剩余时间优先算法。正在执行作业。称最短剩余时间优先算法。此算法不但适用于此算法不但适用于JOB调度，同样也适用于进程调度。调度，同样也适用于进程调度。SRTF算法算法3、最短剩余时间优先算法（、最短剩余时间优先算法（Shortest Remaining Time First）四个作业其到达系统四个作业其到达系统/所需所需CPU时间如下：时间如下：Job1-0/8，Jo
21、b2-1/4，Job3-2/9，Job4-3/5。SRTF调度平均等待时间调度平均等待时间=6.5毫秒。毫秒。SJF调度平均等待时间调度平均等待时间=7.75毫秒。毫秒。J1 J2 J4 J1 J3 015101726SRTF算法举例算法举例FCFS与与SJF是片面的调度算法。是片面的调度算法。FCFS只考虑作业等候只考虑作业等候时间而忽视了作业的计算时问，时间而忽视了作业的计算时问，SJF只考虑用户估计的只考虑用户估计的作业计算时间而忽视了作业等待时间。作业计算时间而忽视了作业等待时间。HRRF是介乎这两者之间的折衷算法，是介乎这两者之间的折衷算法，既考虑作业等待既考虑作业等待时间，又考虑作
22、业的运行时间，既照顾短作业又不使长时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长作业的等待时间过长，改进了调度性能。，改进了调度性能。HRRF算法算法4、最高响应比算法（、最高响应比算法（Highest Response Ratio First）响应比响应比 1+已等待时间已等待时间/估计运行时间估计运行时间 短作业容易得到较高响应比短作业容易得到较高响应比;长作业等待时间足够长后，也将获得足够高的响应比长作业等待时间足够长后，也将获得足够高的响应比;饥饿现象不会发生。饥饿现象不会发生。HRRF算法算法 四个作业到达系统时间四个作业到达系统时间/所需所需CPU时间时间:作业
23、作业1-0/20，作业，作业2-5/15，作业，作业3-10/5，作业，作业4-15/10。SJF调度顺序为作业调度顺序为作业1、3、4、2，平均作业周转时间，平均作业周转时间T=25，平均带权作业周转时间平均带权作业周转时间W=2.25。FCFS调度顺序为作业调度顺序为作业1、2、3、4，平均作业周转时间，平均作业周转时间T=28.75，平均带权作业周转时间平均带权作业周转时间W=3.125。HRRF调度顺序为作业调度顺序为作业1、3、2、4，平均作业周转时间，平均作业周转时间T=26.25，平均带权作业周转时间平均带权作业周转时间W=2.46。HRRF算法举例算法举例5、优先级调度算法（、
24、优先级调度算法（High Priority First）*保证实时性保证实时性。（事件响应的及时性）。（事件响应的及时性）（1）为每个进程设置优先级）为每个进程设置优先级（2）调度时选取优先级最高的进程）调度时选取优先级最高的进程 相同优先级的进程按照相同优先级的进程按照FCFS选取选取抢占式调度：高优先权的进程进入就绪队列时引起调度抢占式调度：高优先权的进程进入就绪队列时引起调度非抢占式调度：非抢占式调度：HPF算法算法静态优先权静态优先权进程的优先权在进程创建时设定，以后不会改变。进程的优先权在进程创建时设定，以后不会改变。优先权设定的一般依据：优先权设定的一般依据：（1）进程类型）进程类
25、型（2）进程对资源的需求）进程对资源的需求（3）根据用户的需求）根据用户的需求优先级设定后可能造成低优先权的进程得不到运行的机会。优先级设定后可能造成低优先权的进程得不到运行的机会。HPF算法算法动态优先权动态优先权进程的优先权在系统周转过程中动态改变。进程的优先权在系统周转过程中动态改变。*就绪等待进程优先级随等待时间以就绪等待进程优先级随等待时间以 速率升高速率升高*执行进程的优先级以执行进程的优先级以 速率下降速率下降*优先权优先权=等待时间等待时间+要求服务时间要求服务时间要求服务时间要求服务时间等待时间一定：优先权与要求服务时间成反比等待时间一定：优先权与要求服务时间成反比要求服务时
26、间一定：优先权与等待时间成正比要求服务时间一定：优先权与等待时间成正比短进程优先短进程优先优先权低的进程也能有运行的机会优先权低的进程也能有运行的机会HPF算法算法（1）等时间片轮转）等时间片轮转保证人机交互的及时性保证人机交互的及时性 按照按照FCFS顺序从就绪队列选取进程顺序从就绪队列选取进程 每个进程分配给每个进程分配给相同的相同的CPU时间片时间片 时间片到后将进程排到就绪队列尾时间片到后将进程排到就绪队列尾公平性的保证公平性的保证响应及时性的保证响应及时性的保证RR算法算法6、轮转调度算法（、轮转调度算法（Round-Robin）*时间片的选择时间片的选择q NTq：时间片大小：时间
27、片大小T：响应时间：响应时间N：就绪队列进程数：就绪队列进程数=*q NT=当当N一定时：一定时：q与与T成正比。成正比。q不能太大不能太大当当T一定时：一定时：q与与N成反比成反比q不能太小不能太小响应时间保证响应时间保证开销加大开销加大RR算法算法（2）不等时间片轮转法）不等时间片轮转法*短时间片满足快速响应的需要短时间片满足快速响应的需要*长时间片使周转时间降低长时间片使周转时间降低 在保证及时响应的基础上，为不同的需求分配大小不在保证及时响应的基础上，为不同的需求分配大小不等的时间片等的时间片长进程长进程短进程短进程I/O频繁型频繁型CPU密集型密集型长时间片长时间片短时间片短时间片降
28、低周转时间降低周转时间。引入引入“前台前台”、“后台后台”提高系统资源利用率提高系统资源利用率RR算法算法进程进程CPU时间时间P153 P2 17 P368 P4 24例：时间片长度例：时间片长度q20P1P2P3P4P1P3P4P1P3P30 20 37 57 77 97 117 121 134 154 162平均周转时间：平均周转时间：(134+37+162+121)/4113.5SJF的平均周转时间：的平均周转时间：(94+17+162+41)/478.57、多级反馈队列调度算法（、多级反馈队列调度算法（Multi-Level Feedback Queue）综合各种算法长处综合各种算法
29、长处*设计思想设计思想:设置多个就绪队列，各队列优先级不一样，分配的时间设置多个就绪队列，各队列优先级不一样，分配的时间片也不一样，高优先权队列进程的时间片较小。片也不一样，高优先权队列进程的时间片较小。*调度算法调度算法MLFQ算法算法短时间片短时间片长时间片长时间片（1）在选取进程时，选）在选取进程时，选取高优先权队列里的进取高优先权队列里的进程。程。分配给相应的时间片。同分配给相应的时间片。同一队列按照一队列按照FCFS（2）进程使用完时间片）进程使用完时间片后，回到就绪态是则进入后，回到就绪态是则进入低一级优先权队列低一级优先权队列（3）当高优先权队列里没）当高优先权队列里没有进程时，
30、才调度低优先有进程时，才调度低优先权队列进程。权队列进程。（4）进程创建后进入最高优先权队列。）进程创建后进入最高优先权队列。优先权优先权时间片轮转时间片轮转动态优先权、不等时间片动态优先权、不等时间片MLFQ算法算法*性能：性能：（1）短进程短进程 在第一级队列的时间片中完成，满足及时响应在第一级队列的时间片中完成，满足及时响应和短进程的周转要求。和短进程的周转要求。（2）动态变化的优先权动态变化的优先权使优先权低的进程也得到执行的机会。使优先权低的进程也得到执行的机会。（3）动态变化的时间片动态变化的时间片 长进程在长时间等待后获得长时间片，可减少周长进程在长时间等待后获得长时间片，可减少
31、周转时间。转时间。MLFQ算法算法 三种优先级别，三种优先级别，3最高、最高、1最低，三个就绪队列。时间片长度最低，三个就绪队列。时间片长度 分别为分别为N、2N和和4N；新进程进入内存后，优先级为新进程进入内存后，优先级为3，加入队列，加入队列3的末尾，按的末尾，按FCFS算法调度；若一个时间片内未能执行完，则优先级降为算法调度；若一个时间片内未能执行完，则优先级降为2，加入到队列，加入到队列2的末尾，同样按的末尾，同样按FCFS算法调度；依此类推。算法调度；依此类推。如果进程在时间片用完之前即被阻塞，则增加它的优先级；如果进程在时间片用完之前即被阻塞，则增加它的优先级；仅当较高优先级的队列
32、为空，才调度较低优先级的队列中的仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。若进程执行时有新进程进入较高优先级的队列，进程执行。若进程执行时有新进程进入较高优先级的队列，则抢先执行新进程。则抢先执行新进程。优先级优先级321MLFQ算法举例算法举例 MLFQ算法是时间片轮转算法和优先级算法的综合算法是时间片轮转算法和优先级算法的综合和发展。其特点是：和发展。其特点是：为提高系统吞吐量和缩短平均周转时间而照顾短进程：新进为提高系统吞吐量和缩短平均周转时间而照顾短进程：新进程一进来即赋予最高优先级。程一进来即赋予最高优先级。为获得较好的为获得较好的I/O设备利用率和缩短响应时间而
33、照顾了设备利用率和缩短响应时间而照顾了I/O繁繁忙的进程：忙的进程：I/O繁忙进程：让其进入最高优先级队列，以及时启动繁忙进程：让其进入最高优先级队列，以及时启动I/O操作。通常只需一个小时间片，即可处理完一次操作。通常只需一个小时间片，即可处理完一次I/O请求，请求，然后转入到阻塞队列。然后转入到阻塞队列。CPU繁忙进程：每次都执行完时间片，进入更低级队列。繁忙进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。最终采用最大时间片来执行，减少调度次数。不必估计进程的执行时间，动态调节，能够适应一个进程在不必估计进程的执行时间，动态调节，能够适应一个进程在不同时间段的不同运行特点。不同时间段的不同运行特点。MLFQ算法算法 优先级和时间片都会根据进程的特点而发生变化。优先级和时间片都会根据进程的特点而发生变化。lowhighhighprioritytimesliceI/O bound jobsCPU bound jobsMLFQ算法算法谢谢！
