随着计算机的技术逐渐步入家用后，新的调度指标接踵而来，周转时间已经不能满足人们日常工作的需求，更多时候人们更希望计算机能有更好的交互性，使其能更快地去响应任务，由此针对优化响应时间的调度策略也遍地开花，但俗话说鱼和熊掌不可兼得，我们并不能要求周转时间好的同时也要求响应时间好，只能择环境而行。
如果仅仅是想要优化响应时间，轮转算法（Round-Robin,俗称RR）是个不错的选择。
一.轮转算法
轮转算法的思想很简单，就是在一段时间内，轮流将运行队列中的任务走一遍，运行一个任务，然后切换到下一个任务，直至所有任务完成。“一段时间”也称之为“时间片（time slice）”，轮转算法也可称之为“时间切片（time-slicing）算法”，这个时间长度必须要是时钟中断周期的倍数，所以不能随意地去定时间片。
我们可以举个例子，假设A、B、C三个任务同时到达，并且都需要运行5秒钟，那么根据轮转算法，将是以下情景：
可以计算出轮转算法的平均响应时间为：（0+1+2）/3=1，类似地，如果使用最短任务优先算法（如果不知道是什么，可以参考我之前写过的一篇文章：【操作系统】调度策略的基本思想），那么响应时间则是：
（0+5+10）/3=5，需要5秒钟的响应时间，远远高于轮转算法，当然，这是以优化响应时间为前提的，在周转时间面前，还得是SJF略胜一筹。像轮转这样的算法虽然降低了响应时间，但是周转时间很差，有没有一种算法可以优化周转时间的同时又降低响应时间呢？多级反馈队列（Multi-level Feedback Queue,俗称MLFQ）应该是个不错的选择。
二.多级反馈队列
（1）定义
多级反馈队列（Multi-level Feedback Queue,俗称MLFQ）有很多独立的队列，每个队列有不同的优先级。一个任务只能在一个队列中，而MLFQ总是优先执行优先级较高的工作，如果多个队列具有相同的优先级，则会采取轮转调度算法。这里就可以得到MLFQ的两个规则：
- 规则一：如果任务A的优先级＞任务B的优先级，则优先运行任务A。
- 规则二：如果任务A的优先级＝任务B的优先级，则轮转运行A和B。
（2）调整优先级
那么不同任务之间的优先级是如何确定的呢？一个任务的优先级是否可以保持不变直到任务完成呢？多级反馈队列是通过观察任务的行为来及时调整它们的优先级的。当一个任务进入系统时，将其放在最高优先级，随后进行观察，如一个任务频繁放弃CPU进行I/O交互，那么系统会认为这是交互性进程而让它保持高优先级，而当一个任务长期占用CPU时，则会降低其优先级。通过这种方式，MLFQ在任务运行中学习其行为，从而预测它未来的行为。
- 规则三：任务进入系统时，放在最高优先级。
- 规则四：任务用完整个时间片后，降低其优先级。
- 规则五：如果工作在其时间片内主动释放CPU，则优先级不变。
举个例子：假如当前只有一个任务在系统中，使用多级反馈队列调度程序，则会出现以下情况：
任务首先进入最高优先级队列Q2，执行10ms(用完时间片)后降级到Q1队列，而后再次降级到最低优先级队列Q0。再复杂一点，当前又来了一个新任务，则会出现以下情况：
旧任务（黑色）在最低优先级队列中运行（可能被调度程序识别为CPU密集型任务了），当T=100时一个新的任务过来了，先被加入到最高优先级队列中，当运行几个时间片后，降低优先级，新任务执行完毕后，继续完成旧任务（黑色）。难度升级，如有I/O交互的任务存在，则会出现以下情况：
因为新任务每1ms便需要进行I/O，根据规则五（如果工作在其时间片内主动释放CPU，则优先级不变），它将长期保持高优先级，在新任务请求I/O时，CPU被空出，旧任务（黑色）将占用CPU，如此循环。
（3）饥俄问题
至此，多级反馈队列的雏形基本完成，但是这个雏形还存在一个致命的问题：饥俄问题。
- 当交互性任务过多，将导致CPU不断被占用，长任务将永远无法得到CPU，或者称那些优先级低的任务被饿死了。
- 如果一个任务每运行99%的时间片后就主动放弃一次CPU，那么根据规则五，将永远保持高优先级，几乎独占了CPU。
为优化避免上面的问题，可以用一个新的思路去解决它：
- 规则六：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。
以上规则一下子解决了两个问题，它优先保证了各个进程都不会被饿死，以下展示了长时间运行的任务和两个交互性短任务竞争CPU时的行为，分别用不采取优先级提升（左）和采取优先级提升（右）的方式对比：
从图片中可以看出，左边没有提升优先级，长时间运行任务在两个短任务到达后被饿死。而右边则每50ms就主动提升一次优先级，因此保证了贝格任务都能有一些进展。
（4）重写规则
即使拥有规则六的加持，只要规则四和规则五的保留优先级条件不变（只要任务在时间片期间主动释放CPU，则优先级不变），那么调度程序还是很容易被攻克。为了避免这种情况，我们需要重写规则四和规则五，并将它们合并成一条：
- 规则四：一旦工作用完了其在一层中的时间配额（无论中间主动放弃多少次CPU），就降低其优先级。
以下给出没有新规则四和有新规则四下的策略对比：
由图可知，没有新规则四的加持下，进程可以在每个时间片结束前发起一次I/O操作，从而垄断了CPU时间，有了新规则四的加持后，不论进程的I/O行为如何，都会慢慢地降低优先级，从而无法获得超过公平地CPU时间比例。
（5）总结
至此，我们总结得出了多级反馈队列的一个初版调度策略规则：
- 规则一：如果任务A的优先级＞任务B的优先级，则优先运行任务A。
- 规则二：如果任务A的优先级＝任务B的优先级，则轮转运行A和B。
- 规则三：任务进入系统时，放在最高优先级。
- 规则四：一旦工作用完了其在一层中的时间配额（无论中间主动放弃多少次CPU），就降低其优先级。
- 规则五：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。
多级反馈队列有多级队列，并利用反馈信息决定某个任务的优先级，对于短时间运行的交互性任务，获得类似于SJF/STCF的很好的全局性能（如果不知道是什么，可以参考我之前写过的一篇文章：【操作系统】调度策略的基本思想），同时对长时间运行的CPU密集型任务也可以公平地、不断地稳步向前。
