操作系统教程第3章-2 进程调度.ppt

第3章 进程管理 3.1 进程的引入 3.2 进程的结构 3.3 进程控制 3.4 进程的同步与互斥 3.5 进程间通信 3.6 进程调度 3.7 死锁 3.8 线程 进程调度概念 又称微观调度、低级调度、短程调度、处理机调度。 控制协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。 操作系统中实现进程调度的程序称为进程(线程)调度程序，或分派程序(Dispatcher)，常驻内存。 进程调度程序是操作系统最为核心的部分，进程调度策略的优劣直接影响到整个系统的性能。 进程调度方式 非抢占方式(Non-preemptive ） 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去。 抢占方式(Preemptive） 当一个进程正在处理器上执行时，系统可以根据规定的原则剥夺分配给它的处理器，而把处理器分配给其他进程使用。常用的剥夺原则如下： 优先权原则：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用。 短进程优先原则 时间片原则 抢占式策略比非抢占式策略的开销大 调度算法性能衡量 周转时间 如果进程i进入内存的时刻是ts，完成时刻是tf，该进程的周转时间ti为：ti = tf - ts 实际上，它是进程的等待时间与运行时间之和。 平均周转时间 为了提高系统的性能，要让若干个进程的平均周转时间和平均带权周转时间最小。 平均周转时间 T = (Σti) / n 带权周转时间和平均带权周转时间 如果进程i的周转时间为ti，所需运行时间为tk，则称 wi=ti /tk为该进程的带权周转时间。 ti是等待时间与运行时间之和，故带权周转时间总大于1。 平均带权周转时间W = (Σwi) / n 调度算法 先来先服务算法（FCFS） 最短进程优先算法（SPF） 最短剩余时间优先调度算法（SRTF） 最高响应比优先调度算法（HRRF） 高优先权优先调度算法（HPF） 基于时间片的轮转调度算法（RR） 多级反馈队列调度算法 先来先服务调度算法FCFS 调度算法 按照进程进入就绪队列的先后次序来选择。 调度方式采用非抢占方式。 例 最短进程优先算法（SPF） 算法 以进程所要求的CPU时间为标准，总选取估计运行时间最短的进程投入运行。 调度方式采用非抢占方式。 例 最短剩余时间优先调度算法SRTF 最短剩余时间优先调度算法也称为抢占式的SPF算法 基本思想 一个新进程进入就绪状态，如果新进程需要的CPU时间比当前正在执行的进程剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行进程。 调度方式采用抢占方式。 最短剩余时间优先调度SRTF算法示例 时间片轮转调度算法（RR） 抢占方式调度。 基本思想 把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行。 轮转调度算法示例 多级反馈队列调度算法 (1)将就绪队列分为N级，每个就绪队列分配给不同的时间片； (2)队列级别越高，时间片越长，级别越小，时间片越短； (3)系统从第一级调度，当第一级为空时，系统转向第二个队列，..... (4)当运行进程用完一个时间片，放弃CPU时，进入下一级队列； (5)等待进程被唤醒时，进入原来的就绪队列； (6)当进程第一次就绪时，进入第一级队列。 《操作系统、实验》 何时发生进程调度呢? 有四种情况都会发生进程调度: 当一个进程从运行态切换成阻塞态时； 当一个进程从运行态切换成就绪态时； 当一个进程从阻塞态切换成就绪态时； 当一个进程中止时。 进程调度的调度队列模型 处理器 低级调度 完成 超时 就绪队列 等待 事件 事件 出现 交互用户 优点 实现简单 缺点 算法只顾及进程的等候时间，没考虑进程要求服务时间的长短； 不利于短进程而优待了长进程； 没考虑进程的优先级。 优点 算法易于实现。 缺点 忽视了进程等待时间；不利于长进程，会出现饥饿现象。 优点 可以用于分时系统，保证及时响应用户要求。 缺点 系统开销增加，首先要保存进程的运行情况记录，以比较其剩余时间大小； 其次，抢占本身也要消耗处理机时间 响应比 R = 周转时间 / 运行时间 =（运行时间+等待时间）/ 运行时间 = 1 +（等待时间 / 运行时间） 短进程容易得到较高响应比；