跳转至

408 高频考点精讲:时间片轮转

模块归属:操作系统 · 进程管理
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:3 次(2017 年第 27 题、2021 年第 25 题、2024 年第 30 题)
  • 历年总考查频次:3 次
  • 出题形式:单项选择题(分值通常为 2 分)
  • 命题特点: 时间片轮转(Round-Robin, RR)调度是操作系统分时机制的基石。纵观 408 历年命题,对该考点的考查主要集中于以下三个核心维度:
  • 底层机制及状态变迁:结合硬件时钟节拍、时钟中断服务程序(ISR)、进程控制块(PCB)上下文保护与恢复,重点考查时间片用完时的进程状态转移(执行态转为就绪态,而非阻塞态)以及时钟中断对剩余时间的更新。
  • 内核关键数据结构支撑:深度辨析操作系统内核支撑 RR 调度所需的数据结构组合(PCB、就绪队列、时钟中断处理程序),考查就绪队列(直接参与调度)及阻塞队列(不参与调度轮转)的功能边界。
  • 量化计算与算法执行轨迹分析:考查多进程并发场景下时间片轮转的离散执行过程,要求在给定时间片大小、进程队列排队次序、CPU 突发服务时间等条件下,准确推导特定进程的完成时刻、周转时间、等待时间与带权周转时间。
  • 时间片选取的权衡逻辑:考查时间片大小 \(q\) 与响应时间、上下文切换开销、系统吞吐量之间的非线性制约关系。

  • 近十年考查年份分布表格:

+------+-------------------+------------------------------------------+ | 年份 | 题号 | 考查切入点 | +------+-------------------+------------------------------------------+ | 2016 | - | 未考查 | | 2017 | 单项选择题 第27题 | 时间片轮转状态转移、时钟中断、影响因素 | | 2018 | - | 未考查 | | 2019 | - | 未考查 | | 2020 | - | 未考查 | | 2021 | 单项选择题 第25题 | 实现时间片轮转所需的内核数据结构及程序 | | 2022 | - | 未考查 | | 2023 | - | 未考查 | | 2024 | 单项选择题 第30题 | 纯就绪队列下多进程时间片轮转周转时间计算 | | 2025 | - | 未考查 | +------+-------------------+------------------------------------------+


二、 具体考察内容

1. 核心概念与机制原理

(1) 基本定义与设计目标

时间片轮转调度算法(Round-Robin Scheduling, RR)是分时操作系统(Time-Sharing System)的核心处理机调度算法。其设计目标是实现处理机资源的公平分配,确保系统中所有就绪进程能够在确定的响应周期内获得 CPU 服务,满足终端用户人机交互的即时响应需求。

(2) 调度工作流程

  1. 队列初始化:系统将所有就绪进程按照到达就绪状态的先后次序,排成一个先进先出(FIFO)就绪队列。
  2. 选程执行:调度程序(Scheduler / Dispatcher)选取就绪队列队首进程,分配处理机投入运行,同时重置硬件定时器为一个固定时长的时间片(Time Slice 或 Time Quantum,记为 \(q\))。
  3. 时钟中断与时间片递减:硬件时钟发生器以固定的时钟节拍(Clock Tick)产生周期性时钟中断。时钟中断服务程序每次递减当前运行进程的时间片剩余时间计数器。
  4. 运行态退出与调度重触发:
  5. 时间片耗尽:若时间片计数器减至 0 时当前进程尚未完成,时钟中断处理程序置调度标志。操作系统保存当前进程的 CPU 硬件上下文至其 PCB 中,将该进程状态由执行态转为就绪态,并将其插入就绪队列队尾。调度器随后重新从就绪队列头部选取新进程分配 CPU。
  6. 进程提前终止:若当前进程在时间片用完前结束计算任务,进程主动调用 exit() 系统调用退出,操作系统回收其资源并撤销 PCB,立即调度就绪队列队首进程。
  7. 进程发起 I/O 或等待同步事件:若进程在时间片内发出 I/O 请求(如磁盘读写、网络收发)或执行同步等待(如申请互斥锁失败、执行 P 操作),该进程主动放弃剩余时间片,状态由执行态转为阻塞态(等待态),移入相应的阻塞队列。

(3) 内核关键数据结构与支撑程序

分时系统实现时间片轮转调度,必须由以下底层内核实体协同支撑: - 进程控制块(PCB):用于维护进程的执行状态(执行态、就绪态)、时间片剩余配额、寄存器上下文镜像(PC、通用寄存器、PSW 等)。在发生时间片轮转抢占时,旧进程现场被压入其 PCB,新进程现场从其 PCB 恢复到物理寄存器中。 - 时钟中断处理程序(Clock ISR):由硬件定时器中断周期性激活,负责维护系统时钟节拍、递减当前执行进程的时间片计数器,并在时间片归零时触发调度标志。 - 进程就绪队列(Ready Queue):按 FIFO 规则组织的链表或队列,专用于存放处于就绪状态的进程 PCB。调度程序始终从该队列头部获取下一个待分配 CPU 的进程。 - 进程阻塞队列(Blocked Queue)的作用边界区分: 阻塞队列用于组织因等待外部事件(如 I/O 传输、信号量)而无法执行的进程。时间片轮转调度器的核心逻辑仅在执行进程与就绪队列之间流转。进程因时间片用尽直接重回就绪队列,阻塞进程在被事件唤醒前绝不参与时间片轮转。因此,实现时间片轮转调度算法本身需要使用 PCB、时钟中断处理程序和就绪队列,而不直接使用阻塞队列。

2. 核心定理推导与计算模型

(1) 时间片大小 q 的量化权衡模型

设就绪队列中共有 \(n\)$ \text{个进程,时间片大小为} $\(q\)$ \text{,进程上下文切换开销(Context Switch Overhead)为} $\(s\)。 - 极值退化分析: - 当 \(q \to \infty\) 时:每个进程均能在单次时间片内完成计算,RR 算法退化为先来先服务(FCFS)算法。系统失去交互分时响应能力,短作业周转时间恶化。 - 当 \(q \to 0\) 时:进程切换高度频繁。CPU 绝大部分时间消耗在寄存器现场保存恢复、页表切换与 Cache 失效等额外开销上,系统吞吐量与处理机有效利用率逼近于 0。 - 系统有效利用率模型: 在单次调度执行周期中,CPU 有效运行时间为 \(q\)$ \text{,系统开销时间为} $\(s\)$ \text{。CPU 的有效计算利用率} $\(\eta\) 为: $\(\eta = \frac{q}{q + s}\)$ 若要求处理机切换开销占比不超过 \(\alpha\)$ \text{(如} $\(\alpha \le 10\%\)),则必须满足: $\(\frac{s}{q + s} \le \alpha \implies q \ge \frac{1 - \alpha}{\alpha} s\)$ 在典型现代操作系统中,上下文切换耗时 \(s\)$ \text{处于微秒(} $\(\mu\text{s}\)$ \text{)量级,而时间片} $\(q\)$ \text{通常设定在} $\(10\text{ ms} \sim 100\text{ ms}\)$ \text{区间,保证} $\(\eta \ge 99\%\)。 - 工程经验准则(80% 准则): 时间片 \(q\) 的理想取值应当使得系统内 80% 的短 CPU 突发作业能在单个时间片内执行完毕,从而在控制切换开销的同时,最大化交互型请求的响应速度。

(2) 响应时间界限(Response Time Bound)

在包含 \(n\)$ \text{个就绪进程的系统中,忽略上下文切换开销} $\(s\) 时: - 就绪队列中任意进程自进入就绪队列至首次获得 CPU 服务的最大等待时间(最坏响应时间 \(R_{\max}\))满足: $\(R_{\max} \le (n - 1) \cdot q\)$ - 任意进程在任意长度为 \(T = n \cdot q\)$ \text{的连续时间段内,必定能够获得至少} $\(q\) 的 CPU 运行时间。

(3) 性能指标计算模型

  • 周转时间(Turnaround Time, \(T_i\)): $\(T_i = T_{\text{completion}, i} - T_{\text{arrival}, i}\)$ 其中 \(T_{\text{completion}, i}\)$ \text{为进程} $\(P_i\)$ \text{完成执行的时刻,} $\(T_{\text{arrival}, i}\) 为其到达系统的时刻。
  • 带权周转时间(Weighted Turnaround Time, \(W_i\)): $\(W_i = \frac{T_i}{T_{\text{service}, i}}\)$ 其中 \(T_{\text{service}, i}\) 为进程实际需要的 CPU 计算时间。
  • 等待时间(Waiting Time, \(t_{w, i}\)): 在纯 CPU 计算型负载下,进程的等待时间为其在就绪队列中排队等待调度的累计时长: $\(t_{w, i} = T_i - T_{\text{service}, i}\)$

3. 核心对比辨析

(1) 处理机调度算法横向对比

以下为 408 考研核心调度算法的多维对比:

算法名称 调度方式(抢占/非抢占) 核心选程依据 算法核心优势 算法核心劣势 饥饿现象
时间片轮转 (RR) 抢占式(基于时间片耗尽) 到达顺序 FIFO + 固定时间片 \(q\) 兼顾公平性,交互响应时间存在确定上限 进程切换开销相对较高,对 I/O 密集型进程不够友好 无
先来先服务 (FCFS) 非抢占式 进入就绪队列的先后次序 算法逻辑简单,无频繁上下文切换开销 护航效应明显,长作业导致后续短作业等待过长 无
短作业优先 (SJF) 非抢占式 预估 CPU 突发时间长度 具有理论最优的平均等待时间和平均周转时间 依赖作业运行时间预估,长作业可能长期无法调度 有(长作业饥饿)
最短剩余时间优先 (SRTF) 抢占式(新短作业抢占) 进程剩余 CPU 执行时间 进一步压缩平均周转时间 调度开销大于 SJF,估算开销高 有(长作业饥饿)
高响应比优先 (HRRN) 非抢占式 响应比 $$ \text{R_p = 1 + \frac{\text{等待时间}}{\text{要求服务时间}}} $$ 动态权衡等待时间与服务时间,克服长作业饥饿 每次调度均需重新计算所有就绪进程响应比,开销较大 无
多级反馈队列 (MLFQ) 抢占式(动态时间片与优先级) 综合历史行为动态降级/提升 兼顾短作业快速完成与交互响应,无需预知运行时间 实现复杂,若无周期性优先级重置机制可能存在饥饿 有(未引入老化机制时)

(2) 深度概念辨析

  1. 时间片耗尽 vs I/O 阻塞的状态变迁机制:
  2. 时间片耗尽:由外部硬件时钟中断引发。进程本身具备一切运行条件,仅因分配的 CPU 配额用尽而交出处理机,状态由执行态转为就绪态,挂入就绪队列尾部。
  3. I/O 请求:由进程内部通过访管指令(Trap)主动发起。进程因等待外部事件丧失运行条件,状态由执行态转为阻塞态,挂入设备阻塞队列。
  4. 时钟中断发生与进程切换的非等价性:
  5. 时钟中断并不等同于进程切换。时钟中断以系统时钟节拍为周期发生(如每 \(1\text{ ms}\)$ \text{一次),而时间片通常涵盖多个时钟节拍(如} $\(q = 10\text{ ms}\) 对应 10 次中断)。
  6. 每次时钟中断仅仅递减当前进程剩余时间片计数;只有当计数递减至 0、触发重新调度标志时,系统才在中断返回前执行上下文切换。

三、 近十年真题精讲(2016~2025)

【真题 1】2017 年 408 第 27 题 · 时间片轮转状态转换与时钟中断机制

题目
下列有关基于时间片的进程调度的叙述中,错误的是( )。
A. 时间片越短,进程切换的次数越多,系统开销也越大
B. 当前进程的时间片用完后,该进程状态由执行态变为阻塞态
C. 时钟中断发生后,系统会修改当前进程在时间片内的剩余时间
D. 影响时间片大小的主要因素包括响应时间、系统开销和进程数量等

【解析】

  • 知识定位:操作系统 · 进程管理 · 处理机调度(时间片轮转运行机制、时钟中断处理及进程状态转换模型)。
  • 核心推导步骤与选项逐项分析:
  • 选项 A 正确:在进程所需 CPU 服务时间给定的前提下,时间片 \(q\) 越短,进程执行完毕所需的轮转次数越多,单位时间内发生的上下文切换越频繁。每次进程切换都伴随着寄存器现场压栈出栈、内核栈切换、TLB 及高速缓存失效等硬件开销,因此系统额外开销显著增加。
  • 选项 B 错误:进程从执行态转变为阻塞态的触发条件为进程主动发起系统调用请求外部资源或等待事件(如 I/O 操作、等待互斥信号量)。当当前进程的时间片耗尽时,该进程并未缺失任何运行资源,依然处于可运行状态,因此操作系统的调度程序将其状态从执行态修改为就绪态,并重新挂入就绪队列尾部。
  • 选项 C 正确:硬件时钟以固定频率产生时钟节拍中断。时钟中断处理程序每次执行时,均会递减当前执行进程的时间片剩余时间计数器。若剩余时间归零,则置调度标志位以启动调度程序。
  • 选项 D 正确:设计时间片大小需统筹平衡多方系统指标:
    1. 响应时间:分时交互体验要求系统响应时间上界满足 \(T_{\text{response}} \approx n \cdot q\),响应时间要求越短,时间片设定越小;
    2. 系统开销:时间片不能过小,必须远大于进程上下文切换开销 \(s\),以保障 CPU 利用率;
    3. 进程数量:系统中并发就绪进程数 \(n\) 越多,在给定的响应时间指标下,分配给各个进程的时间片均值越小。
  • 正确答案:B

【真题 2】2021 年 408 第 25 题 · 时间片轮转所需内核数据结构

题目
下列内核的数据结构或程序中,分时系统实现时间片轮转调度需要使用的是( )。
I. 进程控制块
II. 时钟中断处理程序
III. 进程就绪队列
IV. 进程阻塞队列
A. 仅 II、III
B. 仅 I、IV
C. 仅 I、II、III
D. 仅 I、II、IV

【解析】

  • 知识定位:操作系统 · 进程管理 · 处理机调度的内核实现机理与支撑实体。
  • 核心推导步骤与逐项剖析:
  • I 项(进程控制块,PCB):必须使用。时间片轮转调度涉及处理机的周期性抢占与分配。发生切换时,内核必须将当前进程的寄存器状态、程序计数器(PC)等现场信息保存至其 PCB 中,并将 PCB 内的进程状态标记修改为就绪态;随后根据下一就绪进程的 PCB 恢复现场。PCB 是调度执行的上下文载体。
  • II 项(时钟中断处理程序):必须使用。时间片轮转本质是由硬件时钟驱动的抢占式调度。系统依靠硬件时钟周期性产生中断,激活时钟中断处理程序对当前进程的时间片计数进行递减;当时间片用尽时置调度标志,从而强制剥夺处理机。
  • III 项(进程就绪队列):必须使用。时间片轮转调度算法严格按照先进先出(FIFO)原则组织就绪进程。调度程序从就绪队列头部选取进程投入运行,时间片耗尽但未完成的进程重新排入就绪队列尾部。就绪队列是时间片轮转算法的核心组织结构。
  • IV 项(进程阻塞队列):不使用。阻塞队列用于管理因等待 I/O、信号量等事件而无法执行的进程。时间片轮转调度器的工作范围严格限定在“当前运行进程”与“就绪队列”之间。阻塞进程因不具备运行条件,绝不参与轮转调度。阻塞队列的维护归属于设备管理或同步原语模块,调度算法本身不直接调用或操作阻塞队列。
  • 结论汇总:需要使用的是 I、II、III,IV 排除。
  • 正确答案:C

【真题 3】2024 年 408 第 30 题 · 时间片轮转周转时间计算

题目
假设某系统使用时间片轮转调度算法进行 CPU 调度,时间片大小为 5 ms,系统共有 10 个进程,初始时均处于就绪队列,执行结束前仅处于执行态或就绪态。若队尾的进程 P 所需 CPU 时间最短,时间为 25 ms。在不考虑系统开销的情况下,则进程 P 的周转时间为( )。
A. 200 ms
B. 205 ms
C. 250 ms
D. 295 ms

【解析】

  • 知识定位:操作系统 · 进程管理 · 处理机调度计算模型(时间片轮转执行轨迹推导与周转时间量化)。
  • 核心推导步骤:
  • 参数提取与约束解析:
    • 进程总数:\(N = 10\)$ \text{。将队列中的进程按照初始排队次序记为} $\(P_1, P_2, \dots, P_9, P\)。
    • 初始时刻:\(t = 0\)$ \text{时所有 10 个进程均已在就绪队列中排队,因此进程} $\(P\)$ \text{的到达时刻} $\(T_{\text{arrival}} = 0\)。
    • 进程 \(P\) 位于队尾(第 10 个位置)。
    • 时间片大小:\(q = 5\text{ ms}\)。
    • 进程 \(P\)$ \text{所需 CPU 运行时间:} $\(T_{\text{service}} = 25\text{ ms}\)。
    • 核心隐含条件:“队尾的进程 P 所需 CPU 时间最短,时间为 25 ms,执行结束前仅处于执行态或就绪态”。这表明系统中其余 9 个进程(\(P_1 \sim P_9\)$ \text{)的所需 CPU 时间均满足} $\(T_{\text{service}, i} \ge 25\text{ ms}\)$ \text{,且期间不发生任何 I/O 阻塞。因此,在进程} $\(P\)$ \text{运行结束退出之前,其余 9 个进程均不会执行完毕退出就绪队列。就绪队列在进程} $\(P\) 执行期间始终维持 10 个进程参与完整轮转。
  • 进程 \(P\) 执行所需的时间片轮数: $$ \text{k = \frac{T_{\text{service}}}{q} = \frac{25\text{ ms}}{5\text{ ms}} = 5 \text{ 轮}} $$ 进程 \(P\) 必须经过 5 个调度周期的执行方能结束。
  • 各轮转周期推导与时间轨迹展开:
    • 第 1 轮:
    • 排在进程 \(P\)$ \text{前面的 9 个进程依次各执行 1 个时间片:耗时} $\(9 \times 5 = 45\text{ ms}\)。
    • 队尾的进程 \(P\)$ \text{执行其第 1 个时间片:耗时} $\(5\text{ ms}\)$ \text{,运行时间区间为} $\([45\text{ ms}, 50\text{ ms}]\)。
    • 第 1 轮结束时刻为 \(t = 50\text{ ms}\)$ \text{。此时进程} $\(P\)$ \text{累计运行} $\(5\text{ ms}\),重回队列尾部。
    • 第 2 轮:
    • 前面 9 个进程各运行 1 个时间片:耗时 \(45\text{ ms}\)。
    • 进程 \(P\)$ \text{运行第 2 个时间片:耗时} $\(5\text{ ms}\)$ \text{,运行时间区间为} $\([95\text{ ms}, 100\text{ ms}]\)。
    • 第 2 轮结束时刻为 \(t = 100\text{ ms}\)$ \text{。此时进程} $\(P\)$ \text{累计运行} $\(10\text{ ms}\)。
    • 第 3 轮:
    • 同理,第 3 轮结束时刻为 \(t = 150\text{ ms}\)$ \text{。进程} $\(P\)$ \text{累计运行} $\(15\text{ ms}\)。
    • 第 4 轮:
    • 第 4 轮结束时刻为 \(t = 200\text{ ms}\)$ \text{。进程} $\(P\)$ \text{累计运行} $\(20\text{ ms}\)。
    • 第 5 轮(最后一轮):
    • 前面 9 个进程各运行 1 个时间片:耗时 \(9 \times 5 = 45\text{ ms}\)$ \text{,时间推进到} $\(200 + 45 = 245\text{ ms}\)。
    • 进程 \(P\)$ \text{获得 CPU,执行其第 5 个时间片:运行时间区间为} $\([245\text{ ms}, 250\text{ ms}]\)。
    • 在 \(t = 250\text{ ms}\)$ \text{时刻,进程} $\(P\)$ \text{累计运行时间达到} $\(25\text{ ms}\),全部任务执行完毕,退出系统。
  • 周转时间计算:
    • 进程 \(P\)$ \text{的完成时刻} $\(T_{\text{completion}} = 250\text{ ms}\)。
    • 进程 \(P\)$ \text{的到达时刻} $\(T_{\text{arrival}} = 0\text{ ms}\)。
    • 周转时间 \(T_{\text{turnaround}} = T_{\text{completion}} - T_{\text{arrival}} = 250 - 0 = 250\text{ ms}\)。
  • 干扰项排除:
  • A 选项(200 ms):错误地认为仅需 4 个轮转周期,或完全漏算了最后一轮执行。
  • B 选项(205 ms):误算为 4 个轮转周期(200 ms)后直接加上进程 \(P\)$ \text{的 1 个时间片(5 ms),忽略了在第 5 轮中排在} $\(P\) 前方的 9 个进程依然需要各自消耗 1 个时间片(45 ms)。
  • D 选项(295 ms):误将后续其他进程的执行时间累加到了 \(P\) 的周转时间中。
  • 正确答案:C

四、 综合考法拓展

1. 综合大题考查形态与衍生变式

在 408 综合应用大题中,处理机调度算法通常结合进程状态变迁、I/O 操作及同步互斥进行综合考查。时间片轮转的常考大题形态包括以下方向:

(1) 离散到达场景下的甘特图绘制与性能指标推导

  • 考法特征:给出各进程到达时间 \(T_{\text{arrival}}\)、CPU 突发时间序列,要求绘制调度甘特图(Gantt Chart)并计算平均周转时间、平均等待时间。
  • 难点与仲裁准则:在时间片耗尽时刻,若恰好有新进程到达就绪队列:
  • 默认准则:新到达的进程优先排入就绪队列,随后时间片耗尽的当前进程再追加至就绪队列队尾。做题时若题干给出了特定仲裁说明,必须严格以题干约定为准。
  • 标准指标计算模板: $$ \text{平均周转时间 } \bar{T} = \frac{1}{n}\sum_{i=1}^{n} (T_{\text{completion}, i} - T_{\text{arrival}, i}) $$ $$ \text{平均带权周转时间 } \bar{W} = \frac{1}{n}\sum_{i=1}^{n} \frac{T_{\text{completion}, i} - T_{\text{arrival}, i}}{T_{\text{service}, i}} $$ $$ \text{平均等待时间 } \bar{t}w = \frac{1}{n}\sum) $$}^{n} (T_{\text{completion}, i} - T_{\text{arrival}, i} - T_{\text{service}, i

(2) I/O 密集型进程的公平性失衡与虚拟轮转调度(VRR)

  • 现象分析:在标准 RR 调度下,I/O 密集型进程往往仅运行极短时间便发起 I/O 操作而放弃处理机。当 I/O 完成后,其重新进入就绪队列末尾,必须与完全使用满时间片的 CPU 密集型进程进行平等排队。这导致 I/O 密集型进程获得的 CPU 吞吐率偏低,I/O 设备长期处于空闲状态。
  • VRR 机制拓展: 操作系统引入辅助就绪队列(Auxiliary Queue)。当进程因 I/O 操作未用满时间片而让出 CPU 时,记录其剩余时间片;待其 I/O 完成后,放入辅助就绪队列。辅助就绪队列的调度优先级高于普通就绪队列,且调度辅助队列进程时,仅为其分配此前未用完的剩余时间。该变式常用于考查分时调度优化设计。

(3) 多级反馈队列(MLFQ)体系中时间片轮转的复合应用

  • 分级时间片规则:
  • 队列优先级越高,分配的时间片越短(例如 \(q_1 = 8\text{ ms}, q_2 = 16\text{ ms}, q_3 = 32\text{ ms}\));
  • 各队列内部均采用时间片轮转(RR)调度;
  • 进程时间片耗尽则降级,因 I/O 阻塞被唤醒则重新回到原队列(或保持高优先级)。

2. 底层系统调用与体系结构串联

  • 时钟中断驱动调度的全链路执行流程:
  • 硬件定时器计数溢出,向处理机发送中断请求线信号(INTR)。
  • CPU 硬件响应中断,保存当前进程断点现场(PC、PSW 压入内核栈),查中断向量表跳转至时钟中断处理程序。
  • 内核时钟 ISR 递减当前进程剩余时间片计数值:current->time_slice--。
  • 若剩余时间片减至 0,内核设置重调度标志位 need_resched = 1。
  • 在中断处理完毕、即将从内核态返回用户态的边界点,CPU 检查 need_resched 标志。
  • 若标志置位,调用调度函数 schedule():保存当前进程上下文至其 PCB,根据就绪队列 FIFO 规则选取下一进程 PCB,切换内核栈指针及页表基地址寄存器(CR3),通过中断返回指令(如 iret)投入新进程运行。

五、 考点速记清单

1. 核心要点速记

  • 状态转移铁律:时间片用完 \(\implies\)$ \text{执行态} $\(\to\)$ \text{就绪态(绝对不进入阻塞态);发起 I/O 或等待事件} $\(\implies\)$ \text{执行态} $\(\to\) 阻塞态。
  • 三大必需内核实体:实现时间片轮转调度必须依赖 PCB(上下文与状态记录)、时钟中断处理程序(时间片递减与抢占触发)、进程就绪队列(FIFO 组织)。阻塞队列不属于时间片轮转调度器的直接操作对象。
  • 时间片极限效应:
  • \(q \to \infty\):退化为 先来先服务(FCFS);
  • \(q \to 0\):上下文切换开销支配系统,处理机有效利用率逼近于 0。
  • 时间片设定准则:满足 80% 的 CPU 突发作业能在单个时间片内执行完毕,同时时间片 \(q\)$ \text{必须远大于上下文切换时间} $\(s\)。

2. 核心计算公式汇总

指标名称 计算公式 / 约束条件
CPU 有效利用率 \(\eta = \frac{q}{q + s}\)(\(q\)$ \text{为时间片,} $\(s\) 为上下文切换时间)
最坏响应时间上界 \(R_{\max} \le (n - 1) \cdot q\)(\(n\) 为就绪进程数)
单轮轮转周期总耗时 \(T_{\text{cycle}} = n \cdot q\)
周转时间 \(T_{\text{turnaround}} = T_{\text{completion}} - T_{\text{arrival}}\)
带权周转时间 \(W = \frac{T_{\text{turnaround}}}{T_{\text{service}}} \ge 1\)
等待时间(纯计算型) \(t_w = T_{\text{turnaround}} - T_{\text{service}}\)

3. 易错陷阱清单

  • 陷阱 1:时间片耗尽误判为进入阻塞态。
    纠错:阻塞态表示进程缺乏除 CPU 外的其他必要资源;时间片耗尽时进程只缺 CPU,具备立即运行条件,因此必然进入就绪态。
  • 陷阱 2:误以为每次时钟中断都进行进程切换。
    纠错:时钟中断是基准节拍(如 1 ms 一次),时间片通常包含多个时钟节拍(如 10 ms 包含 10 个节拍)。只有当时间片计数值归零时才触发进程切换。
  • 陷阱 3:周转时间轮转计算中遗漏最后一轮前序进程耗时。
    纠错:计算位于队尾的进程周转时间时,最后一轮轮到该进程执行之前,排在其前面的所有未结束进程必须各执行一个时间片,绝不可遗漏该部分前序等待时间。

4. 解题口诀

时钟节拍扣配额,耗尽回队转就绪;
若是 I/O 进阻塞,未完配额弃一旁;
就绪时钟加控制,三者协同保轮转;
队尾周转推周期,前序等待算周全!