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

《操作系统之处理机调度.ppt》由会员分享，可在线阅读，更多相关《操作系统之处理机调度.ppt（29页珍藏版）》请在三一办公上搜索。

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

2、进程；2)在执行作业控制语句时，系统或根进程为其创建相应的子进程，然后为各子进程分配资源和调度各子进程执行以完成作业要求的任务。,、作业调度,作业调度的功能）记录系统中各作业的状况）从后备队列中挑选出一部分作业投入执行）为被选中作业做好执行前准备工作）在作业执行结束时做善后处理工作,作业调度目标与性能衡量调度目标：对所有作业应该是公平合理的应使设备有高的利用率每天执行尽可能多的作业有快的响应时间。衡量调度策略的指标：周转时间：将一个作业提交给计算机系统后到该作业的结果返回i=Tei Tsi T=(Ti)/n-平均周转时间Wi=Ti/Tri-带权周转时间 W=(Wi)/n-平均带权周转时间,吞吐

3、量：在给定时间内，一个计算机系统完成的总工作量。响应时间：用户向计算机发出一个指令到计算机把相应的执行结果返回给用户所用的时间。设备利用率：设备使用情况,、进程调度,进程调度的功能记录系统中所有进程的执行情况选择占用处理机的进程进行进程上下文切换,进程调度的时机正在执行的进程执行完毕执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态执行中进程调用了原语操作，从而因资源不足而被阻塞；或调用了原语操作激活了等待资源的进程队列执行中进程提出请求后被阻塞在分时系统中时间片用完执行完系统调用，系统程序返回用户进程就绪队列中某进程优先级变得高于当前执行进程得优先级,进程上下文切换一般步骤：）决定是否

4、做上下文切换以及是否允许做）保存当前执行进程的上下文）选择就绪进程）恢复或装配所选进程的上下文进程调度性能评价定形：可靠性、简洁性定量：利用率、进程在就绪队列中的等待时间与执行时间之比、响应时间,、调度算法,先来先服务轮转法多级反馈队列轮转法优先级法最短作业优先法最高响应比优先法,例:某操作系统采用三级调度策略，一级队列时间片10ms，二级100ms，三级1000ms,有若干进程按以下顺序进入队列：进程进入时刻运行时间1010021020350150420013005500206700100,先来先服务从就绪队列队首选择进程,新进程排在队尾短作业在系统中的驻留平均时间与长作业驻留平均时间相同,

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

6、进程进入后，被放入1级队列末尾；队列中按先来先服务分配处理机；时间片用完还未完成，进入下一级队列末尾；如果因输入输出或等待时间主动放弃处理机的进程，离开就绪队列，待事件发生后返回同级队列队尾。5）当1级队列空后调度程序才去调度2级队列中的进程，3级、4级。依次类推。6）当比运行进程更高级别队列中到来一个新的进程时，它将抢占处理机，被抢占进程回到原队列尾,算法实现目标：为提高系统吞吐量和降低作业平均等待时间而照顾短作业；为得到较好的输入输出设备利用率和对交互用户的及时响应而照顾输入输出型作业；为什么会照顾短作业？为什么会照顾输入输出型作业？对于长作业，由于逐级进入第优先级队列，所获时间片越来越大

7、，相对普通轮转法对长作业的响应较优,优先级法按优先级的高低进行调度优先级的确定：静态和动态静态：进程运行前就确定，运行中不可变动态：结合静态优先级和进程动态特征，运行时不断调整优先级静态优先级：作业调度中确定的原则1）用户自己根据作业紧急度输入优先级2）系统或操作员根据作业类型指定优先级（I/O繁忙的作业、CPU繁忙的作业、I/O与CPU均衡的作业、一般作业）3）根据作业资源要求确定（例如根据估计所需的处理机时间、内存量大小、I/O设备类型及数量,进程的静态优先级确定原则：1）按进程类型给予不同优先级（I/O繁忙的进程、CPU繁忙的进程、I/O与CPU均衡的进程、一般进程）2）作业优先级作为进

8、程优先级动态优先级一般原则：1）根据进程占有CPU时间长短决定2）根据就绪进程等待CPU时间长短决定由于优先级不断变化，系统要有一定开销进行优先级计算,最短作业优先选择那些估计需要执行时间最短的最高响应比优先法R=（W+T）/TW-等待时间T-估计需要执行的时间,6、实时系统调度方法,实时系统的特点有限等待时间有限响应时间用户控制可靠性高系统出错处理能力强,实时系统的上述特性要求系统具有的能力1)很快的进程或线程切换速度2)快速的外部中断响应能力3)基于优先级的随时抢占式调度策略优先级+时间片轮转调度策略基于优先级的非抢占式调度策略基于优先级的固定点抢占式调度策略基于优先级的随时抢占式调度策略

9、,实时调度算法的分类1)静态表格驱动对可能的调度条件和参数进行静态分析结果作为实际调度结果2)静态优先级驱动抢先式调度算法先进行静态分析,但结果只作为任务的优先级3)动态计划调度算法在调度任务执行之前排出调度计划,并分析计划的调度结果是否使得任务所要求的处理时限得到满足,能满足就按计划执行,否则修改调度计划4)尽力而为调度算法不进行可能性分析,只按优先级进行调度,时限调度算法与频率单调调度算法以满足用户要求的时限为调度原则的算法所需相关输入信息:任务就绪时间或时间到达时间、开始时限、完成时限、处理时间、资源要求、优先级基本思想：按用户的时限要求顺序设置优先级，优先级高者占据处理机。抢占式,频率

10、单调调度算法基本原理：频率越低（周期越长）优先级越低使用频率单调调度算法的必要条件：C1/T1+C2/T2+Cn/Tn n(21/n-1)例:三个周期组成的实时任务序列，其执行时间与周期比 0.799,习题,进程调度的主要功能进程调度的时机有哪几种实时调度的特点假设一个计算机系统具有以下性能特征处理一次中断平均耗时1ms一次进程调度,平均需要2ms将CPU分配给选中的进程,平均需要1ms设定时器芯片每秒产生100次中断1)操作系统将百分之几的时间用于时钟中断处理2)如果操作系统采用轮转法,10个时钟中断为一个时间片,那么操作系统将百分之几的时间用于进程调度,5.有5个运行作业J1J5,各自运行

11、时间分别为96357,假定作业同时到达,试比较最短作业优先和最高响应比优先算法的平均周转时间?6.为什么说多级反馈调度算法能较好满足交互类、短批处理类和长批处理类等应用？7.设周期性任务P1/P2/P3的周期T1/T2/T3分别为100/150/350,执行时间20/40/100,问是否可以采用频率单调调度算法进行调度8.进程调度其主要功能是:A.选择一个作业调入内存B.选择一个主存中的进程调出到外存C.选择一个外存中的进程调入到主存D.将一个就绪的进程投入运行,9.在分时系统中,若当前运行的进程连续获得了两个时间片,原因可能是:A.该进程的优先级最高B.就绪队列为空C.该进程最早进入就绪队列D.该进程是一个短进程,