FIFO或First Come, First Served (FCFS)先来先服务
调度的顺序就是任务到达就绪队列的顺序
公平、简单(FIFO队列)、非抢占、不适合交互式
未考虑任务特性,平均等待时间可以缩短
Shortest Job First (SJF)
最短的作业(CPU区间长度最小)最先调度
SJF可以保证最小的平均等待时间
Shortest Remaining Job First (SRJF)
SJF的可抢占版本,比SJF更有优势
SJF(SRJF): 如何知道下一CPU区间大小?根据历史进行预测: 指数平均法
优先权调度
每个任务关联一个优先权,调度优先权最高的任务
注意:优先权太低的任务一直就绪,得不到运行,出现“饥饿”现象
Round-Robin(RR)轮转调度算法
设置一个时间片,按时间片来轮转调度(“轮叫”算法)
优点: 定时有响应,等待时间较短;缺点: 上下文切换次数较多
时间片太大,响应时间太长;吞吐量变小,周转时间变长;当时间片过长时,退化为FCFS
多级队列调度
按照一定的规则建立多个进程队列
不同的队列有固定的优先级(高优先级有抢占权)
不同的队列可以给不同的时间片和采用不同的调度方法
存在问题1:没法区分I/O bound和CPU bound
存在问题2:也存在一定程度的“饥饿”现象
多级反馈队列
在多级队列的基础上,任务可以在队列之间移动,更细致的区分任务
可以根据“享用”CPU时间多少来移动队列,阻止“饥饿”
最通用的调度算法,多数OS都使用该方法或其变形,如UNIX、Windows等