Skip to content

文日小栈

时间片轮转算法是什么

时间片轮转算法是什么

时间片轮转算法（Time-Sharing Round Robin，简称 RR）是一种 操作系统进程调度算法，通过将 CPU 时间分成固定长度的时间片（Time Slice），轮流分配给就绪队列中的进程，实现多任务的公平调度。它广泛用于分时系统，确保每个进程都有机会执行。

关键事实

核心思想：
按时间片轮流执行进程，未完成则回到队列尾部。
时间片：
固定时长（如 10ms），由系统定义。
调度方式：
基于就绪队列（FIFO），循环分配 CPU。
目标：
公平性：避免进程饿死。
响应性：适合交互式系统。

实现原理

流程

就绪队列：
所有可执行进程按到达顺序排队。
分配时间片：
当前进程获取 CPU，执行一个时间片。
时间片到期：
如果进程未完成，被抢占，放回队列尾部。
CPU 切换到队列头部下一个进程。
进程完成：
若在时间片内完成，直接退出。

示例

进程：P1（需 20ms）、P2（需 10ms）、P3（需 30ms）。
时间片：10ms。
执行顺序：
0-10ms：P1（剩 10ms）。
10-20ms：P2（完成）。
20-30ms：P3（剩 20ms）。
30-40ms：P1（完成）。
40-50ms：P3（剩 10ms）。
50-60ms：P3（完成）。
总时间：60ms。

伪代码

Queue<Process> readyQueue = new LinkedList<>();
int timeSlice = 10; // 时间片 10ms

while (!readyQueue.isEmpty()) {
    Process p = readyQueue.poll(); // 取出队首进程
    if (p.remainingTime <= timeSlice) {
        run(p, p.remainingTime); // 执行完成
    } else {
        run(p, timeSlice); // 执行一个时间片
        p.remainingTime -= timeSlice;
        readyQueue.offer(p); // 未完成，放回队尾
    }
}

特点

优点：
公平性：每个进程轮流执行，无饿死。
响应快：时间片小，交互性好。
缺点：
上下文切换开销：时间片太小，切换频繁。
吞吐量低：长任务被频繁打断。
时间片选择：
太短：切换过多，效率低。
太长：退化为 FCFS（先来先服务），响应慢。

延伸与面试角度

与其它算法对比：
FCFS：无抢占，先到先得，可能饿死。
SJF（短作业优先）：吞吐量高，但不公平。
RR：公平但效率稍低。
实际应用：
分时系统（如 Unix）。
线程调度（如 Java 线程）。
优化：
动态时间片：根据进程优先级调整。
多级反馈队列：结合优先级。
性能指标：
周转时间：所有进程完成的总时间。
等待时间：队列等待时间。
面试点：
问“时间片作用”时，提公平性和响应。
问“缺点解决”时，提动态调整。

总结

时间片轮转算法通过固定时间片循环调度进程，保证公平性和响应性，适用于分时系统。优点是公平，缺点是切换开销大。面试时，可画调度图或写伪代码，展示理解深度。