CPU 调度算法

调度指标

轮转调度（Round Robin）

每个进程轮流获得固定时间片 Q。抢占式——进程用完时间片后被强制出队。对所有进程公平分配 CPU。

算法步骤

1. 维护就绪队列，按 FCFS 顺序加入新到达的进程
2. 出队队首进程，运行 min(remaining, Q) 时间
3. 若运行完毕，记录完成时间；否则重新入队到队尾
4. 推进时钟；先将新到达进程入队，再将被抢占进程重新入队

// Round Robin scheduler simulation
// Input: n processes, quantum Q, then n lines: arrival burst
// Output: average waiting time (2 decimal places)
double roundRobin(int n, int Q, vector<pair<int,int>>& procs) {
    // remaining[i] = remaining burst
    vector<int> rem(n), arr(n), wait(n, 0);
    for (int i = 0; i < n; i++) { arr[i] = procs[i].first; rem[i] = procs[i].second; }
    queue<int> ready;
    int t = 0, done = 0, i = 0;
    // Enqueue all processes arrived by t=0
    while (i < n && arr[i] <= t) ready.push(i++);
    while (done < n) {
        if (ready.empty()) { t = arr[i]; while (i < n && arr[i] <= t) ready.push(i++); }
        int p = ready.front(); ready.pop();
        int run = min(rem[p], Q);
        t += run; rem[p] -= run;
        while (i < n && arr[i] <= t) ready.push(i++);
        if (rem[p] == 0) { wait[p] = t - arr[p] - procs[p].second; done++; }
        else ready.push(p);
    }
    double s = 0; for (int w : wait) s += w;
    return s / n;
}

应用场景

• Linux 分时调度（CFS 使用虚拟时间，概念上类似同优先级 RR）
• 单核 JVM 的 Java 线程调度
• 网络交换机端口时分复用

时间片选择：时间片小 → 响应更快但上下文切换开销大；时间片大 → 退化为 FCFS。典型操作系统时间片：1–100 ms。

最短作业优先（SJF）

在所有已到达的进程中，始终选择执行时间最短的。非抢占式 SJF 在固定作业集上可使平均等待时间最小。

算法步骤

1. CPU 空闲时，从已到达进程中选执行时间最短者（相同则按到达时间）
2. 不被抢占，运行至完成
3. 重复；若无进程到达，时钟跳至下一个到达时间

// Non-preemptive SJF
double sjf(int n, vector<pair<int,int>>& procs) {
    // Sort by arrival, then greedily pick shortest burst available
    vector<int> idx(n); iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b){ return procs[a].first < procs[b].first; });
    vector<bool> done(n, false);
    int t = 0, completed = 0; double totalWait = 0;
    while (completed < n) {
        int sel = -1;
        for (int i = 0; i < n; i++) {
            if (!done[idx[i]] && procs[idx[i]].first <= t) {
                if (sel == -1 || procs[idx[i]].second < procs[idx[sel]].second)
                    sel = i;
            }
        }
        if (sel == -1) { t = procs[idx[completed]].first; continue; }
        int p = idx[sel]; done[p] = true;
        totalWait += t - procs[p].first;
        t += procs[p].second;
        completed++;
    }
    return totalWait / n;
}

特性

• 非抢占算法中平均等待时间最优
• 抢占式变体 SRTF 在所有算法中平均等待时间最优
• 饥饿风险：长作业可能无限等待——通过老化（渐进提升优先级）解决
• 实际系统需预测执行时间（用过去 CPU 执行时间的指数平均）

注意：SJF 在平均等待时间上可证明最优，但需要提前知道执行时间——仅在批处理系统或有预测机制的场景可行。

多级反馈队列（MLFQ）

多个优先级递减的就绪队列。新进程从最高优先级队列入队。用完完整时间片的进程被降级；提前放弃 CPU（I/O 密集）的进程保持高优先级。

MLFQ 规则

1. 规则 1：若 priority(A) > priority(B)，运行 A
2. 规则 2：若 priority(A) == priority(B)，A、B 轮转执行
3. 规则 3：新作业进入最高优先级队列
4. 规则 4：若作业用完完整时间片，降低一个优先级
5. 规则 5：每隔周期 S，将所有作业提升至最高优先级（防饥饿）

// Simplified MLFQ: 3 queues with quantums Q0=2, Q1=4, Q2=INF
// All processes arrive at time 0.
// Output: completion order and average turnaround time.
void mlfq(int n, vector<int>& burst) {
    const int Q[3] = {2, 4, INT_MAX};
    vector<int> rem(burst), level(n, 0);
    vector<queue<int>> qs(3);
    for (int i = 0; i < n; i++) qs[0].push(i);
    int t = 0; vector<int> finish(n, 0);
    while (true) {
        bool any = false;
        for (int q = 0; q < 3; q++) {
            if (qs[q].empty()) continue;
            any = true;
            int p = qs[q].front(); qs[q].pop();
            int run = min(rem[p], Q[q]);
            t += run; rem[p] -= run;
            if (rem[p] == 0) finish[p] = t;
            else if (q < 2) qs[q+1].push(p);
            else qs[2].push(p);
            break;
        }
        if (!any) break;
    }
    double avg = 0;
    for (int i = 0; i < n; i++) avg += finish[i];
    cout << fixed << setprecision(2) << avg / n << '\n';
}

应用场景

• xv6 教学操作系统——简化版 MLFQ
• Linux O(1) 调度器（CFS 的前身）
• Windows 对前台窗口线程的优先级提升
• FreeBSD 调度器——4BSD + ULE 变体

核心思想：MLFQ 动态学习作业行为：CPU 密集型作业下沉到低优先级（大执行时间），I/O 密集型作业保持高优先级（短执行时间）。优先级提升机制防止老旧长任务饿死。