第二章：进程与线程管理
2.1 进程的基本概念
程序是静态的（存在磁盘上的代码），进程是动态的（程序的一次执行过程）。好比"菜谱"是程序，"照着菜谱做饭的过程"就是进程。
进程的组成（三要素）：
- PCB（进程控制块）：进程的唯一标识，包含PID、状态、程序计数器、CPU寄存器、内存指针等信息。OS通过PCB来管理和控制进程。
- 程序段：进程要执行的代码。
- 数据段：进程运行时使用的数据。
进程的特征：
- 动态性：进程有生命周期（创建→运行→终止），这是最基本的特征。
- 并发性：多个进程可同时存在于内存中并发执行。
- 独立性：进程是资源分配和调度的基本单位（早期）/独立运行的基本单位。
- 异步性：进程以不可预知的速度推进，OS要保证结果一致性。
💡 记忆技巧：PCB是进程存在的唯一标志——进程创建时创建PCB，进程终止时撤销PCB。没有PCB，OS就管不了这个"人"了。
📌 408考点提示：进程三要素（PCB+程序段+数据段）为选择题常考。进程和程序的对比经常以概念题出现。
2.2 进程的状态与转换
2.2.1 五状态模型（最常用）
| 状态 | 含义 | 是否在内存 | 是否占用CPU |
|---|---|---|---|
| 运行态 | 进程正在CPU上执行 | 是 | 是 |
| 就绪态 | 万事俱备，只欠CPU | 是 | 否 |
| 阻塞态（等待态） | 等待某事件（如I/O完成） | 是 | 否 |
| 创建态 | 进程正在被创建 | 是 | 否 |
| 终止态 | 进程正在被撤销 | 是 | 否 |
状态转换：
创建态 → 就绪态（创建完成）
就绪态 → 运行态（被调度程序选中）
运行态 → 就绪态（时间片用完/被抢占）
运行态 → 阻塞态（等待资源/I/O）
阻塞态 → 就绪态（等待的事件发生）
运行态 → 终止态（执行完毕/被强制结束）
⚠️ 易错点：
- 阻塞态不能直接回到运行态——必须先变成就绪态等调度。
- 运行态→阻塞态是进程主动的（自己申请资源），运行态→就绪态是被动的（时间片到/被抢占）。
2.2.2 七状态模型
在五状态基础上增加挂起：
- 就绪挂起：进程在辅存（磁盘），但具备运行条件。
- 阻塞挂起：进程在辅存，且等待事件。
挂起的原因：用户请求、OS内存不足、高优先级进程需要等。
2.3 进程控制块（PCB）
PCB是OS中最重要的数据结构，常驻内存。通常包含：
| 信息类别 | 具体内容 |
|---|---|
| 进程标识 | PID（唯一）、PPID（父进程ID） |
| 处理机状态 | PC、PSW、通用寄存器——用于断点恢复 |
| 进程调度信息 | 状态、优先级、调度算法参数、等待时间 |
| 内存管理信息 | 页表/段表指针、内存界限 |
| I/O状态信息 | 已分配设备列表、打开文件列表 |
PCB的组织方式：线性表（简单但查找慢）、链接表（常用，按状态分成就绪队列、阻塞队列等）、索引表。
2.4 进程控制
2.4.1 进程创建
触发事件：用户登录、作业调度、服务请求（如打印请求）、应用进程派生。
创建过程：分配PID → 分配PCB → 分配资源（内存等）→ 初始化PCB → 插入就绪队列。
注意：在Unix/Linux中，fork()创建一个子进程——子进程复制父进程的PCB（包括代码区和数据区的副本），但有自己的PID。
2.4.2 进程终止
触发事件：正常结束、异常结束（如除零错）、外界干预（如kill命令）。
终止过程：根据PID找到PCB → 回收资源 → 撤销PCB。
2.4.3 进程阻塞与唤醒
- 阻塞：进程等待某资源/事件 → 保存现场 → PCB状态改为阻塞 → 插入阻塞队列 → 转调度。
- 唤醒：发生等待的事件 → 从阻塞队列移除PCB → 状态改就绪 → 插入就绪队列。
阻塞和唤醒必须成对使用，且由不同的进程完成。
2.5 进程通信
进程通信是指进程之间的信息交换。低级通信（PV操作、信号量）解决同步互斥，高级通信交换大量数据。
2.5.1 共享存储
- 多个进程共享一个存储区。
- 分为基于数据结构的共享（低级，如共享一个变量）和基于存储区的共享（高级，如共享内存段）。
- 需要同步互斥机制配合。
2.5.2 消息传递
- 进程通过发送和接收消息来通信，不需要共享空间。
- 直接通信：send(P, message) / receive(Q, message)——显式指定对方。
- 间接通信：通过信箱（mailbox），send(mailbox, message) / receive(mailbox, message)。
2.5.3 管道通信
- 管道是连接读写进程的一个共享文件（pipe）。
- 半双工：数据单向流动（一个管道一个方向）。互斥：一次只有一个进程访问。同步：写满阻塞/读空阻塞。
- 有名管道（FIFO）：可用于任意进程通信。无名管道：只能用于父子进程。
📌 408考点提示：三种通信方式的区分是选择题常见考点。注意管道通信的特点——半双工、互斥、同步。
2.6 线程
2.6.1 线程的基本概念
线程是程序执行流的最小单元，是调度的基本单位（而进程是资源分配的基本单位）。
把一个进程比作一个公司，线程就是公司的员工。公司（进程）拥有办公室、资金（资源），员工（线程）利用这些资源干活，且同一公司的员工共享办公室。
线程的组成：线程ID、PC、寄存器组、栈——没有独立的地址空间（线程共享进程的地址空间）。
引入线程的好处：
- 创建/撤销/切换线程的开销远小于进程。
- 同一进程内的线程间通信更简单（共享内存）。
- 适合多核CPU的并行计算。
2.6.2 多线程模型
| 模型 | 关系 | 优点 | 缺点 | 代表 |
|---|---|---|---|---|
| 一对一 | 1个用户线程→1个内核线程 | 多核并行、一个阻塞不影响其他 | 线程切换开销大 | Linux、Windows |
| 多对一 | 多个用户线程→1个内核线程 | 切换快、效率高 | 一个阻塞全阻塞、不能并行 | 早期系统 |
| 多对多 | 多个用户线程→多个内核线程 | 综合两者优点 | 实现复杂 | Solaris |
📌 408考点提示：三种模型的对比是选择题常见内容，注意区分用户级线程和内核级线程的管理方式。
2.7 处理机调度
2.7.1 调度层次
| 调度层次 | 别名 | 作用范围 | 执行频率 | 调度对象 |
|---|---|---|---|---|
| 高级调度 | 作业调度 | 外存→内存（多个作业中选一个） | 低（秒/分钟级） | 作业 |
| 中级调度 | 内存调度 | 内存→外存（换入换出） | 中等 | 进程 |
| 低级调度 | 进程调度 | CPU分配 | 高（毫秒级） | 进程（线程） |
💡 记忆技巧：三个调度层次从"大周期→小周期"——高级调度（作业进内存）→中级调度（内存平衡）→低级调度（CPU分配）。
2.7.2 调度算法的评价指标
| 指标 | 公式 | 含义 |
|---|---|---|
| CPU利用率 | CPU忙时间 / 总时间 | CPU不空闲的比例 |
| 系统吞吐量 | 完成作业数 / 单位时间 | 系统处理能力 |
| 周转时间 | 完成时间 - 提交时间 | 作业从提交到完成的总时间 |
| 带权周转时间 | 周转时间 / 实际运行时间 | ≥1，越小越好 |
| 等待时间 | 在就绪队列中等待的总时间 | 不包括I/O等待 |
| 响应时间 | 首次响应时间 - 提交时间 | 交互式系统的关键指标 |
📌 408考点提示：周转时间、带权周转时间的计算是每年必考。一定要会画甘特图（Gantt chart）分析各调度算法下的执行时间线。
2.8 典型调度算法
2.8.1 FCFS（先来先服务）
- 按到达顺序排队，非抢占。
- 优点：公平、简单。
- 缺点：对短作业不友好（长作业后面的短作业等很久），平均周转时间长。
2.8.2 SJF/SPF（短作业优先/短进程优先）
- 选择预计运行时间最短的作业/进程。
- SJF（作业调度） / SPF（进程调度）。
- 分为非抢占式和抢占式（SRTN——最短剩余时间优先）。
- 优点：平均周转时间最小（理论最优）。
- 缺点：对长作业不友好（可能饿死），且难以准确预估运行时间。
2.8.3 优先级调度算法
- 选择优先级最高的进程运行。
- 静态优先级（创建时确定）vs 动态优先级（可调整）。
- 非抢占式（运行完再切）vs 抢占式（高优先级立刻抢占）。
- 可能导致优先级反转（低优先级进程持有高优先级所需资源）——可通过优先级继承解决。
2.8.4 高响应比优先（HRRN）
响应比 = （等待时间 + 服务时间）/ 服务时间 = 1 + 等待时间/服务时间
- 每次调度时计算所有就绪进程的响应比，选最高的。
- 兼顾了FCFS（等待时间长则响应比高）和SJF（服务时间短则响应比高）。
- 非抢占式算法。
💡 记忆技巧：HRRN ≈ FCFS + SJF的"取长补短"，等待时间长了会"自动升值"。
2.8.5 时间片轮转（RR）
- 每个进程分配一个固定时间片（通常10-100ms），时间片用完就切换。
- 时间片大小很关键：太大→退化为FCFS，太小→切换开销过大。
- 优点：响应快，适合交互式系统。
- 缺点：频繁切换有开销，对I/O密集型不友好。
2.8.6 多级反馈队列（MFQ）
综合了RR和优先级调度的优点：
- 设置多个就绪队列，优先级从高到低。
- 高优先级队列时间片短，低优先级队列时间片长。
- 新进程先进入最高优先级队列，用完时间片降级。
- 高优先级队列非空时，不运行低优先级队列（抢占）。
典型应用：Unix的调度算法、Windows的调度。
📌 408考点提示：多级反馈队列是调度算法中最复杂的，综合题常考。注意新进程先进入最高优先级队列这一特点。
示例题
示例1: 已知四个进程的到达时间和运行时间如下表，采用FCFS和SJF（非抢占），计算各项指标。
| 进程 | 到达时间 | 运行时间 |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
FCFS调度： 执行顺序：P1(0-7) → P2(7-11) → P3(11-12) → P4(12-16)
| 进程 | 完成时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|
| P1 | 7 | 7-0=7 | 7/7=1 |
| P2 | 11 | 11-2=9 | 9/4=2.25 |
| P3 | 12 | 12-4=8 | 8/1=8 |
| P4 | 16 | 16-5=11 | 11/4=2.75 |
平均周转时间 = (7+9+8+11)/4 = 8.75 平均带权周转时间 = (1+2.25+8+2.75)/4 = 3.5
SJF（非抢占）调度： 执行顺序：P1(0-7) → P3(7-8) → P2(8-12) → P4(12-16) （在P1完成后，就绪队列中有P2(运行时间4)、P3(运行时间1)、P4(运行时间4→此时P4还未到达，实际就绪队列中只有P2和P3)，选最短的P3）
| 进程 | 完成时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|
| P1 | 7 | 7-0=7 | 7/7=1 |
| P3 | 8 | 8-4=4 | 4/1=4 |
| P2 | 12 | 12-2=10 | 10/4=2.5 |
| P4 | 16 | 16-5=11 | 11/4=2.75 |
平均周转时间 = (7+4+10+11)/4 = 8 平均带权周转时间 = (1+4+2.5+2.75)/4 = 2.5625
示例2: 采用时间片轮转（RR）算法，时间片q=2，对上述进程计算。
执行过程：
- 0-2: P1运行
- 2-4: P2(到达2)开始运行，P1在就绪队列末尾
- 4-6: P3(到达4)开始运行，P2在就绪队列末尾，P1还在
- 6-7: P1继续运行1个单位（只剩1个单位）
- 7-9: P4(到达5)运行，就绪队列中P2→P3→P4...
- 由于过程较长，此处简化：最终完成时间依次为P1=7, P3=8, P2=13, P4=14
周转时间分别为：P1=7, P2=11, P3=4, P4=9 平均周转时间 = (7+11+4+9)/4 = 7.75
示例3: 高响应比优先调度。 在示例1数据中，T=7时刻（P1结束时）：
- P2：等待时间=5，响应比=1+5/4=2.25
- P3：等待时间=3，响应比=1+3/1=4 ← 最大，选P3
- P4：等待时间=2，响应比=1+2/4=1.5
P3结束后T=8时：
- P2：等待时间=6，响应比=1+6/4=2.5
- P4：等待时间=3，响应比=1+3/4=1.75 选P2。
本章小结
进程和线程是操作系统的核心概念。需要重点掌握：五（七）状态模型的转换、PCB的作用、三种进程通信方式的对比、线程模型的优缺点、以及最重要的——六大调度算法的计算（画甘特图算周转时间）。调度算法的计算题在408中出现的频率极高，务必熟练掌握。