3操作系统处理器管理和调度课件

第三章第三章 处理器调度处理器调度n调度是系统将计算机资源分配给进程。调度是系统将计算机资源分配给进程。n在单道程序环境下，没有资源竞争问题。在单道程序环境下，没有资源竞争问题。在多道程序环境下，多个进程并发运行，在多道程序环境下，多个进程并发运行，各进程之间存在资源的相互竞争，特别各进程之间存在资源的相互竞争，特别是对处理器资源的竞争，从而影响到系是对处理器资源的竞争，从而影响到系统性能。统性能。n处理器调度指在多道程序环境下将处理处理器调度指在多道程序环境下将处理器分配给各进程。在处理器调度中，合器分配给各进程。在处理器调度中，合理的调度算法能够提高处理器的处理能理的调度算法能够提高处理器的处理能力和系统性能，满足用户需求。力和系统性能，满足用户需求。.第三章第三章 处理器调度处理器调度3.1 3.1 作业的管理和调度作业的管理和调度3.2 3.2 处理器调度的层次处理器调度的层次3.3 3.3 选择调度算法的原则选择调度算法的原则 3.4 3.4 处理器调度算法处理器调度算法.第三章第三章 处理器调度处理器调度3.1 3.1 作业的管理和调度作业的管理和调度3.2 3.2 处理器调度的层次处理器调度的层次3.3 3.3 选择调度算法的原则选择调度算法的原则 3.4 3.4 处理器调度算法处理器调度算法.作业的概念作业的概念n作业：作业：作业由一组统一管理和操作的进作业由一组统一管理和操作的进程集合构成，是用户要求计算机系统完程集合构成，是用户要求计算机系统完成的一项相对独立的工作。成的一项相对独立的工作。n分类：按需要处理工作的类型分分类：按需要处理工作的类型分计算型计算型作业和作业和I/O型作业；型作业；按作业提交的方式按作业提交的方式不同分为不同分为批处理作业和终端型作业批处理作业和终端型作业.作业的概念作业的概念n在多道程序环境下，用户的批处理作业在多道程序环境下，用户的批处理作业被提交到系统的磁盘上，以批处理后备被提交到系统的磁盘上，以批处理后备队列的形式进行组织，这样的作业为批队列的形式进行组织，这样的作业为批处理作业。处理作业。批处理作业需要作业调度将批处理作业需要作业调度将后备队列上的作业调度到内存才能执行。后备队列上的作业调度到内存才能执行。n对终端型作业用户通过终端登录到系统，对终端型作业用户通过终端登录到系统，直接将作业置于内存中直接将作业置于内存中。终端型作业不。终端型作业不需要作业调度便能执行。需要作业调度便能执行。.作业和进程的关系作业和进程的关系n进程：已提交完毕并选中运行的作业进程：已提交完毕并选中运行的作业（程序）的（程序）的执行实体执行实体，也是为完成作业，也是为完成作业任务向系统申请和分配资源的基本单位。任务向系统申请和分配资源的基本单位。n作业得到调度后必须为其生成相应的用作业得到调度后必须为其生成相应的用户进程才能真正执行完成计算任务户进程才能真正执行完成计算任务n一个作业往往由多个父子关系的进程并一个作业往往由多个父子关系的进程并发完成发完成.作业和进程的关系作业和进程的关系n因此：因此：作业是任务实体，进程是完成任务的执作业是任务实体，进程是完成任务的执行实体行实体;没有作业任务，进程无事可干，没有作业任务，进程无事可干，没有进程，作业任务没法完成。没有进程，作业任务没法完成。作业概念更多地用在批处理操作系统，作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系而进程则可以用在各种多道程序设计系统。统。.批处理作业的相关概念批处理作业的相关概念1、作业：作业：用户在一次计算过程中，或者用户在一次计算过程中，或者一次事务处理过程中，要求计算机系统一次事务处理过程中，要求计算机系统所做工作的总称所做工作的总称2、作业步：作业步：一个作业可划分成若干部分，一个作业可划分成若干部分，称为一个作业步典型的作业控制过程：称为一个作业步典型的作业控制过程：“编译编译”、“连接装配连接装配”、“运行运行”.3、作业控制语言作业控制语言：用户用于描述批处理：用户用于描述批处理作业处理过程控制意图的一种特殊程序作业处理过程控制意图的一种特殊程序 书写作业说明书的语言称为作业控制语书写作业说明书的语言称为作业控制语言（言（JCL）4、作业说明书：作业说明书：表达用户对作业的控制表达用户对作业的控制意图内容，如作业的基本描述，作业控意图内容，如作业的基本描述，作业控制描述，资源要求描述制描述，资源要求描述 作业作业=程序程序+数据数据+作业说明书作业说明书.5、作业控制块（、作业控制块（JCB）n作业控制块是批处理作业存在的标志作业控制块是批处理作业存在的标志n保存有系统对于作业进行管理所需要的全部保存有系统对于作业进行管理所需要的全部信息信息n位于磁盘区域中位于磁盘区域中nJCB和作业一一对应和作业一一对应.（1）JCB的建立的建立n当作业开始由输入设备向磁盘的输入井当作业开始由输入设备向磁盘的输入井传输时系统输入程序为其建立一个作业传输时系统输入程序为其建立一个作业控制块进行初始化控制块进行初始化n初始化的大部分信息取自作业说明书初始化的大部分信息取自作业说明书.（2）JCB的使用的使用需要访问作业控制块的程序需要访问作业控制块的程序n系统输入程序系统输入程序n作业调度程序作业调度程序n作业控制程序作业控制程序n系统输出程序等系统输出程序等.（3）JCB的撤消的撤消n作业完成后，其作业控制块由系统输出作业完成后，其作业控制块由系统输出程序撤消程序撤消,作业控制块被撤消后其作业也作业控制块被撤消后其作业也不复存在不复存在.（4）作业表）作业表每个作业有个作业控制块每个作业有个作业控制块n所有作业所有作业JCB构成一个作业表构成一个作业表n作业表存放在外存固定区域中，长度是固定作业表存放在外存固定区域中，长度是固定n限制了系统所能同时容纳的作业数量限制了系统所能同时容纳的作业数量注意：注意：系统输入程序、作业调度程序、系统输出系统输入程序、作业调度程序、系统输出程序都需要访问作业表，因而存在互斥问题程序都需要访问作业表，因而存在互斥问题.批处理作业的组织和管理批处理作业的组织和管理n批处理作业的输入（输入井）批处理作业的输入（输入井）n批处理作业的建立（批处理作业的建立（JCB）n批处理作业的调度批处理作业的调度(按照某种调度算法从按照某种调度算法从输入井的后备作业队列中选取作业，使输入井的后备作业队列中选取作业，使其进入内存运行。其进入内存运行。)(1)选择作业选择作业;(2)分配资源分配资源(3)创建进程创建进程;(4)作业控制作业控制(5)后续处理后续处理 .批处理作业的调度批处理作业的调度n作业调度作业调度按照某种调度算法从输入按照某种调度算法从输入井的后备作业队列中选取作业，使其进井的后备作业队列中选取作业，使其进入内存运行。入内存运行。n作业调度程序的主要功能是审查系统是作业调度程序的主要功能是审查系统是否能满足用户作业的资源要求以及按照否能满足用户作业的资源要求以及按照一定的算法选取作业。一定的算法选取作业。.批处理作业的状态批处理作业的状态n提交状态提交状态:用户将作业提交给操作系统，等待输用户将作业提交给操作系统，等待输入程序和数据到磁盘。入程序和数据到磁盘。n 后备状态后备状态:系统接收输入的用户作业，并将其放系统接收输入的用户作业，并将其放入计算机磁盘。作业在磁盘上以后备队列形式进入计算机磁盘。作业在磁盘上以后备队列形式进行组织，等待作业调度程序将作业调度到内存。行组织，等待作业调度程序将作业调度到内存。n 执行状态执行状态:作业被调度到内存，为作业分配资源作业被调度到内存，为作业分配资源并为其创建与之对应的进程，进程获得并为其创建与之对应的进程，进程获得CPU，开，开始运行。始运行。n完成状态完成状态:从作业的第一个进程完成开始，直到从作业的第一个进程完成开始，直到作业所有的进程完成，释放作业所占用的资源，作业所有的进程完成，释放作业所占用的资源，退出系统的整个进程。退出系统的整个进程。.批处理作业状态及其转换批处理作业状态及其转换执行状态执行状态就绪就绪运行运行阻塞阻塞后备状态后备状态提交状态提交状态完成状态完成状态.终端型作业终端型作业n为每个终端创建一个终端进程，接受用为每个终端创建一个终端进程，接受用户的输入，执行命令解释程序，并把结户的输入，执行命令解释程序，并把结果返回给用户果返回给用户 等待键盘中断，申请中断；等待键盘中断，申请中断；CPU响应中断，将控制权交给命令解释程序响应中断，将控制权交给命令解释程序 创建子进程，执行命令处理文件代码创建子进程，执行命令处理文件代码 处理结束，再次输出命令提示符处理结束，再次输出命令提示符n例如分时操作系统例如分时操作系统n命令解释程序的作用和命令解释程序的作用和JCL解释程序类解释程序类似似.总结总结n批处理作业需要作业调度，特别是在批批处理作业需要作业调度，特别是在批处理操作系统中处理操作系统中n在分时操作系统和实时操作系统中，终在分时操作系统和实时操作系统中，终端用户的作业直接送入到内存，不需要端用户的作业直接送入到内存，不需要作业调度。操作系统需要完成的功能是作业调度。操作系统需要完成的功能是决定是否能够为作业创建进程。决定是否能够为作业创建进程。n分时操作系统和实时操作系统也支持批分时操作系统和实时操作系统也支持批处理作业，在批处理作业存在时，也能处理作业，在批处理作业存在时，也能够完成作业调度。够完成作业调度。.第三章第三章 处理器调度处理器调度3.1 3.1 作业的管理和调度作业的管理和调度3.2 3.2 处理器调度的层次处理器调度的层次3.3 3.3 选择调度算法的原则选择调度算法的原则 3.4 3.4 处理器调度算法处理器调度算法.n在多道程序环境下，进程的数目往往多在多道程序环境下，进程的数目往往多于处理器的数目，多个进程共享处理器于处理器的数目，多个进程共享处理器资源就必然引起对处理机的竞争。资源就必然引起对处理机的竞争。如需要考虑：如需要考虑：按照何种原则挑选批处理作业进入主存？按照何种原则挑选批处理作业进入主存？能否继续接纳分时用户？能否继续接纳分时用户？如何在多进程之间分配处理器？等等如何在多进程之间分配处理器？等等.处理器调度的层次处理器调度的层次n按照层次分为三级：按照层次分为三级：（1）高级调度）高级调度 （作业调度、长程调度）（作业调度、长程调度）（2）中级调度）中级调度 （平衡负载调度、中程调度）（平衡负载调度、中程调度）（3）低级调度）低级调度 （进程（进程/线程调度、短程调度）线程调度、短程调度）.高级调度高级调度n高级调度（作业调度、长程调度、宏观高级调度（作业调度、长程调度、宏观调度）调度）按一定原则对按一定原则对外存输入井上外存输入井上的大量后备作业进行选择调入内存，并的大量后备作业进行选择调入内存，并为它们创建进程、分配必要的资源为它们创建进程、分配必要的资源，再，再将新创建的进程排在就绪队列上，准备将新创建的进程排在就绪队列上，准备执行。执行。n 一般在一般在批处理系统批处理系统中有作业调度。中有作业调度。.高级调度高级调度n执行作业调度时应决定执行作业调度时应决定：接纳多少个作业？接纳多少个作业？接纳哪些作业？接纳哪些作业？取决于多道程序度。取决于多道程序度。取决于所采用的调度算法，如先来先服务取决于所采用的调度算法，如先来先服务调度算法、短作业优先调度算法、最高响调度算法、短作业优先调度算法、最高响应比法等。应比法等。.中级调度中级调度n平衡负载调度，中程调度平衡负载调度，中程调度n决定主存储器中所能容纳的进程数，这决定主存储器中所能容纳的进程数，这些进程将允许参与竞争处理器资源些进程将允许参与竞争处理器资源n中级调度根据存储资源量和进程的当前中级调度根据存储资源量和进程的当前状态来决定辅存和主存中进程的对换状态来决定辅存和主存中进程的对换n引入中级调度的目的是引入中级调度的目的是为了提高内存的为了提高内存的利用率和系统吞吐量利用率和系统吞吐量.低级调度低级调度n低级调度（进程调度、短程调度、微观调度）低级调度（进程调度、短程调度、微观调度）用来用来决定就绪队列中的哪个进程应获得处决定就绪队列中的哪个进程应获得处理机，理机，再由分派程序执行把处理机分配给该进再由分派程序执行把处理机分配给该进程的具体操作。程的具体操作。n低级调度是由每秒可操作许多次的处理机调度低级调度是由每秒可操作许多次的处理机调度程序执行，程序执行，处理机调度程序应常驻内存。处理机调度程序应常驻内存。n进程调度的方式：进程调度的方式：非抢占方式，抢占方式。非抢占方式，抢占方式。抢占原则：抢占原则：1 时间片原则；时间片原则；2优先级原则；优先级原则；3 短进程优先原则。短进程优先原则。.处理器调度的层次处理器调度的层次中级调度中级调度新建态新建态挂起就挂起就绪态绪态挂起等挂起等待态待态高级调度高级调度低级调度低级调度运行态运行态就绪态就绪态等待态等待态终止态终止态.处理器调度与进程状态转换处理器调度与进程状态转换高级高级调度调度中级调中级调度度低级低级调度调度运行运行态态就绪态就绪态终止终止态态新建态新建态挂起就挂起就绪态绪态中级中级调度调度挂起等挂起等待态待态等待态等待态高级调度高级调度高级调度高级调度中级中级调度调度.调度模型调度模型n注意：并不是每个操作系统都有三级调注意：并不是每个操作系统都有三级调度，其中低级调度是每种操作系统必备度，其中低级调度是每种操作系统必备的的n按照层次，处理器调度模型可分为：按照层次，处理器调度模型可分为：三级调度模型（高，中，低）三级调度模型（高，中，低）两级调度模型（高，低）两级调度模型（高，低）一级调度模型（低）一级调度模型（低）.一级调度模型一级调度模型.两级调度模型两级调度模型.处理器的三级调度模型处理器的三级调度模型中级调度中级调度低级调度低级调度高级调度高级调度完成完成超时超时 挂起就绪队列挂起就绪队列挂起等待队列挂起等待队列等待队列等待队列就绪队列就绪队列等待事件等待事件交互式用户交互式用户事件事件出现出现后备作业队列后备作业队列中级调度中级调度.第三章第三章 处理器调度处理器调度3.1 3.1 作业的管理和调度作业的管理和调度3.2 3.2 处理器调度的层次处理器调度的层次3.3 3.3 选择调度算法的原则选择调度算法的原则 3.4 3.4 处理器调度算法处理器调度算法.调度算法的目标调度算法的目标n单位时间内运行尽可能多的作业单位时间内运行尽可能多的作业n使处理机尽可能保持使处理机尽可能保持“忙碌忙碌”n使各种使各种I/O设备得以充分利用设备得以充分利用n对所有的作业都是公平合理的对所有的作业都是公平合理的.调度算法需要考虑的因素调度算法需要考虑的因素n要设计一个理想的调度算法是一件十分困难的要设计一个理想的调度算法是一件十分困难的事，在实际系统中，调度算法往往折衷考虑，事，在实际系统中，调度算法往往折衷考虑，设计调度算法时应考虑的因素：设计调度算法时应考虑的因素：调度算法应与系统设计目标保持一致调度算法应与系统设计目标保持一致 注意系统资源均衡使用注意系统资源均衡使用 保证提交的作业在截止时间内完成保证提交的作业在截止时间内完成 设法缩短作业平均周转时间设法缩短作业平均周转时间n大多数操作系统都采用比较简单的调度算法大多数操作系统都采用比较简单的调度算法.评价调度算法的性能指标评价调度算法的性能指标n面向系统的：面向系统的：1、资源利用率、资源利用率 2、吞吐率、吞吐率 3、公平性、公平性n面向用户的面向用户的：4、响应时间、响应时间 5、周转时间、周转时间.1、资源利用率、资源利用率n CPUCPU利用率利用率=CPU=CPU有效工作时间有效工作时间/CPU/CPU总的总的运行时间运行时间n CPU CPU总的运行时间总的运行时间=CPU=CPU有效工作时间有效工作时间 +CPU+CPU空闲等待时间空闲等待时间.2、吞吐率、吞吐率n单位时间内处理的作业数单位时间内处理的作业数n处理的长作业多，吞吐率低处理的长作业多，吞吐率低 处理的短作业多，吞吐率高处理的短作业多，吞吐率高.3、公平性、公平性n 确保每个用户每个进程获得合理的确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情份额或其他资源份额，不会出现饿死情况。况。.4、响应时间、响应时间n交互式进程从提交一个请求交互式进程从提交一个请求(命令命令)到接到接收到响应之间的时间间隔称响应时间。收到响应之间的时间间隔称响应时间。n使交互式用户的响应时间尽可能短，或使交互式用户的响应时间尽可能短，或尽快处理实时任务。尽快处理实时任务。n这是分时系统和实时系统衡量调度性能这是分时系统和实时系统衡量调度性能的一个重要指标。的一个重要指标。.5、周转时间、周转时间 n从用户把作业提交给系统开始，到作业从用户把作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间应使作业周转时间或平均作业周转时间尽可能短。尽可能短。n这是批处理系统衡量调度性能的一个重这是批处理系统衡量调度性能的一个重要指标。要指标。n调度性能指标重点看调度性能指标重点看：平均作业周转时平均作业周转时间间和和平均带权作业周转时间平均带权作业周转时间.作业周转与平均周转时间作业周转与平均周转时间n如果作业如果作业i提交给系统的时刻是提交给系统的时刻是ts，完成，完成时刻是时刻是tf，该作业的周转时间，该作业的周转时间ti为：为：ti=tf-tsti=tf-tsn 平均作业周转时间平均作业周转时间 T=(ti)/nT=(ti)/n.作业带权周转时间和平均作业带权周转时间和平均作业带权周转时间作业带权周转时间n如果作业如果作业i的周转时间为的周转时间为ti，所需运行时，所需运行时间为间为tk，则称，则称wi=ti/tkwi=ti/tk为该作业的带权为该作业的带权周转时间。周转时间。ti是等待时间与运行时间之是等待时间与运行时间之和，故带权周转时间总大于和，故带权周转时间总大于1。n 平均作业带权周转时间平均作业带权周转时间 W=(wi)/n W=(wi)/n注意：注意：为了提高系统的性能，要让若干个用户的平为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。均作业周转时间和平均带权周转时间最小。T T：衡量不同调度算法对同一个作业流的性能：衡量不同调度算法对同一个作业流的性能 W W：同一调度算法对不同作业流的性能衡量：同一调度算法对不同作业流的性能衡量.第三章第三章 处理器调度处理器调度3.1 3.1 作业的管理和调度作业的管理和调度3.2 3.2 处理器调度的层次处理器调度的层次3.3 3.3 选择调度算法的原则选择调度算法的原则 3.4 3.4 处理器调度算法处理器调度算法.低级调度的功能和类型低级调度的功能和类型n低级调度的对象低级调度的对象:进程或内核级线程进程或内核级线程，而，而 用户级线程调度是用户自己的事用户级线程调度是用户自己的事n低级调度需要解决的问题低级调度需要解决的问题:WHAT:按什么原则分配按什么原则分配CPU 调度算法调度算法 WHEN:何时分配何时分配CPU 调度的时机调度的时机 HOW:如何分配如何分配CPU 调度过程（进程的上下文切换）调度过程（进程的上下文切换）.低级调度的功能低级调度的功能n(1)调度调度:实现调度策略实现调度策略n(2)分派分派:实现调度机制实现调度机制.什么时候出现低级调度？什么时候出现低级调度？n进程正常终止或异常终止进程正常终止或异常终止n正在执行的进程因某种原因而阻塞正在执行的进程因某种原因而阻塞 提出提出I/O请求请求 在调用在调用P操作时因资源不足而阻塞操作时因资源不足而阻塞n在引入时间片的系统中在引入时间片的系统中,时间片用完时间片用完n在剥夺调度方式中在剥夺调度方式中,就绪队列中某进程的优就绪队列中某进程的优先权变得比当前正在执行的进程高先权变得比当前正在执行的进程高,或有优或有优先权更高的进程进入就绪队列先权更高的进程进入就绪队列.调度机制的功能模块调度机制的功能模块n（1）队列管理程序）队列管理程序 根据要求在各等待队列和就绪队列中移动根据要求在各等待队列和就绪队列中移动PCB/TCB指针指针n（2）上下文切换程序）上下文切换程序 保存当前运行进程的上下文信息到保存当前运行进程的上下文信息到PCB，恢复，恢复选中进程，使其运行选中进程，使其运行 n（3）分派程序）分派程序 当前进程上下文当前进程上下文分派进程上下文分派进程上下文选中的进选中的进程上下文程上下文.低级调度的基本类型低级调度的基本类型n非剥夺式非剥夺式(Non Non-preemptive Mode)Mode)：分派程序一旦把处理机分分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配完成或发生某事件而阻塞时，才把处理机分配给另一个进程。给另一个进程。n剥夺方式剥夺方式(Preemptive Mode)Mode)：当一个进程正在运行时，系统可以基于某种原当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其则，剥夺已分配给它的处理机，将之分配给其它进程。它进程。.作业调度和低级调度算法作业调度和低级调度算法n在操作系统中，大多数调度算法对作业调度和在操作系统中，大多数调度算法对作业调度和低级调度都是适用的。低级调度都是适用的。n1、先来先服务算法（、先来先服务算法（FCFS）n2、最短作业优先算法（、最短作业优先算法（SJF）n3、最短剩余时间优先算法（、最短剩余时间优先算法（SRTF）n4、响应比最高者优先算法（、响应比最高者优先算法（HRRF）n5、优先级调度算法、优先级调度算法n6、轮转调度算法、轮转调度算法n7、多级反馈队列调度算法、多级反馈队列调度算法n8、彩票调度算法、彩票调度算法.1、先来先服务算法、先来先服务算法应用范围与含义应用范围与含义n 作业调度：选择一个或多个作业调度：选择一个或多个最先进入最先进入后备队列的作业后备队列的作业，将它们调入内存，为，将它们调入内存，为它们分配资源、创建进程，并放入就绪它们分配资源、创建进程，并放入就绪队列。队列。n 进程调度：按照进程调度：按照进程就绪的先后次序进程就绪的先后次序来调度来调度进程，为之分配处理机。进程，为之分配处理机。n非剥夺式，最简单非剥夺式，最简单.特点：特点：n比较有利于长作业，而不利于短作业。比较有利于长作业，而不利于短作业。n有利于有利于CPU 繁忙的作业，而不利于繁忙的作业，而不利于I/O 繁忙的作业。繁忙的作业。n只考虑了作业的等待时间因素，忽略了只考虑了作业的等待时间因素，忽略了作业的长短，偏爱长作业作业的长短，偏爱长作业.例例1：在单道环境下，某批处理系统有四道作业，：在单道环境下，某批处理系统有四道作业，已知它们的进入系统的时刻、估计运算时间如已知它们的进入系统的时刻、估计运算时间如下：下：用用FCFS 算法计算作业的运行情况、平均周转时算法计算作业的运行情况、平均周转时间和平均带权周转时间间和平均带权周转时间.解解:1)调度次序：调度次序：1 2 3 4 2)完成时间图完成时间图 0122.52.62.8234 3)T=2+2+1.6+1.3)41.725(h)W=(2/2+2/0.5+1.6/0.1+1.3/0.2)4 6.875(h).例例2：.解：调度次序：解：调度次序：A B D C E T=72（m）W=3.55（m）0A427296120BCED132.2、最短作业优先算法（、最短作业优先算法（SJF）n是对是对FCFS 算法的改进，其目标是减少算法的改进，其目标是减少平均周转时间。平均周转时间。n对对预计执行时间短的作业预计执行时间短的作业投入运行。通投入运行。通常后来的短作业不抢先正在执行的作业。常后来的短作业不抢先正在执行的作业。n也可用于低级调度：调度时选取也可用于低级调度：调度时选取就绪队就绪队列中下一个列中下一个CPU用时最短的进程用时最短的进程，但在，但在实际应用中较少采用实际应用中较少采用.SJF的主要特点的主要特点n优点：优点：（1）比）比FCFS 改善平均周转时间和平均带权周转时改善平均周转时间和平均带权周转时间；间；（2）缩短作业的等待时间；）缩短作业的等待时间；（3）提高系统的吞吐量；）提高系统的吞吐量；n缺点：缺点：（1）对长作业非常不利，可能长时间得不到执行；）对长作业非常不利，可能长时间得不到执行；（2）只考虑了作业运行时间，忽略了等待时间；）只考虑了作业运行时间，忽略了等待时间；（3）难以准确估计作业（进程）的执行时间，从而）难以准确估计作业（进程）的执行时间，从而影响调度性能。影响调度性能。.例例3:设有设有5道作业道作业.解：根据解：根据SJF原则，调度次序为：原则，调度次序为：P1-P2-P5-P4-P30P10.30.811.3P2P4P3P51.7T=(0.3+0.6+0.4+0.8+1.3)50.68(h)W=(0.3/0.3+0.6/0.5+0.4/0.2+0.8/0.3+1.3/0.4)5 2.024(h).例例4:.3、最短剩余时间优先算法、最短剩余时间优先算法(SRTF)nSJF的剥夺式改进的剥夺式改进n例如例如,假设有假设有4个就绪进程先后移入就绪队列个就绪进程先后移入就绪队列,所需所需CPU时间如下时间如下:进程进程到达系统时到达系统时间间所需所需CPU时间时间P1P2P3P401238495平均等待时间平均等待时间=(10-1)+(1-1)+(17-2)+(5-3)/4=6.5(ms)0P1151017P2P4P1P326平均周转时间平均周转时间=(17-0)+(5-1)+(26-2)+(10-3)/4=13(ms).4、响应比最高者优先算法（、响应比最高者优先算法（HRRF）n是是FCFS 和和SJF 的折衷的折衷 响应比响应比 作业周转时间作业周转时间/作业处理时间作业处理时间 （作业等待时间作业处理时间）（作业等待时间作业处理时间）/作业处理时间作业处理时间 1 1作业等待时间作业等待时间/作业处理时间作业处理时间或或=1+=1+进程等待处理时间进程等待处理时间/进程估计计算时间进程估计计算时间.响应比响应比R=1+（作业等待时间（作业等待时间/作业执行作业执行时间）时间）n如作业等待时间相同，则执行时间越短，响应如作业等待时间相同，则执行时间越短，响应比越高，有利于短作业。比越高，有利于短作业。n对于长作业，随等待时间增加，响应比增高，对于长作业，随等待时间增加，响应比增高，最后同样可获得处理机。最后同样可获得处理机。n如执行时间相同，等待时间越长，响应比越高，如执行时间相同，等待时间越长，响应比越高，实现的是先来先服务。实现的是先来先服务。.n例例5：设有：设有4个作业个作业P1、P2、P3和和P4，它们到达时间和计算时间如表它们到达时间和计算时间如表.解解:若这四个作业在一台处理机上按单道方式运行，采若这四个作业在一台处理机上按单道方式运行，采用最高响应比优先调度算法，则第一次计算响应比在用最高响应比优先调度算法，则第一次计算响应比在8：00，此时只有，此时只有P1作业提交，其相应比作业提交，其相应比Rp11；在作；在作业业P1结束后，第二次计算各作业的响应比为：结束后，第二次计算各作业的响应比为：Rp2(1.5+1)/12.5 Rp3(1+0.25)/0.255 Rp4(0.5+0.5)/0.52 此时，选择作业此时，选择作业P3调入内存，调入内存，P3执行结束时，第执行结束时，第三次计算剩余各作业的响应比为：三次计算剩余各作业的响应比为：Rp2(1.75+1)/12.75 Rp4(0.75+0.5)/0.52.5 此时，选择作业此时，选择作业P2调入内存，调入内存，P2执行结束时，调入执行结束时，调入P4。因此因此,调度次序为调度次序为:P1-P3-P2-P4.5、优先级调度算法、优先级调度算法n根据确定的优先级来选取进程，总是选根据确定的优先级来选取进程，总是选择就绪队列中的优先级最高者投入运行。择就绪队列中的优先级最高者投入运行。n适用于作业调度和进程调度适用于作业调度和进程调度n一般用优先数（一般用优先数（0-4095）来表达）来表达.n优先级调度算法的类型（进程调度时）优先级调度算法的类型（进程调度时）非剥夺式优先级算法非剥夺式优先级算法 主要用于批处理系统中，也可用于对实时性要主要用于批处理系统中，也可用于对实时性要求不高的实时系统。求不高的实时系统。剥夺式优先级算法剥夺式优先级算法 能较好满足紧迫作业的要求，常用于要求比较能较好满足紧迫作业的要求，常用于要求比较严格的实时系统，和性能要求较高的分时和批严格的实时系统，和性能要求较高的分时和批处理系统。处理系统。.n优先级类型优先级类型静态优先级静态优先级 在作业或进程创建时指定优先数，在运行时优在作业或进程创建时指定优先数，在运行时优先数不变。先数不变。动态优先级动态优先级 在作业或进程创建时创立一个优先数，但在其在作业或进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。生命周期内优先数可以动态变化。.6、轮转调度算法（、轮转调度算法（RR）n也叫时间片调度也叫时间片调度 具体过程为：具体过程为：把把CPU 划分成若干时间片。划分成若干时间片。将系统中所有的就绪进程按照将系统中所有的就绪进程按照FCFS 原则，排原则，排成一个队列。成一个队列。每次调度时将每次调度时将CPU 分派给队首进程，让其执分派给队首进程，让其执行一个时间片。时间片的长度从几个行一个时间片。时间片的长度从几个ms 到几到几百百ms。在一个时间片结束时，发生时钟中断。调度程在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪序据此暂停当前进程的执行，将其送到就绪 队列的末尾，并通过上下文切换执行当前的队队列的末尾，并通过上下文切换执行当前的队首进程。首进程。进程可以未使用完一个时间片，就出让进程可以未使用完一个时间片，就出让CPU（如阻塞）。（如阻塞）。.时间片长度的确定时间片长度的确定n时间片轮转策略特别适合于时间片轮转策略特别适合于分时系统分时系统中使用中使用n在轮转法中，时间片长度的选取非常重要，时在轮转法中，时间片长度的选取非常重要，时间片长度的选择会直接影响系统开销和响应时间片长度的选择会直接影响系统开销和响应时间间 过长：过长：退化为退化为FCFS 算法，进程在一个时间算法，进程在一个时间片内都执行完，响应时间长。片内都执行完，响应时间长。过短：过短：用户的一次请求需要多个时间片才用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，系统开销大。能处理完，上下文切换次数增加，系统开销大。n最佳的时间片量值应能使分时用户得到最佳的时间片量值应能使分时用户得到好的响应时间好的响应时间.7、多级反馈队列调度算法、多级反馈队列调度算法n又称反馈循环队列或多队列策略。主要又称反馈循环队列或多队列策略。主要思想是思想是将就绪进程分为两级或多级，系将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时较高优先级的队列一般分配给较短的时间片。间片。n处理器调度先从高级就绪进程队列中选处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。时，才从较低级的就绪进程队列中选取。.8、彩票调度算法、彩票调度算法n基本思想：为进程发放针对各种资源基本思想：为进程发放针对各种资源（如（如CPU时间）的彩票。调度程序随机时间）的彩票。调度程序随机选择一张彩票，持有该彩票的进程获得选择一张彩票，持有该彩票的进程获得系统资源。系统资源。n进程都是平等的，有相同的运行机会。进程都是平等的，有相同的运行机会。如果某些进程需要更多的机会，可被给如果某些进程需要更多的机会，可被给予更多彩票，增加其中奖机会。予更多彩票，增加其中奖机会。.示例示例n例例6:有有5 个批处理作业个批处理作业A 到到E 均已到达计算均已到达计算中心，其运行时间分别中心，其运行时间分别10、6、2、4 和和8 分钟；各自的优先级分别被规定为分钟；各自的优先级分别被规定为3、5、2、1 和和4，这里，这里5 为最高级。若不考虑系统切为最高级。若不考虑系统切换开销，计算出平均作业周转时间。换开销，计算出平均作业周转时间。(1)FCFS（按（按A、B、C、D、E);(2)优先级调度算法，优先级调度算法，(3)时间片轮转法（每个作业获得相同的时间片轮转法（每个作业获得相同的2 分分钟长的时间片）。钟长的时间片）。.n解解:(1)FCFS 调度算法调度算法.(2)优先级调度算法优先级调度算法.(3）时间片轮转法）时间片轮转法:按次序按次序 ABCDEABDEABEAEA轮转执行。轮转执行。T=(30+22+6+16+28)/5=20.4W=(3+3.66+3+4+3.5)/5=3.43.例例7:有一个具有两道作业的批处理系统，作业调有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，在下表所以优先数为基础的抢占式调度算法，在下表所示的作业序列，作业优先数即为进程优先数，示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。优先数越小优先级越高。(1）列出所有作业进入内存时间及结束时间。）列出所有作业进入内存时间及结束时间。(2）计算平均周转时间。）计算平均周转时间。.分析分析:每个作业运行将经过两个阶段：作业每个作业运行将经过两个阶段：作业调度（调度（SJF 算法）和进程调度（优先数算法）和进程调度（优先数抢占式）。另外，批处理最多容纳抢占式）。另外，批处理最多容纳2 道道作业，更多的作业将在后备队列等待。作业，更多的作业将在后备队列等待。.答答:.各作业周转时间为：作业各作业周转时间为：作业A 70，作业，作业B 30，作业，作业C 90，作业，作业D 90。因此因此:T=70.n例例8：若后备作业队列中等待运行的同时：若后备作业队列中等待运行的同时有三个作业有三个作业J1、J2、J3，已知它们，已知它们各自的运行时间为各自的运行时间为a、b、c，且满足，且满足a b c，试证明采用短作业优先算法，试证明采用短作业优先算法调度能获得最小平均作业周转时间。调度能获得最小平均作业周转时间。.n证明：采用短作业优先算法调度时，三个作业的总周证明：采用短作业优先算法调度时，三个作业的总周转时间为：转时间为：Tl=a+(a+b)+(a+b+c)=3a+2b+c 若不按短作业优先算法调度，不失一般性，设调度次若不按短作业优先算法调度，不失一般性，设调度次序为：序为：J2、J1、J3。则三个作业的总周转时间为：。则三个作业的总周转时间为：T2=b(ba)(ba+c)=3b+2a+c 令令-式得到：式得到：T2-Tl=b-a 0 因此，采用短作业优先算法调度才能获得最小平均作因此，采用短作业优先算法调度才能获得最小平均作业周转时间。业周转时间。.n例例9：有五个作业正等待运行，估计它们：有五个作业正等待运行，估计它们的运行时间分别为的运行时间分别为9，6，3，5，x。为。为获得最小的平均周转时间，应当按照什获得最小的平均周转时间，应当按照什么顺序运行它们？给出答案应是么顺序运行它们？给出答案应是x的函数的函数（提示可以证明采用短作业优先调度算法，（提示可以证明采用短作业优先调度算法，平均周转时间是最小的）平均周转时间是最小的）.解：解：当当X3时，则运行次序为时，则运行次序为x,3,5,6,9(即即ECDBA)平均周转时间为：平均周转时间为：T=(5x+12+15+12+9)/5=x+9.6当当3x5时时,则运行次序为则运行次序为3,x,5,6,9(即即CEDBA)平均周转时间为：平均周转时间为：T=(15+4x+15+12+9)/5=.8x+10.2剩余的请同学们自己补充剩余的请同学们自己补充.n 例例10：有一个四道作业的操作系统，若在一：有一个四道作业的操作系统，若在一段时间内先后到达段时间内先后到达6 个作业，它们的提交和估个作业，它们的提交和估计运行时间由下表给出。计运行时间由下表给出。系统采用系统采用SJF 调度调度算法，作业被调度进入系统后中途不会退出，算法，作业被调度进入系统后中途不会退出，但作业运行时可被更短作业抢占。（但作业运行时可被更短作业抢占。（l）分别）分别给出给出6 个作业的执行时间序列、即开始执行时个作业的执行时间序列、即开始执行时间、作业完成时间、作业周转时间。（间、作业完成时间、作业周转时间。（2）计）计算平均作业周转时间。算平均作业周转时间。.n、有一个具有两道作业的批处理系统，作业调、有一个具有两道作业的批处理系统，作业调度采用最高响应比调度算法，进程调度采用短度采用最高响应比调度算法，进程调度采用短进程优先的抢占式调度算法（以优先数为基础进程优先的抢占式调度算法（以优先数为基础的抢占式调度算法），在下表所示的作业序列，的抢占式调度算法），在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先作业优先数即为进程优先数，优先数越小优先级越高。级越高。n(1）列出所有作业进入内存时间及结束时间。）列出所有作业进入内存时间及结束时间。(2）计算平均周转时间。）计算平均周转时间。40.3.5 实时调度用用于于实实时时操操作作系系统统中中的的处处理理器器调调度度为为实实时调度。时调度。实实时时系系统统是是那那些些时时间间因因素素非非常常关关键键的的系系统统。如如监监控控系系统统、自自动动驾驾驶驶系系统统、安安全全控控制制系系统统等等，这这些些系系统统中中，迟迟到到的的响响应应即使正确，也和没有响应一样糟糕。即使正确，也和没有响应一样糟糕。在在实实时时系系统统中中，衡衡量量调调度度性性能能的的指指标标不不是是周周转转时时间间和和等等待待时时间间，而而是是能能否否满满足足实时任务的截止时间要求。实时任务的截止时间要求。.硬实时系统和软实时系统实时系统通常分为硬实时（hard real time）系统和软实时（soft real time）系统。前者意味着存在必须满足的时间限制；后者意味着偶尔超过时间限制时可以容忍的。.实时调度需要满足的条件1 1系统向实时调度提供与实时任务相关系统向实时调度提供与实时任务相关的信息的信息n就绪起始时间：什么时候实时任务对应的进程就绪起始时间：什么时候实时任务对应的进程被创建并加入到进程就绪队列的被创建并加入到进程就绪队列的n截止时间：当实时系统中的实时任务发生时，截止时间：当实时系统中的实时任务发生时，实时系统中的就绪进程按照进程的截止时间进实时系统中的就绪进程按照进程的截止时间进行排列。行排列。n处理时间：实时任务从开始到完成所需要的时处理时间：实时任务从开始到完成所需要的时间。间。n实时任务的资源需求实时任务的资源需求n实时任务的优先级实时任务的优先级.实时调度需要满足的条件2对系统处理能力的衡量对系统处理能力的衡量实实时时系系统统响响应应的的任任务务可可划划分分为为周周期期性性任任务务和非周期性任务。和非周期性任务。对对于于周周期期性性任任务务必必须须满满足足以以下下条条件件系系统统才才能能进进行行这这些些周周期期性性实实时时任任务务的的调调度度，否否则则系统不能调度周期性实时任务。系统不能调度周期性实时任务。其中：其中：i表示周期事件表示周期事件i，Pi为周期事件为周期事件i发生的周期，发生的周期，Ci为需要处理器的处理时间。为需要处理器的处理时间。.n当系统不能调度这些周期性实时任务时，可以当系统不能调度这些周期性实时任务时，可以通过提高处理器的处理能力的方法减少每个周通过提高处理器的处理能力的方法减少每个周期任务的处理时间；或者采用多处理器系统，期任务的处理时间；或者采用多处理器系统，提高处理能力。提高处理能力。n如果采用的处理器数目为如果采用的处理器数目为N，则处理条件变为：，则处理条件变为：.例例3-8 3-8 如果一个单处理器实时系统中有如果一个单处理器实时系统中有3 3个周期性任个周期性任务，它们的周期分别为务，它们的周期分别为80ms80ms、40ms40ms和和240ms240ms，需要，需要CPUCPU处理的时间分别为处理的时间分别为20ms20ms、10ms10ms和和40ms40ms，问该实时系统，问该实时系统能否调度这能否调度这3 3个周期性任务？个周期性任务？所以，该系统可调度这所以，该系统可调度这3 3个周期性实时任务。个周期性实时任务。但是，如果这但是，如果这3 3个周期性实时任务需要处理器处理个周期性实时任务需要处理器处理的时间分别变为的时间分别变为30ms30ms、20ms20ms和和60ms60ms时，则：时，则：系统不能调度这系统不能调度这3 3个周期性实时任务。个周期性实时任务。.如果将该单处理器系统变为具有两个处理器的系统，如果将该单处理器系统变为具有两个处理器的系统，则：则：则双处理器系统可以调度这则双处理器系统可以调度这3 3个周期性实时任务。个周期性实时任务。.实时调度算法(1)1）单比率调度算法(按周期长度)基本思想：为每个进程分配一个与事件发生频率成正比的优先数。例如，周期为20ms的进程优先数为50，周期为100ms的进程优先数为10，运行时调度程序总是调度优先数最高的就绪进程，并采取抢占式分配策略。.实时调度算法(2)2）限期调度算法(按截止时间)基本思想：当一个事件发生时，对应的进程就按照截止期限被加入就绪进程队列。对于一个周期性事件，其截止期限即为事件下一次发生的时间。该调度算法首先运行队首进程，即截止时间最近的那个进程。.实时调度算法(3)3）最少裕度法 基本思想：首先计算各个进程的富裕时间，即裕度（laxity），然后选择裕度最少的进程执行。裕度=截止时间-(就绪时间+计算时间).多处理器调度 流行的多处理器系统有：松散耦合多处理器系统 紧密耦合多处理器系统 现代操作系统往往采用进程调度与线程调度相结合的方式来完成多处理器调度。.多处理器调度算法(1)基本思想：进程并不分配给一个特定处理器，系统维护一个全局性就绪线程队列，当一个处理器空闲时，就选择一个就绪线程占有处理器运行。1）负载共享调度算法）负载共享调度算法.多处理器调度算法(2)基本思想：把属于一个进程的一组线程在同一时间一次性调度到一组处理器上运行。它具有的优点：当紧密相关的线程同时执行时，同步造成的等待将减少，线程切换也相应减少，系统性能得到提高。由于一次性同时调度一组处理器，调度的代价也将减少。2）群调度算法）群调度算法.多处理器调度算法(3)基本思想：给一个应用指派一组处理器，一旦一个应用被调度，它的每个线程被分配一个处理器并一直占有处理器运行直到整个应用运行结束。采用这一算法，处理器将不适用多道程序设计，即该应用的一个线程阻塞后，线程对应的处理器不会被调度给其他线程，而处于空闲状态。3）处理器专派调度算法）处理器专派调度算法.多处理器调度算法(4)基本思想：由操作系统和应用进程共同完成调度。操作系统负责在应用进程之间划分处理器。应用进程在分配给它的处理器上执行可运行线程的子集，哪一些线程应该执行，哪一些线程应该挂起完全是应用进程自己的事。4）动态调度算法）动态调度算法(1).多处理器调度算法(5)如果有空闲处理器，满足要求。否则，对新到达进程，从当前分配了一个以上处理器的进程中收回一个，并把它分给新到达进程。如果要求不能被满足，则保留申请直到出现可用处理器或要求取消。释放了一个或多个处理器后，扫描申请处理器的进程队列，按照FCFS原则把处理器逐一分配给每个申请进程直到没有可用处理器。动态调度算法动态调度算法(2).本章小结本章小结n重点内容重点内容:理解处理器调度的层次理解处理器调度的层次掌握调度算法掌握调度算法 (FCFS,SJF,SRTF,HRRF,优先级调度优先级调度,RR,MLFQ)及其应用及其应用.