处理器管理和调度.pptx

第三章第三章 处理器调度处理器调度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）0A427296120BCED1322、最短作业优先算法（、最短作业优先算法（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-P45、优先级调度算法、优先级调度算法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=70n例例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个周期性实时任务。个周期性实时任务。如果将该单处理器系统变为具有两个处理器的系统，如果将该单处