第五讲进程调度线程概念.ppt

进程调度（CPU调度） 要解决的问题 WHAT：按什么原则分配CPU —进程调度算法 WHEN：何时分配CPU —进程调度的时机 HOW： 如何分配CPU —CPU调度过程（进程的上下文切换） 处理机调度分成三个层次 处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性能指标有重要影响 可把处理机调度分成三个层次： 高级调度 中级调度 低级调度 高级调度也称为作业调度或宏观调度 高级调度的时间尺度通常是分钟、小时或天 中级调度涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问 低级调度也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效 一.进程调度算法 1．进程调度 进程调度的任务是控制协调进程对CPU的竞争。即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程 2．确定算法的原则 具有公平性 资源利用率高（特别是CPU利用率） 在交互式系统情况下要追求响应时间（越短越好） 在批处理系统情况下要追求系统吞吐量 3．各种进程调度算法 先进先出进程调度算法（FIFO） 按照进程就绪的先后次序来调度进程 优点:实现简单 缺点:没考虑进程的优先级 基于优先数的调度（HPF—Highest Priority First） 优先选择就绪队列中优先级最高的进程投入运行 优先级根据优先数来决定 确定优先数的方法 静态优先数法： 在进程创建时指定优先数，在进程运行时优先数不变 动态优先数法： 在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变 两种占用CPU的方式 可剥夺式（可抢占式Preemptive）： 当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用 不可剥夺式（不可抢占式 Non-preemptive ）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去 时间片轮转程序调度算法(RR—Round Robin) 把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行 分时系统中常用时间片轮转法 时间片选择问题： 固定时间片 可变时间片 与时间片大小有关的因素： 系统响应时间 就绪进程个数 CPU能力 多队列反馈调度算法： 将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，.....当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列 * 首先系统中设置多个就绪队列 * 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大 * 各个队列按照先进先出调度算法 * 一个新进程就绪后进入第一级队列 * 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列 * 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾 * 当第一级队列空时，就去调度第二级队列，如此类推 * 当时间片到后，进程放弃CPU，回到下一级队列 二.进程调度的时机 当一个进程运行完毕，或由于某种错误而终止运行 当一个进程在运行中处于等待状态（等待I/O） 分时系统中时间片到 当有一个优先级更高的进程就绪（可抢占式） 例如：新创建一个进程，一个等待进程变成就绪 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语） 三. 进程切换 进程切换 一个进程让出处理器，由另一个进程占用处理器的过程 进程的切换使系统中的各进程均有机会占用CPU 进程的切换是由进程状态的变化引起的，而进程状态的变化又与出现中断事件有关 当有中断事件发生时，当前运行的进程被中断，中断响应后由操作系统处理出现的中断事件。中断处理后，某些进程的状态会发生变化，也可能又创建了一些新的进程。因此，要进行队列的调整。然后，进程调度根据预定的调