OS:TEP MLFQ 策略
前言
其实, 我学 Linux 内核的时候, 并不只是阅读 LKD 和翻阅源码. 我同时还在阅读 OS:TEP(Operating System: Three Easy Pieces), 对, 就那本讲操作系统的书. 每一个部分看完之后, 我就立马阅读 LKD 的对应部分和源码.
最近, 我刚好学到 Linux 的 CFS 调度策略, 就想着回过头来复习一下之前学过的 MLFQ.
1.SJF 调度算法
SJF 没啥好说的, 书上讲的很清楚了, SJF 就是最短任务优先原则, 其设计初衷是想解决 FIFO 的糟糕的周转时间的问题.
但是, 正如书上所说, 这玩意主打一个秩序井然, 只能处理所有任务同时到队列的情况, 要是某堆进程不按这套路出牌, 那 SJF 立马完蛋, 书上就有一个完蛋的例子:
2.PSJF/STCF 调度算法
这个时候, 我突然想起了(其实是 OSTEP 告诉我的), 诶, 咱 CPU 还有个功能叫做"抢占"(更准确的说, 时钟中断)呢, 那可以把它们用起来啊. 于是, 就有了 STCF.
这也没什么好说的, 书上也有:
对, 这样确实能让周转时间大大提高, 但是对于响应时间来说, 这个方案还是有点令人头疼的, 毕竟它只在新任务来的时候抢占任务, 假设用户在终端中运行一个任务, 还是得等待前面一个任务完成了, 才能知道这个任务在运行了:
那对这种情况, 又该怎么办呢?
3.RR 调度算法
那我们先把周转时间抛开不谈, 为了能给用户一个好的体验, 那必须优化响应时间.
不过, 既然 CPU 每隔一个固定的时间就被打断一次, 那我们就把这个固定的时间取个名字, 叫做时间片吧.
那我们只需要轮流调度任务堆中的任务就可以了, 例如有 A B C 三个任务, 都是100ms, CPU 每隔 50ms 就被打断一次, 那时间片为 50ms.
- 第一个 50ms 我们运行任务A 50ms
- 第二个 50ms 我们运行任务B 50ms
- 第三个 50ms 我们运行任务C 50ms
- 第四个 50ms 我们重新运行任务A 50ms, 任务A 运行完了
- 第五个 50ms 我们重新运行任务B 50ms, 任务B 运行完了
- 第六个 50ms 我们重新运行任务C 50ms, 任务C 运行完了
- 至此, 全部任务运行完毕
这就是轮转调度, 也叫做 RR.
但是, 这会导致新的问题-- RR改变了响应时间, 但是因为三个任务的周转时间都包含了其他任务的运行时间, 所以周转时间可能比 SJF 还要糟糕啊!
有没有什么好办法呢?
4.MLFQ 调度算法
MLFQ 的全称是多级反馈调度机制, 其实本质上就是STCF 调度算法和RR 调度算法的究极缝合怪.
首先, 就是关键问题:
MLFQ 给出的解决方案大概是这样的:
- 定义几个队列, 优先级从高到低.
- 每个队列单独设置一个固定的时间额度, 任务在该队列执行完对应的 CPU 时间额度后, 要是还没嘎, 就会自动被丢到低一个优先级级的队列.
- CPU 对最高优先级的队列中的所有任务进行轮转调度.
- 每隔一段时间后, 所有队列的任务都需要被丢到最高优先级的队列.
用书上的原话来说:
还有一点, 针对 I/O 密集型的任务, MLFQ又做了如下优化:
一句话, 分解任务, 重叠使用.
那么, RR是好理解的, 毕竟同一优先级下, CPU采用的是轮转调度任务制. 但是, 什么地方体现了 STCF 呢?
5.MLFQ 到底哪一点像 STCF?
让我们仔细研究一下上面我写的解决方案的第 2 条, 它们怎么设置某个优先级的时间额度?
对, 时间额度长度是随优先级的递减而递增的.
那也就是说, 我们可以总结 MLFQ 设计的思路:
- 先假定一个任务是I/O 密集型任务(短时间), 丢到最高优先级的队列里面, 让它先执行.
- 如果时间片没有用完, 证明假设不成立, 就丢到下一个队列中继续工作, 代表该任务也许是CPU密集型任务.
- 以此类推做筛选, 最终在最低优先级的队列的任务就 都是CPU密集型任务 了.
也就是这张图了:
这种"抢占式最短作业执行"思路, 是不是在哪见过... 这是不是特别类似 PSJF/STCF 算法?
这个设计看似合理, 但是它对一种情况却欠考虑, 对, 就是上面的I/O密集型任务的情况. 说不定, 这个任务被分解为好几个子任务, 其中一个子任务占用 CPU 时间特别长,后半段有超多的 CPU 和 I/O 混合的任务呢, 如我下面所画的情况?
对于这类情况, 要是仅凭借子任务 1 就忽略了后面的那一堆短时间的 I/O 密集型的子任务, 是不是过于短视了?
所以, 为了避免这种情况, 就跟上面我说的解决方案的第 4 点一样, 每隔一段时间后, 就假设所有大任务中当前正在执行的小任务 (例如图中的子任务1) 已经执行完了, 然后把这些大任务重新丢回最高优先级的队列.
要是大任务改变了行为, 那假设成立, 证明当前的子任务已经执行完成, 已经在进行下一个子任务了.
例如上面的大任务改变了行为 (本来是在最低优先级队列运行 CPU 密集型的子任务 1, 但是某次, 大任务却突然留在高优先级队列了, 那就证明大任务已经执行完子任务 1 并且启动后面的 I/O 密集型任务了), 这样保证大任务的 I/O 密集型子任务也能够做到快速响应, 做到真正的 STCF.
这就是 MLFQ 像 STCF 的点.
The End
本期文章写到这, 感谢大家的观看哦~萌新初涉 Linux 内核, 有错误也请多多指正~