计算机 408 · 操作系统

第 2 章「进程与线程」学习笔记

[!NOTE]
本章主线是：程序如何变成进程 → 多个进程如何轮流使用 CPU → 并发访问共享资源如何保持正确 → 为什么会死锁以及如何处理。
建议先读“白话解释”，再看术语、公式和代码。每次学习结束后完成文末自测。

快速导航

• 0. 全章地图
• 1. 进程：正在运行的程序
• 2. 线程：进程内部的执行线
• 3. CPU 调度
• 4. 同步与互斥
• 5. 死锁
• 6. 高频易错点
• 7. 分阶段学习法
• 8. 轻量自测
• 9. 记忆卡片

学习进度

• 能区分程序、进程、线程和 PCB
• 能画出五状态转换图，解释阻塞与唤醒
• 能计算周转时间、带权周转时间、响应比
• 能写出生产者-消费者问题的信号量顺序
• 能说出死锁四个必要条件，并判断安全状态

0. 全章地图

程序（静态代码）
      │ 装入内存并获得运行现场
      ▼
进程（资源分配的基本单位） ──┐
      │                       │ 同一进程内拆分执行流
      └──── CPU 调度 ────────► 线程（调度的基本单位）
                                │
                 共享数据 ─────┴─────► 同步 / 互斥
                                             │
                                  资源互相等待？
                                             ▼
                                      死锁预防与避免

1. 进程：正在运行的程序

1.1 程序、进程、作业到底有什么区别？

把“程序”想成菜谱，把“进程”想成正在厨房里照着菜谱做菜的一桌订单：

概念	本质	是否动态	例子
程序	指令和数据的集合	否	chrome.exe 文件
进程	程序的一次执行及其运行环境	是	已打开的 Chrome 实例
作业	用户提交给系统的任务	是	编译一个项目的完整任务

同一个程序可以同时对应多个进程；进程结束后，程序文件仍然存在。

1.2 进程的组成：程序段 + 数据段 + PCB

PCB（进程控制块）是进程存在的唯一标志。系统通过 PCB 管理进程，而不是只看代码文件。

组成	保存什么	直观比喻
程序段	CPU 要执行的指令	菜谱
数据段	全局变量、常量、堆等	食材
PCB	状态、PID、寄存器、调度信息、资源清单	订单卡和厨房进度表

进程映像通常还包括栈、堆、共享库等。切换进程时，真正被保存和恢复的是 PCB 中的现场信息。

1.3 五状态及转换

记住两个容易混淆的方向：

• 阻塞是主动的：运行中的进程主动申请 I/O 或等待条件。
• 唤醒是被动的：等待的事件发生后，由系统或其他进程把它放回就绪队列。

1.4 进程控制

创建、终止、阻塞、唤醒、切换等操作由原语完成。原语具有原子性，执行过程中不能被中断，避免 PCB 只改了一半就被其他进程看到。

典型创建过程：申请空白 PCB → 分配资源 → 初始化 PCB → 插入就绪队列。终止过程反向回收资源，唤醒等待父进程的相关进程。

1.5 进程通信（IPC）

方式	数据如何传递	优点	需要注意
共享存储	多个进程映射同一片内存	快	必须配合同步机制
消息传递	send/receive 发送消息	易隔离、适合分布式	有复制和系统调用开销
管道	内核缓冲区中的字节流	使用简单	通常具有方向性和容量限制
信号	发送短小事件通知	及时	只能表达少量信息

2. 线程：进程内部的执行线

线程是 CPU 调度和执行的基本单位；进程是资源分配的基本单位。一个进程可含多个线程。

2.1 线程共享什么？独有什么？

共享	独有
代码段、数据段、打开的文件、信号处理方式	线程 ID、程序计数器、寄存器、栈、状态

生活化理解：进程像一个工作室，线程像工作室里的多个员工；员工共用设备和材料，但各自保留手上的步骤和工作台。

2.2 线程实现模型

模型	映射	优点	缺点
多对一	多用户线程 → 一个内核线程	切换快	一个线程阻塞，整个进程阻塞；不能利用多核
一对一	一个用户线程 → 一个内核线程	可并行、阻塞影响小	内核线程多，开销大
多对多	多用户线程 → 多个内核线程	灵活平衡	实现复杂

3. CPU 调度

3.1 调度、切换不是一回事

• 调度：决定“下一个让谁运行”，是策略和决策。
• 切换：保存旧进程现场、恢复新进程现场，是执行动作。

调度发生在进程进入就绪队列、运行进程阻塞或时间片用完等时机。上下文切换本身不产生用户程序工作，过于频繁会降低有效利用率。

3.2 三级调度

层次	作用	发生频率
高级调度（作业调度）	外存作业 → 内存进程	低
中级调度（内存调度）	暂时换出/换入进程，控制驻留数	中
低级调度（进程调度）	就绪队列 → CPU	高

3.3 评价指标与公式

指标	公式/含义
CPU 利用率	CPU 忙碌时间 / 总时间
吞吐量	单位时间完成的作业数
周转时间	完成时间 - 到达时间
带权周转时间	周转时间 / 实际运行时间
等待时间	在就绪队列中等待 CPU 的总时间
响应时间	从提交到第一次获得 CPU 的时间

3.4 常考调度算法

算法	规则	优点	风险/特点
FCFS	先到先服务	简单、公平	短作业可能被长作业拖慢
SJF/SPF	估计运行时间最短优先	平均等待时间短	需要估计，长作业可能饥饿
HRRN	响应比最高优先	兼顾等待与运行时间	非抢占，需动态计算
优先级	优先级最高先运行	可表达任务重要性	低优先级可能饥饿；可老化
时间片轮转 RR	每个进程运行一个时间片后排队	交互响应好	时间片过小切换开销大
多级反馈队列	多队列 + 动态降级/升级	兼顾响应和吞吐	参数多、实现复杂

高响应比优先公式：

[
R=\frac{等待时间+估计运行时间}{估计运行时间}=1+\frac{等待时间}{估计运行时间}
]

做调度计算题的固定顺序：画时间轴 → 写每个进程完成时间 → 计算周转/等待/响应 → 求平均值。先确认题目是抢占式还是非抢占式。

4. 同步与互斥

4.1 临界区

访问共享变量、缓冲区或设备的代码称为临界区。一个进程的完整结构是：

进入区 → 临界区 → 退出区 → 剩余区

临界区解决方案必须满足：空闲让进、忙则等待、有限等待、让权等待。目标不是让所有进程同时进入，而是保证共享数据的一致性。

4.2 互斥工具

工具	核心思想	适合场景
软件算法（如 Peterson）	共享变量表示意愿和轮次	理论题，依赖严格内存模型
硬件指令（TestAndSet/Swap）	一条不可分割指令完成检查和上锁	实现自旋锁
互斥锁	lock/unlock	临界区较短的通用场景
信号量	对资源数量进行计数	互斥、同步、资源管理
管程	把共享数据和操作封装起来	高级同步抽象

4.3 信号量：P（wait）与 V（signal）

记录型信号量通常包含 value 和等待队列：

wait(S): S.value--; 若 S.value < 0，则阻塞并排队
signal(S): S.value++; 若 S.value <= 0，则唤醒一个等待进程

• 互斥信号量初值通常为 1。
• 计数信号量初值等于可用资源数。
• P/V 操作必须写在正确位置：先申请资源，再进入临界区；使用完先退出临界区，再释放资源。

生产者-消费者的经典顺序：

empty = n, full = 0, mutex = 1
生产者：P(empty) → P(mutex) → 放入 → V(mutex) → V(full)
消费者：P(full)  → P(mutex) → 取出 → V(mutex) → V(empty)

把 P(mutex) 放在 P(empty) 前可能造成死锁：生产者拿着互斥锁却等不到空槽，消费者也拿不到锁取走数据。

4.4 经典同步问题

• 读者-写者：多个读者可并发读；写者必须互斥访问。题目常追问“读者优先”是否会导致写者饥饿。
• 哲学家进餐：每人先拿左筷子再拿右筷子会形成循环等待；可规定资源编号顺序、限制同时就餐人数或设置服务员。
• 管程：条件变量常用 wait / signal；管程一次只允许一个进程进入，互斥由管程自动保证。

5. 死锁

5.1 现象与四个必要条件

死锁是多个进程因互相等待资源而永久阻塞。必须同时满足：

1. 互斥：资源一次只能给一个进程。
2. 不可剥夺：资源只能由持有者主动释放。
3. 请求并保持：已持有资源，同时继续请求其他资源。
4. 循环等待：存在进程-资源的环形等待链。

饥饿是某进程长期得不到资源但系统仍在推进；死锁则是一组进程都无法推进。两者不要混淆。

5.2 处理策略

策略	做法	代价
预防	破坏四个必要条件之一	资源利用率或并发度下降
避免	每次分配前判断是否仍处于安全状态	需要最大需求等先验信息
检测与解除	允许死锁发生，定期检测后恢复	处理成本高，可能损失进程工作

5.3 银行家算法的思路

安全状态意味着：存在一个进程完成顺序，使每个进程都能用“当前可用资源 + 前面完成进程释放的资源”满足其剩余需求。计算时：

Need = Max - Allocation
Work = Available
反复寻找 Need_i <= Work 的进程 i
完成后 Work += Allocation_i
若所有进程都能完成 → 安全；否则 → 不安全

不安全状态不等于已经死锁，但系统不应在不安全状态继续分配。

5.4 死锁解除

• 剥夺资源：从某些进程拿回资源并重新分配。
• 撤销进程：一次撤销一个或多个进程。
• 回滚：恢复到安全检查点重新执行。

选择牺牲者时会综合考虑进程优先级、已运行时间、已占资源数量、回滚代价等。

6. 高频易错点

易错点	正确判断
进程和程序一样	程序是静态文件，进程是一次执行活动
PCB 只是进程的一部分信息	PCB 是系统识别和管理进程的唯一标志
阻塞后直接变运行	阻塞事件完成后先进入就绪队列，仍需调度
调度等于切换	调度是决策，切换是现场保存/恢复
P/V 只是普通函数	它们必须具有原子性
信号量初值都为 1	互斥量常为 1，资源计数应按资源数设置
不安全状态就是死锁	不安全只表示未来可能无法找到安全序列
饥饿就是死锁	饥饿可通过调度继续缓解，死锁中的进程集合无法推进

7. 分阶段学习法

第 1 遍：建立图景（约 40 分钟）

只回答：进程是什么、线程为什么出现、CPU 怎么选人、为什么需要同步、死锁怎样产生。

第 2 遍：掌握题型（约 60 分钟）

手算一题调度时间轴、一题生产者消费者、一题银行家算法。每题都写“状态/资源/队列”的变化。

第 3 遍：脱稿复述（约 20 分钟）

不看笔记画出五状态图、信号量顺序和死锁四条件，再检查遗漏。

8. 轻量自测

题 1

为什么阻塞进程被 I/O 唤醒后先进入就绪态，而不是直接运行？

题 2

有 3 个空缓冲区时，生产者-消费者模型中 empty、full、mutex 的初值分别是什么？

题 3

某进程到达时间为 2，完成时间为 10，实际运行时间为 4。周转时间和带权周转时间是多少？

题 4

银行家算法中，Need_i <= Work 的进程完成后为什么要执行 Work += Allocation_i？

展开答案

1. CPU 仍可能被其他就绪进程占用，唤醒只表示“具备运行条件”，不代表获得 CPU。
2. empty=3、full=0、mutex=1。
3. 周转时间 10-2=8；带权周转时间 8/4=2。
4. 进程完成会释放它已占有的资源，这些资源成为后续进程可用的 Work。

9. 记忆卡片

进程 = 程序段 + 数据段 + PCB
进程是资源分配单位，线程是调度执行单位
五状态：创建 → 就绪 → 运行 → 阻塞/终止
周转 = 完成 - 到达；带权周转 = 周转 / 运行
临界区四原则：空闲让进、忙则等待、有限等待、让权等待
死锁四条件：互斥、不可剥夺、请求并保持、循环等待
银行家：先算 Need，再找安全序列

复习日志

日期	学习内容	能否脱稿讲解	仍然困惑的点

下一步：完成日志后，回到本章对照例题，优先练习调度、信号量和银行家算法。