【OSTEP】调度: 多级反馈队列 (MLFQ) | 优先级提升 | 饥饿问题 | 愚弄调度问题 | MLFQ 调优

💭 写在前面

本系列博客为复习操作系统导论的笔记，内容主要参考自：

• Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy PiecesA. Silberschatz, P. Galvin, and G. Gagne,
• Operating System Concepts, 9th Edition, John Wiley & Sons, Inc., 2014, ISBN 978-1-118-09375-7.Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

0x00 引入：需要一个新的高效算法

FIFO 算法

• Simple but suffers from convoy effect → results in low CPU and device utilization.
• 简单，但受到护航效应的影响 → 导致 CPU 和设备利用率低。
  

SJF 算法

• Good for reducing average turnaround time and average waiting time.
• 对减少平均周转时间和平均等待时间有好处。
• Problem: How to know the job length? Is estimation always good?
• 问题：如何知道任务长度？估算总是好的吗？

RR scheduling 算法

• Good for reducing response time but not good for reducing turnaround time.
• 对减少响应时间有作用，但对减少周转时间没屌用。

需要一个新的算法来做下面的事情

• Optimize turnaround time → Run shorter jobs first.
• 优化周转时间 → 先运行较短的任务。
• Minimize response time → Use RR to make processes run as much as possible.
• 最大限度地减少响应时间 → 使用RR，使进程尽可能地运行。
• Learn from the past to predict the future without a priori knowledge of job length.
• 通过学习过去，预测未来，而不需要先验的任务长度知识。

本章将介绍一种著名的调度方法 —— 多级反馈队列，简称 MLFQ。

0x01  多级反馈队列算法（MLFQ Algorithm）

MLFQ has a number of distinct queues.    MLFQ 有许多不同的队列

• Each queue has a different priority level   每一个队列都有不同的优先级。

A job that is ready to run is on a single queue.    一个工作只能存在于一个队列中。

• A job on a higher queue is chosen to run   在较高队列上的任务被选择运行。
• Use round-robin scheduling among jobs in the same queue.    在同一队列中的任务之间使用轮转调度（RR）
• 规则1：如果 A 的优先级＞ B 的优先级，运行A（不运行B）。
• 规则2：如果 A 的优先级 = B 的优先级，轮转运行 A 和 B

MLFQ varies the priority of a job based on its observed behavior  MLFQ 根据观察到的行为来改变作业的优先级。

• A job repeatedly relinquishes the CPU while waiting IOs → Keep its priority high.
• A job uses the CPU intensively for long periods of time → Reduce its priority.

0x02 如何改变优先级

我们必须决定，在一个工作的生命周期中，MLFQ 如何改变其优先级，放到在哪个队列中。

• 规则3：When a job enters the system, it is placed at the queue with the highest priority  工作进入系统时，放在最高优先级（最上层队列）
• 规则4a：: If a job uses up an entire time slice while running, its priority is reduced (i.e., it moves down on queue).   工作用完整个时间片后，降低其优先级（移入下一个队列）
• 规则4b：If a job gives up the CPU before the time slice is up, it stays at the same priority level.  如果工作在其时间片以内主动释放CPU，则优先级不变。

In this manner, MLFQ approximates SJF

用这种方式，让MFLO近似SJF

实例1:  一个时间片为10ms的三队列调度器

实例2：伴随着一个短暂的工作

• 任务A： 一个长期运行的CPU密集型工作
• 任务B： 一个短期运行的交互型动作（运行时间为20ms）
• A 已经运行了一段时间，然后 B 在时间 T = 100 时到达

实例3：如果有IO呢？我们假设 ——

• 工作A：A long-running CPU-intensive job.   一个交互型工作
• 工作B：An interactive job that need the CPU only for 1ms before performing an I/O.  一个交互式作业，在执行I/O之前只需要CPU 1ms的时间

The MLFQ approach keeps an interactive job at the highest priority.

0x03 当前MLFQ存在的问题（Problems with the Basic MLFQ）

饥饿（Starvation）：

• 如果系统有 "太多" 交互型工作，就会不断占用 CPU
• 导致长工作永远无法得到CPU（饿死了）

愚弄调度程序（Game the scheduler）：

• 每运行 99% 的时间片时间，就调用一个 I/O 操作（比如访问一个无关的文件）。
• 这样一个工作就可以占用更多的 CPU 时间，做的好时甚至可以几乎独占CPU。

一个程序可能在不同时间表现不同：

• 绑定 CPU 进程 → 绑定 I/O 进程
• 需要优先级堆积机制
  

0x04 提升优先级（The Priority Boost ）

我们来试着改变之前的规则看看能否避免饥饿问题？要让 CPU 密集型工作也能取得一些进展（即使不多），我们能做些什么？

一个简单的速录就是周期性地提升（boost）所有工作的优先级，有很多方式都可以做到这一点，这里我们就采用一个最简单的方式 ——

将所有工作扔到最高优先级队列，于是就有了如下新规则：

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

💭 举个例子：

一个长期运行的作业 (A) 与两个短期运行的互动作业 (B, C)

0x05 Better Accounting

如何防止对我们的调度程序进行博弈？

改写 规则4：Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced (i.e., it moves down on queue).   一旦工作用完了其在某一层中的时间配额（无论中间中间主动放弃了多少次CPU），就降低其优先级（移入第一级队列）。

0x06 MLFQ 调优及其他问题（Tuning MLFQ And Other Issues）

高优先级队列  →  较短的时间片：

• 比如 10ms 或者更少

低优先级的队列  →  较长的时间片：

• 100 milliseconds

Lower Priority, Longer Quanta

🔺 0x07 MLFQ: 小结

The refined set of MLFQ rules：

• Rule 1：If Priority(A) > Priority(B), A runs (B doesn’t).
• Rule 2：If Priority(A) = Priority(B), A & B run in RR.
• Rule 3：When a job enters the system, it is placed at the highest priority.
• Rule 4：Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced (i.e., it moves down on queue).
• Rule 5：After some time period S, move all the jobs in the system to the topmost queue.

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

MLFQ 有趣的原因： It does not require prior knowledge on the CPU usage of a process.

MLFQ 不需要事先了解一个进程的CPU使用率！而是通过观察工作的运行来给出对应的优先级。

SolarisMLFQ 的实现：

For the Time-Sharing scheduling class (TS)    

• 60 Qeueus
• Slowly increasing time-slice length.缓慢增加的时间片长度：

• 最高优先级：20毫秒
• 最低优先级：几百毫秒

• 优先级大约每1秒提升一次。

📌 [ 笔者 ]   王亦优
📃 [ 更新 ]   2022.
❌ [ 勘误 ]   /* 暂无 */
📜 [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！