先来先服务(FCFS, First Come First Serve)是最简单的调度算法,按先后顺序进行调度。
按照作业提交或进程变为就绪状态的先后次序,分派CPU;
当前作业或进程占用CPU,直到执行完或阻塞,才出让CPU(非抢占方式)。
在作业或进程唤醒后(如I/O完成),并不立即恢复执行,通常等到当前作业或进程出让CPU。
比较有利于长作业,而不利于短作业。
有利于CPU繁忙的作业,而不利于I/O繁忙的作业。
轮转法(Round Robin)是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。
将系统中所有的就绪进程按照FCFS原则,排成一个队列。
每次调度时将CPU分派给队首进程,让其执行一个时间片。时间片的长度从几个ms到几百ms。
在一个时间片结束时,发生时钟中断。
调度程序据此暂停当前进程的执行,将其送到就绪队列的末尾,并通过上下文切换执行当前的队首进程。
进程可以未使用完一个时间片,就出让CPU(如阻塞)。
时间片长度变化的影响
过长->退化为FCFS算法,进程在一个时间片内都执行完,响应时间长。
过短->用户的一次请求需要多个时间片才能处理完,上下文切换次数增加,响应时间长。
对响应时间的要求:T(响应时间)=N(进程数目)*q(时间片)
就绪进程的数目:数目越多,时间片越小
系统的处理能力:应当使用户输入通常在一个时间片内能处理完,否则使响应时间,平均周转时间和平均带权周转时间延长。
多级反馈队列算法(Round Robin with Multiple Feedback)是轮转算法和优先级算法的综合和发展。
设置多个就绪队列,分别赋予不同的优先级,如逐级降低,队列1的优先级最高。每个队列执行时间片的长度也不同,规定优先级越低则时间片越长,如逐级加倍。