操作系统之处理机调度

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

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

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

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

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

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

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

8、数量,进程的静态优先级确定原则： 1）按进程类型给予不同优先级（I/O繁忙的进程、CPU繁忙的进程、 I/O与CPU均衡的进程、一般进程） 2）作业优先级作为进程优先级 动态优先级 一般原则： 1）根据进程占有CPU时间长短决定 2）根据就绪进程等待CPU时间长短决定 由于优先级不断变化，系统要有一定开销进行优先级计算,最短作业优先 选择那些估计需要执行时间最短的 最高响应比优先法 R = （W + T ）/ T W -等待时间 T -估计需要执行的时间,6、实时系统调度方法,实时系统的特点 有限等待时间 有限响应时间 用户控制 可靠性高 系统出错处理能力强,实时系统的上述特性要求系统具有的能

9、力 1)很快的进程或线程切换速度 2)快速的外部中断响应能力 3)基于优先级的随时抢占式调度策略 优先级+时间片轮转调度策略 基于优先级的非抢占式调度策略 基于优先级的固定点抢占式调度策略 基于优先级的随时抢占式调度策略,实时调度算法的分类 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,各自运行时间分别为96357,假定作业同时到达,试比较最短作业优先和最高响应比优先算法的平均周转时间? 6.为什么说多级反馈调度算法能较好满足交互类、短批处理类和长批处理类等应用？ 7.设周期性任务P1/P2/P3的周期T1/T2/T3分别为100/150/350,执行时间20/40/100,问是否可以采