多级反馈队列调度算法

操作系统之多级反馈队列调度算法

多级反馈队列调度(MLFQ)算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。多级反馈队列调度算法是目前操作系统调度算法中被公认的一种较好的调度算法。它可以满足各种类型进程的需要，既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。

算法原理

1. 设有N个队列（Q1,Q2....QN），其中各个队列对于处理机的优先级不同,即位于各个队列中的作业(进程)的优先级也是不一样的。
   一般来说，优先级Priority(Q1) > Priority(Q2) > ... > Priority(QN)。
   位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高，依次类推其它的队列。

2. 对于优先级最低的队列(QN)，作业调度遵循时间片轮转法。位于队列QN中有M个作业，运行时间是通过QN这个队列所设定的时间片来确定的；
   对于其他队列，遵循的是先来先服务算法,同时每一进程分配一定的时间片，若时间片运行完时进程未结束，则进入下一优先级队列的末尾。

3. 各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。
   同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大。

算法描述

1. 进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
2. 首先调度优先级高的队列中的进程。若Q1中没有调度的进程，则调度次优先级队列中的进程。当且仅当高优先级队列中没有调度的进程是，才调度次优先级。
3. 对于同一个进程中的进程，采用先来先服务(FCFS)分配固定时间片调度(除了最后一个对列)。分配的时间片大小取决去当前队列。如果当前作业在固定时间片内未完成，进入下一级队列，直至完成。
4. 在最后一个对列的进程，采用时间片轮转调度方式调度。
5. 当低优先级队列中的进程正在运行时，有新的作业到达，此时须立即把正在运行的进程放回当前队列的队尾，然后把处理机分给高优先级进程(抢占式)。或者等待当前进程执行结束，重新回到高优先级队列中(非抢占式)。

算法总结

​ 多级反馈队列调度算法既能最小化交互工作的响应时间，又能减少对工作长度的先验知识，从而最小化周转时间。