对 OS:TEP 的 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 的点.