多级反馈队列

Multi-level Feedback Queue = MLFQ

如名字所示，解决思路就是将任务分级。

分成多个队列，每个队列的优先级不同，调度程序永远先运行完高优先级中的任务，再运行低优先级队列中的任务。

同一队列有多个任务时，轮转运行。

一个任务只能存在于一个队列中。

MLFQ调度策略的关键在于如何设置优先级。

MLFQ不是设置固定的优先级，而是在程序运行过程中观察其行为动态调整。

譬如交互性任务会有频繁的I/O操作，从而放弃CPU. 那么可以提高他的优先级，让他的响应时间变短。

如果任务频繁使用CPU, 那么就可以降低其优先级，让他的周转时间变短。

于是，产生了2个规则：

1. 如果A的优先级> B的优先级，运行A(不运行B)
2. 如果A的优先级=B的优先级，轮转运行。

通过观察进程的行为，产生了下面的规则：

3. 工作进入系统时，放在最高优先级（最上层队列）
4. 规则4a: 工作用完整个时间片后，降低其优先级（移入下一个队列）
5. 规则4b: 如果工作在其时间片内主动释放CPU, 则优先级不变。

显然，调度程序假设了刚进入的工作是短时运行任务/交互任务。如果假设失败，就会进入规则4a.

看起来挺好，但是这里有3个问题：

1. 如果交互任务很多。那么低优先级的CPU密集型任务将没有运行机会，会被饿死。
2. 了解到了规则4b, 程序员可以作弊。故意在时间片用完之前执行一行I/O操作，从而保持自己的高优先级不变，破坏了公平性。
3. 程序并不是一成不变的，CPU密集型工作在某段时间也有交互型工作，当他已经进入低优先级队列后，享受不到交互性工作的待遇。

观察发现，问题之所以存在是因为工作降到低优先级后，得不到运行的机会。

解决办法很简单，让这些低优先级工作重新进入高优先级队列不就行了。

加入规则5：

6. 规则5：经过一段时间S, 就将系统中所有工作重新加入最高优先级队列。

ps: 这里S怎么设置是个问题，过高，长工作会饿死。过低，交互型工作又得不到合适的CPU时间比例。

问题，1，3 解决。还有问题2. 问题是规则4b, 改变计时方式，把原来的调度时重新计时，改成记录在某层队列中总的CPU时间即可。

改写规则4：

规则4： 一旦工作用完了其在某一层中消耗的时间配额（无论中间主动放弃了多少次CPU), 就降低其优先级（移入低一级队列）

总结下：

1. 规则1：如果A的优先级> B的优先级，运行A(不运行B)
2. 规则2：如果A的优先级=B的优先级，轮转运行。
3. 规则3：工作进入系统时，放在最高优先级（最上层队列）
4. 规则4： 一旦工作用完了其在某一层中消耗的时间配额（无论中间主动放弃了多少次CPU), 就降低其优先级（移入低一级队列）
5. 规则5：经过一段时间S, 就将系统中所有工作重新加入最高优先级队列。

实际使用中有些问题：

1. 配置多少队列？
2. 每一层队列的时间片配额多大？
3. S怎么设置，即该多久提升一次进程的优先级

不同的实现有不同的配置。一般来说高优先的时间片短，低优先级的时间片长。