时间片轮转（RR）调度算法：让每个进程都有机会运行

操作系统调度系列第二篇：从"先来后到"到"人人有份"

引言

上一篇文章我们聊了 FCFS（先来先服务）。它简单公平，但有个致命硬伤：响应时间无法保证。

想象你在分时系统里敲 ls，结果系统要等前面一个跑 10 分钟的科学计算程序跑完才给你返回——你肯定想砸键盘。交互式系统需要的不是朴素公平，而是每个任务都能定期获得 CPU 的关注。

时间片轮转（Round Robin，RR） 就是为解决这个问题而生的。

1. 核心机制

RR 引入了一个关键概念：时间片（Time Quantum）——CPU 分配给每个进程的一次性连续运行时间。

算法流程：

1. 就绪进程按到达时间排成 FIFO 队列
2. 取队首进程，分配一个时间片
3. 进程运行：
   • 完成或阻塞 → 立即切换下一个
   • 时间片用完未完成 → 强制保存上下文，挂到队尾
4. 循环直到所有进程完成

RR 是抢占式调度。时间片一到，无论进程愿不愿意，都必须交出 CPU。这种强制性时钟中断，确保了没有任何进程能独霸 CPU。

2. 一个具体例子

进程集合（时间片 = 5）：

进程	到达时间	服务时间
A	0	20
B	5	15
C	10	5
D	15	10

调度推演：

• 0~5：A 运行 → 还剩 15 → 队尾
• 5~10：B 运行 → 还剩 10 → 队尾
• 10~15：C 运行 → 正好完成（只需 5）
• 15~20：D 运行 → 还剩 5 → 队尾
• 20~25：A 第二轮 → 还剩 10 → 队尾
• 25~30：B 第二轮 → 还剩 5 → 队尾
• 30~35：D 第二轮 → 完成
• 35~40：A 第三轮 → 还剩 5 → 队尾
• 40~45：B 第三轮 → 完成
• 45~50：A 第四轮 → 完成

统计结果：

进程	完成时间	周转时间	带权周转时间
A	50	50	2.5
B	45	40	2.67
C	15	5	1
D	35	20	2

对比 FCFS：在 FCFS 中，C 的周转时间是 30、带权周转时间 6；而在 RR 中 C 的周转时间缩短到 5，立即被执行。短作业的响应速度有了质的飞跃。

3. 时间片：RR 的灵魂参数

时间片大小是 RR 性能的关键，存在经典权衡：

时间片过大 → 退化为 FCFS

如果时间片是 100 秒，几乎所有进程都能在一个时间片内完成，RR 行为与 FCFS 无异，交互响应极差。

时间片过小 → 上下文切换开销爆炸

每次切换都要保存寄存器、程序计数器，加载下一个进程的状态。上下文切换本身也是 CPU 开销：

• 时间片 1ms（1000μs）：切换开销约 0.1%~1%，可接受
• 时间片 100μs：切换开销可能占 10%，得不偿失

工程实践：现代操作系统（Linux、Windows）通常将时间片设在 10ms ~ 100ms。这个范围既能保证交互响应（人能接受的延迟），又能控制切换开销。

Linux CFS（完全公平调度器）虽然用动态时间片，但 RR 思想仍是其根基。

4. 代码实现（Java 模拟）

import java.util.*;

class RoundRobinScheduler {

    static class Process {
        String pid;
        int arrival;
        int burst;          // 剩余运行时间
        int originalBurst;  // 原始运行时间（用于后续统计）
        int finishTime;

        Process(String pid, int arrival, int burst) {
            this.pid = pid;
            this.arrival = arrival;
            this.burst = burst;
            this.originalBurst = burst;
            this.finishTime = 0;
        }
    }

    public static void roundRobin(List<Process> processes, int quantum) {
        // 按到达时间排序
        processes.sort(Comparator.comparingInt(p -> p.arrival));

        Queue<Process> readyQueue = new ArrayDeque<>();
        int time = 0;
        int idx = 0;
        int n = processes.size();
        int completed = 0;
        List<Process> result = new ArrayList<>();

        while (completed < n) {
            // 将所有已到达的进程加入就绪队列
            while (idx < n && processes.get(idx).arrival <= time) {
                readyQueue.offer(processes.get(idx));
                idx++;
            }

            // 如果队列为空，CPU 空闲，直接跳到下一个进程的到达时间
            if (readyQueue.isEmpty()) {
                time = processes.get(idx).arrival;
                continue;
            }

            Process current = readyQueue.poll();

            if (current.burst > quantum) {
                current.burst -= quantum;
                time += quantum;

                // 在时间片结束后，可能有新进程到达，先入队
                while (idx < n && processes.get(idx).arrival <= time) {
                    readyQueue.offer(processes.get(idx));
                    idx++;
                }
                // 当前进程未完成，放回队尾
                readyQueue.offer(current);
            } else {
                // 进程完成
                time += current.burst;
                current.burst = 0;
                current.finishTime = time;
                completed++;
                result.add(current);

                // 进程执行期间也可能有进程到达
                while (idx < n && processes.get(idx).arrival <= time) {
                    readyQueue.offer(processes.get(idx));
                    idx++;
                }
            }
        }

        // 输出结果
        for (Process p : result) {
            int turnaround = p.finishTime - p.arrival;
            System.out.printf("进程 %s: 完成时间=%d, 周转时间=%d%n",
                              p.pid, p.finishTime, turnaround);
        }
    }

    public static void main(String[] args) {
        List<Process> procs = Arrays.asList(
            new Process("A", 0, 20),
            new Process("B", 5, 15),
            new Process("C", 10, 5),
            new Process("D", 15, 10)
        );
        roundRobin(procs, 5);
    }
}

运行结果

执行 main 方法后，输出：

进程 C: 完成时间=15, 周转时间=5
进程 D: 完成时间=35, 周转时间=20
进程 B: 完成时间=45, 周转时间=40
进程 A: 完成时间=50, 周转时间=50

（注意输出顺序是完成顺序）

5. 优缺点

优点

• 响应时间短：交互用户能定期获得 CPU
• 公平性极高：每个进程轮流获得 CPU，不会饿死
• 可预测性强：n 个进程、时间片 q 的情况下，每个进程等待时间 ≤ (n-1) × q
• 兼顾批处理和交互任务

缺点

• 上下文切换开销大：频繁中断和切换消耗 CPU
• 不区分优先级：紧急任务和普通任务一视同仁，无法提供 QoS 保障
• 吞吐量通常低于 SJF：短作业无法像在短作业优先中那样快速完成
• 时间片调优困难：需要工程经验，难适应所有场景

6. 适用场景

• 分时操作系统（早期 UNIX、多用户终端）——RR 最经典场景
• 通用桌面操作系统（Windows / Linux 调度器底层组件）
• 响应时间敏感、吞吐量不敏感的系统

总结

从 FCFS 到 RR，是一次从"朴素公平"到"响应式公平"的进化：

• FCFS 解决"让进程开始运行"的问题，但响应时间不可控
• RR 引入时间片和抢占机制，让交互式系统成为可能，代价是切换开销

RR 的本质是把 CPU 时间切成等长"配额"，在进程间轮转。它不关心谁更重要、谁更快，只关心一件事——所有人都不应该等太久。

---