跳转至

408 高频考点精讲:处理机调度算法

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


一、 考情档案

1. 考查频次统计

  • 近十年考查频次:11 次(2016 年第 46 题、2017 年第 23 题、2017 年第 27 题、2018 年第 24 题、2019 年第 27 题、2020 年第 26 题、2021 年第 25 题、2022 年第 25 题、2023 年第 29 题、2024 年第 30 题、2025 年第 25 题)
  • 历年总考查频次:16 次(2009~2025 年统考期间,另有 2010 年第 25 题、2011 年第 26 题、2012 年第 25 题、2013 年第 26 题、2015 年第 24 题等)
  • 出题形式:单项选择题为主(占 90% 以上),兼考综合应用题(如 2016 年第 46 题)。

2. 命题特点与规律

处理机调度算法是操作系统考查中覆盖度最高、出题频率最稳定的核心考点之一。近十年的命题呈现出四个鲜明的学术与实战特征: 1. 指标计算精细化与工程化:考查重心从单纯推演甘特图(Gantt Chart)计算周转时间,深化至考虑实际系统开销(如 2018 年考查包含进程上下文切换系统开销的平均周转时间计算;2024 年定量考查多进程时间片轮转的周期与周转耗时)。 2. 调度时机与次数判定细致化:命题深入考查进程状态转换时调度发生的精确时机与调度次数统计(如 2022 年考查抢占式优先级调度的触发时间点与调度总次数)。 3. 混合调度模型与算法设计并重:多级反馈队列(MLFQ)作为兼顾响应时间与系统吞吐量的综合调度机制,频繁考查其混合调度逻辑(如 2019 年)及设计要素(如 2020 年);综合题考查根据系统目标设计包含惩罚项与老化项的动态优先数计算公式(如 2016 年)。 4. 内核机制与底层数据结构联动:命题不再局限于概念表层,开始联动数据结构基础,考查进程就绪队列在内核中的组织形式(如单链表、优先队列)对插入进程、选出进程时间复杂度的决定性影响(如 2025 年)。

3. 近十年考查年份分布表格

+------+------+------------+------+--------------------------------------------------------+
| 年份 | 题号 |  题目类型  | 分值 |                        考查主题                        |
+------+------+------------+------+--------------------------------------------------------+
| 2016 |  46  | 综合解答题 | 7分  | 静态优先数饥饿原因分析、动态优先数防饥饿公式设计       |
| 2017 |  23  | 单项选择题 | 2分  | 指定时刻(t=2)下 FCFS 与 SJF 作业调度的决策比对          |
| 2017 |  27  | 单项选择题 | 2分  | 时间片轮转机制辨析、时钟中断与进程状态转换(执行态->就绪)|
| 2018 |  24  | 单项选择题 | 2分  | 考虑进程切换系统开销(1us)的非抢占优先级调度周转时间计算|
| 2019 |  27  | 单项选择题 | 2分  | 二级反馈队列(RR+SPF)进程运行轨迹与平均等待时间推导     |
| 2020 |  26  | 单项选择题 | 2分  | 多级反馈队列调度算法设计需考虑的四大系统要素           |
| 2021 |  25  | 单项选择题 | 2分  | 分时系统实现时间片轮转调度所需的内核数据结构与程序     |
| 2022 |  25  | 单项选择题 | 2分  | 抢占式优先级调度的调度时机判定与调度总次数统计         |
| 2023 |  29  | 单项选择题 | 2分  | 抢占式优先级调度下的甘特图推导与平均周转时间计算       |
| 2024 |  30  | 单项选择题 | 2分  | 时间片轮转调度下多进程轮转周期的定量周转时间推算       |
| 2025 |  25  | 单项选择题 | 2分  | 优先权调度中单链表组织就绪队列的插入与选出时间复杂度   |
+------+------+------------+------+--------------------------------------------------------+

二、 具体考察内容

1. 处理机调度的层次、时机与切换机制

(1) 调度的三个层次

  • 高级调度(作业调度/长程调度):从外存后备队列中挑选作业分配内存与资源,创建进程 PCB,进入就绪队列。发生频度最低(几分钟或几小时一次)。
  • 中级调度(内存调度/交换技术):将暂时不能运行的进程挂起(移至外存对换区),当内存空闲且进程具备运行条件时重新调入内存,修改其状态为挂起就绪 \(\to\) 就绪。发生频度中等。
  • 低级调度(进程调度/短程调度):从就绪队列中选择一个进程为其分配处理机。发生频度极高(通常几十毫秒一次)。

(2) 进程调度的时机与限制

  • 不能进行进程调度与切换的情形:
  • 在处理中断的过程中。
  • 处于操作系统内核程序临界区中(持有内核自旋锁或访问内核共享数据结构,若此时发生调度可能导致死锁或内核数据不一致)。
  • 执行屏蔽中断的原语操作过程中。

    重要概念辨析:进程处于“内核程序临界区”不可进行调度与切换;但处于“普通临界区”(访问临界资源如打印机、用户态共享内存等)时,若互斥资源不可用,进程会主动进入阻塞态并触发调度让出 CPU,因此普通临界区内完全可以发生进程调度。

  • 必须进行进程调度与切换的情形:
  • 主动放弃 CPU:进程正常执行终止(Exit 系统调用)、发生异常崩溃终止、发起 I/O 请求进入阻塞态、主动执行睡眠操作(如 sleep())。
  • 被动剥夺 CPU:分配给当前进程的时间片耗尽(时钟中断触发)、更高优先级进程进入就绪队列(抢占式系统)。

(3) 调度的控制方式

  • 非抢占方式(非剥夺式,Non-preemptive):一旦把处理机分配给某进程,便一直由该进程占用,直到该进程完成或因发生某事件进入阻塞态时,才把处理机分配给其他进程。实现简单,系统开销小,但无法用于分时系统与实时系统。
  • 抢占方式(剥夺式,Preemptive):当有更高优先级的进程进入就绪队列,或当前进程的时间片用尽时,系统可暂停正在执行的进程,将处理机重新分配给其他就绪进程。抢占原则通常依据:优先权原则、短进程优先原则、时间片原则。

2. 调度算法评价指标与数学模型

设系统中共有 \(n\)$ \text{个作业或进程,对第} $\(i\) 个作业/进程定义如下时间标量: - 到达时刻(Arrival Time):\(A_i\) - 开始运行时刻(Start Time):\(S_i\)(首次获得 CPU 的时刻) - 完成时刻(Completion Time):\(C_i\) - 服务时间 / 运行时间(Burst Time / Service Time):\(T_{s,i}\)

各项评价指标的严格数学推导与定义如下:

(1) 周转时间(Turnaround Time)

作业从提交到完成所经历的全部时间跨度: $\(T_i = C_i - A_i\)$

(2) 平均周转时间(Average Turnaround Time)

系统内所有作业周转时间的算术平均值: $\(T_{\text{avg}} = \frac{1}{n} \sum_{i=1}^n T_i = \frac{1}{n} \sum_{i=1}^n (C_i - A_i)\)$

(3) 带权周转时间(Weighted Turnaround Time)

作业周转时间与其实际运行时间的比值,反映系统对短作业的相对响应优劣: $\(W_i = \frac{T_i}{T_{s,i}} = \frac{C_i - A_i}{T_{s,i}} \quad (W_i \ge 1)\)$

(4) 平均带权周转时间(Average Weighted Turnaround Time)

\[W_{\text{avg}} = \frac{1}{n} \sum_{i=1}^n W_i = \frac{1}{n} \sum_{i=1}^n \frac{C_i - A_i}{T_{s,i}}\]

(5) 等待时间(Waiting Time)

进程在就绪队列中等待获得处理机的总时间。 - 不考虑进程切换开销时: $$T_{w,i} = T_i

  • T_{s,i} = C_i

  • A_i

  • T_{s,i}$$

  • 考虑进程切换开销 \(\tau\) 时: 若进程在就绪队列中经历了初始等待及若干次被抢占中断后的再等待,其周转时间由“到达前等待时间 + 各次纯就绪等待时间 + 实际执行时间 + 调度与进程切换开销”共同构成。计算时必须将每次发生调度导致的系统开销 \(\tau\) 计入时间轴推进。

(6) 响应时间(Response Time)

对于交互式系统,从用户提交请求到系统首次产生响应的这一段物理时间间隔: $\(R_i = S_i - A_i\)$


3. 典型调度算法深度剖析

(1) 先来先服务算法(FCFS, First-Come, First-Served)

  • 算法规则:按照作业或进程进入系统的先后顺序进行调度。
  • 算法性质:属于非抢占式算法;对长作业有利,对短作业极其不利;绝对不会发生饥饿(Starvation)。
  • 护航效应(Convoy Effect):当一个长 CPU 密集型进程占用处理机时,所有短 I/O 密集型进程均须在就绪队列中长时间等待,导致 I/O 设备与 CPU 利用率严重失衡。

(2) 短作业优先算法(SJF) / 短进程优先算法(SPF)

  • 算法规则:从就绪队列中选择估计运行时间(CPU Burst Time)最短的作业或进程投入运行。
  • 变体分类:
  • 非抢占式 SJF/SPF:一旦短进程开始执行,即使有更短的进程到达,也必须等待当前进程执行结束。
  • 抢占式 SJF(最短剩余时间优先 SRTF, Shortest Remaining Time First):当新进程到达时,若新进程所需的运行时间短于当前正在运行进程的“剩余运行时间”,系统剥夺当前进程的处理机,改由新进程执行。
  • 理论极值性:在所有进程同时到达的前提下,SJF 算法可以获得理论上的最小平均周转时间与最小平均等待时间。
  • 算法缺陷:
  • 必须预知进程的运行时间(现实中难以精确获知,多采用加权指数平均法预测)。
  • 极易产生饥饿现象:若长作业在等待期间源源不断有短作业到达,长作业可能永远得不到调度(饿死)。

(3) 高响应比优先算法(HRRN, Highest Response Ratio Next)

  • 响应比公式定义: $$ \text{R_p = \frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}} = 1 + \frac{\text{等待时间}}{\text{要求服务时间}}} $$
  • 机制原理:
  • 作业服务时间短时,分母较小,响应比容易攀升,体现了短作业优先的特点。
  • 作业等待时间逐渐拉长时,分子逐渐变大,响应比随等待时间线性提高,当等待足够长时必能获得处理机,有效规避了饥饿现象。
  • 算法性质:通常采用非抢占式调度。每次调度前需要对就绪队列中的所有进程重新计算一次响应比,带来一定的算法计算开销。

(4) 时间片轮转调度算法(RR, Round-Robin)

  • 核心机制: 就绪进程按 FCFS 原则排成就绪队列。系统由硬件时钟发生器周期性产生时钟中断,每隔一个固定时间片 \(q\),中断处理程序介入。若当前进程在时间片内执行完成,则主动让出 CPU;若时间片用尽而未完成,操作系统剥夺其处理机,将该进程状态修改为就绪态(并非阻塞态!),并将其插入就绪队列末尾,随后调度队头进程运行。
  • 时间片大小 \(q\) 的选择与系统权衡:
  • 若 \(q \to \infty\):就绪队列中每个进程都能在单个时间片内执行完毕,算法完全退化为 FCFS 算法。
  • 若 \(q \to 0\):每个时间片内用于进程上下文切换(Context Switch)的开销比例剧增,导致处理机有效利用率逼近于 0。
  • 确定原则:时间片大小应略大于一次典型交互所需的时间,使得 80% 的短任务能在一个时间片内完成。
  • 内核底层依赖组件(2021 考点):
  • 进程控制块(PCB):用于保存时间片剩余计数、程序计数器 PC、通用寄存器上下文。
  • 时钟中断处理程序:系统节拍的核心驱动者,在中断服务例程中对运行进程的时间片计数器执行递减操作,触发调度标志位。
  • 进程就绪队列:按先进先出组织就绪进程,提供入队、出队操作。

    进程阻塞队列不参与时间片轮转的分配调度。

(5) 优先级调度算法(Priority Scheduling)

  • 数值与等级定义:考研题目中,优先权数值与优先级高低的关系必须严格遵循题目给定假设(有的题目规定数值越大优先级越高,有的题目规定数值越小优先级越高,审题务必看清说明)。
  • 静态优先级 vs 动态优先级:
  • 静态优先级:创建进程时确定,在整个生命周期内固定不变。易导致低优先级进程发生饥饿。
  • 动态优先级:随进程运行状态动态调整。调整原则通常为:
    • 根据等待时间调整:等待时间越长,优先级适当调高(老化机制 Aging)。
    • 根据 CPU 占用时间调整:已消耗 CPU 时间越长,优先级适当降低(惩罚长 CPU 密集型任务)。
    • 根据 I/O 操作频率调整:频繁进行 I/O 请求的进程应赋予高优先级,以提升 I/O 设备的并行利用率。
  • 就绪队列底层数据结构与时间复杂度(2025 考点):
  • 单链表(按优先级降序维护,最高优先级在队头):
    • 插入新进程:需在链表中从头遍历寻找适宜的插入位置以维持有序性,最坏与平均时间复杂度均为 \(O(n)\)。
    • 选出最高优先级进程:直接取出单链表队头节点,时间复杂度为 \(O(1)\)。
  • 无序单链表(新进程直接入队尾或队头):
    • 插入新进程:\(O(1)\)。
    • 选出最高优先级进程:必须全表扫描寻找极值节点,\(O(n)\)。
  • 二叉优先队列(最大堆 / 最小堆):
    • 插入新进程:堆的上浮调整,\(O(\log n)\)。
    • 选出最高优先级进程:删除堆顶并下沉调整,\(O(\log n)\)。

(6) 多级反馈队列调度算法(MLFQ, Multi-Level Feedback Queue)

现代操作系统的经典通用调度模型(Unix、Linux、Windows 的前身模型),具备动态自适应能力。 - 核心体系结构设计: 1. 设置多个就绪队列 \(Q_1, Q_2, \dots, Q_k\)$ \text{,队列优先级依次递减:} $\(\text{Priority}(Q_1) > \text{Priority}(Q_2) > \dots > \text{Priority}(Q_k)\)。 2. 各队列分配的时间片大小依次递增:通常下一级队列的时间片比上一级翻倍,即 \(q_{i+1} = 2 q_i\)。 3. 各队列内部的调度策略:通常高优先级队列采用时间片轮转(RR),最低级队列可采用 RR、FCFS 或 SPF。 - 工作运转流程: 1. 新创建的进程首先进入第一级队列 \(Q_1\)$ \text{队尾,按 FCFS 获得 CPU 并执行一个时间片} $\(q_1\)。 2. 若该进程在时间片 \(q_1\)$ \text{内执行完成,便直接退出;若未执行完成,调度程序将其强制剥夺 CPU 并降级插入第二级队列} $\(Q_2\) 队尾。 3. 仅当高优先级队列为空时,系统才调度低优先级队列中的进程执行(强抢占原则)。若低优先级队列进程正在运行时有新进程进入高优先级队列,新进程立即剥夺当前处理机。 - 架构设计必须考量的四大系统要素(2020 考点): - Ⅰ. 就绪队列的数量。 - Ⅱ. 就绪队列的优先级设定。 - Ⅲ. 各就绪队列内部所采用的调度算法。 - Ⅳ. 进程在不同就绪队列之间的迁移条件(降级规则与防饥饿升级规则)。


4. 核心调度算法横向对比矩阵

+----------------------+----------+--------------------------------+--------------------+--------------------+----------+--------------------+
|       算法名称       | 调度方式 |            核心思想            |        优点        |        缺点        | 是否饥饿 |      适用场景      |
+----------------------+----------+--------------------------------+--------------------+--------------------+----------+--------------------+
| 先来先服务 (FCFS)    |  非抢占  | 按进入系统的先后次序调度       | 算法最简单、无饥饿 | 护航效应,不利短作业|    否    | 早期批处理系统     |
+----------------------+----------+--------------------------------+--------------------+--------------------+----------+--------------------+
| 短作业/进程优先(SJF) | 抢占/非抢| 选择估计运行时间最短的进程调度 | 平均周转时间理论最优| 长作业饥饿、需预估 |    是    | 批处理作业调度     |
+----------------------+----------+--------------------------------+--------------------+--------------------+----------+--------------------+
| 高响应比优先 (HRRN)  |  非抢占  | 结合等待时间与服务时间动态权衡 | 兼顾短作业,避免饥饿| 需动态计算响应比开销|    否    | 批处理系统作业调度 |
+----------------------+----------+--------------------------------+--------------------+--------------------+----------+--------------------+
| 时间片轮转 (RR)      |   抢占   | 循环为就绪进程分配定长时间片   | 响应及时,适合交互 | 频繁上下文切换开销 |    否    | 分时操作系统       |
+----------------------+----------+--------------------------------+--------------------+--------------------+----------+--------------------+
| 优先级调度算法       | 抢占/非抢| 按紧迫程度(优先权大小)调度   | 区分任务轻重缓急   | 静态优先级导致饥饿 |静态是/动态否| 实时操作系统/通用  |
+----------------------+----------+--------------------------------+--------------------+--------------------+----------+--------------------+
| 多级反馈队列 (MLFQ)  |   抢占   | 优先级与时间片倒数配合、自适应 | 兼顾响应、吞吐、周转| 算法实现复杂、调参多|可通过老化免| 现代主流通用系统   |
+----------------------+----------+--------------------------------+--------------------+--------------------+----------+--------------------+

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

【真题 1】2016 年 408 第 46 题 · 动态优先数调度模型设计与防饥饿机制

题目
某进程调度程序采用基于优先数(priority)的调度策略,即选择优先数最小的进程运行,进程创建时由用户指定一个 nice 作为静态优先数。为了动态调整优先数,引入运行时间 cpuTime 和等待时间 waitTime,初值均为 0。进程处于执行态时,cpuTime 定时加 1,且 waitTime 置 0;进程处于就绪态时,cpuTime 置 0,waitTime 定时加 1。请回答下列问题。
(1) 若调度程序只将 nice 的值作为进程的优先数,即 priority = nice,则可能会出现饥饿现象,为什么?
(2) 使用 nice、cpuTime 和 waitTime 设计一种动态优先数计算方法,以避免产生饥饿现象,并说明 waitTime 的作用。

【解析】

  • 知识定位:基于优先级的处理机调度策略;静态优先权缺陷;动态优先级数学模型设计与防饥饿(老化机制)。
  • 推导与分析:
  • 第 (1) 问分析:
    题目明确规定“选择优先数最小的进程运行”。当采用静态优先数 priority = nice 时,就绪队列中若持续不断地有优先数较小(即优先级较高)的新进程到达,系统将始终优先调度这些优先数较小的新进程。因此,优先数较大(即优先级较低)的就绪进程将长期无法获得处理机,从而发生饥饿现象(饿死)。
  • 第 (2) 问分析:
    要避免饥饿现象,必须打破低优先级进程永久无法运行的困境,其核心手段为老化(Aging)机制:随着进程在就绪队列中等待时间的推移,动态降低其优先数(即动态提升其优先级)。
    • 目标:优先数越小越优先获得 CPU。
    • 基准值:进程创建时的初始静态偏好 nice。
    • 惩罚项:进程在运行态占用 CPU 越久,应使优先数增大(降低优先级,避免垄断 CPU),因此 cpuTime 项的系数应为正数,即 \(+ k_1 \times \text{cpuTime}\)。
    • 补偿项 / 老化项:进程在就绪态等待越久,应使其优先数不断减小(提升优先级,防止饥饿),因此 waitTime 项的系数应为负数,即 \(- k_2 \times \text{waitTime}\)。
    • 综上,动态优先数的数学模型可设计为: $\(\text{priority} = \text{nice} + k_1 \times \text{cpuTime} - k_2 \times \text{waitTime} \quad (k_1 > 0, \; k_2 > 0)\)$
    • waitTime 的作用:使长期处于就绪态等待调度的进程,其优先数随等待时间的增加而逐步降低(即优先级逐步提升),直到该进程的优先数低于系统中其他正在运行或就绪的进程,从而确保其能够被调度程序选中执行,彻底避免饥饿现象。

正确答案:
(1) 由于采用了静态优先数,若就绪队列中总有优先数较小(优先级较高)的进程到达,优先数较大(优先级较低)的进程将一直无法获得 CPU 运行,因而会出现饥饿现象。
(2) 动态优先数计算方法为:\(\text{priority} = \text{nice} + k_1 \times \text{cpuTime} - k_2 \times \text{waitTime}\)$ \text{,其中} $\(k_1 > 0, k_2 > 0\)(用于调节 CPU 运行惩罚与等待补偿在优先级计算中的权重比例)。waitTime 的作用在于对长期处于就绪态等待的进程进行优先级提升(降低其优先数值),确保等待时间足够长的进程必然能获得运行机会,从而避免饥饿。


【真题 2】2017 年 408 第 23 题 · FCFS 与 SJF 在特定时刻的决策比对

题目
假设 4 个作业到达系统的时刻和运行时间如下表所示。

作业    到达时刻 t    运行时间
J1         0             3
J2         1             3
J3         1             2
J4         3             1
系统在 \(t = 2\) 时开始作业调度。若分别采用先来先服务和短作业优先调度算法,则选中的作业分别是( )。
A. \(J_2\)、\(J_3\)
B. \(J_1\)、\(J_4\)
C. \(J_2\)、\(J_4\)
D. \(J_1\)、\(J_3\)

【解析】

  • 知识定位:高级调度(作业调度);FCFS 算法与 SJF 算法决策逻辑。
  • 推导与分析:
  • 系统在 \(t = 2\)$ \text{时刻才正式启动作业调度。因此,必须首先考察在} $\(t = 2\) 时刻,系统中已经到达后备队列的作业集合。
  • 作业到达时刻核查:
    • \(J_1\)$ \text{于} $\(t = 0\) 到达(已到达)。
    • \(J_2\)$ \text{于} $\(t = 1\) 到达(已到达)。
    • \(J_3\)$ \text{于} $\(t = 1\) 到达(已到达)。
    • \(J_4\)$ \text{于} $\(t = 3\)$ \text{到达(在} $\(t = 2\) 时尚未到达,绝对不可被选入考虑范围)。 因此,在 \(t = 2\)$ \text{时刻可供调度的作业候选集仅为} $\(\{J_1, J_2, J_3\}\)。
  • 先来先服务(FCFS)决策:
    在候选集中挑选到达时刻最早的作业。\(J_1\)$ \text{到达时刻为 0,} $\(J_2, J_3\)$ \text{到达时刻为 1,故最早到达者为} $\(J_1\)$ \text{。选中的作业为} $\(J_1\)。
  • 短作业优先(SJF)决策:
    在候选集中挑选要求运行时间最短的作业。已知各候选作业运行时间为:\(J_1 = 3, J_2 = 3, J_3 = 2\)$ \text{。运行时间最短者为} $\(J_3\)$ \text{(所需时间为 2)。选中的作业为} $\(J_3\)。
  • 综合以上分析,选中的作业分别为 \(J_1\)$ \text{和} $\(J_3\)。

正确答案:D


【真题 3】2017 年 408 第 27 题 · 时间片轮转调度与进程状态转换辨析

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

【解析】

  • 知识定位:时间片轮转(RR)调度机制;三态模型转换;时钟中断原理。
  • 逐项分析:
  • A 项正确:时间片越小,单位时间内发生的时钟中断与进程上下文切换频率越高。保存与恢复硬件上下文(PC、寄存器、PSW 等)均耗费 CPU 周期,因此系统开销显著增大。
  • B 项错误:当前运行进程的时间片用尽,仅仅代表操作系统依据调度规则收回了其处理机使用权,该进程并未请求任何外设,亦未等待任何外部同步事件(其指令、数据与资源均完备)。因此,该进程是由执行态转变为就绪态,并重新排入就绪队列末尾,而不是变为阻塞态。
  • C 项正确:硬件时钟周期性产生时钟节拍中断,操作系统在时钟中断处理例程中对当前执行进程的剩余时间片进行递减操作,以监控该进程是否超时。
  • D 项正确:在分时系统中,设响应时间指标为 \(T\)$ \text{,就绪进程数量为} $\(N\)$ \text{,系统进程切换开销为} $\(S\)$ \text{,时间片为} $\(q\)$ \text{。系统响应周期近似满足} $\(T \ge N(q + S)\)$ \text{。因此确定} $\(q\) 必须权衡响应时间指标要求、进程并发规模以及切换开销。

正确答案:B


【真题 4】2018 年 408 第 24 题 · 考虑上下文切换开销的非抢占优先级调度周转时间计算

题目
某系统采用基于优先权的非抢占式进程调度策略,完成一次进程调度和进程切换的系统时间开销为 \(1\ \mu\text{s}\)$ \text{。在} $\(T\)$ \text{时刻就绪队列中有 3 个进程} $\(P_1\)、\(P_2\)$ \text{和} $\(P_3\),其在就绪队列中的等待时间、需要的 CPU 时间和优先权如下表所示。

进程    等待时间    需要的 CPU 时间    优先级
 P1      30 us          12 us           10
 P2      15 us          24 us           30
 P3      18 us          36 us           20
若优先权值大的进程优先获得 CPU,从 \(T\) 时刻起系统开始进程调度,则系统的平均周转时间为( )。
A. \(54\ \mu\text{s}\)
B. \(73\ \mu\text{s}\)
C. \(74\ \mu\text{s}\)
D. \(75\ \mu\text{s}\)

【解析】

  • 知识定位:非抢占式优先级调度;进程上下文切换系统开销;周转时间定义。
  • 核心推导步骤:
  • 执行序列判定:
    题目明确“优先权值大者优先”,且为“非抢占式”。在 \(T\)$ \text{时刻三个进程均已在就绪队列中:} $\(P_1\)$ \text{优先权为 10,} $\(P_2\)$ \text{优先权为 30,} $\(P_3\) 优先权为 20。
    因此优先级高低关系为:\(P_2 (30) > P_3 (20) > P_1 (10)\)。
    进程调度执行顺序严格为:\(P_2 \to P_3 \to P_1\)。
  • 时间轴推进(设 \(T = 0\ \mu\text{s}\)$ \text{,调度切换开销} $\(\tau = 1\ \mu\text{s}\)):
    • 调度并运行 \(P_2\):
    • \(0 \sim 1\ \mu\text{s}\)$ \text{:调度并切换到} $\(P_2\)$ \text{(开销} $\(1\ \mu\text{s}\))。
    • \(1 \sim 25\ \mu\text{s}\):\(P_2\)$ \text{执行} $\(24\ \mu\text{s}\)$ \text{,于} $\(t = 25\ \mu\text{s}\) 完成。
    • \(P_2\)$ \text{完成时刻为} $\(25\ \mu\text{s}\)$ \text{。由于在} $\(T\)$ \text{时刻前} $\(P_2\)$ \text{已等待了} $\(15\ \mu\text{s}\)$ \text{(即到达时刻为} $\(-15\ \mu\text{s}\)),
      故 \(P_2\)$ \text{的周转时间为:} $\(T_2 = 25 - (-15) = 15 + 25 = 40\ \mu\text{s}\)。
    • 调度并运行 \(P_3\):
    • \(25 \sim 26\ \mu\text{s}\)$ \text{:调度并切换到} $\(P_3\)$ \text{(开销} $\(1\ \mu\text{s}\))。
    • \(26 \sim 62\ \mu\text{s}\):\(P_3\)$ \text{执行} $\(36\ \mu\text{s}\)$ \text{,于} $\(t = 62\ \mu\text{s}\) 完成。
    • \(P_3\)$ \text{在} $\(T\)$ \text{时刻前已等待} $\(18\ \mu\text{s}\)$ \text{(到达时刻为} $\(-18\ \mu\text{s}\)),
      故 \(P_3\)$ \text{的周转时间为:} $\(T_3 = 62 - (-18) = 18 + 62 = 80\ \mu\text{s}\)。
    • 调度并运行 \(P_1\):
    • \(62 \sim 63\ \mu\text{s}\)$ \text{:调度并切换到} $\(P_1\)$ \text{(开销} $\(1\ \mu\text{s}\))。
    • \(63 \sim 75\ \mu\text{s}\):\(P_1\)$ \text{执行} $\(12\ \mu\text{s}\)$ \text{,于} $\(t = 75\ \mu\text{s}\) 完成。
    • \(P_1\)$ \text{在} $\(T\)$ \text{时刻前已等待} $\(30\ \mu\text{s}\)$ \text{(到达时刻为} $\(-30\ \mu\text{s}\)),
      故 \(P_1\)$ \text{的周转时间为:} $\(T_1 = 75 - (-30) = 30 + 75 = 105\ \mu\text{s}\)。
  • 计算平均周转时间: $\(T_{\text{avg}} = \frac{T_2 + T_3 + T_1}{3} = \frac{40 + 80 + 105}{3} = \frac{225}{3} = 75\ \mu\text{s}\)$

正确答案:D


【真题 5】2019 年 408 第 27 题 · 二级反馈队列(RR+SPF)平均等待时间推导

题目
系统采用二级反馈队列调度算法进行进程调度。就绪队列 \(Q_1\)$ \text{采用时间片轮转调度算法,时间片为} $\(10\text{ ms}\)$ \text{;就绪队列} $\(Q_2\)$ \text{采用短进程优先调度算法;系统优先调度} $\(Q_1\)$ \text{队列中的进程,当} $\(Q_1\)$ \text{为空时系统才会调度} $\(Q_2\)$ \text{中的进程;新创建的进程首先进入} $\(Q_1\);\(Q_1\)$ \text{中的进程执行一个时间片后,若未结束,则转入} $\(Q_2\)$ \text{。若当前} $\(Q_1, Q_2\)$ \text{为空,系统依次创建进程} $\(P_1, P_2\)$ \text{后即开始进程调度,} $\(P_1, P_2\)$ \text{需要的 CPU 时间分别为} $\(30\text{ ms}\)$ \text{和} $\(20\text{ ms}\)$ \text{,则进程} $\(P_1, P_2\) 在系统中的平均等待时间为( )。
A. \(25\text{ ms}\)
B. \(20\text{ ms}\)
C. \(15\text{ ms}\)
D. \(10\text{ ms}\)

【解析】

  • 知识定位:多级反馈队列(MLFQ)调度运行推演;等待时间计算公式。
  • 推导与分析:
  • 初始状态与到达:\(P_1, P_2\)$ \text{依次创建进入} $\(Q_1\)$ \text{队尾,此时} $\(Q_1\)$ \text{中有} $\(P_1\)$ \text{(在队头)和} $\(P_2\)$ \text{(在队尾),到达时刻均视为} $\(t = 0\text{ ms}\)。
  • 第一阶段:\(Q_1\)$ \text{队列调度(时间片轮转,时间片} $\(10\text{ ms}\)):
    • \(0 \sim 10\text{ ms}\)$ \text{:调度} $\(P_1\)$ \text{执行一个时间片(} $\(10\text{ ms}\))。\(P_1\)$ \text{剩余运行时间为} $\(30 - 10 = 20\text{ ms}\)$ \text{,未结束,降入} $\(Q_2\) 队列尾部。
    • \(10 \sim 20\text{ ms}\)$ \text{:调度} $\(P_2\)$ \text{执行一个时间片(} $\(10\text{ ms}\))。\(P_2\)$ \text{剩余运行时间为} $\(20 - 10 = 10\text{ ms}\)$ \text{,未结束,降入} $\(Q_2\) 队列尾部。
  • 第二阶段:\(Q_2\) 队列调度(短进程优先 SPF,非抢占):
    • 此时 \(Q_1\)$ \text{已空,调度程序转向} $\(Q_2\)。
    • 在 \(t = 20\text{ ms}\)$ \text{时,} $\(Q_2\) 队列中存在两个候选进程:
    • \(P_1\)$ \text{(剩余 CPU 时间} $\(20\text{ ms}\))
    • \(P_2\)$ \text{(剩余 CPU 时间} $\(10\text{ ms}\))
    • \(Q_2\)$ \text{采用短进程优先(SPF),比较剩余 CPU 时间:} $\(P_2(10\text{ ms}) < P_1(20\text{ ms})\)$ \text{,故系统选择} $\(P_2\) 运行。
    • \(20 \sim 30\text{ ms}\):\(P_2\)$ \text{执行} $\(10\text{ ms}\)$ \text{,彻底完成退出。完成时刻} $\(C_2 = 30\text{ ms}\)。
    • \(30 \sim 50\text{ ms}\):\(Q_2\)$ \text{中仅剩} $\(P_1\)$ \text{,调度} $\(P_1\)$ \text{执行} $\(20\text{ ms}\)$ \text{,彻底完成退出。完成时刻} $\(C_1 = 50\text{ ms}\)。
  • 指标计算:

  • 等待时间 = 完成时刻

  • 到达时刻

  • 自身服务时间(即 $T_{w} = C

  • A

  • T_s$):

    • \(P_1\)$ \text{的等待时间:} $\(T_{w,1} = 50 - 0 - 30 = 20\text{ ms}\)。
      (验算分段等待:在 \(Q_1\)$ \text{未等待,在} $\(Q_2\)$ \text{等待了} $\(10 \sim 30\text{ ms}\)$ \text{共} $\(20\text{ ms}\),正确)
    • \(P_2\)$ \text{的等待时间:} $\(T_{w,2} = 30 - 0 - 20 = 10\text{ ms}\)。
      (验算分段等待:在 \(0 \sim 10\text{ ms}\)$ \text{等待} $\(P_1\)$ \text{执行} $\(10\text{ ms}\)$ \text{,在} $\(20\text{ ms}\)$ \text{时直接被调度执行,累计等待} $\(10\text{ ms}\),正确)
    • 平均等待时间: $\(T_{\text{avg\_wait}} = \frac{T_{w,1} + T_{w,2}}{2} = \frac{20 + 10}{2} = 15\text{ ms}\)$

正确答案:C


【真题 6】2020 年 408 第 26 题 · 多级反馈队列调度算法设计要素

题目
下列与进程调度有关的因素中,在设计多级反馈队列调度算法时需要考虑的是( )。
Ⅰ. 就绪队列的数量
Ⅱ. 就绪队列的优先级
Ⅲ. 各就绪队列的调度算法
Ⅳ. 进程在就绪队列间的迁移条件
A. 仅Ⅰ、Ⅱ
B. 仅Ⅲ、Ⅳ
C. 仅Ⅱ、Ⅲ、Ⅳ
D. Ⅰ、Ⅱ、Ⅲ和Ⅳ

【解析】

  • 知识定位:多级反馈队列调度算法(MLFQ)系统设计要素。
  • 逐项分析:
  • Ⅰ 正确:就绪队列的数量决定了分级的粒度。队列数量过多会增加管理开销,过少则无法区分长短进程与 I/O 密集型进程。
  • Ⅱ 正确:各就绪队列的相对优先级决定了队列间的抢占调度关系(只有高优先级队列为空时才调度低优先级队列)。
  • Ⅲ 正确:各个队列内部可采用不同的调度算法,例如最高级队列采用短时间片 RR,中间队列采用较长时间片 RR,最低级队列可采用 FCFS 或 SPF。
  • Ⅳ 正确:进程如何在队列之间流动是算法的核心动态机制(如:时间片用尽降级、I/O 阻塞返回保持原级或升级、等待时间过长通过老化升级防止饥饿)。
  • 综上,Ⅰ、Ⅱ、Ⅲ、Ⅳ 均为设计多级反馈队列调度时必须明确的要素。

正确答案:D


【真题 7】2021 年 408 第 25 题 · 时间片轮转调度所依赖的内核数据结构与程序

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

【解析】

  • 知识定位:分时操作系统内核架构;时间片轮转调度底层实现机制。
  • 逐项分析:
  • Ⅰ 正确:进程控制块(PCB)是操作系统管理进程的核心数据结构。实现时间片轮转必须利用 PCB 记录当前进程的执行状态、保存上下文(通用寄存器、PC、PSW),并维护进程分配的时间片限额及剩余时间。
  • Ⅱ 正确:时钟中断是实现时间片轮转的硬件基础。操作系统通过周期性的时钟中断处理程序对当前进程消耗的时间进行计数,当时间片递减为 0 时,由时钟中断处理程序置调度标志并调用调度器进行进程切换。
  • Ⅲ 正确:时间片轮转针对处于就绪态的进程进行排队轮转,必须依托就绪队列来维护各个进程的先后调度次序。
  • Ⅳ 错误:阻塞队列用于挂起等待外部事件(如 I/O 完成、信号量同步)的进程。时间片用完的进程并未发生阻塞,而是由执行态直接变为就绪态,插入就绪队列末尾。整个时间片轮转调度过程在就绪队列与处理机之间闭环运转,不使用进程阻塞队列。
  • 故正确组合为 Ⅰ、Ⅱ、Ⅲ。

正确答案:C


【真题 8】2022 年 408 第 25 题 · 抢占式优先级调度的调度时机判定与调度次数统计

题目
进程 \(P_0\)、\(P_1\)、\(P_2\)$ \text{和} $\(P_3\) 进入就绪队列的时刻、优先级(值越小优先权越高)及 CPU 执行时间如下表所示。

进程    进入就绪队列的时刻    优先级    CPU 执行时间
 P0             0 ms           15          100 ms
 P1            10 ms           20           60 ms
 P2            10 ms           10           20 ms
 P3            15 ms            6           10 ms
若系统采用基于优先权的抢占式进程调度算法,则从 \(0\text{ ms}\) 时刻开始调度,到 4 个进程都运行结束为止,发生进程调度的总次数为( )。
A. 4
B. 5
C. 6
D. 7

【解析】

  • 知识定位:抢占式优先级调度;调度发生时机(抢占点与进程正常完成点)。
  • 注意前提:“优先级数值越小,优先权越高”。
  • 调度过程与调度事件推导:
  • \(t = 0\text{ ms}\):
    就绪队列中仅有 \(P_0\)$ \text{到达。系统首次启动调度,调度} $\(P_0\) 占用 CPU。【第 1 次调度】
  • \(0 \sim 10\text{ ms}\):
    \(P_0\)$ \text{执行} $\(10\text{ ms}\)$ \text{,剩余运行时间为} $\(100 - 10 = 90\text{ ms}\)。
  • \(t = 10\text{ ms}\):
    \(P_1\)$ \text{(优先级 20)和} $\(P_2\)$ \text{(优先级 10)同时进入就绪队列。此时运行中的} $\(P_0\) 优先级为 15。
    比较优先级:\(P_2(10) > P_0(15) > P_1(20)\)。\(P_2\)$ \text{优先权高于当前运行的} $\(P_0\),发生抢占。
    系统剥夺 \(P_0\)$ \text{的 CPU 并放回就绪队列,调度} $\(P_2\) 占用 CPU。【第 2 次调度】
  • \(10 \sim 15\text{ ms}\):
    \(P_2\)$ \text{执行} $\(5\text{ ms}\)$ \text{,剩余运行时间为} $\(20 - 5 = 15\text{ ms}\)。
  • \(t = 15\text{ ms}\):
    \(P_3\)$ \text{(优先级 6)进入就绪队列。此时运行中的} $\(P_2\) 优先级为 10。
    比较优先级:\(P_3(6) > P_2(10)\)。\(P_3\)$ \text{优先权高于当前运行的} $\(P_2\),发生抢占。
    系统剥夺 \(P_2\)$ \text{的 CPU 并放回就绪队列,调度} $\(P_3\) 占用 CPU。【第 3 次调度】
  • \(15 \sim 25\text{ ms}\):
    \(P_3\)$ \text{运行} $\(10\text{ ms}\)$ \text{。在} $\(t = 25\text{ ms}\)$ \text{时,} $\(P_3\) 执行完毕并退出。
    此时就绪队列中有三个进程:\(P_2\)$ \text{(优先级 10,剩 15 ms)、} $\(P_0\)$ \text{(优先级 15,剩 90 ms)、} $\(P_1\)(优先级 20,剩 60 ms)。
    其中最高优先级者为 \(P_2\)$ \text{,系统调度} $\(P_2\) 占用 CPU。【第 4 次调度】
  • \(25 \sim 40\text{ ms}\):
    \(P_2\)$ \text{运行剩余的} $\(15\text{ ms}\)$ \text{。在} $\(t = 40\text{ ms}\)$ \text{时,} $\(P_2\) 执行完毕并退出。
    此时就绪队列中剩余进程:\(P_0\)$ \text{(优先级 15)、} $\(P_1\)(优先级 20)。
    最高优先级者为 \(P_0\)$ \text{,系统调度} $\(P_0\) 占用 CPU。【第 5 次调度】
  • \(40 \sim 130\text{ ms}\):
    \(P_0\)$ \text{运行剩余的} $\(90\text{ ms}\)$ \text{。在} $\(t = 130\text{ ms}\)$ \text{时,} $\(P_0\) 执行完毕并退出。
    此时就绪队列中仅剩 \(P_1\)(优先级 20)。
    系统调度 \(P_1\) 占用 CPU。【第 6 次调度】
  • \(130 \sim 190\text{ ms}\):
    \(P_1\)$ \text{运行} $\(60\text{ ms}\)$ \text{。在} $\(t = 190\text{ ms}\)$ \text{时,} $\(P_1\) 执行完毕,所有进程全部执行结束,不再发生调度。
  • 调度发生时刻汇总:
    共在 \(t = 0\text{ ms},\; 10\text{ ms},\; 15\text{ ms},\; 25\text{ ms},\; 40\text{ ms},\; 130\text{ ms}\) 六个时刻发生了进程调度,总调度次数为 6 次。

正确答案:C


【真题 9】2023 年 408 第 29 题 · 抢占式优先级调度的甘特图推导与平均周转时间

题目
进程 \(P_1\)、\(P_2\)$ \text{和} $\(P_3\) 进入就绪队列的时刻,优先值(越大优先权越高)以及 CPU 的执行时间如下表所示。

进程名    进入就绪队列的时刻    优先级    CPU 执行时间
  P1             0 ms            1           60 ms
  P2            20 ms           10           42 ms
  P3            30 ms          100           13 ms
系统采用基于优先权的抢占式 CPU 调度算法,从 \(0\text{ ms}\)$ \text{时刻开始进行调度,则} $\(P_1\)、\(P_2\)$ \text{和} $\(P_3\) 的平均周转时间为( )。
A. \(60\text{ ms}\)
B. \(61\text{ ms}\)
C. \(70\text{ ms}\)
D. \(71\text{ ms}\)

【解析】

  • 知识定位:抢占式优先级调度;甘特图时间推进;平均周转时间计算。
  • 注意审题:“优先值越大,优先权越高”。
  • 调度甘特图推导:
  • \(0 \sim 20\text{ ms}\):
    \(t = 0\text{ ms}\)$ \text{时仅} $\(P_1\)$ \text{到达,} $\(P_1\)$ \text{获得处理机开始运行。运行至} $\(t = 20\text{ ms}\)$ \text{时,消耗了} $\(20\text{ ms}\)$ \text{CPU 时间,还剩} $\(60 - 20 = 40\text{ ms}\)。
  • \(t = 20\text{ ms}\):
    \(P_2\)$ \text{到达,优先权为 10;当前运行的} $\(P_1\)$ \text{优先权为 1。由于} $\(10 > 1\),\(P_2\)$ \text{抢占 CPU,} $\(P_1\) 被迫暂停进入就绪队列。
  • \(20 \sim 30\text{ ms}\):
    \(P_2\)$ \text{获得 CPU 执行,运行了} $\(10\text{ ms}\)$ \text{,还剩} $\(42 - 10 = 32\text{ ms}\)。
  • \(t = 30\text{ ms}\):
    \(P_3\)$ \text{到达,优先权为 100;当前运行的} $\(P_2\)$ \text{优先权为 10。由于} $\(100 > 10\),\(P_3\)$ \text{抢占 CPU,} $\(P_2\) 被迫暂停进入就绪队列。
  • \(30 \sim 43\text{ ms}\):
    \(P_3\)$ \text{需要运行} $\(13\text{ ms}\)$ \text{。由于后续无更高优先级进程到达,} $\(P_3\)$ \text{连续执行至} $\(t = 30 + 13 = 43\text{ ms}\) 完成并退出。
    \(P_3\)$ \text{的完成时刻} $\(C_3 = 43\text{ ms}\)。
  • \(43 \sim 75\text{ ms}\):
    \(P_3\)$ \text{退出后,就绪队列中剩余} $\(P_2\)$ \text{(优先权 10,剩 32 ms)和} $\(P_1\)(优先权 1,剩 40 ms)。
    \(P_2\)$ \text{优先权高于} $\(P_1\)$ \text{,故系统调度} $\(P_2\)$ \text{恢复运行。} $\(P_2\)$ \text{运行} $\(32\text{ ms}\)$ \text{,于} $\(t = 43 + 32 = 75\text{ ms}\) 完成并退出。
    \(P_2\)$ \text{的完成时刻} $\(C_2 = 75\text{ ms}\)。
  • \(75 \sim 115\text{ ms}\):
    \(P_2\)$ \text{退出后,调度} $\(P_1\)$ \text{恢复运行。} $\(P_1\)$ \text{运行剩余的} $\(40\text{ ms}\)$ \text{,于} $\(t = 75 + 40 = 115\text{ ms}\) 完成并退出。
    \(P_1\)$ \text{的完成时刻} $\(C_1 = 115\text{ ms}\)。
  • 周转时间计算(周转时间 = 完成时刻 - 到达时刻):
  • \(P_1\)$ \text{的周转时间:} $\(T_1 = 115 - 0 = 115\text{ ms}\)
  • \(P_2\)$ \text{的周转时间:} $\(T_2 = 75 - 20 = 55\text{ ms}\)
  • \(P_3\)$ \text{的周转时间:} $\(T_3 = 43 - 30 = 13\text{ ms}\)
  • 平均周转时间: $\(T_{\text{avg}} = \frac{T_1 + T_2 + T_3}{3} = \frac{115 + 55 + 13}{3} = \frac{183}{3} = 61\text{ ms}\)$

正确答案:B


【真题 10】2024 年 408 第 30 题 · 时间片轮转调度的轮转周期与周转时间定量推算

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

【解析】

  • 知识定位:时间片轮转(RR)调度机制;多进程轮转周期分析;周转时间计算。
  • 推导与分析:
  • 初始队列状态:
    系统共有 10 个进程(设为 \(P_1, P_2, \dots, P_9, P\)$ \text{),初始时刻(} $\(t = 0\text{ ms}\)$ \text{)均处于就绪队列中,且进程} $\(P\) 排在队尾(即第 10 个位置)。
  • 关键条件挖掘:
    “队尾的进程 \(P\)$ \text{所需 CPU 时间最短,时间为} $\(25\text{ ms}\)”。
    由于时间片为 \(5\text{ ms}\)$ \text{,进程} $\(P\) 需要执行的轮次(时间片数)为: $$ \text{轮次} = \frac{25\text{ ms}}{5\text{ ms}} = 5 \text{次} $$ 而系统中其他 9 个进程的所需 CPU 时间均大于或等于 \(25\text{ ms}\)$ \text{,这意味着在进程} $\(P\) 执行结束(即完成第 5 个时间片)之前,系统中没有任何其他进程会提前执行完毕退出就绪队列。
  • 轮转周期与推进:
    就绪队列中的有效进程数在 \(P\) 完成前恒定为 10 个。
    每个完整的轮转周期耗时为: $\(T_{\text{cycle}} = 10 \times 5\text{ ms} = 50\text{ ms}\)$
    • 在第 1 个周期(\(0 \sim 50\text{ ms}\)$ \text{)内:前 9 个进程各运行} $\(5\text{ ms}\)$ \text{,随后} $\(P\)$ \text{运行其第 1 个时间片,于} $\(t = 50\text{ ms}\) 时结束第 1 轮。
    • 在第 2 个周期(\(50 \sim 100\text{ ms}\)$ \text{)内:前 9 个进程各运行} $\(5\text{ ms}\)$ \text{,随后} $\(P\)$ \text{运行其第 2 个时间片,于} $\(t = 100\text{ ms}\) 时结束第 2 轮。
    • 在第 3 个周期(\(100 \sim 150\text{ ms}\)$ \text{)内:前 9 个进程各运行} $\(5\text{ ms}\)$ \text{,随后} $\(P\)$ \text{运行其第 3 个时间片,于} $\(t = 150\text{ ms}\) 时结束第 3 轮。
    • 在第 4 个周期(\(150 \sim 200\text{ ms}\)$ \text{)内:前 9 个进程各运行} $\(5\text{ ms}\)$ \text{,随后} $\(P\)$ \text{运行其第 4 个时间片,于} $\(t = 200\text{ ms}\) 时结束第 4 轮。
    • 在第 5 个周期(\(200 \sim 250\text{ ms}\)$ \text{)内:前 9 个进程各运行} $\(5\text{ ms}\)$ \text{,随后} $\(P\)$ \text{运行其第 5 个时间片,于} $\(t = 250\text{ ms}\)$ \text{时正好累计执行满} $\(25\text{ ms}\),执行完毕退出。
  • 周转时间计算:
    进程 \(P\)$ \text{于} $\(t = 0\text{ ms}\)$ \text{处于就绪队列(到达),于} $\(t = 250\text{ ms}\) 完成。
    $\(T_{\text{turnaround}} = C_P - A_P = 250\text{ ms} - 0\text{ ms} = 250\text{ ms}\)$

正确答案:C


【真题 11】2025 年 408 第 25 题 · 就绪队列数据结构组织与优先权调度的时间复杂度

题目
在优先权调度中,采用单链表保存进程就绪队列,高优先级进程在队头。若就绪队列长度为 \(n\),则插入进程、选出进程的时间复杂度为( )。
A. \(O(1), O(1)\)
B. \(O(1), O(n)\)
C. \(O(n), O(1)\)
D. \(O(n), O(n)\)

【解析】

  • 知识定位:操作系统内核就绪队列的数据结构设计;插入排序与优先队列的时间复杂度。
  • 推导与分析:
  • 数据结构约束:系统采用单链表组织就绪队列,且队列维护了特定的有序状态——高优先级进程在队头,即单链表各节点按照优先级从高到低有序链接。
  • 插入进程操作:
    当一个新进程被创建或被唤醒进入就绪队列时,为了维持单链表“高优先级在队头、低优先级在队尾”的有序性,必须根据该新进程的优先级在链表中寻找正确的插入位置。由于单链表无法进行随机访问或二分查找,必须从头指针开始依次向后遍历比较每个节点的优先级。在平均和最坏情况下,遍历比较的节点数为 \(O(n)\)$ \text{。确定插入位置后的指针修改为} $\(O(1)\)$ \text{,故插入进程的总时间复杂度为 } $\(O(n)\)。
  • 选出进程操作:
    调度程序触发调度时,需要从就绪队列中选取优先级最高的进程投入运行。由于单链表已经按优先级严格有序排列,最高优先级的进程始终位于单链表的队头(第一个节点)。调度程序只需读取头结点的指针域并将该节点从单链表中移出(出队头),无需进行任何遍历操作,该操作的时间复杂度为 \(O(1)\)。
  • 综上所述,插入进程的时间复杂度为 \(O(n)\)$ \text{,选出进程的时间复杂度为} $\(O(1)\)。

正确答案:C


四、 综合考法拓展

1. 综合大题中调度甘特图的标准解题范式

在 408 综合大题或复杂计算题中,涉及处理机调度的题目建议采用标准“四步法”推导:

[事件到达点划分] ---> [抢占条件判断] ---> [标注上下文切换] ---> [建立时间矩阵回算]
  • 第一步:建立离散事件轴(Arrival Points)
    将题干中所有作业/进程的到达时刻(\(A_i\)$ \text{)列出,形成事件驱动的关键时间节点序列(如} $\(0, 10, 15, 20\dots\))。
  • 第二步:动态维护就绪队列与抢占判定
    到达某一时刻时,将新到达进程推入就绪队列。若为抢占式算法,对比“当前正在运行进程的当前属性值”与“新到达就绪进程的属性值”(如剩余执行时间或优先权),若新进程胜出,立即截断当前运行段,发生抢占。
  • 第三步:精细化处理系统切换开销(Context Switch Overhead)
    若题干明确给出“进程切换与调度开销为 \(\tau\)$ \text{”,则在每两个不同进程的执行区间之间必须插入一段长度为} $\(\tau\) 的不可用于进程计算的时间间隔。
  • 第四步:建立指标计算矩阵
    汇总每个进程的完成时刻 \(C_i\),依据公式矩阵回算: $$ \text{周转时间 } T_i = C_i

  • A_i, \quad \text{带权周转时间 } W_i = \frac{T_i}{T_{s,i}}, \quad \text{等待时间 } T_{w,i} = T_i

  • T_{s,i}

  • T_{\text{overhead}} $$


2. 动态优先级公式设计大题的建模方法与采分点

2016 年第 46 题代表了 408 命题的一个重要方向——系统机制设计与数学建模。针对防饥饿动态优先级设计的大题,其标准建构思路如下:

   Priority = BaseValue (基准偏好)
            + PenaltyTerm (CPU执行惩罚项: 正系数 * 运行时间)
            - AgingTerm   (就绪等待老化项: 正系数 * 等待时间)
  • 基准量(Base):静态初始值(如 nice、用户指定权值、作业类型固有权值)。
  • 惩罚项(Penalty):用于压制长时间霸占 CPU 的长作业。运行时间越长,该项使得优先数值朝“优先级降低”的方向变动。若“数值大代表优先级低”,则该项符号为正(\(+ k_1 \times \text{cpuTime}\));反之若“数值大代表优先级高”,该项符号为负。
  • 老化补偿项(Aging):用于提升长久未获调度的就绪进程。等待时间越长,该项使得优先数值朝“优先级提高”的方向变动。
  • 采分要点:
  • 必须包含题目要求的全部核心变量。
  • 权重因子(系数 \(k_1 > 0, k_2 > 0\))必须显式声明,用于调节两类时间在优先级决议中的相对重要性。
  • 必须对老化项(如 waitTime)的作用进行功能性陈述:“随等待时间增加促使优先级持续提升,使等待充分长的进程必然能获得调度,彻底消除饥饿”。

3. 处理机调度与相关模块的综合考查脉络

(1) 调度与进程同步互斥(优先级反转现象)

  • 现象描述:高优先级进程 \(P_H\)$ \text{等待低优先级进程} $\(P_L\)$ \text{占有的互斥共享资源,而中优先级进程} $\(P_M\)$ \text{(不需要该共享资源)由于优先级高于} $\(P_L\)$ \text{而抢占了} $\(P_L\)$ \text{的 CPU,导致} $\(P_L\)$ \text{无法运行并释放互斥资源,间接造成高优先级进程} $\(P_H\)$ \text{被中优先级进程} $\(P_M\) 长时间阻塞。
  • 解决机制:
  • 优先级继承协议(Priority Inheritance Protocol, PIP):当 \(P_H\)$ \text{因请求} $\(P_L\)$ \text{持有的互斥锁而被阻塞时,} $\(P_L\)$ \text{临时继承} $\(P_H\) 的高优先级,直到释放该锁为止。
  • 优先级天花板协议(Priority Ceiling Protocol, PCP):为每个互斥锁预先分配一个等于所有可能访问该锁的进程中最高优先级的“天花板优先级”。

(2) 调度与虚存缺页异常

  • 当运行进程访问的虚拟页面不在内存中时,硬件触发缺页异常(Page Fault)。
  • 当前进程被迫陷入内核,状态由执行态转变为阻塞态,进入等待 I/O 完成的阻塞队列。
  • 操作系统调度程序立即介入,从就绪队列中选出另一个就绪进程分配 CPU。
  • 当外存对换区的页面读取进入内存后,产生磁盘 I/O 完成中断,操作系统将原进程的状态由阻塞态唤醒为就绪态,重新进入就绪队列竞争 CPU。

五、 考点速记清单

1. 核心计算公式汇总

  • 周转时间:$$ \text{T = \text{完成时刻} - \text{到达时刻} = C - A} $$
  • 平均周转时间:\(T_{\text{avg}} = \frac{1}{n} \sum_{i=1}^n T_i\)
  • 带权周转时间:\(W = \frac{T}{T_s} = \frac{C - A}{T_s} \ge 1\)
  • 等待时间(无切换开销):$T_w = T

  • T_s = C

  • A

  • T_s$

  • 高响应比优先响应比:$$ \text{R_p = \frac{\text{等待时间} + \text{服务时间}}{\text{服务时间}} = 1 + \frac{\text{等待时间}}{\text{服务时间}}} $$

2. 调度算法关键特性对照速记

+----------------------+------------+------------+--------------------------------------------+
|       调度算法       |  抢占机制  | 是否饥饿? |                  核心考点                  |
+----------------------+------------+------------+--------------------------------------------+
| FCFS                 |   非抢占   |   无饥饿   | 护航效应,利长不利短                       |
| SJF / SPF            | 抢占或非抢 |   会饥饿   | 平均周转理论最小,需预估,长作业易饿死     |
| HRRN                 |   非抢占   |   无饥饿   | 动态折中,等待时间长响应比高,有效克服饥饿 |
| RR (时间片轮转)      |    抢占    |   无饥饿   | 时间片耗尽转入就绪态;q过大退化为 FCFS     |
| 优先级调度           | 抢占或非抢 | 静态会/动态否| 静态易饥饿;动态通过老化(Aging)消除饥饿   |
| 多级反馈队列 (MLFQ)  |    抢占    | 可通过老化免| 多级就绪队列,优先级高时间片小,新进放队首 |
+----------------------+------------+------------+--------------------------------------------+

3. 高频易错陷阱

  • 陷阱 1:时间片耗尽后的进程状态
    时间片用尽后,进程从执行态进入就绪态(重新排队),绝对不进入阻塞态。
  • 陷阱 2:优先权数值与优先级的高低对应
    切勿默认为“数值大代表优先级高”。做题前必须先读题目说明(如 2016#46 与 2022#25 规定数值小优先权高;2018#24 与 2023#29 规定数值大优先权高)。
  • 陷阱 3:周转时间中等待时间的界定
    若题目指出在 \(T\) 时刻前进程已有初始等待时间(如 2018#24),周转时间必须追溯至最原始的到达时刻(即包含初始等待时间)。
  • 陷阱 4:进程就绪队列的组织方式与开销
    按优先级降序组织的单链表,取出最高优先级(队头)为 \(O(1)\)$ \text{,新进程插入定位为} $\(O(n)\)$ \text{。若采用二叉堆,则插入与选出均为} $\(O(\log n)\)。

4. 极速解题推导口诀

调控层次看频率,高频短程低级调;
内核临界禁切换,普通临界可相让。
周转即是完减到,带权除以运行长;
先来利长防饥饿,短程最优长者饥。
响应比高兼长短,等待变大终得尝;
轮转关键在时钟,时间片尽落就绪。
反馈队列多层设,降级加倍老化强!