概述
1962年，Corbato首次提出多级反馈队列，应用于兼容时分共享系统(CTSS)。Corbato因在CTSS中的贡献和后来在Multics中的贡献，获得了ACM颁发的图灵奖(Turing Award)。该调度程序经过多年的一系列优化，出现在许多现代操作系统中。
多级反馈队列需要解决两方面的问题：
- 优化周转时间(T 周转时间= T 完成时间−T 到达时间 )
- 降低响应时间(T 响应时间= T 首次运行−T 到达时间 )
设计
规则定义
MLFQ 中有许多独立的队列(queue)，每个队列有不同的优先级(priority level)。任何时刻，一个工作只能存在于一个队列中。
- 规则 1：如果 A 的优先级 > B 的优先级，运行 A(不运行 B)。
- 规则 2：如果 A 的优先级 = B 的优先级，轮转运行 A 和 B。
- 规则 3：工作进入系统时，放在最高优先级(最上层队列)。
- 规则 4：一旦工作用完了其在某一层中的时间配额(无论中间主动放弃了多少次 CPU)，就降低其优先级(移入低一级队列)。
- 规则 5：经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。
基本原则
规则1和规则2为基础规则，保证了高优先级的先运行，同等优先级的轮转执行。
改变优先级
规则3描述了多级反馈队列的初始状态，即一个进程进入队列时，先将其放入最高优先级队列中。
规则4描述了多级反馈队列的下调优先级(down)原则，采用时间配额制度(在MLFQ 的每层队列提供更完善的 CPU 计时方式(accounting)。 调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时)，可以防止某些恶意程序几乎独占CPU。
提升优先级
规则5的存在是为了避免饥饿(starvation)问题。解决方法是周期性地提升(boost)所有工作的优先级。
总结
MLFQ不需要对工作的运行方式有先验知识，而是通过观察工作的运行来给出对应的优先级。通过这种方式，MLFQ可以同时满足各种工作的需求：对于短时间运行的交互型工作，获得类似于SJF/STCF的很好的全局性能，同时对长时间运行的CPU密集型负载也可以公平地、不断地稳步向前。
因此，许多系统使用某种类型的MLFQ作为自己的基础调度程序，包括类BSD UNIX系统、Solaris以及Windows NT和其后的Window系列操作系统。
Linux Real-Time Scheduler，使用Multi-level Queue优先级调度
-
每个任务有自己的优先级、具体策略
-
具体策略可根据任务需求针对性选择
- SCHED_RR:任务执行一定时间片后挂起
- SCHED_FIFO:任务执行至结束
reference
[1] 操作系统导论(ostep)
[2] 上海交通大学并行与分布式系统研究所-进程/线程调度
