《操作系统之处理机调度ppt课件》由会员分享，可在线阅读，更多相关《操作系统之处理机调度ppt课件（29页珍藏版）》请在金锄头文库上搜索。
1、第四章 处置机调度分级调度作业调度进程调度调度算法实时系统调度方法1、分级调度作业的形状及其转换调调度的度的层层次次通常通常处处置机置机调调度可以分度可以分为为级级作作业调业调度高度高级调级调度度按一定原那么按一定原那么对对外存外存输输入井上的大量后入井上的大量后备备作作业进业进展展选择选择，给选给选出的作出的作业业分配内存、分配内存、输输入入输输出出设备设备等必要等必要资资源，并建立源，并建立进进程。作程。作业终业终了后，了后，回收回收资资源。源。交交换调换调度中度中级调级调度度将将处处于外存交于外存交换换区中的就区中的就绪绪形状或就形状或就绪绪等待形状的等待形状的进进程程调调入内存，或把入
2、内存，或把处处于内存就于内存就绪绪形形状或内存等待形状的状或内存等待形状的进进程交程交换换到外存交到外存交换换区区进进程程调调度低度低级调级调度度选选取取处处于就于就绪绪形状的形状的进进程占用，程占用，进进程上下文切程上下文切换换线线程程调调度度作业与进程的关系作业是义务虚体，进程是执行实体。作业如何分解为进程？1)系统必需为一个作业创建一个根进程； 2)在执行作业控制语句时，系统或根进程为其创建相应的子进程，然后为各子进程分配资源和调度各子进程执行以完成作业要求的义务。、作业调度作业调度的功能记录系统中各作业的情况从后备队列中挑选出一部分作业投入执行为被选中作业做好执行前预备任务在作业执行终
3、了时做善后处置任务作作业调业调度目的与性能衡量度目的与性能衡量调调度目的：度目的：对对一切作一切作业应该业应该是公平合理的是公平合理的应应使使设备设备有高的利用率有高的利用率每天每天执执行尽能行尽能够够多的作多的作业业有快的呼有快的呼应时间应时间。衡量衡量调调度度战战略的目的：略的目的：周周转时间转时间：将一个作：将一个作业业提交提交给计给计算机系算机系统统后到后到该该作作业业的的结结果前往果前往i = Tei Tsii = Tei Tsi T = (Ti)/n - T = (Ti)/n -平均周平均周转时间转时间Wi = Ti/Tri - Wi = Ti/Tri - 带权带权周周转时间转时间
4、 W = (Wi)/n - W = (Wi)/n -平均平均带权带权周周转时间转时间吞吐量：在给定时间内，一个计算机系统完成的总任务量。呼应时间：用户向计算机发出一个指令到计算机把相应的执行结果前往给用户所用的时间。设备利用率：设备运用情况 、进程调度进程调度的功能记录系统中一切进程的执行情况选择占用途置机的进程进展进程上下文切换进进程程调调度的度的时时机机正在正在执执行的行的进进程程执执行行终终了了执执行中行中进进程本人程本人调调用阻塞原用阻塞原语语将本人阻塞起来将本人阻塞起来进进入睡入睡眠等待形状眠等待形状执执行中行中进进程程调调用了原用了原语语操作，从而因操作，从而因资资源缺乏而被源缺乏
5、而被阻塞；或阻塞；或调调用了原用了原语语操作激活了等待操作激活了等待资资源的源的进进程程队队列列执执行中行中进进程提出程提出恳恳求后被阻塞求后被阻塞 在分在分时时系系统统中中时间时间片用完片用完执执行完系行完系统调统调用，系用，系统统程序前往用程序前往用户进户进程程 就就绪队绪队列中某列中某进进程程优优先先级变级变得高于当前得高于当前执执行行进进程得程得优优先先级级进程上下文切换普通步骤：决议能否做上下文切换以及能否允许做保管当前执行进程的上下文选择就绪进程恢复或装配所选进程的上下文进程调度性能评价定形：可靠性、简约性定量：利用率、进程在就绪队列中的等待时间与执行时间之比、呼应时间、调度算法先
6、来先效力轮转法多级反响队列轮转法优先级法最短作业优先法最高呼应比优先法例例:某操作系统采用三级调度战略，一级队列某操作系统采用三级调度战略，一级队列时间片时间片10ms，二级，二级100ms，三级，三级1000ms,有假设干进程按以下顺序进入队列：有假设干进程按以下顺序进入队列：进程进程进入时辰进入时辰运转时间运转时间1010021020350150420013005500206700100 先来先效力从就绪队列队首选择进程,新进程排在队尾短作业在系统中的驻留平均时间与长作业驻留平均时间一样,对短作业不利。轮转法将CPU的处置时间分成固定大小的时间片。假设一个进程在被调度选中后用完了系统规定的
7、时间片，但未完成要求的义务，那么它自行释放本人所占有的CPU而陈列在就绪队列队尾。轮转法调度只适宜于可抢占式资源时间片长的选取：太长：？太短：？g = R / NmaxR -系统对呼应时间的要求Nmax-就绪队列允许最大进程数呼应时间和效力时间成正比，在呼应时间上优于FCFS，对长作业不利多多级级反响反响队队列列调调度算法度算法1 1系系统统中有多个中有多个进进程就程就绪队绪队列，每个就列，每个就绪队绪队列列对应对应一个一个调调度度级别级别，各，各级级具有不同运具有不同运转优转优先先级级，第一，第一级级最高。最高。2 2各各级队级队列有不同的列有不同的时间时间片，片，优优先先级级越高越高时间时
8、间片越片越小。小。3 3各各级队级队列均按先来先效力原那么排序列均按先来先效力原那么排序4 4调调度方法：新度方法：新进进程程进进入后，被放入入后，被放入1 1级队级队列末尾；列末尾；队队列中按先来先效力分配列中按先来先效力分配处处置机；置机；时间时间片用完片用完还还未完成，未完成，进进入下一入下一级队级队列末尾；假列末尾；假设设因因输输入入输输出或等待出或等待时间时间自自动动放放弃弃处处置机的置机的进进程，分开就程，分开就绪队绪队列，待事件列，待事件发发生后前往同生后前往同级级队队列列队队尾。尾。5 5当当1 1级队级队列空后列空后调调度程序才去度程序才去调调度度2 2级队级队列中的列中的进
9、进程，程，3 3级级、4 4级级。依次。依次类类推。推。6 6当比运当比运转进转进程更高程更高级别队级别队列中到来一个新的列中到来一个新的进进程程时时，它将，它将抢抢占占处处置机，被置机，被抢抢占占进进程回到原程回到原队队列尾列尾算法算法实现实现目的：目的：为为提高系提高系统统吞吐量和降低作吞吐量和降低作业业平均等待平均等待时间时间而而照照顾顾短作短作业业；为为得到得到较较好的好的输输入入输输出出设备设备利用率和利用率和对对交互用交互用户户的及的及时时呼呼应应而照而照顾输顾输入入输输出型作出型作业业； 为为什么会照什么会照顾顾短作短作业业？为为什么会照什么会照顾输顾输入入输输出型作出型作业业？
10、对对于于长长作作业业，由于逐，由于逐级进级进入第入第优优先先级队级队列，所列，所获获时间时间片越来越大，相片越来越大，相对对普通普通轮转轮转法法对长对长作作业业的呼的呼应较优应较优优优先先级级法法按按优优先先级级的高低的高低进进展展调调度度优优先先级级确确实实定：静定：静态态和和动态动态静静态态：进进程运程运转转前就确定，运前就确定，运转转中不可中不可变变动态动态：结结合静合静态优态优先先级级和和进进程程动态动态特征，运特征，运转时转时不断不断调调整整优优先先级级静静态优态优先先级级：作作业调业调度中确定的原那么度中确定的原那么1 1用用户户本人根据作本人根据作业紧业紧急度急度输输入入优优先先
11、级级2 2系系统统或操作或操作员员根据作根据作业类业类型指定型指定优优先先级级I/OI/O忙碌的作忙碌的作业业、CPUCPU忙碌的作忙碌的作业业、 I/O I/O与与CPUCPU平衡平衡的作的作业业、普通作、普通作业业3 3根据作根据作业资业资源要求确定例如根据源要求确定例如根据估估计计所需的所需的处处置机置机时间时间、内存量大小、内存量大小、I/OI/O设备类设备类型及数型及数量量进进程的静程的静态优态优先先级级确定原那么：确定原那么：1 1按按进进程程类类型型给给予不同予不同优优先先级级I/OI/O忙碌的忙碌的进进程、程、CPUCPU忙碌的忙碌的进进程、程、 I/O I/O与与CPUCPU
12、平衡的平衡的进进程、普程、普通通进进程程2 2作作业优业优先先级级作作为进为进程程优优先先级级动态优动态优先先级级普通原那么：普通原那么：1 1根据根据进进程占有程占有CPUCPU时间长时间长短决短决议议2 2根据就根据就绪进绪进程等待程等待CPUCPU时间长时间长短决短决议议由于由于优优先先级级不断不断变变化，系化，系统统要有一定开要有一定开销进销进展展优优先先级计级计算算最短作业优先选择那些估计需求执行时间最短的最高呼应比优先法R = W + T / TW -等待时间T -估计需求执行的时间6、实时系统调度方法实时系统的特点有限等待时间有限呼应时间用户控制可靠性高系统出错处置才干强实时系统
13、的上述特性要求系统具有的才干1)很快的进程或线程切换速度2)快速的外部中断呼应才干3)基于优先级的随时抢占式调度战略优先级+时间片轮转调度战略基于优先级的非抢占式调度战略基于优先级的固定点抢占式调度战略基于优先级的随时抢占式调度战略实时调实时调度算法的分度算法的分类类1)1)静静态态表格表格驱动驱动对对能能够够的的调调度条件和参数度条件和参数进进展静展静态态分析分析结结果作果作为实为实践践调调度度结结果果2)2)静静态优态优先先级驱动抢级驱动抢先式先式调调度算法度算法先先进进展静展静态态分析分析, ,但但结结果只作果只作为义务为义务的的优优先先级级3)3)动态动态方案方案调调度算法度算法在在调
14、调度度义务执义务执行之前排出行之前排出调调度方案度方案, ,并分并分析方案的析方案的调调度度结结果能否使得果能否使得义务义务所要求的所要求的处处置置时时限得到限得到满满足足, ,能能满满足就按方案足就按方案执执行行, ,否那么修正否那么修正调调度度方案方案4)4)尽力而尽力而为调为调度算法度算法不不进进展能展能够够性分析性分析, ,只按只按优优先先级进级进展展调调度度时限调度算法与频率单调调度算法以满足用户要求的时限为调度原那么的算法所需相关输入信息:义务就绪时间或时间到达时间、 开场时限、完成时限、处置时间、 资源要求、优先级根本思想：按用户的时限要求顺序设置优先级，优先级高者占据处置机。抢
15、占式进进程程事件事件发发生生时时限限执执行行时时限限终终了了时时限限DA101530DA2301560DA3601590DB103875DB27538150DB315038225频率单调调度算法根本原理：频率越低周期越长优先级越低运用频率单调调度算法的必要条件：C1/T1 + C2/T2 + +Cn/Tn n(21/n-1)例:三个周期组成的实时义务序列，其执行时间与周期比 0.799习题1.进程调度的主要功能进程调度的主要功能2.进程调度的时机有哪几种进程调度的时机有哪几种3.实时调度的特点实时调度的特点4.假设一个计算机系统具有以下性能特征假设一个计算机系统具有以下性能特征5.处置一次中断
16、平均耗时处置一次中断平均耗时1ms1ms6.一次进程调度一次进程调度, ,平均需求平均需求2ms2ms7.将将CPUCPU分配给选中的进程分配给选中的进程, ,平均需求平均需求1ms1ms8.设定时器芯片每秒产生设定时器芯片每秒产生100100次中断次中断9.1)1)操作系统将百分之几的时间用于时钟中断处置操作系统将百分之几的时间用于时钟中断处置10.2)2)假设操作系统采用轮转法假设操作系统采用轮转法,10,10个时钟中断为一个时个时钟中断为一个时间片间片, ,那么操作系统将百分之几的时间用于进程调度那么操作系统将百分之几的时间用于进程调度5.5.有有5 5个运个运转转作作业业J1J5,J1
17、J5,各自运各自运转时间转时间分分别为别为96357,96357,假定作假定作业业同同时时到达到达, ,试试比比较较最短作最短作业优业优先和最高呼先和最高呼应应比比优优先算法的平均周先算法的平均周转时间转时间? ?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.该进程是一个短进程
