[OS]Three Easy Pieces Chapter 8

Scheduling: The Multi-Level Feedback Queue

多级反馈队列（Multi-level Feedback Queue，MLFQ）需要解决两个问题：

1. 优化周转时间

   通过SJF或者STCT可以优化周转时间，但是这需要提前知道一个任务的运行时间。

2. 优化响应时间

   RR可以优化响应时间，但是周转时间很差。

1 MLFQ: Basic Rules

多级反馈队列有多个队列，每个队列的优先级不同。总是让优先级高的任务先运行，如果两个任务在同一个队列（优先级相同），则使用RR策略。

• 规则1：如果$Priority(A) > Priority(b)$，那么A运行
• 规则2：如果$Priority(A) = Priority(B)$，那么A，B用RR策略

多级反馈队列根据任务的历史行为来预测任务的未来行为，并以此调整任务的优先级。如果一个任务频繁的放弃CPU，申请IO，那么维持这个任务的高优先级（IO密集型），因为该任务可能需要较强的交互性；反之，如果一个任务使用CPU很长一段时间（CPU密集型），那么降低任务的优先级。

2 Attempt #1: How To Change Priority

任务的配额：即一个给定任务在当前优先级的队列能运行的时间，如果时间用完了，那么就会降低其优先级。

• 规则3：作业进入系统时，会被置于最高优先级（最顶队列）。
• 规则4a：如果作业在运行过程中用完了分配资源，其优先级就会降低（即向下移动一个队列）。
• 规则4b：如果作业在分配时间结束前放弃 CPU（如执行 I/O 操作），则其优先级保持不变（即其分配时间被重置）。

问题

1. 饥饿问题

   如果一直有短作业到来，那么优先级低的任务将永远无法运行。

2. 恶意程序

   如果一个任务在用完自己的时间片之前，申请一个IO操作，那么它将永远维持高优先级，导致分配不公平。

3. 任务变动

   如果一个任务从CPU密集型转变为IO密集型，如何处理

3 Attempt #2: The Priority Boost

• 规则5：在经过一段时间S后，将所有的任务重新放置在最高优先级队列中。

通过这么做，解决了上述的问题1和问题2。

S的值很难确定，如果太长，会导致低优先级的任务饥饿；如果太短，会导致交互性降低。

4 Attempt #3: Better Accounting

调度器应该记录每个任务在当前队列的运行时间，只要用完了时间片，就降低其优先级。所以，规则4修改为

• 规则4：一旦某项作业用完了给定级别的时间分配（无论它让出 CPU 多少次），其优先级就会降低（即向下移动一个队列）。

5 Tuning MLFQ And Other Issues

大多数实现允许不同优先级的队列有不同的时间片大小，高优先级的通常小一点，低优先级的通常高一些。