多级反馈队列与累计配额

一次可见的反馈过程 ​

仍用SCHED-16的到达和服务量，先忽略切换开销。每隔12毫秒有一次全体优先级提升，称为boost。为得到唯一答案，本实验在boost边界先结算服务、移除完成者，再处理到达；随后把所有未完成任务提升Q0并清零该层用量及片用量。可运行者按任务名排列，阻塞者保持阻塞且只更新优先级。最后重新派发。

这项按名字重排是实验规则，不声称是某个操作系统的实现。后面会看到，boost的队列次序与周期同样影响公平。

12之前A已经在两层累计取得6，B取得3；boost没有抹掉这些总服务，只重置政策用于分类的层配额。12之后A剩3、B剩1，不会重新变成原需求9和4。

最终A、B、C、D完成于16、15、6、7，周转为16、14、4、3，均值9.25；首次响应为0、1、2、2，均值1.25。与普通RR的8.75和1.75比较，平均首次派发稍早，平均周转稍长。反馈政策不是对每份负载都同时改进全部指标。

为什么不能在I/O之后忘记已用服务 ​

单独做一个作弊实验：Q0时间片为2、层配额为4。任务G每运行1.5毫秒便主动做一次短I/O，从不连续跑满2。如果规则是“只有跑满整片才降级，I/O回来把用量清零”，G就能无限重复这种行为而留在最高层。

累计配额的账本不同。G第一段用1.5，层累计为1.5；第二段再用1.5，累计为3；第三段只允许再用1，累计到4时立即降级。中间等待I/O不增加CPU服务，也不抹去已经消耗的3。

这条改动防的是通过切碎服务来逃避已经声明的层配额，不能推出“所有I/O任务都公平”或“任何进程都无法操纵调度器”。如果用户可以不停创建新身份，新任务总从Q0开始，又会出现另一种资源身份问题，需要组级配额等独立机制。

提升能解决什么，还欠什么条件 ​

没有boost时，Q0可以不断出现新的短任务，使Q2里的长任务永远没有机会。周期性把长任务带回高层，能让政策重新观察其行为，也能处理“以前CPU密集、后来变成交互式”的任务。

但是“有boost”本身不是无饥饿证明。按本实验的名字排序，若两个任务A、B一直可运行，Q0时间片为2，而boost周期改成1，那么每次刚给A运行1毫秒就重排，A仍在前；B可以永远轮不到。两个参数看似更积极，组合起来却破坏公平。

若一次boost后至多有 $N$ 个可运行任务，后到任务只入队尾，且下一次重排前允许每个前方任务最多跑完一个Q0片，则目标第一次取得服务的等待至多 $(N-1)q_0$，忽略开销。要用这条界排除饥饿，必须确保boost不会在轮到它之前反复把它移回队尾；例如周期足够长，或采用保持等待次序的提升协议。这里只证明写出的条件，不把未指定的队列操作交给一句“定期提升”。

实现里哪些账本不能丢 ​

每个任务至少保留所在层、当前层已用服务、当前片已用服务、READY/BLOCKED状态。运行 $\mathrm{\Delta }$ 后，实际服务和两份政策计数按各自定义增加；因阻塞停下时，只有当前片可在下次重置，层用量仍在。每次改变层或状态，也要从旧队列移除，防止同一任务同时存在两处。

为避免同刻边界歧义，本实验若完成、配额耗尽与boost重合，先完成退出；未完成者再执行boost，不需要先降到低层又立即升回高层。外部观察应得到同一总服务，但队列次序仍需明确记录。

小量固定队列可以逐层检查，层内入队出队为常数工作；层数可变时另计查找非空层的成本。周期扫描所有 $n$ 个任务作boost为 $O(n)$，可用其他表示推迟部分工作，但不能因为单次选队首为 $O(1)$ 就把全局提升成本省略。

从一个版本迁移到另一个版本 ​

阅读某个真实调度器时，先查四个具体问题：每层时间片多长；降级看连续片还是累计服务；阻塞和抢占后哪些计数保留；提升如何处理正在运行与睡眠任务。只有这些回答一致，才能把本页的表直接搬过去。

MLFQ是利用历史服务作分类的一种启发式，不保证准确预测剩余工作，也不是按指定权重分配CPU的合同。若主要诉求是“持续繁忙时A拿两份、B拿一份”，应转向彩票理路彩票调度与随机服务份额Lottery scheduling · Proportional-share lottery scheduling · Lottery tickets用均匀抽签把正权重转成时间片选择概率，精算有限样本服务份额和连续未中签概率，区分概率无饥饿与确定等待界。或步幅调度理路步幅调度与虚拟服务账本Stride scheduling · Proportional-share stride scheduler · Virtual pass按票数倒数设置步幅，每次运行最小pass者并按实际服务推进，复算十二片序列，证明固定成员下的有界虚拟差并说明加入和短片边界。的份额模型。