处理机调度（CPU调度）.pptVIP

处理机调度（CPU调度） (1)起因 (2)调度范围与调度模型 (3)调度标准 (4)调度方式与调度算法 (5)性能分析 (6)后果（饥饿，死锁）及解决 处理机调度（CPU调度） 关键要解决的问题 WHAT：按什么原则分配CPU —进程调度算法 WHEN：何时分配CPU —进程调度的时机 HOW： 如何分配CPU —CPU调度过程（进程的上下文切换） 处理机调度的三个层次 处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性能指标有重要影响 可把处理机调度分成三个层次： 高级调度 中级调度 低级调度 处理机调度的三个层次（续） 高级调度也称为作业调度或宏观调度 高级调度的时间尺度通常是分钟、小时或天 中级调度涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问 低级调度也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效 处理机调度的分类 分类 ---按层次：高级（作业）、中级、低级（进程） ---按OS类型：批处理、分时、实时、多处理机 ---按时间尺度：宏观（分、时、天），微观（毫秒） 1.处理机调度算法 （1）处理机调度 处理机调度的任务是控制协调进程对CPU的竞争即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程 （2）调度标准－确定算法的原则 用户希望周转时间短---对批处理系统 系统希望平均（带权）周转时间短---对批处理系统 用户希望响应时间短---对分时系统 用户希望开始执行的时间或完成时间短---对实时系统 用户希望自己优先权高---对三种OS 系统希望吞吐量大---对批处理系统 系统希望处理机和资源的利用率高---对三种OS （３）调度方式与算法　 调度方式:抢占式／非抢占式 可剥夺式（可抢占式Preemptive）： 当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用 不可剥夺式（不可抢占式 Non-preemptive ）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去 常用算法 　FIFO,SPF（改进得最短剩余时间优先SRT: shortest remaining time first）,优先级,时间片轮转（round robin）,高响应比优先（Highest Response Ratio Next）、Unix的多级队列反馈（Round Robin with Multiple Feedback） 不同OS，选择特定的算法 评价 各种进程调度算法 先进先出进程调度算法（FIFO） 按照进程就绪的先后次序来调度进程 优点:实现简单 缺点:没考虑进程的优先级 基于优先数的调度（HPF—Highest Priority First） 优先选择就绪队列中优先级最高的进程投入运行 优先级根据优先数来决定 确定优先数的方法 静态优先数法： 在进程创建时指定优先数，在进程运行时优先数不变 动态优先数法： 在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变 时间片轮转程序调度算法(RR—Round Robin) 把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行 分时系统中常用时间片轮转法： 时间片选择问题： 固定时间片 可变时间片 与时间片大小有关的因素： 系统响应时间 就绪进程个数 CPU能力 各种进程调度算法（续6） 多级队列反馈调度算法 将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，.....当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列 * 首先系统中设置多个就绪队列 * 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大 * 各个队列按照先进先出调度算法 * 一个新进程就绪后进入第一级队列