操作系统之处理机调度.ppt

第四章 处理机调度•分级调度•作业调度•进程调度•调度算法•实时系统调度方法1、分级调度•作业的状态及其转换•调度的层次调度的层次通常处理机调度可以分为４级通常处理机调度可以分为４级１）作业调度（高级调度）１）作业调度（高级调度）按一定原则对外存输入井上的大量后备作业进按一定原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出设备行选择，给选出的作业分配内存、输入输出设备等必要资源，并建立进程作业完毕后，回收资等必要资源，并建立进程作业完毕后，回收资源２）交换调度（中级调度）２）交换调度（中级调度）将处于外存交换区中的就绪状态或就绪等待状将处于外存交换区中的就绪状态或就绪等待状态的进程调入内存，或把处于内存就绪状态或内态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区存等待状态的进程交换到外存交换区３）进程调度（低级调度）３）进程调度（低级调度）选取处于就绪状态的进程占用ＣＰＵ，进程上选取处于就绪状态的进程占用ＣＰＵ，进程上下文切换下文切换４）线程调度４）线程调度•作业与进程的关系作业是任务实体，进程是执行实体作业如何分解为进程？1) 系统必须为一个作业创建一个根进程； 2) 在执行作业控制语句时，系统或根进程为其创建相应的子进程，然后为各子进程分配资源和调度各子进程执行以完成作业要求的任务。

２、作业调度•作业调度的功能１）记录系统中各作业的状况ＪＣＢ２）从后备队列中挑选出一部分作业投入执行３）为被选中作业做好执行前准备工作４）在作业执行结束时做善后处理工作•作业调度目标与性能衡量作业调度目标与性能衡量调度目标：调度目标：对所有作业应该是公平合理的对所有作业应该是公平合理的应使设备有高的利用率应使设备有高的利用率每天执行尽可能多的作业每天执行尽可能多的作业有快的响应时间有快的响应时间衡量调度策略的指标：衡量调度策略的指标：周转时间周转时间：将一个作业提交给计算机系统后到该：将一个作业提交给计算机系统后到该作业的结果返回作业的结果返回ＴＴi = i = TeiTei – – TsiTsi T = (∑Ti)/n --- T = (∑Ti)/n ---平均周转时间平均周转时间WiWi = Ti/Tri --- = Ti/Tri --- 带权周转时间带权周转时间　　 W = (∑W = (∑Wi)/nWi)/n --- ---平均带权周转时间平均带权周转时间吞吐量：在给定时间内，一个计算机系统完成的总工作量响应时间：用户向计算机发出一个指令到计算机把相应的执行结果返回给用户所用的时间。

设备利用率：设备使用情况 ３、进程调度•进程调度的功能记录系统中所有进程的执行情况选择占用处理机的进程进行进程上下文切换•进程调度的时机进程调度的时机正在执行的进程执行完毕正在执行的进程执行完毕执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态待状态执行中进程调用了Ｐ原语操作，从而因资源不足而被阻塞；执行中进程调用了Ｐ原语操作，从而因资源不足而被阻塞；或调用了Ｖ原语操作激活了等待资源的进程队列或调用了Ｖ原语操作激活了等待资源的进程队列执行中进程提出Ｉ／Ｏ请求后被阻塞执行中进程提出Ｉ／Ｏ请求后被阻塞 在分时系统中时间片用完在分时系统中时间片用完执行完系统调用，系统程序返回用户进程执行完系统调用，系统程序返回用户进程 就绪队列中某进程优先级变得高于当前执行进程得优先级就绪队列中某进程优先级变得高于当前执行进程得优先级•进程上下文切换一般步骤：１）决定是否做上下文切换以及是否允许做２）保存当前执行进程的上下文３）选择就绪进程４）恢复或装配所选进程的上下文•进程调度性能评价定形：可靠性、简洁性定量：ＣＰＵ利用率、进程在就绪队列中的等待时间与执行时间之比、响应时间４、调度算法•先来先服务•轮转法•多级反馈队列轮转法•优先级法•最短作业优先法•最高响应比优先法例例:某操作系统采用三级调度策略，一级队列时间片10ms，二级100ms，三级1000ms,有若干进程按以下顺序进入队列：进程进入时刻运行时间1010021020350150420013005500206700100 •先来先服务从就绪队列队首选择进程,新进程排在队尾短作业在系统中的驻留平均时间与长作业驻留平均时间相同,对短作业不利。

•轮转法将CPU的处理时间分成固定大小的时间片如果一个进程在被调度选中后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU而排列在就绪队列队尾轮转法调度只适合于可抢占式资源时间片长的选取：太长：？太短：？g = R / NmaxR ---系统对响应时间的要求Nmax---就绪队列允许最大进程数响应时间和服务时间成正比，在响应时间上优于FCFS，对长作业不利•多级反馈队列调度算法多级反馈队列调度算法1 1）系统中有多个进程就绪队列，每个就绪队列对应一个）系统中有多个进程就绪队列，每个就绪队列对应一个调度级别，各级具有不同运行优先级，第一级最高调度级别，各级具有不同运行优先级，第一级最高2 2）各级队列有不同的时间片，优先级越高时间片越小各级队列有不同的时间片，优先级越高时间片越小3 3）各级队列均按先来先服务原则排序）各级队列均按先来先服务原则排序4 4）调度方法：新进程进入后，被放入）调度方法：新进程进入后，被放入1 1级队列末尾；队列级队列末尾；队列中按先来先服务分配处理机；时间片用完还未完成，进入中按先来先服务分配处理机；时间片用完还未完成，进入下一级队列末尾；如果因输入输出或等待时间主动放弃处下一级队列末尾；如果因输入输出或等待时间主动放弃处理机的进程，离开就绪队列，待事件发生后返回同级队列理机的进程，离开就绪队列，待事件发生后返回同级队列队尾。

队尾5 5）当）当1 1级队列空后调度程序才去调度级队列空后调度程序才去调度2 2级队列中的进程，级队列中的进程，3 3级、级、4 4级依次类推依次类推6 6）当比运行进程更高级别队列中到来一个新的进程时，）当比运行进程更高级别队列中到来一个新的进程时，它将抢占处理机，被抢占进程回到原队列尾它将抢占处理机，被抢占进程回到原队列尾算法实现目标：算法实现目标：为提高系统吞吐量和降低作业平均等待时间而为提高系统吞吐量和降低作业平均等待时间而照顾短作业；照顾短作业；为得到较好的输入输出设备利用率和对交互用为得到较好的输入输出设备利用率和对交互用户的及时响应而照顾输入输出型作业；户的及时响应而照顾输入输出型作业； 为什么会照顾短作业？为什么会照顾短作业？为什么会照顾输入输出型作业？为什么会照顾输入输出型作业？对于长作业，由于逐级进入第优先级队列，所获对于长作业，由于逐级进入第优先级队列，所获时间片越来越大，相对普通轮转法对长作业的响时间片越来越大，相对普通轮转法对长作业的响应较优应较优•优先级法优先级法按优先级的高低进行调度按优先级的高低进行调度优先级的确定：优先级的确定：静态静态和和动态动态静态：静态：进程运行前就确定，运行中不可变进程运行前就确定，运行中不可变动态：动态：结合静态优先级和进程动态特征，运行时不断调整结合静态优先级和进程动态特征，运行时不断调整优先级优先级静态优先级：静态优先级：作业调度中确定的原则作业调度中确定的原则1 1）用户自己根据作业紧急度输入优先级）用户自己根据作业紧急度输入优先级2 2）系统或操作员根据作业类型指定优先级）系统或操作员根据作业类型指定优先级（（I/OI/O繁忙的作业、繁忙的作业、CPUCPU繁忙的作业、繁忙的作业、 I/OI/O与与CPUCPU均衡的作均衡的作业、一般作业）业、一般作业）3 3）根据作业资源要求确定（例如根据估计所）根据作业资源要求确定（例如根据估计所需的处理机时间、内存量大小、需的处理机时间、内存量大小、I/OI/O设备类型及数量设备类型及数量进程的静态优先级确定原则：进程的静态优先级确定原则：1 1）按进程类型给予不同优先级）按进程类型给予不同优先级（（I/OI/O繁忙的繁忙的进进程程、、CPUCPU繁忙的繁忙的进程进程、、 I/OI/O与与CPUCPU均衡的均衡的进程进程、一、一般般进程进程））2 2）作业优先级作为进程优先级）作业优先级作为进程优先级动态优先级动态优先级一般原则：一般原则：1 1）根据进程占有）根据进程占有CPUCPU时间长短决定时间长短决定2 2）根据就绪进程等待）根据就绪进程等待CPUCPU时间长短决定时间长短决定由于优先级不断变化，系统要有一定开销进行由于优先级不断变化，系统要有一定开销进行优先级计算优先级计算•最短作业优先选择那些估计需要执行时间最短的•最高响应比优先法R = （W + T ）/ TW ---等待时间T ---估计需要执行的时间6、实时系统调度方法•实时系统的特点有限等待时间有限响应时间用户控制可靠性高系统出错处理能力强•实时系统的上述特性要求系统具有的能力1)很快的进程或线程切换速度2)快速的外部中断响应能力3)基于优先级的随时抢占式调度策略优先级+时间片轮转调度策略基于优先级的非抢占式调度策略基于优先级的固定点抢占式调度策略基于优先级的随时抢占式调度策略•实时调度算法的分类实时调度算法的分类1)1)静态表格驱动静态表格驱动对可能的调度条件和参数进行静态分析对可能的调度条件和参数进行静态分析结果作为实际调度结果结果作为实际调度结果2)2)静态优先级驱动抢先式调度算法静态优先级驱动抢先式调度算法先进行静态分析先进行静态分析, ,但结果只作为任务的优先级但结果只作为任务的优先级3)3)动态计划调度算法动态计划调度算法在调度任务执行之前排出调度计划在调度任务执行之前排出调度计划, ,并分析计并分析计划的调度结果是否使得任务所要求的处理时限得划的调度结果是否使得任务所要求的处理时限得到满足到满足, ,能满足就按计划执行能满足就按计划执行, ,否则修改调度计划否则修改调度计划4)4)尽力而为调度算法尽力而为调度算法不进行可能性分析不进行可能性分析, ,只按优先级进行调度只按优先级进行调度•时限调度算法与频率单调调度算法以满足用户要求的时限为调度原则的算法所需相关输入信息:任务就绪时间或时间到达时间、 开始时限、完成时限、处理时间、 资源要求、优先级基本思想：按用户的时限要求顺序设置优先级，优先级高者占据处理机。

抢占式进程程事件事件发生生时限限执行行时限限结束束时限限DA（（1））01530DA（（2））301560DA（（3））601590DB（（1））03875DB（（2））7538150DB（（3））15038225频率单调调度算法基本原理：频率越低（周期越长）优先级越低使用频率单调调度算法的必要条件：C1/T1 + C2/T2 + +Cn/Tn ≦n(21/n-1)例:三个周期组成的实时任务序列，其执行时间与周期比 ≦0.799习题1.进程调度的主要功能进程调度的主要功能2.进程调度的时机有哪几种进程调度的时机有哪几种3.实时调度的特点实时调度的特点4.假设一个计算机系统具有以下性能特征假设一个计算机系统具有以下性能特征处理一次中断平均耗时处理一次中断平均耗时1ms1ms一次进程调度一次进程调度, ,平均需要平均需要2ms2ms将将CPUCPU分配给选中的进程分配给选中的进程, ,平均需要平均需要1ms1ms设定时器芯片每秒产生设定时器芯片每秒产生100100次中断次中断1)1)操作系统将百分之几的时间用于时钟中断处理操作系统将百分之几的时间用于时钟中断处理2)2)如果操作系统采用轮转法如果操作系统采用轮转法,10,10个时钟中断为一个时间个时钟中断为一个时间片片, ,那么操作系统将百分之几的时间用于进程调度那么操作系统将百分之几的时间用于进程调度5.5.有有5 5个运行作业个运行作业J1…J5,J1…J5,各自运行时间分别为各自运行时间分别为9\6\3\5\7,9\6\3\5\7,假定作业同时到达假定作业同时到达, ,试比较最短作业试比较最短作业优先和最高响应比优先算法的平均周转时间优先和最高响应比优先算法的平均周转时间? ?6.6.为什么说多级反馈调度算法能较好满足交互类、为什么说多级反馈调度算法能较好满足交互类、短批处理类和长批处理类等应用？短批处理类和长批处理类等应用？7.7.设周期性任务设周期性任务P1/P2/P3P1/P2/P3的周期的周期T1/T2/T3T1/T2/T3分别为分别为100/150/350,100/150/350,执行时间执行时间20/40/100,20/40/100,问是否可以采问是否可以采用频率单调调度算法进行调度用频率单调调度算法进行调度8.8.进程调度其主要功能是进程调度其主要功能是: :A.A.选择一个作业调入内存选择一个作业调入内存B.B.选择一个主存中的进程调出到外存选择一个主存中的进程调出到外存C.C.选择一个外存中的进程调入到主存选择一个外存中的进程调入到主存D.D.将一个就绪的进程投入运行将一个就绪的进程投入运行9.在分时系统中,若当前运行的进程连续获得了两个时间片,原因可能是:A.该进程的优先级最高B.就绪队列为空C.该进程最早进入就绪队列D.该进程是一个短进程。