💭 写在前面
本系列博客为复习操作系统导论的笔记，内容主要参考自：
- 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 引入：需要一个新的高效算法
0x01 多级反馈队列算法（MLFQ Algorithm）
0x02 如何改变优先级
0x03 当前MLFQ存在的问题（Problems with the Basic MLFQ）
0x04 提升优先级（The Priority Boost ）
0x05 Better Accounting
0x06 MLFQ 调优及其他问题（Tuning MLFQ And Other Issues）
🔺 0x07 MLFQ: 小结
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使用率！而是通过观察工作的运行来给出对应的优先级。
Solaris MLFQ 的实现：
For the Time-Sharing scheduling class (TS)
- 60 Qeueus
-
Slowly increasing time-slice length. 缓慢增加的时间片长度：
- 最高优先级：20毫秒
- 最低优先级：几百毫秒
- 优先级大约每1秒提升一次。
📌 [ 笔者 ] 王亦优
📃 [ 更新 ] 2022.
❌ [ 勘误 ] /* 暂无 */
📜 [ 声明 ] 由于作者水平有限，本文有错误和不准确之处在所难免，
本人也很想知道这些错误，恳望读者批评指正！| 📜 参考资料 Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces A. 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]. []. .文章来源：https://www.toymoban.com/news/detail-460874.html 百度百科[EB/OL]. []. https://baike.baidu.com/.文章来源地址https://www.toymoban.com/news/detail-460874.html |
到了这里，关于【OSTEP】调度: 多级反馈队列 (MLFQ) | 优先级提升 | 饥饿问题 | 愚弄调度问题 | MLFQ 调优的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
