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

第四章 处理机调度 分级调度 作业调度 进程调度 调度算法 实时系统调度方法 1、分级调度 作业的状态及其转换 调度的层次 通常处理机调度可以分为４级 １）作业调度（高级调度） 按一定原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出设备等必要资源，并建立进程。作业完毕后，回收资源。 ２）交换调度（中级调度） 将处于外存交换区中的就绪状态或就绪等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区 ３）进程调度（低级调度） 选取处于就绪状态的进程占用ＣＰＵ，进程上下文切换 ４）线程调度 作业与进程的关系 作业是任务实体，进程是执行实体。 作业如何分解为进程？ 1) 系统必须为一个作业创建一个根进程； 2) 在执行作业控制语句时，系统或根进程为其创建相应的子进程，然后为各子进程分配资源和调度各子进程执行以完成作业要求的任务。 ２、作业调度 作业调度的功能 １）记录系统中各作业的状况 ＪＣＢ ２）从后备队列中挑选出一部分作业投入执行 ３）为被选中作业做好执行前准备工作 ４）在作业执行结束时做善后处理工作 作业调度目标与性能衡量 调度目标： 对所有作业应该是公平合理的 应使设备有高的利用率 每天执行尽可能多的作业 有快的响应时间。 衡量调度策略的指标： 周转时间：将一个作业提交给计算机系统后到该作业的结果返回 Ｔi = Tei – Tsi T = (∑Ti)/n ---平均周转时间 Wi = Ti/Tri --- 带权周转时间 　 W = (∑Wi)/n ---平均带权周转时间 吞吐量：在给定时间内，一个计算机系统完成的总工作量。 响应时间：用户向计算机发出一个指令到计算机把相应的执行结果返回给用户所用的时间。 设备利用率：设备使用情况 ３、进程调度 进程调度的功能 记录系统中所有进程的执行情况 选择占用处理机的进程 进行进程上下文切换 进程调度的时机 正在执行的进程执行完毕 执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态 执行中进程调用了Ｐ原语操作，从而因资源不足而被阻塞；或调用了Ｖ原语操作激活了等待资源的进程队列 执行中进程提出Ｉ／Ｏ请求后被阻塞 在分时系统中时间片用完 执行完系统调用，系统程序返回用户进程 就绪队列中某进程优先级变得高于当前执行进程得优先级 进程上下文切换 一般步骤： １）决定是否做上下文切换以及是否允许做 ２）保存当前执行进程的上下文 ３）选择就绪进程 ４）恢复或装配所选进程的上下文 进程调度性能评价 定形：可靠性、简洁性 定量：ＣＰＵ利用率、进程在就绪队列中的等待时间与执行时间之比、响应时间 ４、调度算法 先来先服务 轮转法 多级反馈队列轮转法 优先级法 最短作业优先法 最高响应比优先法 例:某操作系统采用三级调度策略，一级队列时间片10ms，二级100ms，三级1000ms, 有若干进程按以下顺序进入队列： 进程 进入时刻 运行时间 1 0 100 2 10 20 3 50 150 4 200 1300 5 500 20 6 700 100 先来先服务 从就绪队列队首选择进程,新进程排在队尾 短作业在系统中的驻留平均时间与长作业驻留平均时间相同,对短作业不利。 轮转法 将CPU的处理时间分成固定大小的时间片。如果一个进程在被调度选中后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU而排列在就绪队列队尾。 轮转法调度只适合于可抢占式资源 时间片长的选取： 太长：？ 太短：？ g = R / Nmax R ---系统对响应时间的要求 Nmax---就绪队列允许最大进程数 响应时间和服务时间成正比，在响应时间上优于FCFS，对长作业不利 多级反馈队列调度算法 1）系统中有多个进程就绪队列，每个就绪队列对应一个调度级别，各级具有不同运行优先级，第一级最高。 2）各级队列有不同的时间片，优先级越高时间片越小。 3）各级队列均按先来先服务原则排序 4）调度方法：新进程进入后，被放入1级队列末尾；队列中按先来先服务分配处理机；时间片用完还未完成，进入下一级队列末尾；如果因输入输出或等待时间主动放弃处理机的进程，离开就绪队列，待事件发生后返回同级队列队尾。 5）当1级队列空后调度程序才去调度2级队列中的进程，3级、4级。。。依次类推。 6）当比运行进程更高级别队列中到来一个新的进程时，它将抢占处理机，被抢占进程回到原队列尾 算法实现目标： 为提高系统吞吐量和降低作业平均等待