之前介绍了3种早期批处理的调度算法 调度算法——先来先服务算法、短作业优先算法 和 高响应比优先算法，本节要介绍的3种算法则常用于分时操作系统和实时操作系统等交互式系统。

时间片轮转 RR
算法思想：让每个进程公平的、轮流的得到运行机会，每个进程在一定时间间隔内都可以得到响应（即得到CPU运行），相比于先来先服务算法，RR除了公平外还考虑了让每个进程的响应时间尽量短；
算法规则：让每一个到达就绪队列的进程执行一个时间片，一开始按照进程进入队列的顺序执行，如果进程未在一个时间片内执行完，则剥夺CPU，将其重新放到就绪队列队尾；
用于作业/进程调度：仅用于进程调度；
是否可抢占：抢占式调度；
优点：公平；每个进程响应快；
缺点：没有考虑到作业/进程的紧急程度；时间片大小需要足够合适，否则会降低进程运行效率。
是否导致饥饿：不会。
适用于：分时操作系统。

上面是时间片大小为2的情况。

如果时间片大小太大，每个进程都能在一个时间片内完成，则RR算法会退化为先来先服务算法，增大进程的响应时间（即后到达的进程可能要等很久才能开始执行），进程变为串行，从而降低并发效率。

PS：增大响应时间是指，例如系统中有10个进程在并发执行，每个进程需要2个时间片才会运行完。如果时间片为1，则第10个进程需要等待9秒才被响应。如果时间片为2，则需要18秒才被响应。

如果时间片大小太小，进程频繁发生切换，CPU时间都消耗在进程切换而非用户任务处理，也会降低CPU效率，降低进程运行效率。切换进程的CPU时间应该小于CPU总运行时间的1%。

优先级调度算法

算法思想：根据任务的紧急程度来决定处理顺序；

算法规则：每个作业/进程有各自的优先级，选择优先级最高的 作业/进程最先运行；

用于作业/进程调度：皆可；

是否可抢占：非抢占式调度（只有在当前进程主动放弃CPU时才会引发调度），抢占式调度（每次就绪队列改变都会引发调度）；

优点：区分进程的紧急程度，根据优先级决定调度顺序；也可以灵活设定 CPU/IO密集型进程的优先级；

缺点：若源源不断地有高优先级进程到来，则可能导致饥 饿。

是否导致饥饿：会。

就绪队列未必只有一个，可以按照不同优先级组织多个队列。也可以把优先级的进程排在更接近队头位置。

根据优先级是否可变，可将优先级分为静态优先级和动态优先级两种。

静态优先级：创建进程是确定，之后一直不变。

动态优先级：创建进程时有一个初始值，之后根据情况动态调整优先级。

如何合理设置各类进程的优先级？通常来说

系统进程优先级 高于 用户进程。

前台进程 高于 后台进程。

IO密集型进程 高于 CPU密集型进程。原因是IO设备和CPU可以并行工作，优先让IO密集型进程工作可以让IO设备尽早投入工作，并且CPU会在发出IO请求后立刻处理之后的CPU密集型进程，如此一来两种进程并行运行，IO设备处理IO密集型进程的请求，同时CPU也在运行CPU密集型的进程运算，IO设备和CPU都不会闲着。提高了资源利用率，系统吞吐量和并发率。

如果采用动态优先级，什么时候应该调整优先级？（可以从公平、提高资源利用率的角度考虑）

如果某进程在就绪队列等待了很长时间，可以提升其优先级。

如果某进程占用CPU时间很长，可以适当降低其优先级。

如果发现一个进程频繁的发生IO操作，可以提升其优先级。

其实 高响应比算法 本质也是一种动态优先级算法，根据进程的等待时间和运行时间调整哪个进程优先被调度。

小结：FCFS的特点是公平；SJF的特点是先处理短作业，追求最小的平均等待时间；RR的特点是在追求公平的前提下，还保证了每个进程被尽早响应（被尽早开始处理）；优先级调度算法的特点是区分进程紧急程度，根据优先级决定调度顺序。

下面介绍的多级反馈队列调度算法折中了上述几种算法的优点。

多级反馈队列调度算法

算法思想：对其他调度算法的折中（公平性、每个进程及时响应、区分紧急程度）；

算法规则：

1、设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。

2、新进程到达时先进入第1级队列（最高优先级），分配最长时间片，按FCFS原则调度。

若时间片用完，进入下一级队列队尾。如果已经处于最低级队列，则时间片用完时，重新放到本队列队尾。

3、当第k级队列为空时，才会选择调度k+1级队列的进程。只有开始调度某一进程时，才会为这个队头进程分配时间片。

4、被抢占时，当前进程不降级，放回本队列的队尾。

5、主动让出CPU时，当前进程不降级，例如如果进程因IO阻塞而让出CPU，则放回本队列的队尾，如果多次因IO阻塞让出CPU，说明他是IO密集型进程，还可以被放入上一级队列中。

用于作业/进程调度：用于进程调度；

是否可抢占：抢占式，当k级队列的进程在运行时，若更上级的队列进入一个新进程，新进程会抢占处理机，原来的进程会返回k级队列尾部；

优点：该算法同时使用了FCFS、RR、SPF 和 优先级调度算法，也集合了他们的优点，即公平、快速响应、短进程快速完成（他们可能在第一级队列就完成了）、区分进程紧急程度、灵活调整系统对CPU/IO密集型进程的偏好；

缺点：可能导致饥饿。

是否导致饥饿：会，例如不停有新进程进入1级队列，而且这些进程都是短进程，在1个时间片内就可以完成，此时下级队列的进程就一直无法持有CPU。

UNIX系统使用的就是多级反馈队列算法。

这3种算法更适用于交互式系统。

更多内容请关注微信公众号