多级反馈队列

多级反馈队列正如之前说的一样，有多个队列，不同队列有不同优先级，相应的进程被分配到不同的队列中，高优先级的队列中的进程优先执行，并且一个队列中的进程之间采用之前介绍过的调度算法进行调度

书中采用的是Round Robin调度，所以现在我们有以下规则：

• rule1：优先级高的队列中的进程先运行
• rule2：优先级相同的队列中的进程采用Round Robin调度同时进行

此外，一个进程的优先级不是固定的，而是动态调整的，OS可以根据进程的历史行为对进程类型进行一定程度的估计，然后根据估计结果调整进程的优先级，这样可以使得进程的优先级更加合理

这里我们的进程优先级的变化规则是：

• rule3：一个进程刚刚被接收到时，拥有最高优先级
• rule4：一个进程如果运行完一个时间片后没有被阻塞，那么它的优先级会降低；一个进程如果在未运行完时如果被阻塞了，那么它的优先级不会降低（被阻塞说明进程与用户可能有着高交互性）

在这样的方式下，OS不用知道进程的具体运行时间，一个运行久的进程自然就会在低优先级下运行，如果此时插入一个新的进程，它会在高优先级下抢占CPU并运行，如果它是个短进程，那么它能在优先级降到最低前完成，否则认为它也是个长进程，而在低优先级下运行
这样的优先级调整方式既可以在不知道进程具体长度的条件下优先执行短进程，也能很好地保证高交互性的进程优先运行，同时优化了turnaround time和response time

缺陷和优化

这样的规格还有一些缺陷，比如说：

• 如果CPU一直被很多短时进程占用，那么一些长进程就难以运行，从而陷入饥饿状态（starvation）
• 有些人可以编写程序欺骗系统的调度，比如编写一个进程在时间片的99%时刻阻塞，然后在1%时刻解除阻塞，这样就可以让进程一直处于高优先级队列中，从而不断地抢占CPU
• 一个进程可能在一段时间内是长进程，得到了低优先级，但是一段时间后过渡到了高交互的短进程，但是此时它的优先级已经降到最低，从而无法抢占CPU

对于以上的缺陷，我们可以通过Boost来解决以上问题
Boost的做法是，每隔一定的时间，就将所有的进程提高到最高优先级的队列中，这样的话，即便是低优先级的长进程也能有所运行，而不会陷入饥饿状态
而欺骗调度程序的收益将会大幅度下降，因为在Boost的时候，所有的进程都会被提高到最高优先级
而交互性提高的长程序也能来到高优先级，并在高交互的阶段保持高优先级，从而能够抢占CPU

所以我们有：

• rule5：每隔一段时间，将所有的进程提高到最高优先级的队列中

继续优化

虽然上面的做法能够一定程度上缓解欺骗调度的问题，但是书上提出了更好的解决方式：
我们给每个进程在一个优先级的队列中分配一个配额时间，当它的配额时间用完后，不管是否阻塞，都会被减低优先级，从而让其他进程有机会运行
这样的话rule4就可以被改写为：

• rule4：每个进程在队列中被分配一段配额时间，如果一个进程的配额时间用完，那么它的优先级会被降低

一般来说，队列的优先级越高，配额时间越少

总结

以上几条就是MLFQ的基本规则，此外的很多操作系统有着自己的各种更具体地功能和优化，比如说：

• Solaris使用一个table储存各种调度参数
• freeBSD使用数学公式动态改变各个队列的优先级
• 还有些OS的最高优先级是为OS保留的，不会被分配给用户进程