调度：多级反馈队列

MLFQ旨在解决的双重目标

调度器希望缩短交互式用户的响应时间，同时又希望让短作业尽快完成以优化周转时间。然而系统通常并不知道作业会运行多久。MLFQ通过让作业从高优先级开始，并根据其是否持续占用CPU来降低优先级，从历史行为中推断未来需求。

队列、规则与优先级调整

系统维护多个优先级队列，新到达的作业放入最高队列。同一队列中的作业按时间片轮转。作业若用尽当前层的时间配额则降级；若提前放弃处理器（例如发起I/O）则保留原优先级。这样交互型作业倾向于留在高层，而CPU密集型作业逐渐下沉。

近似最短作业优先及其局限

未知作业被乐观地当作短作业给予高优先级，若它确实很快结束则获得类似SJF的待遇；若它很长则慢慢降到低层。该方法在作业行为具有阶段性时可工作良好，但当交互作业过多时会长作业饥饿，且恶意程序可通过反复短暂运行来“欺骗”调度器。

常见误区

• 大量短交互作业会使长作业完全得不到CPU而产生饥饿
• 用户可通过在时间片结束前主动yield来保持高优先级从而不公平地占用资源
• 若缺少定期的优先级提升机制，被降到最低层的作业可能长期无法运行

最低标准 C11 · 完整程序 · 下载 .c

#include <stdio.h>
#define SLICE 4
#define MAXT 25
int main(void) {
    char names[2] = {'A', 'B'};
    int rem[2] = {20, 5};
    int prio[2] = {2, 2};
    int used[2] = {0, 0};
    int arr[2] = {0, 12};
    printf("MLFQ sim: 3 levels, slice=%d\n", SLICE);
    printf("Gantt (A=long CPU, B=short arr@12):\n");
    for(int t=0; t<MAXT; t++) {
        int best=-1, bp=-1;
        for(int i=0; i<2; i++) {
            if(arr[i]<=t && rem[i]>0 && prio[i]>bp) {
                bp=prio[i];
                best=i;
            }
        }
        if(best<0) {
            putchar('.');
            continue;
        }
        putchar(names[best]);
        rem[best]--;
        used[best]++;
        if(used[best]>=SLICE) {
            if(prio[best]>0) prio[best]--;
            used[best]=0;
        }
    }
    printf("\n");
    printf("Final remaining A=%d B=%d\n", rem[0], rem[1]);
    return 0;
}

在本地编译

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-08-mlfq.c -o example && ./example

预期结果

MLFQ sim: 3 levels, slice=4
Gantt (A=long CPU, B=short arr@12):
AAAAAAAAAAAABBBBBAAAAAAAA
Final remaining A=0 B=0

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

一个CPU密集型作业已经降到最低优先级队列。此时一个只需很少CPU时间的交互作业到达。请说明MLFQ会如何调度它们，以及为什么这种行为对交互用户有利。

继续查证

• OSTEP chapter PDF

标准草案与官方章节会更新；版本标记只说明示例最低要求。