Appearance
2.10 调度算法
根据系统的资源分配策略所规定的资源分配算法。
对于不同的系统目标，通常采用不同的调度算法。
先来先服务（FCFS，First Come First Served）
选择最先进入就绪队列的进程投入执行，即进程按照请求CPU的顺序使用CPU。
举例
评价
- 属于非抢占调度方式
- 有利于CPU繁忙型的进程，而不利于I/O繁忙型的进程
- 不能直接用于分时系统，通常与其它调度算法混合使用
- 平均周转时间长
- 对长进程(作业)有利，不利于短进程(作业)
时间片轮转调度（RR，Round Robin）
- 每个进程被分配一个时间片，如果在时间片结束时该进程还在运行，则剥夺其CPU并分配给另一个进程。
- 被剥夺CPU的进程则插入到就绪队列末尾，等待下次调度。
- 如果该进程在时间片内阻塞或结束，则立即切换CPU。
典型应用系统示例——分时联机系统
举例
评价
- 属于抢占调度方式
- 常用于分时系统或事务处理系统
- 时间片的设置与系统性能、响应时间密切相关
- 时间片太短——进程切换频繁，降低CPU效率
- 时间片太长——引起对短的交互请求的响应时间变长
- 在分时系统中，时间片大小的确定应综合考虑最大用户数目、响应时间、系统效率等多种因素。
- 对CPU密集型(繁忙型)进程有利，对I/O型密集型(繁忙型)进程不利
- CPU密集型进程可充分利用时间片
- 而I/O密集型进程每次短时间使用CPU，之后I/O阻塞，I/O操作完成加入就绪队列后，若有CPU密集型进程占用CPU，或就绪队列里已经有CPU密集型进程，则需要长时间等待
- CPU密集型进程不公平的使用了大部分CPU时间
短进程（作业）优先（SPN/SJN，Shortest Job/Process Next）
短进程或短作业优先调度，前提为执行时间预知。
举例
评价
- 非抢占调度方式
- 该算法对长作业不利，可能导致长进程饥饿
- 有利于短进程，减小了平均周转时间
- 缺少剥夺机制，不适用于分时系统或事务处理环境
- 作业(进程)的长短根据用户所提供的估计执行时间而定，用户估计不准时，导致该算法不一定能真正做到短作业优先调度
剩余时间最短者优先（SRT，Shortest Remaining Time）
调度程序总是选择预期剩余时间最短的进程。
当一个新进程加入就绪队列时，如果它比当前运行的进程具有更短的剩余时间，就可能抢占当前正在运行的进程。
在SPN的基础上增加了剥夺机制。
举例
评价
优点
- 既不像FCFS那样偏爱长进程，也不像RR算法那样会产生很多额外的中断(因时间片而产生)，从而减少了开销。
- 周转时间方面，SRT比SPN性能要好，短作业可以立即被选择执行。
问题
- 需要估计预计的服务时间
- 存在进程饥饿现象
- 必须记录进程的已服务时间
最高响应比优先（HRRN，Highest Response Ratio Next）
当前进程执行完毕或需要阻塞时，选择就绪队列中响应比最高的进程投入执行。
举例
评价
- 实质上是一种动态优先权调度算法
- 是FCFS和SPN的结合，既照顾了短进程，又考虑了作业到达的先后次序，不会使长进程长期得不到服务
- 利用该算法时，每次调度之前，都须先做响应比的计算，会增加系统开销，且难以准确计算
多级反馈队列调度（MFQS，Multilevel Feedback Queue Scheduling）
采用多级队列区别对待的方法“惩罚长进程”
- 多个独立的、优先级不同的就绪队列
- 各队列区别对待，即优先调度优先级高的队列
- 进程执行过程中可降级，即在整个生命周期内可能位于不同队列
基于时间片轮转的反馈调度算法
- 设置多个就绪队列，每个队列赋予不同优先级。
- 第一队列优先级最高，依次递减
- 各个队列中进程执行的时间片不相同，优先级越高的队列，时间片越小
- 新进程进入时，首先放入第一个队列尾，按FCFS原则排队。
- 如果进程在当前队列规定的时间片内完成则退出，一般而言，从队列i中调度的进程允许执行2i的时间，然后才被抢占，降级到下一个优先级队列(如果没有被抢占，则当前进程不降级)。
- 到达最低优先级队列后，不再降级。
- 仅当第一队列空闲时，才调度第二队列中的进程，依次类推。
举例
评价
多级反馈队列调度算法具有较好的性能，能较好地满足各种类型用户的需要。
- 有利于终端型作业用户。常为短作业，能在第一队列所规定的时间片内完，对短作业用户有利。
- 长批处理作业用户。对于长作业，它将依次在第1,2,…,n个队列中运行，然后再按轮转方式运行，能在前几个队列所规定的时间片内完成。
问题：当不断有新进程到来时，长进程可能饥饿