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

1、处理机调度处理机调度 处理机调度的基本概念 在多道程序环境下，进程数目往往多于处理机数目，致使 它们争用处理机。 这就要求系统能按某种算法，动态地把处理机分配给就绪 队列中的一个进程，使之执行。 分配处理机的任务是由进程调度程序完成的。它是操作系 统设计的中心问题之一。 处理机调度的基本概念 进程调度要解决的问题： WHAT：按什么原则分配CPU 进程调度算法 WHEN：何时分配CPU 进程调度的时机 HOW： 如何分配CPU CPU调度过程（进程的上下文切换） 1. 高级、中级和低级调度 处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性能指 标有重要影响 可把处理机调度

2、分成三个层次： 高级调度高级调度 中级调度中级调度 低级调度低级调度 高级调度也称为作业调度或宏观调度 高级调度的时间尺度通常是分钟、小时或天 中级调度涉及进程在内外存间的交换 从存储器资源管理的角度来看，把进程的部分 或全部换出到外存上，可为当前运行进程的执 行提供所需内存空间，将当前进程所需部分换 入到内存。指令和数据必须在内存里才能被处 理机直接访问 低级调度也称微观调度 从处理机资源分配的角度来看，处理机需要经 常选择就绪进程或线程进入运行状态，低级调 度的时间尺度通常是毫秒级的。 由于低级调度算法的频繁使用，要求在实现时 做到高效。 1. 高级、中级和低级调度 高级调度（作业调度、长

3、程调度、接纳调度） 将外存作业调入内存，创建PCB等，插入就绪队列。 一般用于批处理系统，分/实时系统一般直接入内存，无 此环节。 调度特性 接纳作业数（内存驻留数） 太多周转时间T长 太少系统效率低 接纳策略：即采用何种调度算法：FCFS、短作业优先等 1. 高级、中级和低级调度 低级调度（进程调度，短程调度） 主要是由分派程序（Dispatcher）分派处理机。 非抢占方式： 简单，实时性差 (如win31) 抢占方式 时间片原则 优先权原则 短作业优先原则。 1. 高级、中级和低级调度 中级调度（中程） 为提高系统吞吐量和内存利用率而引入的内- 外存对换功能（换出时，进程为挂起或就绪驻

4、外状态） 进程调度的运行频率 低中高 2. 进程调度的任务 进程调度的任务是控制协调进程对CPU的竞 争，即按一定的调度算法从就绪队列中选 中一个进程，把CPU的使用权交给被选中的 进程。 思考 三种调度被引发的事件？三种调度被引发的事件？ 事件的表现方式？事件的表现方式？ 3.确定算法的原则 具有公平性 资源利用率高（特别是CPU利用率） 在交互式系统情况下要追求响应时间（越 短越好） 在批处理系统情况下要追求系统吞吐量 4.进程调度方式 非剥夺方式：分派程序一旦把处理机分配给某 进程后便让它一直运行下去，直到进程完成或 发生某事件而阻塞时，才把处理机分配给另一 个进程。 剥夺方式：当一个进

5、程正在运行时，系统可以 基于某种原则，剥夺已分配给它的处理机，将 之分配给其它进程。剥夺原则有：优先权原则、 短进程优先原则、时间片原则。 5.进程调度性能衡量的指标 周转时间 响应时间 CPU-I/O执行期 6.进程调度模型 1)1)只有进程调度的调度队列模型只有进程调度的调度队列模型 图 4 - 1 仅具有进程调度的调度队列模型 图 4-2 具有高、低两级调度的调度队列模型 6.进程调度模型 图 4-3 具有三级调度时的调度队列模型 6.进程调度模型 7.选择调度方式的准则 面向用户的准则： 周转时间短； 响应时间快； 截止时间的保证； 优先权准则 面向系统的准则： 系统吞吐量高； 处理机

6、利用率好； 各类资源的平衡利用 周转时间：作业从提交到完成的时间，分为： （1）驻外等待调度时间 （2）驻内等待调度时间 （3）执行时间 （4）阻塞时间 平均周转时间 平均带权 可见：带权w越小越好,Ts为实际服务时间。 1 1 n i s i T T n W 1 1 n i i T n T 响应时间快：（对交互性作业）键盘提交请求到 首次响应时间： （1）输入传送时间 （2）处理时间 （3）响应传送时间 3.2 调度算法 调度算法实际上就是一个资源分配的问题 先进先出(FIFO)算法 最短CPU运行期优先调度算法 最高优先权优先调度算法 轮转法 多级反馈队列 1.先进先出算法FIFO 思想：

7、 把处理机分配给最先进入就绪队列的进程，一 个进程一旦分得处理机，便执行下去，直到该 进程完成或阻塞时，才释放处理机。 评价: 优点:实现简单. 缺点:没考虑进程的优先级 进程名 到达 时间 服务 时间 开始执 行 时间 完成 时间 周转 时间 带权周 转时间 A010111 B110011011001 C21101102100100 D31001022021991.99 2.最短CPU运行期优先调度算法 思想： 该算法从就绪队列中选出“下一个CPU执行期” 最短的进程，为之分配处理机。 评价： 优点：可获得较好的调度性能 缺点：难以准确地知道下一个CPU执行期，而 只能根据每一个进行的执行历

8、史来预测。 3.FIFO与SJF的比较 作业情况 调度算法 进程名A B C D E平均 到达时间0 1 2 3 4 服务时间4 3 5 2 4 FCFS（a） 完成时间4 7 12 14 18 周转时间4 6 10 11 149 带权周转时 间 1 2 2 5.5 3.5 2.8 SJF（b） 完成时间4 9 18 6 13 周转时间4 8 16 3 98 带权周转时 间 1 2.67 3.1 1.5 2.25 2.1 4.最高优先权优先调度算法 思想： 该算法总是把处理机分配给就绪队列中具有最高优 先权的进程。常用以下两种方法来确定进程的优先 权(优先级根据优先数来决定) 分类： 静态优先

9、数法：静态优先权是在创建进程时确定的，在 整个运行期间不再改变。依据有：进程类型、进程对资 源的要求、用户要求的优先权。 动态优先数法：在进程创建时创立一个优先数，但在其 生命周期内优先数可以动态变化。如等待时间长优先数 可改变。 5.高响应比优先调度算法 优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系 统对该作业的响应时间，故该优先权又 相当于响应比RP。据此，又可表示为： 6.轮转法 思想： 把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一 个进程，进程轮流占有CPU，当时间片用完时，即使进程未执 行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末 尾。同时系

10、统选择另一个进程运行。 分类： 简单轮转法：系统将所有就绪进程按FIFO规则排队，按一定 的时间间隔把处理机分配给队列中的进程。这样，就绪队列 中所有进程均可获得一个时间片的处理机而运行。 多级队列方法：将系统中所有进程分成若干类，每类为一级。 7.时间片轮转法 时间片选择问题： 固定时间片 可变时间片 与时间片大小有关的因素： 系统响应时间 就绪进程个数 CPU能力 简单轮转法调度模型 多级反馈队列调度算法 将就绪队列分为N级，每个就绪队列分配给不 同的时间片，队列级别越高，时间越长，级别 越小，时间片越小，最后一级采用时间片轮转， 其他队列采用先进先出； 系统从第一级调度，当第一级为空时，

11、系统转 向第二个队列，.当运行进程用完一个时 间片，放弃CPU时，进入下一级队列； 等待进程被唤醒时，进入原来的就绪队列；当 进程第一次就绪时，进入第一级队列。 首先系统中设置多个就绪队列 每个就绪队列分配给不同时间片，优先级高的为第一级 队列，时间片最小，随着队列级别的降低，时间片加大 各个队列按照先进先出调度算法 一个新进程就绪后进入第一级队列 进程由于等待而放弃CPU后，进入等待队列，一旦等待的 事件发生，则回到原来的就绪队列 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢 占进程回到原来一级就绪队列末尾 当第一级队列空时，就去调度第二级队列，如此类推 当时间片到后，进程放弃CPU

12、，回到下一级队列 多级反馈队列调度算法 多级反馈队列调度算法 最高优先权队列时间片 I/ O 至CPU S1 次高优先权队列时间片 至CPU S2 至CPU S3 最低优先权队列时间片 至CPU Sn （时间片：S1S2S3） 8.进程调度的时机 进程运行完毕，或由于某种错误而终止运行 进程在运行中处于等待状态（等待I/O） 分时系统中时间片到 有一个优先级更高的进程就绪（可抢占式） 例如：新创建一个进程，一个等待进程变成就绪 在进程通信中，执行中的进程执行了某种原语 操作（P操作，阻塞原语，唤醒原语） 何时切换进程 只要OS取得对CPU的控制，进程切换就可能发 生，如: 超级用户调用 来自程序的显式请求来自程序的显式请求 ( (如：打开文件如：打开文件) )，该进程通常会，该进程通常会 被阻塞被阻塞 陷阱 最末一条指令导致出错，会引起进程移至退出状态最末一条指令导致出错，会引起进程移至退出状态 中断 外部因素影响当前指令的执行，控制被转移至外部因素影响当前指令的执行，控制被转移至IHIH（中（中 断处理程序）断处理程序） 9.引起进程调度的原因 正在执行的进程执行完毕或因