嵌入式系统教学课件：操作系统6-处理机调度.ppt

处理机调度 处理机调度的基本概念 处理机调度的基本概念 1. 高级、中级和低级调度 处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性能指标有重要影响 可把处理机调度分成三个层次： 高级调度 中级调度 低级调度 1. 高级、中级和低级调度 高级调度（作业调度、长程调度、接纳调度） 将外存作业调入内存，创建PCB等，插入就绪队列。 一般用于批处理系统，分/实时系统一般直接入内存，无此环节。 调度特性 接纳作业数（内存驻留数） 太多――― 周转时间T长 太少――― 系统效率低 接纳策略：即采用何种调度算法：FCFS、短作业优先等 1. 高级、中级和低级调度 低级调度（进程调度，短程调度） 主要是由分派程序（Dispatcher）分派处理机。 非抢占方式： 简单，实时性差 (如win31) 抢占方式 时间片原则 优先权原则 短作业优先原则。 1. 高级、中级和低级调度 中级调度（中程） 为提高系统吞吐量和内存利用率而引入的内-外存对换功能（换出时，进程为挂起或就绪驻外状态） 进程调度的运行频率 低中高 2. 进程调度的任务 进程调度的任务是控制协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。 思考 三种调度被引发的事件？ 事件的表现方式？ 3.确定算法的原则 具有公平性 资源利用率高（特别是CPU利用率） 在交互式系统情况下要追求响应时间（越短越好） 在批处理系统情况下要追求系统吞吐量 4.进程调度方式 非剥夺方式：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。 剥夺方式：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。 5.进程调度性能衡量的指标 周转时间 响应时间 CPU-I/O执行期 6.进程调度模型 1)只有进程调度的调度队列模型 6.进程调度模型 6.进程调度模型 7.选择调度方式的准则 面向用户的准则： 周转时间短； 响应时间快； 截止时间的保证； 优先权准则 3.2 调度算法 调度算法实际上就是一个资源分配的问题 先进先出(FIFO)算法 最短CPU运行期优先调度算法 最高优先权优先调度算法 轮转法 多级反馈队列 1.先进先出算法FIFO 思想： 把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。 评价: 优点:实现简单. 缺点:没考虑进程的优先级 2.最短CPU运行期优先调度算法 思想： 该算法从就绪队列中选出“下一个CPU执行期”最短的进程，为之分配处理机。 评价： 优点：可获得较好的调度性能 缺点：难以准确地知道下一个CPU执行期，而只能根据每一个进行的执行历史来预测。 3.FIFO与SJF的比较 4.最高优先权优先调度算法 思想： 该算法总是把处理机分配给就绪队列中具有最高优先权的进程。常用以下两种方法来确定进程的优先权(优先级根据优先数来决定) 分类： 静态优先数法：静态优先权是在创建进程时确定的，在整个运行期间不再改变。依据有：进程类型、进程对资源的要求、用户要求的优先权。 动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变。 5.高响应比优先调度算法 优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： 6.轮转法 思想： 把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行。 分类： 简单轮转法：系统将所有就绪进程按FIFO规则排队，按一定的时间间隔把处理机分配给队列中的进程。这样，就绪队列中所有进程均可获得一个时间片的处理机而运行。 多级队列方法：将系统中所有进程分成若干类，每类为一级。 7.时间片轮转法 时间片选择问题： 固定时间片 可变时间片 与时间片大小有关的因素： 系统响应时间 就绪进程个数 CPU能力 ①简单轮转法调度模型 ②多级反馈队列调度算法 将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，.....当运行进程用完一个时间片，放弃CPU时，进入下一级队列； 等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列。 ②多级反馈队列调