OS-1/2 进程、线程与 CPU 调度

这一部分为什么存在？

单道程序时代，程序独占整机：一旦做 I/O，CPU 就空转。为了提高 CPU 利用率，要让多个程序并发驻留内存、交替使用 CPU。但并发带来一个根本困难：程序是静态的代码，无法描述“跑到哪了、等什么资源、占用多少内存”这些动态信息。

于是 OS 做了两层抽象：

1. 进程：为“正在运行的程序”建立一个身份档案（PCB），使其成为资源分配的基本单位——没有进程，OS 无法回答“这块内存/这个文件是谁的”；
2. 线程：进程切换要换地址空间、刷 TLB，开销太大，而同一任务内部的并行（如浏览器一个标签页内同时渲染、下载、响应输入）不需要独立资源 → 把调度执行的单位再切小，让同一进程内的多条执行流共享资源。

紧接着的问题是：多个就绪进程/线程抢一个 CPU，谁先跑、跑多久——这就是调度。调度的目标是多维且互相冲突的：CPU 利用率、吞吐量、周转时间、响应时间、公平性，调度算法的历史就是在这些目标间不断权衡的历史。

没有这套机制会怎样：CPU 利用率低（独占 + I/O 空等），交互系统无从谈起（一个长任务卡死全机），多核与多任务应用（浏览器、服务器）无法实现。

flowchart TD
    A["程序并发失去封闭性<br/>结果不可再现"] --> B["引入进程<br/>= 程序 + 数据 + PCB"]
    B --> C["PCB：进程存在的唯一标志<br/>常驻内存内核区"]
    B --> D["进程状态转换<br/>就绪 / 运行 / 阻塞"]
    B --> E["进程切换开销大<br/>换地址空间 + 更新页表基址"]
    E --> F["引入线程<br/>= CPU 调度的基本单位"]
    D --> G["多个就绪者抢 CPU<br/>→ 调度问题"]
    F --> G
    G --> H["调度算法演进<br/>FCFS → SJF → HRRN → 优先级 → RR → 多级反馈队列"]

核心概念：

1. 状态转换的驱动事件（选择题最高频）

两个常见误判：① “时间片用完变阻塞”——错，是变就绪（2017-27 B 项陷阱）；② 时钟中断本身不改状态，只是修改剩余时间片，时间片耗尽才引发调度（2017-27 C 项正确）。可能引起调度程序执行的事件：中断处理结束、进程阻塞、进程结束、时间片用完——全部（2021-27）。

2. 为什么有了进程还要线程

进程切换 = 换执行现场 + 换地址空间（PDBR 更新、TLB 失效），代价大。线程把“资源所有权”和“执行流”解耦：资源归进程，执行归线程。收益：同进程线程切换不换地址空间（快）、共享数据无需 IPC、多核上可真正并行。代价：共享带来互斥需求（直接接 OS-3，2016-30、2017-46 的线程互斥题正源于此）。

3. 调度算法的演进链（每种都在修上一种的病）

计算模板（来源：复习资料 P3 §三，统一算例 P1(0,7)、P2(2,4)、P3(4,1)、P4(5,4)）：先画甘特图，再算周转/带权/等待。SRTN 的易错点：抢占比较的是剩余时间，且每个“新到达时刻”都要重新比较。RR 的易错点：新到进程与被抢占进程谁排前（新到先排，被抢占回队尾，2024-30）。

4. 真题演示范例

• 2019-27（二级反馈队列）：Q1 轮转 q=10ms、Q2 短进程优先，P1(30ms)、P2(20ms)：P1 跑 10→降 Q2；P2 跑 10→降 Q2；Q2 中 P2 短先跑完；P1 再补 20ms。P1 等 20、P2 等 10，平均等待 15ms。
• 2023-28（抢占优先级）：P1(0,60,1)、P2(20,42,10)、P3(30,13,100)，P3 抢 P2 抢 P1 → 周转 13、55、115，平均 61ms。
• 2024-30（RR，q=5ms，10 进程，队尾 P 需 25ms）：每轮 P 等其余 9 个 × 5ms = 45ms，自身跑 5ms，5 轮 → 周转 250ms。

进程 vs 线程（本模块第一易混对）：为什么易混——都是“执行单位”，都有状态转换。本质区别——进程是资源分配的基本单位（无论系统是否支持线程，2012-31 A 正确），线程是 CPU 调度的基本单位；进程间地址空间独立，线程间共享进程资源但各自有栈。判别线索：题目问“谁拥有资源/地址空间”→ 进程；问“切换快/共享方便/调度单位”→ 线程；问“栈、栈指针、寄存器”→ 线程私有（2011-25、2024-28）。

用户级线程 vs 内核级线程：为什么易混——名字都带“线程”。本质区别——管理表（TCB）在内核还是用户态线程库。判别线索：“切换不需内核支持/效率高”→ 用户级；“一个线程阻塞整个进程阻塞”→ 用户级的缺陷；“可被 OS 单独调度到多核”→ 内核级（2019-23）。

调度算法的公平 vs 效率谱系：FCFS、RR 不饥饿但效率一般；SJF/SRTN 效率最优但饥饿；HRRN、动态优先级、多级反馈队列是“效率向公平妥协”的三种修补（2014-23：不可能饥饿的是 RR；2011-23：短任务优先且不饥饿的是 HRRN）。

形态一：状态转换与调度时机（选择题高频）：2015-25、2017-27（时间片用完→就绪不是阻塞）、2019-24、2021-27、2022-28、2023-27；分时系统实现 RR 需要 PCB + 时钟中断处理程序 + 就绪队列（不需要阻塞队列，2021-25）。

形态二：进程/线程概念辨析：2011-25、2012-31、2019-23、2024-28；PCB 内核区驻留（2025-46）；PDBR 存物理地址、进程切换变、线程切换不变（2018-44）。

形态三：调度算法计算（选择 + 大题）：给定到达/运行时间表，画甘特图算周转/带权/等待——2009-24、2011-23（HRRN）、2017-23（t=2 时 FCFS 选 J1、SJF 选 J3）、2018-24（含切换开销 1μs 的优先级调度）、2019-27（二级反馈队列 15ms）、2022-25（抢占优先级调度总次数）、2023-28（61ms）、2024-30（RR 250ms）；大题 2012-29（计算-I/O 交错的多道批处理 260ms）、2016-45（设计动态优先数避免饥饿，waitTime 的作用）。

做题触发词：看到“时间片用完”→ 就绪；看到“等待 I/O、wait()”→ 阻塞；看到“平均周转/带权周转”→ 立即画甘特图；看到“抢占式 + 优先级/剩余时间”→ 每个到达时刻重新比较；看到“饥饿”→ 想 HRRN 或老化。

来源：真题markdown/2009-2024统考真题.md、2025 年真题 md；复习资料 P3 §二、§三。

• 向前依赖：OS-0 中断与内核态（时钟中断驱动 RR、系统调用触发状态转换；PCB 驻留内核区）。
• 向后引出：
  • 并发执行的线程共享数据 → 竞争条件 → OS-3 同步互斥（2016-30、2017-46 直接衔接）；
  • 互相等待 → OS-4 死锁（死锁的进程处于阻塞态）；
  • 进程是资源分配单位 → 其地址空间由 OS-5/6 内存管理提供；进程切换换 PDBR → X-1 / X-5（TLB 失效代价）；
  • 进程等 I/O 时阻塞 → I/O 完成后中断唤醒 → OS-8 / X-2；
  • 就绪队列、阻塞队列本质是数据结构中的队列，多级页表/目录用树 —— 数据结构在 OS 中的应用（X-8）。

1. 为什么程序并发执行会失去封闭性？OS 用什么抽象解决？（进程 = 程序 + 数据 + PCB）
2. PCB 里记什么？为什么它常驻内存内核区？
3. 三态转换各有几个方向？哪两个方向不存在？（阻塞↛运行、就绪↛阻塞）
4. 时间片用完和等 I/O 分别把进程送去哪个状态？
5. 进程切换开销大在哪？（换现场 + 换地址空间/PDBR + TLB 失效）
6. 于是引入了什么？线程之间共享什么、私有什么？（共享地址空间/打开文件；私有栈/寄存器）
7. 用户级和内核级线程的根本差别？（TCB 在哪、谁来调度、阻塞影响范围）
8. 多个就绪进程抢 CPU，评价调度好坏有哪些指标？
9. FCFS 的病？SJF 怎么修、又引入什么病？（护航；饥饿）
10. 哪两种方案能治饥饿？原理各是什么？（HRRN 等待升权；优先级老化）
11. RR 的时间片为什么不能太大太小？多级反馈队列如何综合各家长处？
12. 拿到调度计算题的标准动作是什么？（画甘特图 → 周转/带权/等待三列）
13. 进程/线程的并发共享下一步引出什么？（同步互斥 → 死锁）