时间片轮转调度

2026 大纲 二（二）4 CPU 调度算法的 RR（时间片轮转），它是分时/交互式系统的基础调度算法。指标口径与算例数据沿用 调度的基本概念与目标。

交互可视化

加载可视化中...

不比长短，也不比先后，轮着来

FCFS 按到达先后排，SJF 按作业长短排。它们都在"排序"，而只要排序就会有人排在最后。 FCFS 的最后一名要等前面所有人跑完（护航效应），SJF 的最后一名可能永远排不上（饥饿）。

分时系统受不了这个。终端前坐着人，每个人都得在可接受的时间内看到反应， 哪怕他的作业很长。

于是 RR 换了个思路：根本不比较任何进程属性。就绪进程排成一个循环队列， 每人给一个固定的时间片 $q$，用完就挪到队尾，下一个上。

"不比较"这一条推出它的全部性质。 没有比较键，就没有"谁排在后面"这回事， 所以它不会饥饿；抢占不由任何进程属性触发，而由时钟中断触发—— 这也是它必须以时钟中断为硬件前提的原因。

它买到的东西是响应时间的上界：$n$ 个进程时，任何一个最多等 $n$ 轮就能上 CPU。 付出的是周转时间变差——每个进程都被切成很多段，谁也不能一口气跑完。 这就是 RR 的核心交易：用周转时间，换响应时间的确定性。

于是唯一的调参问题落在 $q$ 上，而它被两条方向相反的约束夹着： $q$ 太小则切换开销占比过高，$q$ 太大则退化回 FCFS。

一、算法规则

时间片轮转（Round Robin, RR）：

1. 所有就绪进程按 FCFS 策略排成一个循环队列
2. 每个进程一次获得一个时间片（Time Quantum, $q$）
3. 时间片用完但进程未结束 → 计时器中断处理程序被激活，把它送到队尾，CPU 交给新的队首进程
4. 进程在时间片用完前提前完成 → 立即激活调度程序，把它从就绪队列删除，调度新的队首进程并启动一个新的时间片

RR 是抢占式算法，抢占由时钟中断触发——时钟中断是它的硬件前提，没有它，"时间片用完"这件事内核根本无从知晓。

二、时间片大小：从定性到定量

时间片	效果	定量边界
太大	退化为 FCFS	$q\ge$ 所有进程中最长的服务时间时，轮转从未真正发生，甘特图与 FCFS 完全一致
太小	切换开销占比过高	见下方 CPU 利用率公式
合适	略大于一次典型交互所需的处理时间	使大多数交互进程能在一个时间片内完成，从而拿到很小的响应时间

判据一：CPU 利用率 = q/(q+δ)

设一次上下文切换的开销为 $\delta$（保存/恢复现场、刷新内存映射等，见 上下文切换机制）。RR 下的时间轴是"跑 $q$ → 切换 $\delta$ → 跑 $q$ → 切换 $\delta$ → …"，一个完整周期长 $q+\delta$，其中只有 $q$ 在做有效计算：

$$\text{CPU 利用率}=\frac{q}{q+\delta }$$

这个公式怎么来的：把时间轴按"一个时间片 + 紧随其后的一次切换"分段，每段长度固定为 $q+\delta$、有效工作时间固定为 $q$，比值即为利用率。

代入 $\delta =1$ ms 看它衰减得多快：

$q$	1 ms	2 ms	4 ms	10 ms	20 ms	50 ms
CPU 利用率	50.00%	66.67%	80.00%	90.91%	95.24%	98.04%

什么时候不适用：该式假定每个时间片后都恰好发生一次切换（提前完成的进程不占满时间片，实际会略高），且只算了切换本身的显式开销——真实系统里切换还会造成 Cache 与 TLB 失效，那部分不在 $\delta$ 里显式出现，所以实测利用率通常低于公式值。

判据二：响应时间上界 ≈ n×(q+δ)

RR 给出了一个别的算法给不了的保证：任何一个就绪进程，最多等一轮就能上 CPU。

就绪队列里有 $n$ 个进程 ⇒ 排在最末尾的那个，前面最多有 $n-1$ 个进程各占一个时间片 ⇒ 它最多等 $(n-1)(q+\delta )$ 就轮到自己 ⇒ 响应时间上界 $\approx n\times (q+\delta )$。

这个式子还解释了"均衡性"为什么会被破坏：$n$ 增大时上界线性增大——用户一多人人都变慢，这是 RR 的固有性质，与进程本身无关。

三、同一时刻入队的两种约定

同一时刻可能同时发生两件事：一个进程时间片耗尽要回队尾，另一个进程刚好到达要入队。谁先进？不同教材约定不一致，而这一步会让整张甘特图完全变样。

指标（本篇数据，$q=2$）	约定 A（新到达优先）	约定 B（时间片用完者优先）
平均周转时间	9.00	10.25
平均带权周转时间	2.38	3.13
平均等待时间	5.00	6.25
平均响应时间	1.50	2.50
P1（最长进程）完成时刻	16	14
P3（最短进程）带权周转	3.00	5.00

差异是可以解释的：约定 B 相当于让"已经在队列里的老进程"插在新到达者前面，于是老进程更快跑完（P1 从 16 提前到 14），代价是新到达的进程要多等一轮（P3 的带权周转从 3.00 涨到 5.00）。约定 A 更贴合 RR 的设计意图，所以本站其余各处一律采用约定 A。

动笔前的固定动作：先在草稿上标出所有"时间片到点"与"进程到达"重合的时刻，确认采用哪种约定，再往下画。只要这几个时刻处理一致，后面的推进就是机械的。

四、RR 拿什么换什么

特性	结论	判据／理由
抢占方式	抢占式，由时钟中断触发	与进程属性无关，时间到就换人
是否饥饿	不会	循环队列必然前进，每个进程最多等一轮
响应时间	有上界保证 $\approx n(q+\delta )$	这是 SJF/SRTF/优先级都给不了的——那些算法里长作业或低优先级进程的等待时间没有上界
周转时间	通常劣于 SJF	例中 RR 9.00 > SJF 8.00 > SRTF 7.00
对长短作业	都比较公平	轮转次序与进程特征无关
开销	频繁切换	由 $q/(q+\delta )$ 定量刻画

一句话：RR 用周转时间换响应时间的确定性。SRTF 平均周转最优，却可能让一个长作业无限期得不到响应；分时系统宁可整体慢一点，也不能容忍某个用户永远没反应——这正是调度目标里分时系统首选响应时间的原因。

两种入队约定各推一遍：从冲突时刻到两张甘特图（想看约定差异怎么一步步放大成不同结果时展开）

沿用共用算例，$q=2$：

进程	到达时间	服务时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

冲突时刻有两个：t = 2（P1 时间片耗尽 + P2 到达）与 t = 4（P2 时间片耗尽 + P3 到达）。

约定 A：新到达的进程先入队

• t=0～2：队列 [P1]，P1 运行，剩余 7→5。t=2 时间片到。
• t=2（第一个冲突点）：P2 此刻到达。先把 P2 挂到队尾，再把 P1 挂到 P2 后面 → 队列 [P2, P1]。取队首 P2 运行，剩余 4→2。这一步决定全局：P1 被排到 P2 后面，此后每一轮的次序都跟着改变。
• t=4（第二个冲突点）：P3 到达，同时 P2 时间片到（剩余 2）→ 队列 [P1, P3, P2]。取 P1 运行 4–6（剩余 5→3）。其间 t=5 时 P4 到达挂到队尾 → [P3, P2, P4]。
• t=6 起不再有冲突：依次 P3（服务 1，完成于 t=7）、P2（剩 2，完成于 t=9）、P4（剩 4→2）、P1（剩 3→1）、P4（剩 2，完成于 t=15）、P1（剩 1，完成于 t=16）。

时间区间	0–2	2–4	4–6	6–7	7–9	9–11	11–13	13–15	15–16
执行进程	P1	P2	P1	P3	P2	P4	P1	P4	P1

进程	完成时间	周转时间	带权周转时间	等待时间	响应时间
P1	16	16	16/7 ≈ 2.29	9	0
P2	9	7	7/4 = 1.75	3	0
P3	7	3	3/1 = 3.00	2	2
P4	15	10	10/4 = 2.50	6	4
平均		9.00	2.38	5.00	1.50

约定 B：时间片用完的进程先入队（只改冲突时刻的处理，其余规则完全相同）

• t=2：P1 先回队尾，P2 再排到它后面 → 队列 [P1, P2]。取队首——还是 P1，所以 P1 连着跑了 0–4 两个时间片。
• t=4：P1 时间片到（剩 3）、P3 到达 → 队列 [P2, P1, P3]。取 P2 运行 4–6（剩 4→2）。其间 t=5 时 P4 到达挂队尾 → [P1, P3, P4]。
• t=6：P2 时间片到回队尾 → [P1, P3, P4, P2]。取 P1 运行 6–8（剩 3→1），回队尾 → [P3, P4, P2, P1]。
• t=8 起：P3（服务 1，完成于 9）、P4（剩 4→2）、P2（剩 2，完成于 13）、P1（剩 1，完成于 14）、P4（剩 2，完成于 16）。

时间区间	0–4	4–6	6–8	8–9	9–11	11–13	13–14	14–16
执行进程	P1	P2	P1	P3	P4	P2	P1	P4

进程	完成时间	周转时间	带权周转时间	等待时间	响应时间
P1	14	14	14/7 = 2.00	7	0
P2	13	11	11/4 = 2.75	7	2
P3	9	5	5/1 = 5.00	4	4
P4	16	11	11/4 = 2.75	7	4
平均		10.25	3.13	6.25	2.50

另附退化验证：本篇数据里最长服务时间是 P1 的 7，取 $q=7$ 时甘特图恰好变成 0–7 P1、7–11 P2、11–12 P3、12–16 P4，四项指标与 FCFS 完全一致（平均周转 8.75、平均带权 3.50）——轮转规则一次也没生效。

考点速记

1. RR 把就绪进程排成循环队列，每人一个时间片 $q$，用完移到队尾、提前完成则下一个进程重启一个新时间片。
2. 它是抢占式的，但抢占由时钟中断触发，不比较任何进程属性——这正是它不会饥饿的原因。
3. 两条定量判据方向相反：CPU 利用率 $=q/(q+\delta )$ 要求 $q$ 大（$\delta$ 是一次切换的开销，$q\approx 20\delta$ 才能把损耗压到 5%）；响应时间上界 $\approx n(q+\delta )$ 要求 $q$ 小。落点是"略大于一次典型交互所需的处理时间"。
4. ⚠️**$q\ge$ 最长服务时间时，RR 退化为 FCFS**（每个进程一次就跑完了）。
5. ⚠️同一时刻"时间片用完"与"新进程到达"并存时，必须先定入队约定（谁先进队尾），全程只能用一种。两种约定会算出不同的平均周转时间。
6. RR 的核心 trade-off：用周转时间换响应时间的确定性。

这一节在真题里被考过的形式：

手算题一道，另有一道问它靠什么实现。

• 给时间片大小与各进程的到达和执行时间，算周转时间（2024-30）。⚠️ 两处必须先在题干里确认：时间片多大、同一时刻"用完"与"新到达"谁先入队（速记第五条）。第二处题目未必明说，但只要全程用同一种约定，答案通常能对上选项；两种约定混用则一定错。
• 问分时系统实现时间片轮转要用到哪些内核结构（2021-25，在调度的基本概念讲）。答时钟中断处理程序 + 进程控制块 + 进程就绪队列，阻塞队列无关——这正是速记第二条"抢占由时钟中断触发"的直接考法。
• RR 还是"哪些算法不会饥饿"这类判断题的标准答案（2014-23）。

复习优先级：必须会手算。 做题前圈出时间片大小与入队约定这两件事， 其余就是按时刻推进。速记第三、四条（$q$ 的两条约束、$q$ 过大退化为 FCFS）是概念题的落点。

易错：手算时把"时间片用完"和"新进程到达"的入队顺序中途换了一种。全程只能用一种约定。

易错：认为 RR 也会饥饿。它不比较任何进程属性，按轮次来，人人有份。

易错：认为时间片越小越好。$q$ 太小则切换开销占比过高，CPU 利用率 $=q/(q+\delta )$。

易错：认为时间片越大越接近最优。$q\ge$ 最长服务时间时退化为 FCFS。

易错：认为进程提前完成后，下一个进程接着用剩下的时间片。重新起一个完整的时间片。

教材出处

• 汤小丹《计算机操作系统》3.3.2 轮转调度算法（轮转基本原理、两种进程切换时机、时间片大小对系统性能的影响、"时间片太长则退化为 FCFS"、"较可取的时间片略大于一次典型交互所需时间"），印刷 p93

相关知识

调度的基本概念与目标｜SJF 短作业优先调度｜优先级调度｜上下文切换机制

真题练习

相关真题（12题）

2025Q252分2024Q302分2021Q252分2020Q262分2019Q272分2017Q232分2016Q466分2014Q232分2013Q312分2011Q232分2010Q262分2009Q242分

上一篇SJF 短作业优先调度下一篇优先级调度

相关文章

• 进程基本概念
• 进程状态与转换
• 线程（内核级与用户级）
• 进程的组织与控制
• 进程间通信
• 调度的基本概念与目标
• FCFS 先来先服务调度
• SJF 短作业优先调度
• 优先级调度
• 高响应比优先调度
• 多级队列调度
• 多级反馈队列调度
• 公平调度算法
• 调度算法对比模拟器
• 多处理机调度
• 上下文切换机制
• 上下文切换模拟器
• 同步与互斥基本概念
• 同步互斥实现方法
• 锁
• 信号量
• 条件变量
• 生产者-消费者问题
• 读者-写者问题
• 哲学家进餐问题
• 死锁的概念与预防
• 银行家算法
• 死锁检测与解除