第2章 进程与线程
第2章 进程与线程¶
操作系统的核心，每年必考的重点。其中进程的概念、进程调度、信号量机制实现同步互斥、死锁是重中之重。⚠️ 本章极易出综合题，尤其是用信号量实现进程同步、调度算法分析、死锁问题。
b_49_10【知识树】第2章骨架¶
- 进程与线程
- 进程：概念与特征、组成（PCB/程序段/数据段）、内存映像、五种状态、进程控制（创建/终止/阻塞/唤醒）
- 进程通信：共享存储、消息传递、管道、信号
- 线程：与进程的区别、三种实现方式、多线程模型
- CPU 调度
- 三级调度、调度时机与方式、闲逛进程
- 调度算法：FCFS / SJF / 优先级 / 高响应比 / 时间片轮转 / 多级反馈队列
- 上下文切换
- 同步与互斥
- 临界区、四条准则
- 软件方法、硬件方法、信号量、管程
- 经典问题：生产者-消费者、读者-写者、哲学家进餐
- 死锁
- 必要条件、处理策略
- 预防、避免（银行家算法）、检测与解除
b_49_1；PDF 第 49 页 · b_49_32.1 进程与线程简介¶
为什么要引入进程？¶
因为并发性破坏了程序原本的封闭性，使执行过程呈现间断性，并可能导致结果不可再现。
引入进程是为了有效描述和控制程序的并发行为，支撑操作系统的两大基本特性：并发性与共享性。
⚠️ PCB 是进程存在的唯一标志 —— 创建进程的本质是创建其 PCB，撤销进程即释放该 PCB 及相关资源。 进程实体（进程映像）= 程序段 + 相关数据段 + PCB。
b_50_2；PDF 第 50 页 · b_50_3进程的正式定义是什么？¶
"进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。"
⚠️ 这里的"系统资源"不仅包括内存空间、I/O 设备等硬件资源，也包括 CPU 的使用权（通过时间片分配实现）。
💡 推论：正因为它是资源分配与调度的基本单位，它必然不是静态的程序，而是一个动态的、有生命周期的过程性实体。
b_50_8进程的四个特征？哪个最根本？¶
- 动态性：⚠️ 动态性是进程最根本的特征 —— 有创建、就绪、运行、阻塞、终止的生命周期
- 并发性：多个进程同时驻留内存并交替或并行执行；⚠️ 引入进程的根本目的就是支持并发
- 独立性：能独立运行、独立获取资源、作为调度基本单位；⚠️ 任何未建立 PCB 的程序都不能被调度执行
- 异步性：以不可预知的速度推进，可能导致结果不可再现
💡 记忆法："动并独异"。
b_50_9PCB 里存了哪四类信息？¶
| 类别 | 内容 |
|---|---|
| 进程标识信息 | PID、父进程 PPID、用户 UID |
| 进程调度信息 | 当前状态、优先级、CPU 占用时间、等待时间、进入内存时间、阻塞原因 |
| 资源和内存信息 | 代码段/数据段/堆栈段指针、文件描述符列表、I/O 资源清单 |
| 处理机状态信息 | 通用寄存器、程序计数器、PSW、栈指针 SP |
⚠️ 处理机状态信息也称 CPU 上下文 —— 进程被切换出 CPU 时必须完整保存到 PCB，再次被调度时恢复到 CPU。 ⚠️ PCB 常驻内存，可随时被系统访问，进程终止时被回收。
b_51_3PCB 的两种组织方式？¶
- 链接方式：把相同状态的 PCB 用指针链成一个队列（就绪队列、阻塞队列）；⚠️ 阻塞进程还可按阻塞原因进一步分成多个阻塞子队列
- 索引方式：为每种状态建立一个索引表（就绪索引表、阻塞索引表），表项指向对应状态的 PCB
b_51_9程序段和数据段哪个能共享？¶
- 程序段：⚠️ 程序本身是静态的，可被多个进程共享 —— 多个用户运行同一个编辑器时，内存中只保留一份代码副本，各进程通过 PCB 指向该共享代码段
- 数据段：⚠️ 每个进程的数据段是私有的 —— 即使多个进程运行同一程序，数据段也彼此隔离
💡 这正是进程独立性与安全性的保障。
b_52_0；PDF 第 52 页 · b_52_1进程虚拟地址空间有哪几个区域？ ★1考¶
从高地址到低地址： - 用户栈：⚠️ 从高地址向低地址扩展；存局部变量、函数参数、返回地址，LIFO，由系统自动管理 - 共享库的存储映射区：printf() 等公共函数代码，运行时动态映射，只读且可被多进程共享 - 堆：⚠️ 从低地址向高地址增长；malloc() 申请、free() 释放，大小不固定 - 读/写数据段：.data（已初始化的全局变量和静态变量，如 int x=5）、.bss（未初始化的，如 int y） - 只读代码段：.init（启动时自动调用的初始化代码）、.text（主程序指令）、.rodata（只读数据，如字符串常量）
⚠️ 两个必考细节： - PCB 不属于进程的虚拟地址空间 —— 它由内核维护、存放在系统内核区，对用户进程不可见 - 代码段和数据段的大小在程序加载时就已确定，堆和栈可在运行中动态扩展和收缩
★ 考过 2025
💡 记忆法："栈从上往下长，堆从下往上长，中间留给共享库"。
b_52_4五种进程状态各是什么？ ★1考¶
前三种是基本状态： - 运行态：正在 CPU 上执行；⚠️ 单 CPU 中任一时刻最多只有一个 - 就绪态：⚠️ 已获得除 CPU 外的所有必要资源，一获得 CPU 即可运行；组织成就绪队列 - 阻塞态（等待态）：因等待某事件暂停；⚠️ 此时即使 CPU 空闲也无法执行 - 创建态：⚠️ 短暂的中间状态 —— 申请空白 PCB → 填写控制管理信息 → 分配资源 → 转入就绪态插入就绪队列 - 终止态：已完成执行，等待系统回收资源；⚠️ 不再参与调度，但 PCB 等信息可能暂时保留
★ 考过 2023
b_53_6就绪态和阻塞态的本质区别？¶
- 就绪态：仅缺少 CPU，只要拿到 CPU 就能运行
- 阻塞态：需要 CPU 以外的其他资源，或在等待某一事件
⚠️ 为什么要把 CPU 与其他资源分开：分时系统时间片很短（通常几毫秒），进程会频繁在运行态与就绪态之间切换；而外设分配或 I/O 完成往往需要较长时间，进入阻塞态的频率远低于就绪态。
b_53_10四种基本状态转换分别由什么触发？ ★5考¶
- 就绪 → 运行：被调度程序选中获得 CPU
- 运行 → 就绪：⚠️ 两种情况 —— 时间片用完；可剥夺式调度下有更高优先级进程就绪
- 运行 → 阻塞：⚠️ 主动行为 —— 通过系统调用请求某项服务而无法立即满足；注意并非所有系统调用都会阻塞，只有需要等待外部事件的才会
- 阻塞 → 就绪：⚠️ 被动行为 —— 等待的事件发生后，由中断处理程序把它改为就绪态并插入就绪队列
⚠️ 不存在"阻塞 → 运行"和"就绪 → 阻塞"。
💡 做题按“事件—动作主体—去向”三列判断：时间片/抢占由调度器把运行态送回就绪；运行进程主动等待才进入阻塞；I/O 完成由中断处理把阻塞进程送回就绪，绝不直接跳到运行态。
★ 考过 2014、2015、2018、2023、2025
💡 记忆法："睡是自己去睡（主动），醒要别人叫（被动）"。
b_54_02.1.5 进程控制¶
进程控制为什么要用原语实现？¶
因为原语在执行期间不允许被中断，是一个不可分割的基本单位 —— 确保创建、撤销、状态转换等关键操作的原子性和一致性。
b_54_7；PDF 第 54 页 · b_54_8父进程和子进程什么关系？ ★2考¶
子进程创建时复制父进程的当前状态：程序代码、数据段、堆栈内容、打开的文件描述符、环境变量。
⚠️ 但子进程与父进程是相互独立的实体，拥有各自的 PCB 和虚拟地址空间。
触发创建的四种情形：终端用户登录、作业调度启动批处理任务、系统提供服务、用户程序发起应用请求。
★ 考过 2010、2020、2024
b_54_11创建原语的四个步骤？ ★1考¶
- ① 分配唯一标识并申请 PCB：分配 PID，从系统 PCB 池申请空白 PCB；⚠️ PCB 资源耗尽则创建失败返回错误
- ② 分配运行所需资源：内存、文件、I/O 设备（记录在 PCB 中）；⚠️ 资源或从操作系统获得，或从父进程继承
- ③ 初始化 PCB：标识信息、处理机状态信息、调度与控制信息、内存与资源信息；⚠️ 通常设为最低优先级，除非用户显式要求
- ④ 插入就绪队列
★ 考过 2021
b_54_15终止原语的五个步骤？什么是级联终止？ ★1考¶
- ① 检索 PCB，读取当前状态
- ② 若正在运行则立即剥夺 CPU，并触发调度程序选下一个
- ③ 释放所有系统资源归还操作系统
- ④ 若支持级联终止则递归终止所有子孙进程，否则子孙继续运行
- ⑤ 把 PCB 从所在队列中移除
引起终止的三类事件：正常结束；异常结束（存储区越界、非法指令、特权指令违规、算术运算错误、I/O 故障、运行超时）；外界干预（操作员强制终止、系统因资源不足或安全策略终止、父进程请求终止子进程）。
⚠️ Linux 不采用级联终止：父进程终止后，子进程由 init 进程（PID=1）收养并继续正常运行。
★ 考过 2024
b_55_3阻塞原语的三步？为什么说阻塞是主动的？ ★3考¶
- ① 保存 CPU 现场（PC、状态寄存器等）到 PCB
- ② 把 PCB 状态改为阻塞态，插入所等待事件的等待队列
- ③ 调用调度程序，从就绪队列另选一个进程运行
⚠️ 阻塞是进程的主动行为，所以只有处于运行态的进程才能执行阻塞操作。
常见等待事件：请求系统资源暂不可用、等待 I/O 完成、等待接收数据、等待信号量。
★ 考过 2018、2022、2023
b_55_7唤醒原语的三步？为什么必须成对使用？ ★2考¶
- ① 在指定事件的等待队列中找到目标进程的 PCB
- ② 移出等待队列，状态置为就绪态
- ③ 插入就绪队列
⚠️ Block 与 Wakeup 是一对作用相反的原语，必须成对使用 —— 若某进程 Block 后没有任何机制调用对应的 Wakeup，它将永久停留在阻塞态。
谁来唤醒：由内核的中断处理程序或合作进程调用。
★ 考过 2014、2019
b_55_102.1.6 进程的通信¶
低级通信和高级通信怎么分？¶
- 低级通信：传递控制信息（同步、互斥），典型代表是 PV 操作
- 高级通信：高效传输大量数据 —— 共享存储、消息传递、管道通信、信号
b_55_14共享存储通信中，操作系统管不管同步？¶
⚠️ 不管。 操作系统仅负责分配共享内存区并完成地址映射，不会自动提供同步保护；读/写逻辑与同步控制都要由用户程序自行设计（如用信号量的 P、V 操作）。
原理：通过特殊的系统调用创建一段独立的内存区域，映射到多个进程的虚拟地址空间中，进程直接读写该区域。
💡 教材类比：甲乙之间放一个公共大布袋 —— 甲放进去、乙取出来，但乙不能直接伸手拿甲手里的东西。
b_56_0；PDF 第 56 页 · b_56_1消息传递的两种模式？¶
数据交换以格式化的消息为单位，通过发送原语和接收原语进行。 - 直接通信：⚠️ 发送方指定接收进程；内核把消息从发送方复制到接收方的内核缓冲队列 - 间接通信：⚠️ 双方不直接指定对方，通过中间实体"信箱"交换 —— 发送方投递到信箱，接收方从信箱取
⚠️ 重要性：消息传递是目前应用最广泛的 IPC 机制；微内核与服务器之间的交互正是基于消息传递；也是多处理器系统、分布式系统、计算机网络中的主流方式。
💡 类比：直接通信 = 邮差把信交到本人手里；间接通信 = 投进门口的邮箱。
b_56_3；PDF 第 56 页 · b_56_4管道到底是文件还是内存？ ★1考¶
⚠️ 编程接口上像文件（支持 read()/write()，是一种特殊的共享文件），但实现上并非磁盘文件，而是内核维护的一块固定大小的内存缓冲区（如环形缓冲区 64KB）。
基于先进先出原则，常用于有亲缘关系的进程（父子进程）之间，以生产者-消费者模式交换数据。
⚠️ 为什么子进程能用：管道由父进程通过 pipe() 系统调用创建，子进程创建时继承父进程的文件描述符表，因此能访问同一管道。
★ 考过 2014
b_56_14管道必须提供哪三种协调能力？¶
- 互斥：⚠️ 任一时刻只允许一个进程对管道进行读或写
- 同步：管道满 → 写进程阻塞，直到读进程取走部分数据；管道空 → 读进程阻塞，直到写进程写入新数据
- 写端关闭检测：⚠️ 写端关闭后，读端 read() 返回 0，表明无数据可读
⚠️ 缓冲区大小固定，不会像普通文件那样无限增长 —— 满了 write() 就阻塞。
b_57_0管道读取有什么特殊之处？¶
- ⚠️ 从管道读数据是一次性操作 —— 数据一旦被读出，缓冲区空间即被释放，供后续写入
- ⚠️ 普通管道仅支持单向通信；要双向通信必须创建两个管道
⚠️ 还有个自动阻塞规则：读进程消费快于写进程时，管道被读空，read() 会阻塞等待写入。
b_57_6信号是怎么记录和屏蔽的？¶
在 PCB 中用一个 n 位向量（Linux 用一个 32 位整型变量）记录当前待处理的信号：发送信号时内核把对应位置 1，处理成功后清零。
⚠️ PCB 中还有另一个 n 位向量记录被阻塞（屏蔽）的信号 —— 某位为 1 表示该信号不会被立即处理，而是暂存起来直到解除阻塞。
⚠️ Linux 内核实现了约 30 种信号，编号通常 1~30。
b_57_7；PDF 第 57 页 · b_57_8信号什么时候被检查和处理？¶
⚠️ 操作系统从内核态返回用户态时（如系统调用结束），检查当前进程是否存在未被阻塞的待处理信号；若有则立即处理其中一个（通常优先处理序号较小的）。
两种发送方式：内核发送（检测到系统事件时，如执行非法指令发 SIGILL，序号 4）；进程发送（调用 kill() 并提供目标 PID 和信号序号，也可以给自己发）。
两种处理方式：执行默认的信号处理程序（如 SIGILL 默认终止进程）；执行进程自定义的信号处理程序。
⚠️ 信号处理程序执行结束后，通常返回到原程序被中断的位置继续执行。
b_57_132.1.7 线程和多线程模型¶
引入线程是为了解决什么？ ★3考¶
引入进程是为了让多道程序并发执行，提高资源利用率和吞吐量； 引入线程是为了进一步降低程序并发执行时的时空开销，提升并发性能。
线程是"轻量级进程"，是程序执行流的最小单元，也是处理器调度的基本单位。
⚠️ 内涵变化：引入线程后，进程成为"除 CPU 外"的系统资源分配单位，线程成为 CPU 调度和执行的基本单位。 ⚠️ 进程处于"执行"状态，实际上是指该进程中的某个线程正在运行。
★ 考过 2011、2019、2024
b_58_0线程的五个属性？¶
- 轻量级执行实体：⚠️ 不拥有独立的系统资源，但拥有运行必需的私有数据结构 —— 线程 ID、程序计数器、寄存器集合、栈，以及 TCB
- 共享代码段：同一进程的多个线程可并发执行相同的程序代码（如 Web 服务器为每个用户请求开一个线程）
- 资源共享：共享进程的代码段、数据段、堆、文件描述符 → 通信和数据共享非常高效，无须复杂的 IPC
- 独立调度单位：单 CPU 下时间片轮转，多 CPU 下可并行运行于多个核心
- 生命周期：创建 → 就绪/运行/阻塞 → 终止
b_58_1进程和线程的六点比较？ ★1考¶
| 维度 | 进程 | 线程 |
|---|---|---|
| 调度 | 传统 OS 中既是资源拥有者又是调度单位 | 调度的基本单位；⚠️ 同进程内线程切换不引起进程切换，跨进程则会 |
| 并发性 | 进程之间可并发 | 进程内多线程也可并发，跨进程的线程也能并发 |
| 拥有资源 | 资源分配的基本单位 | 不拥有独立资源，只有必需的私有数据结构 |
| 独立性 | 地址空间完全独立，其他进程无法直接访问 | 共享地址空间，紧密协作；⚠️ 一个进程的线程对其他进程完全不可见 |
| 系统开销 | 创建/撤销要分配回收 PCB、地址空间、I/O 资源，开销显著 | 仅需分配栈和少量内核对象，开销很小；切换只需保存恢复寄存器 |
| 多处理器 | 单线程进程任一时刻只能在一个 CPU 上执行 | 多线程可同时调度到多个 CPU 并行 |
★ 考过 2012
b_58_14TCB 里存什么？线程能访问别的线程的栈吗？ ★1考¶
TCB 包含：① 线程标识符；② 寄存器集合（程序计数器、状态寄存器、通用寄存器）；③ 线程当前状态；④ 调度优先级；⑤ 线程局部存储区；⑥ 堆栈指针（指向私有栈）。
⚠️ 一个高频陷阱：每个线程有独立的私有栈，但这些栈都位于进程的地址空间内 —— 技术上一个线程可以访问另一个线程的栈内容，只是严重违反编程规范，实际开发中应严格避免。
⚠️ 同一进程的所有线程共享地址空间和全局变量。
★ 考过 2024
b_59_11线程终止后资源马上释放吗？¶
⚠️ 不会。 大多数操作系统中，线程终止后并不立即释放其占用的资源 —— 只有当进程中的其他线程执行了相应的分离操作后，资源才被回收。
⚠️ 更反直觉的一点：已被终止但尚未释放资源的线程仍可被其他线程调用，使其重新恢复运行。
四种终止原因：正常执行完主函数、发生未处理的异常、主动调用线程终止函数、被其他线程通过取消机制强制终止。
b_59_8用户级线程的调度为什么不公平？ ★1考¶
⚠️ 根源：采用用户级线程时，调度仍以进程为单位 —— 调度器只能感知进程，看不到进程内部的多个用户级线程，只给整个进程分配一个时间片。
教材算例（时间片 100ms）：进程 A 只有 1 个用户级线程 → 独占 100ms；进程 B 有 100 个用户级线程 → 每个线程平均只有 1ms → A 的线程获得的 CPU 时间是 B 的 100 倍。
★ 考过 2019
b_60_1用户级线程的三优两缺？¶
优点： - ⚠️ 线程切换在用户空间完成，无须切换到内核态，避免模式切换开销 - 调度策略可由应用程序定制，不同进程可用不同算法 - ⚠️ 实现与操作系统无关，线程管理代码是用户程序的一部分，可移植性好
缺点： - ⚠️ 系统调用的阻塞问题：某个线程执行阻塞型系统调用时，整个进程被内核挂起，进程中所有线程都被阻塞 - ⚠️ 无法发挥多处理器的并行优势：内核只把该进程调度到一个 CPU 上
💡 一句话：内核完全感知不到用户级线程的存在。
b_60_0；PDF 第 60 页 · b_60_1内核级线程的三优一缺？¶
优点： - 能发挥多处理器的并行优势：可把同一进程的多个线程同时调度到不同核心 - 阻塞处理更灵活：⚠️ 某个线程被阻塞时，内核仍可调度该进程中的其他线程运行 - 内核自身可采用多线程技术
缺点：⚠️ 线程切换需从用户态陷入内核态 —— 每次切换都涉及模式转换和上下文保存/恢复，开销较大。
⚠️ 内核为每个内核级线程维护一个 TCB，通过它感知和控制线程。
b_60_4；PDF 第 60 页 · b_60_6三种多线程模型的优缺点？ ★1考¶
| 模型 | 映射 | 优点 | 缺点 |
|---|---|---|---|
| 多对一 | 多个 ULT → 1 个 KLT | 切换效率高（用户空间完成） | ⚠️ 一个线程阻塞则整个进程挂起；无法多处理器并行 |
| 一对一 | 每个 ULT → 1 个 KLT | 阻塞隔离，支持真正并发与多 CPU 并行 | ⚠️ 每建一个用户线程就要建一个内核线程，开销大，限制最大线程数 |
| 多对多 | n 个 ULT → m 个 KLT（n ≥ m） | 兼具两者优点：切换高效 + 多核并行 + 阻塞隔离 | — |
⚠️ 多对一模型中：每个进程仅拥有一个内核级线程，每次只允许一个线程进行映射。
★ 考过 2019
b_61_3；PDF 第 61 页 · b_61_8线程库的两种实现和三大主流库？¶
两种实现： - 纯用户空间实现：全部代码和数据结构在用户态，调用库函数仅触发本地过程调用，无须陷入内核 → 对应用户级线程 - 内核支持实现：API 调用通常触发系统调用，由内核完成实际操作 → 对应内核级线程
三大主流库： - POSIX Pthreads：⚠️ 具体实现可基于用户级或内核级 - Windows 线程 API：⚠️ 直接构建于 Windows 内核之上，属内核级 - Java 线程 API：⚠️ 通过调用宿主系统的线程库实现（Windows 上用 Windows API，类 UNIX 上用 Pthreads）
b_61_14；PDF 第 61 页 · b_61_15引入进程解决了并发的哪三个问题？¶
- 失去封闭性：进程通过地址空间隔离，为每个程序提供独立、受保护的执行环境
- 执行过程的间断性：进程用 PCB 保存和恢复执行上下文，确保中断后能准确继续
- 结果不可再现性：隔离机制 + 调度策略共同保障可控性与可再现性
b_62_82.2 CPU 调度¶
三级调度分别在哪两级存储之间？¶
- 高级调度（作业调度）：⚠️ 内存与外存之间的调度 —— 从外存后备队列挑作业，分配资源并创建进程；⚠️ 每个作业只被调入一次、调出一次；⚠️ 传统多道批处理系统才配备，分时/实时系统一般不设
- 中级调度（内存调度）：⚠️ 实际上就是存储器管理中的对换功能 —— 内存紧张时把暂时不能运行的进程换出到外存（挂起态），条件满足再换入恢复为就绪态
- 低级调度（进程调度）：从就绪队列选进程分配 CPU；⚠️ 最基础、最频繁，所有操作系统都必须有，通常每几十毫秒执行一次
⚠️ 调度频率：作业调度最低 < 中级调度 < 进程调度最高。
💡 记忆法："高级管进门、中级管换气、低级管上机"。
b_78_17进程调度的三个任务？¶
- 保存 CPU 现场信息：把当前进程的 PC、通用寄存器等完整保存到 PCB
- 选取待运行进程：按算法从就绪队列选一个，状态由就绪态改为运行态
- 完成 CPU 分配：由分派程序把选中进程 PCB 中的 CPU 现场加载到处理器寄存器，移交控制权
b_79_11调度程序由哪三部分组成？¶
- 排队器：把所有就绪进程按策略组织成一个或多个就绪队列
- 分派器：从就绪队列移出目标进程、触发上下文切换、移交 CPU 控制权
- 上下文切换器：⚠️ 一次 CPU 切换会发生两对上下文切换 —— ① 保存当前进程上下文到 PCB，装入分派程序的上下文；② 移出分派程序的上下文，装入新进程的 CPU 现场
⚠️ 为什么开销大：要执行大量 load 和 store 指令保存寄存器内容。 硬件优化：用两组寄存器（一组内核用、一组用户用），切换时只需改变指针指向。
b_80_3什么时候需要进行调度与切换？ ★2考¶
- 创建新进程后：父子都就绪，要决定先运行谁
- 进程正常结束或异常终止后：⚠️ 若没有就绪进程，则运行系统提供的闲逛进程
- 进程因 I/O 请求、信号量操作等被阻塞时
- I/O 设备准备就绪发出中断后：原等待进程变就绪，要决定是让它运行还是让被中断的进程继续
支持抢占的系统还有两种：更高优先级进程进入就绪队列；当前进程时间片用完。
★ 考过 2012、2021
b_80_10哪两种情况下不能进行调度与切换？¶
- ⚠️ 处理中断的过程中：中断处理逻辑复杂难以安全切换；且中断处理属于内核工作，逻辑上不隶属于任何用户进程，不应被剥夺 CPU
- ⚠️ 执行原子操作的过程中：加锁解锁、中断现场的保护与恢复等需要屏蔽中断保证原子性 —— 连中断都禁止了，更不应调度
⚠️ 处理办法：若此期间发生了调度条件，系统设置一个调度请求标志，待临界区或中断处理完成后再执行调度。
b_81_1进程切换具体切什么？¶
内核把原进程的上下文（PC、寄存器状态等）保存到其 PCB 或内核栈；然后从新进程的 PCB 或内核栈加载上下文，更新地址空间相关信息（如页表基址），重置程序计数器，开始执行。
💡 三个步骤的顺序：请求调度的事件发生 → 运行调度程序 → 调度出新进程后进行切换；⚠️ 但实际内核中，即使发生了引发调度的条件，也不一定能立即调度与切换。
💡 PCB 枢纽链：由当前 PCB 的状态/优先级决定是否调度 → 从就绪队列选下一 PCB → 保存旧 PC/寄存器 → 恢复新寄存器、页表基址和栈信息。做综合题时要把“调度决策”和“实际切换”分成两步。
b_81_2；PDF 第 81 页 · b_81_9抢占式和非抢占式的分界？¶
- 非抢占（非剥夺）：即使有更紧迫的进程进入就绪队列，仍让当前进程执行到完成，或因等待 I/O、执行 Block 原语而主动阻塞才让出 CPU
- 优点：实现简单、系统开销小，适用于早期批处理系统
- ⚠️ 缺点：无法满足分时系统和大多数实时系统对及时响应的要求
- 抢占（剥夺）：出现更高优先级就绪进程时可暂停当前进程
- ⚠️ 抢占不是任意行为，必须遵循原则：优先级原则、短进程优先原则、时间片原则
b_81_4闲逛进程有什么特点？¶
- PID 为 0，优先级最低，仅在无其他就绪进程时运行
- 一旦有新进程进入就绪队列就立即让出 CPU
- 主要任务是在空闲循环中不断检测中断请求
- ⚠️ 不占用除 CPU 外的其他系统资源，也不会因等待事件而被阻塞
b_81_8；PDF 第 81 页 · b_81_9两种线程调度的开销差多少？¶
- 用户级线程调度：内核以进程为单位分配 CPU 时间，由进程内部的线程库决定运行哪个线程；切换只需保存少量寄存器，开销极小；⚠️ 一个线程阻塞则整个进程阻塞
- 内核级线程调度：内核直接调度特定线程，每个线程有独立内核上下文、可单独赋予时间片；⚠️ 涉及完整上下文切换、地址空间更新（跨进程时）、可能的 TLB 刷新和缓存失效，开销通常高出数倍
b_81_11调度的五个衡量指标怎么算？ ★6考¶
- CPU 利用率 = CPU 有效工作时间 / (CPU 有效工作时间 + CPU 空闲等待时间)
- 系统吞吐量 = 单位时间完成的作业数；⚠️ 长作业降低吞吐量，短作业提升吞吐量
- 周转时间 = 作业完成时间 − 作业提交时间（含等待、排队、执行、I/O 全部时间）
- 带权周转时间 = 周转时间 / 作业实际运行时间
- 等待时间 = 进程在就绪队列中等待 CPU 的总时间；⚠️ 调度算法不影响实际执行时间和 I/O 时间，只影响等待时间
- 响应时间 = 从提交请求到系统首次产生响应的时间；⚠️ 交互式系统中比周转时间更有意义
⚠️ 算作业完成时间时的大坑：CPU 与 I/O 设备之间、不同 I/O 设备之间可以并行执行。
⚠️ 不存在一种调度算法能同时满足所有需求。
★ 考过 2012、2016、2018、2019、2023、2024
b_82_2上下文切换的五个步骤？ ★3考¶
- ① 挂起当前进程，把 CPU 上下文保存到其 PCB
- ② 把该 PCB 移入相应队列（就绪队列或阻塞队列）
- ③ 选择另一个进程执行，更新其 PCB 信息
- ④ 恢复新进程的 CPU 上下文
- ⑤ 跳转到新进程 PCB 中程序计数器所指的位置开始执行
⚠️ 进程上下文由 PCB 表示，包括 CPU 寄存器的值、进程状态、内存管理信息。 ⚠️ 开销：单次仅微秒量级，但高负载下每秒数十上百次，累积消耗可观；优化办法是多个寄存器组，切换寄存器组指针。
★ 考过 2023、2024、2025
b_83_3模式切换和上下文切换的区别？ ★1考¶
- 模式切换：⚠️ 发生在同一进程内部（用户态↔内核态），当前进程并未改变，因此不涉及上下文切换
- 上下文切换：⚠️ 从一个进程切换到另一个进程，必须保存旧进程上下文、恢复新进程上下文；⚠️ 只能由内核完成，整个过程运行在内核态
⚠️ 还要分清调度与切换：调度是决策行为（决定 CPU 给谁）；切换是执行行为（实际转移 CPU 控制权）——先调度决策，再触发切换。
★ 考过 2023
b_83_19；PDF 第 83 页 · b_83_212.2.5 CPU 调度算法¶
FCFS 对什么样的作业有利？ ★5考¶
每次选最早进入队列的作业/进程，属于非抢占式算法。
⚠️ 特性判断（高频）： - 实现简单，但效率较低 - 对长作业有利，对短作业不利（相比 SJF 或高响应比） - ⚠️ 对 CPU 繁忙型作业有利，对 I/O 繁忙型作业不利 —— I/O 型进程本可及时让出 CPU 提高并发，但排在长作业后面仍要长时间等待 - ⚠️ 不适合分时系统和实时系统，但常被结合到其他策略中（如优先级相同的进程按 FCFS 调度）
★ 考过 2009、2011、2014、2017
b_83_22FCFS 例题的四个平均值怎么算？ ★2考¶
4 个作业提交时间 8.0 / 8.4 / 8.8 / 9.0，运行时间 2 / 1 / 0.5 / 0.2：
| 作业 | 提交 | 运行 | 开始 | 等待 | 完成 | 周转 | 带权周转 |
|---|---|---|---|---|---|---|---|
| 1 | 8 | 2 | 8 | 0 | 10 | 2 | 1 |
| 2 | 8.4 | 1 | 10 | 1.6 | 11 | 2.6 | 2.6 |
| 3 | 8.8 | 0.5 | 11 | 2.2 | 11.5 | 2.7 | 5.4 |
| 4 | 9 | 0.2 | 11.5 | 2.5 | 11.7 | 2.7 | 13.5 |
平均等待 1.575，平均周转 2.5，平均带权周转 5.625。
★ 考过 2012、2016
💡 解题模板：等待 = 开始 − 提交；周转 = 完成 − 提交；带权 = 周转 / 运行。
b_84_0SJF 例题为什么平均值更优？ ★1考¶
同一组作业改用 SJF：
| 作业 | 提交 | 运行 | 开始 | 等待 | 完成 | 周转 | 带权周转 |
|---|---|---|---|---|---|---|---|
| 1 | 8 | 2 | 8 | 0 | 10 | 2 | 1 |
| 2 | 8.4 | 1 | 10.7 | 2.3 | 11.7 | 3.3 | 3.3 |
| 3 | 8.8 | 0.5 | 10.2 | 1.4 | 10.7 | 1.9 | 3.8 |
| 4 | 9 | 0.2 | 10 | 1 | 10.2 | 1.2 | 6 |
平均等待 1.175，平均周转 2.1，平均带权周转 3.525 —— 三项全面优于 FCFS。
⚠️ 结论要记牢：所有作业同时到达且运行时间已知时，SJF 的平均等待时间和平均周转时间是最优的。
★ 考过 2017
b_84_12SJF 的三个缺点？什么是饥饿？ ★1考¶
- ⚠️ 对长作业不利，甚至产生饥饿现象 —— 长作业进入后备队列后不断有新短作业到达，长作业长期得不到服务
- 未考虑作业的紧迫程度（完全忽略截止时间）
- ⚠️ "长短"由用户提交的估计值决定，用户可能故意低估以获取调度优势
⚠️ 饥饿 vs 死锁：饥饿是调度策略导致的无限期等待，与死锁中的环形等待有本质区别。
⚠️ SPF 默认是非抢占式；抢占式版本叫最短剩余时间优先 —— 新进程到达时，若其估计运行时间比当前进程的剩余执行时间更短就抢占。
★ 考过 2016
b_85_0；PDF 第 85 页 · b_85_10高响应比优先怎么兼顾两头？¶
- 等待时间相同时：运行时间越短响应比越高 → 有利于短作业（像 SJF）
- 运行时间相同时：等待时间越长响应比越高 → 体现 FCFS 的公平性
- ⚠️ 长作业的响应比随等待时间不断提高，最终能被调度 → 有效避免饥饿
⚠️ 它主要用于作业调度，是 FCFS 和 SJF 的综合平衡。
💡 记忆法："等得越久、干得越快，越先上"。
b_85_6；PDF 第 85 页 · b_85_7优先级调度的两种抢占方式？ ★3考¶
- 非抢占式优先级：更高优先级进程到达时，⚠️ 仍让当前进程执行到自身让出 CPU（任务完成或等待事件）
- 抢占式优先级：⚠️ 立即暂停当前进程，把 CPU 给优先级更高的
★ 考过 2018、2022、2023、2025
b_85_13；PDF 第 85 页 · b_85_18静态优先级和动态优先级怎么选？ ★2考¶
- 静态优先级：创建时确定，整个运行期不变；依据进程类型、资源需求、用户指定
- 优点实现简单、开销小；⚠️ 缺点不灵活，可能出现饥饿
- 动态优先级：创建时给初始值，随进程推进或等待时间动态调整 —— 例如优先级随等待时间增加而提高，让低优先级进程等久了也能被调度
★ 考过 2010、2016
b_86_1优先级设置的三条原则？为什么 I/O 型优先？ ★1考¶
- 系统进程 > 用户进程
- 交互型进程 > 非交互型进程（前台 > 后台）
- ⚠️ I/O 型进程 > 计算型进程
为什么 I/O 型要更高：I/O 设备速度远低于 CPU —— 让 I/O 型进程尽快拿到 CPU 并启动 I/O 操作，使设备尽早开始工作，从而提高系统整体吞吐量。
★ 考过 2013
b_86_7时间片轮转的调度时机？ ★3考¶
就绪进程按 FCFS 组织成队列，每隔固定时间片（例如 30ms）产生一次时钟中断激活调度程序。⚠️ 时间片用完即使没运行完也必须被剥夺 CPU，放到就绪队列末尾。
两种调度时机： - 时间片结束前已运行完成 → 调度程序立即被激活进行切换 - 时间片用尽 → 由时钟中断处理程序触发调度
⚠️ RR 主要适用于分时系统，最大特点是公平性。
★ 考过 2017、2021、2024
b_86_10时间片过大或过小会怎样？ ★1考¶
- ⚠️ 过大：大到每个进程都能在一个时间片内跑完时，RR 退化为 FCFS，无法满足短作业和交互式用户的快速响应需求
- ⚠️ 过小：频繁进行调度和上下文切换，系统开销大增，真正执行用户程序的 CPU 时间反而减少
取值要综合考虑三点：系统的期望响应时间、就绪队列中的进程数量、系统的处理能力。 💡 经验法则：时间片应略长于一次典型交互所需的时间（如输入一个字符、按下回车，通常几十到上百毫秒）。
★ 考过 2017
b_86_13多级队列调度是怎么分队列的？¶
把就绪进程划分为多个独立的就绪队列，每队对应一类相似特性的进程（系统进程、交互型、批处理）： - ⚠️ 每个队列可独立采用适合自身特性的调度算法 —— 交互型队列常用 RR，批处理队列可用 FCFS 或 SJF - ⚠️ 各队列本身具有不同优先级：总是优先调度高优先级队列，只有高优先级队列全空才调度低优先级队列
b_87_0；PDF 第 87 页 · b_87_1多级反馈队列的三条实现机制？ ★2考¶
- ① 设置多个就绪队列，优先级依次降低；⚠️ 优先级越高的队列时间片越小，第 i+1 级队列的时间片通常是第 i 级的 2 倍
- ② 每个队列内部用 RR；⚠️ 新进程先进第 1 级队列末尾；时间片内完成就退出；用完还没完成就降到下一级队列末尾；最低级队列行为接近 FCFS，但仍用 RR 保证公平
- ③ 按队列优先级调度：⚠️ 仅当第 1 ~ i−1 级队列均为空时才调度第 i 级；⚠️ 新进程总是进第 1 级，所以若当前运行的是低优先级队列进程，新进程会立即抢占它（被抢占者放回原队列末尾）
★ 考过 2019、2020
b_87_10多级反馈队列对三类用户各有什么好处？¶
- 交互型（终端型）用户：进程短且频繁 I/O，能在高优先级队列中快速完成
- 短批处理作业用户：优先级高、时间片小，迅速执行完毕，周转时间短
- 长批处理作业用户：虽最终降到低优先级队列，但已在高优先级队列获得部分 CPU 时间；⚠️ 这只能改善初始响应，不能无条件保证以后不饥饿
⚠️ 校订/边界：若高优先级任务持续到达，低队列作业仍可能长期等不到 CPU；只有在到达负载有限，或系统采用老化、周期性优先级提升（priority boost）时，才能更可靠地避免饥饿。
💡 它的三大优势：兼顾短进程（提高吞吐、缩短周转）、兼顾 I/O 型进程、无须事先知道进程的运行时间。
b_87_5保证调度和公平分享调度差在哪？¶
- 保证调度算法：对进程公平 —— n 个并发进程时每个进程获得约 1/n 的 CPU 时间。实现四步：跟踪已获得的 CPU 时间 → 计算应获得的（创建以来时间 ÷ n）→ 算公平比率 → 选比率最小的运行，直到其比率超过最接近它的进程
- 公平分享调度算法：对用户公平 —— ⚠️ 保证调度未必对用户公平：用户 1 有 4 个进程、用户 2 有 1 个，RR 下用户 1 拿 80%、用户 2 只拿 20%
公平分享下的调度序列示例（两用户等分）：A E B E C E D E …（用户 1 的 4 个进程与用户 2 的 E 交替）。
b_88_3五种调度算法的总对照表？¶
| FCFS | SJF | 高响应比 | 时间片轮转 | 多级反馈队列 | |
|---|---|---|---|---|---|
| 能否抢占 | 否 | 可以 | 否 | 可以 | 队列内算法不一定 |
| 优点 | 公平、实现简单 | 平均等待/周转最优 | 兼顾长短作业 | 兼顾长短作业 | 兼顾长短作业、响应好、可行性强 |
| 缺点 | 不利于短作业 | 长作业饥饿、估计时间不易确定 | 计算响应比开销大 | 平均等待较长、切换浪费时间 | 最复杂 |
| 适用于 | 无 | 批处理系统 | 无 | 分时系统 | 相当通用 |
💡 这张表几乎每年都在选择题里出现，务必背熟"能否抢占"和"适用于"两行。
b_88_16AMP 和 SMP 的区别？¶
- 非对称多处理机 AMP：主从式架构 —— 一个主 CPU 负责全部调度决策和系统管理，从 CPU 只执行任务；内核一般运行在主 CPU 上，从 CPU 空闲时向主 CPU 发请求信号；⚠️ 实现简单，但主 CPU 在高负载下容易成为瓶颈
- 对称多处理机 SMP：所有 CPU 地位对等，均可参与调度，任意就绪进程可分配给任意空闲 CPU
b_89_2；PDF 第 89 页 · b_89_11处理器亲和性和负载平衡为什么矛盾？¶
- 处理器亲和性：进程从一个 CPU 迁到另一个时，要把第一个 CPU 的缓存设为无效，再重新填充第二个 CPU 的缓存，代价高 → 应尽量让进程运行在同一个 CPU 上
- 负载平衡：把负载平均分配到所有 CPU，否则有的 CPU 空闲、有的高负载
⚠️ 矛盾点：负载平衡通常会抵消处理器亲和性带来的好处（迁移就丢了缓存）。 ⚠️ 折中办法：只有当不平衡达到一定程度后，才触发进程迁移。
b_89_6；PDF 第 89 页 · b_89_7公共就绪队列和私有就绪队列各有什么代价？¶
- 公共就绪队列：负载平衡好（CPU 一空闲就取一个跑）；⚠️ 缺点是进程可能频繁在不同 CPU 间切换，亲和性不好
- 补救：软亲和（调度程序尽量保持在某 CPU，但可迁移）、硬亲和（用户进程通过系统调用主动绑定到固定 CPU）；⚠️ Linux 实现了软亲和，也支持硬亲和的系统调用
- 私有就绪队列：亲和性好；⚠️ 缺点是必须进行负载平衡
- 两种迁移：推迁移（系统程序周期性检查，从超载 CPU"推"出进程）、拉迁移（低负载 CPU 主动"拉"取）；⚠️ 实际系统中两者常结合使用
b_89_11哪些算法适合分时系统？哪些适合实时系统？¶
- ⚠️ FCFS 和 SJF 都不适用：无法保证在限定时间内响应用户请求
- 实时系统：优先级调度算法（通常需配合抢占机制确保关键任务及时执行）
- 分时系统：以时间片轮转、多级反馈队列为典型；它们依靠时间片与反馈机制改善交互响应
- ⚠️ 高响应比优先（HRRN）通常是非抢占的作业调度算法，用于兼顾长短作业，不靠时间片保证分时响应
⚠️ 校订/边界：不要因为名称里有“响应比”，就把 HRRN 归入分时系统。
b_90_52.3 同步与互斥¶
访问临界资源的四个部分？ ★3考¶
while(true){
entry section; //进入区：检查是否允许进入，允许则设置"正在访问"标志
critical section; //临界区：实际访问临界资源的代码段
exit section; //退出区：清除标志，表示已释放资源
remainder section; //剩余区：其余部分
}
临界资源 = 同一时刻仅允许一个进程访问的资源（打印机等物理设备、被多进程共享的变量和数据结构）。
★ 考过 2016、2021、2023、2024
b_111_9同步和互斥的本质区别？¶
- 同步（直接制约关系）：⚠️ 源于进程之间的相互合作 —— 为完成某任务需要协调彼此的运行次序
- 例：A 通过单缓冲向 B 提供数据 —— 缓冲区空时 B 阻塞，A 送入数据后唤醒 B；缓冲区满时 A 阻塞，B 取走数据后唤醒 A
- 互斥（间接制约关系）：⚠️ 源于共享资源的竞争 —— 一个进程在临界区时，其他进程必须等待
- 例：只有一台打印机时，A 要打印但打印机已给 B，A 阻塞；B 释放后唤醒 A 转为就绪态
💡 记忆法："同步是合作排队，互斥是竞争排他"。
b_111_16同步机制的四条准则？哪条不是必须的？ ★1考¶
- 空闲让进：临界区空闲时，应允许一个请求进入的进程立即进入
- 忙则等待：已有进程在临界区时，其他进程必须等待
- 有限等待：保证在有限时间内能进入临界区，避免无限期等待
- 让权等待：⚠️ 原则上应遵循，但非必须 —— 等待时应主动放弃 CPU 转为阻塞态，而不是原地循环测试（避免忙等待）
★ 考过 2020
💡 记忆法："空闲让进、忙则等待、有限等待、让权等待" —— 前三条硬性，第四条只是"最好做到"。
b_112_4单标志法违反了哪条准则？¶
// P0: // P1:
while(turn != 0); while(turn != 1); //进入区
critical section; critical section; //临界区
turn = 1; turn = 0; //退出区
用一个公用整型变量 turn 指示当前允许进入的进程编号，退出时把使用权转让给对方。
⚠️ 能保证互斥，但违背"空闲让进" —— 两个进程必须交替进入；若 P1 没有进入打算而 turn 一直是 1，则即使临界区空闲，P0 也无法再进入。
b_112_11双标志先检查法违反了哪条准则？¶
// P0: // P1:
while(flag[1]); ① while(flag[0]); ② //先检查对方
flag[0]=true; ③ flag[1]=true; ④ //后设置自己
critical section; critical section;
flag[0]=false; flag[1]=false;
优点：无须交替进入，可连续使用临界区。
⚠️ 违背"忙则等待"：按 ①②③④ 顺序执行时，两个进程都先检查（发现对方 false）再设置自己 → 同时进入临界区。 ⚠️ 根本原因："检查对方标志"和"设置自己标志"两个操作不是原子的，中间可能发生进程切换。
💡 交错题通法：保持每个进程内部指令次序不变，只枚举进程间合法交错；x=x+1 若题目允许拆分，就按 load → add → store 追踪。原子指令则不能再擅自拆开。
b_112_15双标志后检查法又出了什么问题？¶
⚠️ 按 ①②③④ 顺序：两个进程都先设置了标志，再互相检查，发现对方也想进 → 彼此等待，谁也进不去。
同时违背两条准则："空闲让进"（临界区空着却没人能进）和"有限等待"（可能永远进不去，产生饥饿）。
💡 一句话对比：先检查后设置 → 双双进入（不互斥）；先设置后检查 → 双双卡死（饥饿）。
b_113_2Peterson 算法的关键一步是什么？ ★2考¶
// P0: // P1:
flag[0]=true; flag[1]=true;
turn=1; turn=0; // ← 关键：主动"谦让"给对方
while(flag[1] && turn==1); while(flag[0] && turn==0);
critical section; critical section;
flag[0]=false; flag[1]=false;
思路：用 flag[] 解决互斥，用 turn 解决饥饿。
⚠️ 关键在 turn=j 这一步 —— 主动把进入机会"谦让"给对方。两个进程同时请求时，turn 的最终值由后执行赋值的进程决定，因此总有一个进程的 while 条件不成立。
💡 断点证明法：分别停在两边 flag[i]=true 和 turn=j 之后，记录最新的 flag[]/turn，再代入两个 while 条件。两个进程同时请求时，最后一次 turn 赋值只会让一边等待，另一边必能进入。
⚠️ 评价：遵循"空闲让进""忙则等待""有限等待"三条准则，但因采用忙等待，没有遵循"让权等待" —— 在纯软件互斥算法中是满足前三条方面最完善的方案。
★ 考过 2010、2018
b_113_7中断屏蔽法的三个缺点？ ★1考¶
做法：关中断 → 临界区 → 开中断。原理是 CPU 仅在响应中断时才可能发生进程切换。
三个缺点： - 限制了 CPU 的并发执行能力，显著降低系统效率 - ⚠️ 不能把关中断权限开放给用户进程 —— 若某进程关中断后未及时开中断，可能导致系统死锁或崩溃 - ⚠️ 不适用于多处理器系统 —— 在某一 CPU 上关中断，无法阻止其他 CPU 上的进程访问同一临界区
★ 考过 2021
b_114_4TestAndSet 指令做了什么？ ★2考¶
boolean TestAndSet(boolean *lock) {
boolean old;
old = *lock; //保存旧值
*lock = true; //置为 true
return old; //返回旧值
}
使用方式：
- 返回 false → 原来没人在临界区，成功获得锁
- 返回 true → 已有进程在临界区，循环等待
优点：⚠️ 由硬件保证"检查锁"与"加锁"的原子性；⚠️ 因为 lock 是共享变量，适用于多处理器系统（这点强于关中断）。 缺点：⚠️ 忙等待，无法实现"让权等待"，浪费 CPU。
★ 考过 2016、2018
b_114_12Swap 指令和 TS 指令有什么不同？ ★2考¶
用法：共享变量 lock 初值 false，每个进程有局部变量 key，每次进入前置为 true；执行 Swap(&lock,&key) 后 key 中保存 lock 的旧值： - key = false → 此前无人持锁，成功获得访问权 - key = true → 锁已被占用，继续循环等待
⚠️ 本质与 TS 指令相同：通过一次原子操作，既获取锁的当前状态，又把锁置为占用。 ⚠️ 说明：教材对 TS 和 Swap 的 C 描述仅为功能示意，实际由硬件逻辑实现，不会被中断。
★ 考过 2018、2023
b_115_6硬件指令法的三优两缺？¶
优点： - 实现简单，正确性易于验证 - ⚠️ 支持任意数量的进程，并适用于多处理器系统 - 系统中可存在多个临界区，只需为每个临界区分配独立的 lock 变量
缺点： - ⚠️ 忙等待，无法实现"让权等待" - ⚠️ 锁的获取顺序不确定，可能产生"饥饿"
💡 说明：这些代码并非实际编程接口，而是抽象模型 —— 真实系统中已封装在信号量、互斥锁等高级同步原语里。
b_115_9互斥锁（自旋锁）适合什么场景？¶
⚠️ acquire() 和 release() 的执行必须是原子操作，因此互斥锁通常采用硬件机制实现。
它也叫自旋锁，主要缺点是忙等待（同类的还有单标志法、TS 指令、Swap 指令）。
⚠️ 适用场景：多处理器系统 —— 一个线程可以在一个处理器上"旋转"，而不影响其他线程执行。 优点：等待锁期间没有上下文切换；若持有锁的时间较短，等待代价较低。
b_115_10；PDF 第 115 页 · b_115_11整型信号量为什么不好？ ★1考¶
用整型变量 S 表示某类资源的可用数量，只允许三种操作：初始化、wait、signal。
⚠️ 缺陷：S ≤ 0 时进程持续循环测试，处于忙等待 —— 未遵循"让权等待"，浪费 CPU，单 CPU 系统尤其低效。
★ 考过 2010
b_116_5记录型信号量的 wait/signal 怎么写？ ★2考¶
typedef struct{ int value; struct process *L; } semaphore;
void wait(semaphore S) { //申请资源
S.value--;
if (S.value < 0) { add this process to S.L; block(S.L); }
}
void signal(semaphore S) { //释放资源
S.value++;
if (S.value <= 0) { remove a process P from S.L; wakeup(P); }
}
- wait：先减 1；⚠️ 减完 < 0 说明资源已分配完，调用 block 自我阻塞并加入等待队列 S.L → 实现"让权等待"
- signal：先加 1；⚠️ 加完 ≤ 0 说明仍有进程在等待，调用 wakeup 唤醒一个
⚠️ 两个判断条件不一样：wait 判 < 0，signal 判 ≤ 0，这是最容易记反的地方。
★ 考过 2018、2023
b_116_12用信号量实现互斥的三条注意？ ★1考¶
⚠️ 两个进程竞争时 S 的取值只可能是 1、0、−1： - S = 1：两个进程都没进临界区 - S = 0：有一个进程正在临界区中 - S = −1：一个在临界区，另一个已阻塞在等待队列
三条注意： - 不同的临界资源应配置独立的互斥信号量 - ⚠️ P(S) 与 V(S) 必须成对出现 —— 缺 P(S) 无法互斥；缺 V(S) 资源永不释放，等待进程永久阻塞 - ⚠️ 若有多个同类资源，信号量初值应设为资源总数
★ 考过 2024
b_117_4用信号量实现同步，初值为什么是 0？ ★1考¶
⚠️ 初值 0 的含义：初始时 P2 所需的资源尚未满足，而该资源只能由 P1 的执行结果提供。
两种执行顺序都正确： - P1 先 V(S)：S 由 0 变 1；P2 执行 P(S) 时 S=1 有资源，减为 0 后不阻塞，直接执行 y - P2 先 P(S)：S 由 0 减为 −1，调用 block 阻塞；P1 执行 V(S) 后 S 由 −1 变 0，调用 wakeup 唤醒 P2
💡 PV 使用总口诀： - 同步问题：提供资源的行为之后 V，使用资源的行为之前 P - 互斥问题：⚠️ P、V 必须紧夹使用临界资源的那个行为，中间不得插入任何无关代码
★ 考过 2024
b_118_5前驱关系怎么用信号量表达？ ★2考¶
规则：为每条前驱边设置一个同步信号量，初值均为 0；前驱段执行完后 V 通知所有直接后继；后继段开始前 P 等待所有直接前驱。
教材例（S1→S2, S1→S3, S2→S4, S2→S5, S3→S6, S4→S6, S5→S6）：
semaphore a12=0,a13=0,a24=0,a25=0,a36=0,a46=0,a56=0;
S1(){ ...; V(a12); V(a13); }
S2(){ P(a12); ...; V(a24); V(a25); }
S3(){ P(a13); ...; V(a36); }
S4(){ P(a24); ...; V(a46); }
S5(){ P(a25); ...; V(a56); }
S6(){ P(a36); P(a46); P(a56); ...; } //三个前驱都要等
💡 数边即可：有几条箭头就设几个信号量，箭尾 V、箭头 P。
★ 考过 2020、2022
b_118_6分析同步互斥问题的三个步骤？¶
- ① 关系分析：识别参与并发的进程，厘清是互斥关系（竞争同一临界资源）、同步关系（要等对方结果）还是前驱关系（明确执行顺序约束）
- ② 思路梳理：确定关键同步点，初步规划 P、V 位置；类比典型场景（生产者-消费者、读者-写者、前驱图）
- ③ 信号量设置：定义信号量、明确语义与初值，把 P、V 嵌入适当位置，避免死锁与饥饿
💡 落代码前先分流：普通资源计数/前驱同步 → 基本 PV；请求路径取决于当前共享状态 → “辅助变量 + mutex + 资源信号量”；同类可并发、异类互斥 → 尝试读者—写者模板。
💡 每个动作再问四遍：①什么条件不满足会阻塞；②对应哪个信号量；③初值是多少；④谁在什么动作后 V 它。写完后检查 P/V 是否守恒、是否持有 mutex 再等待其他资源、是否可能饥饿。
b_119_1生产者-消费者要设哪三个信号量？ ★8考¶
约束条件：缓冲区未满生产者才能写；缓冲区非空消费者才能读；缓冲区是临界资源必须互斥访问。
三个信号量： - mutex = 1：控制对缓冲区的互斥访问 - empty = n：记录空缓冲区的数量 - full = 0：记录满缓冲区的数量
⚠️ 关系分析的关键：生产者与消费者对缓冲区既是互斥关系（共享临界资源），又是同步关系（消费者必须等生产者生产）。 ⚠️ 必须严格控制 P 和 V 的执行顺序，以避免死锁。
★ 考过 2009、2011、2013、2014、2015、2017、2019、2025
b_119_4生产者-消费者的标准代码？¶
semaphore mutex=1, empty=n, full=0;
producer(){ while(1){
生产一个产品
P(empty); //要用什么，P 一下
P(mutex); //互斥夹紧
将产品放入缓冲区
V(mutex); //互斥夹紧
V(full); //提供什么，V 一下
}}
consumer(){ while(1){
P(full); P(mutex);
从缓冲区取出一个产品
V(mutex); V(empty);
消费产品
}}
💡 王道口诀："要用什么 P 一下，提供什么 V 一下，互斥夹紧"。
b_120_0为什么 P(empty) 必须在 P(mutex) 之前？ （死锁陷阱）¶
⚠️ 顺序颠倒会死锁。
反例：缓冲区已满（empty=0）时，若生产者先 P(mutex) 拿到锁，再 P(empty) 被阻塞 —— 此时消费者想取产品，却因 mutex 被生产者持有而进不了临界区，执行不了 P(full) 和消费操作。 结果：生产者等消费者腾空位，消费者等生产者放 mutex，互相阻塞。
同理，缓冲区为空（full=0）时消费者先 P(mutex) 也会死锁。
💡 结论一句话：必须先申请资源状态（empty/full），再申请互斥访问（mutex） —— 确保进程不会在持有互斥锁的同时等待资源。
b_120_2吃水果问题为什么不能只用一个 full？¶
题目：盘子最多放一个水果；爸爸放苹果、妈妈放橘子；女儿只吃苹果、儿子只吃橘子。
关系分析：爸爸和妈妈之间互斥；爸爸↔女儿、妈妈↔儿子分别是同步关系；⚠️ 儿子和女儿之间既无互斥也无同步（各等各的水果）。
⚠️ 关键点：不同类型的产品要由不同的消费者消费，所以不能只用一个 full 表示满状态，必须为每种产品设置独立的同步信号量。
信号量：plate=1（盘子互斥）、apple=0、orange=0。
b_120_5吃水果问题的代码和 V(plate) 的位置？¶
semaphore plate=1, apple=0, orange=0;
dad(){ while(1){ 准备苹果; P(plate); 放入苹果; V(apple); }}
mom(){ while(1){ 准备橘子; P(plate); 放入橘子; V(orange); }}
son(){ while(1){ P(orange); 取出橘子; V(plate); 吃; }}
daughter(){ while(1){ P(apple); 取出苹果; V(plate); 吃; }}
⚠️ 注意 V(plate) 在孩子进程里，不在父母进程里 —— 只有当女儿拿走苹果或儿子拿走橘子之后，才释放盘子供下一次使用。
💡 因此 dad() 和 daughter()、mom() 和 son() 必须成对执行。
b_121_1；PDF 第 121 页 · b_121_6读者-写者问题的四条要求和三个信号量？¶
四条要求：允许多个读者同时读；任一时刻只允许一个写者写；写者写时不允许任何其他读者或写者访问；写者开始前必须等所有已进入的读者和写者退出。
关系分析：读者↔写者互斥；写者↔写者互斥；读者↔读者不互斥可并发。
💡 陌生题识别法：先画“同类/异类关系矩阵”。若某类内部可并发，而它与另一类互斥，就把前者视作“读者”、后者视作“写者”；若同类内部还有容量上限，再叠加计数信号量。
信号量： - count = 0：⚠️ 记录当前读者数量的计数器（这是本题的灵魂） - mutex = 1：控制对 count 的互斥访问 - rw = 1：控制读者与写者对文件的互斥访问
💡 解题思想：第一个读者进来时阻塞写者，最后一个读者离开时释放写者。
💡 count 只负责选择“第一人/最后一人”路径，本身不会让进程睡眠；它是可修改的共享变量，所以检查和增减必须由 mutex 保护，真正阻塞仍由 rw 完成。
b_121_3读者优先的代码？它有什么问题？¶
int count=0; semaphore mutex=1, rw=1;
writer(){ while(1){ P(rw); 写文件; V(rw); }}
reader(){ while(1){
P(mutex);
if(count==0) P(rw); //第一个读者，阻止写者
count++;
V(mutex);
读文件;
P(mutex);
count--;
if(count==0) V(rw); //最后一个读者，放行写者
V(mutex);
}}
⚠️ 问题：写者饥饿 —— 只要已有读者在读，后续读者都能立即进入，写者要等所有读者退出；读者持续到达时，写者可能被无限期推迟。
b_122_1；PDF 第 122 页 · b_122_3写者优先靠哪个信号量？为什么读者要提前 V(w)？¶
在读者优先基础上增加互斥信号量 w = 1，作用是控制所有进程进入"准备访问文件"阶段的权限（相当于"门卫"）：
writer(){ while(1){ P(w); P(rw); 写文件; V(rw); V(w); }}
reader(){ while(1){
P(w); //有写者持有或等待 w 时，新读者被挡住
P(mutex);
if(count==0) P(rw);
count++;
V(mutex);
V(w); //立即释放 w
读文件;
P(mutex); count--; if(count==0) V(rw); V(mutex);
}}
⚠️ 读者为什么在更新 count 后立即 V(w)：只要存在活跃读者（count>0），写者已被 rw 阻塞，提前释放 w 可避免不必要地阻碍其他进程。
⚠️ 它只是相对优先，不是绝对优先：若多个进程同时阻塞在 w 上，谁先被唤醒取决于信号量实现；只有题设明确采用 FIFO 等待/唤醒时，才能据到达次序讨论“公平”。本质是在防止写者饥饿的前提下给予有限优先。
💡 通用解题启发：读者-写者问题的关键是"受互斥保护的计数器 count" —— 复杂同步问题可考虑引入计数器动态判断资源状态。
b_123_0；PDF 第 123 页 · b_123_1哲学家进餐问题为什么会死锁？¶
semaphore chopstick[5]={1,1,1,1,1};
Pi(){ do{
P(chopstick[i]); //拿左侧筷子
P(chopstick[(i+1)%5]); //拿右侧筷子
进餐;
V(chopstick[i]); V(chopstick[(i+1)%5]);
思考;
} while(1); }
⚠️ 死锁场景：5 名哲学家同时饥饿，几乎同时执行完 P(chopstick[i]) —— 每人各持一根左筷、都在等右筷 → 循环等待 → 全部阻塞。
编号约定：哲学家 0~4，第 i 位左筷编号 i，右筷编号 (i+1)%5。
b_123_3防止哲学家死锁的三种办法？¶
- ① 限制最多 4 名哲学家同时尝试进餐 —— 确保至少有一人能拿到两根筷子，从而打断五人首尾相接的循环等待
- ② 奇数号先拿左筷再拿右筷，偶数号相反 —— ⚠️ 打破循环等待条件
- ③ 仅当左右两根筷子都空闲时，才允许同时拿起
⚠️ 校订/边界：①、②都通过不同方式破坏循环等待；③要求两根同时可得，本质上避免“先占一根再等另一根”的请求并保持。
b_124_0哲学家问题的"同时拿两根"怎么写？¶
semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex=1; //取筷子的信号量
Pi(){ do{
P(mutex); //整个"取筷"动作互斥
P(chopstick[i]); //拿左筷
P(chopstick[(i+1)%5]); //拿右筷
V(mutex);
进餐;
V(chopstick[i]); V(chopstick[(i+1)%5]);
思考;
} while(1); }
⚠️ 关键在 mutex 把“取筷流程”串行化：某位哲学家可以先拿到左筷、再在持有 mutex 时等待右筷；因此它并不保证“两根同时获得或一根也不占”。它真正保证的是不会有多名哲学家并发形成首尾相接的取筷环。
⚠️ 校订/边界：若题目明确要求“要么两根同时取得，要么一根也不拿”，应使用能原子检查两根状态的方案，而不是仅用上述 mutex 包住两个 P 操作。
💡 哲学家问题的本质是预防循环等待。
b_124_52.3.6 管程¶
引入管程是为了解决信号量的什么问题？ ★1考¶
信号量机制下每个进程都要自行编写 P/V 操作 —— 分散的同步代码增加编程复杂度，且极易因操作顺序不当引发死锁。
管程的两个改进： - 把共享资源及其操作封装于一体，自动保证互斥访问，程序员无须显式编写互斥代码 - 通过条件变量实现灵活的进程同步，降低死锁风险
★ 考过 2016
b_124_9管程由哪四部分组成？¶
- ① 管程的名称
- ② 局部于管程内部的共享数据结构说明
- ③ 对该数据结构进行操作的一组过程（函数）
- ④ 对共享数据进行初始化的语句
两个基本特性（与"类"高度相似）： - 封装性：⚠️ 内部共享数据只能被管程自身的过程访问，外部进程必须调用这些过程 - 互斥性：⚠️ 任一时刻仅允许一个进程执行管程内的过程 —— 这由编译器自动保证
b_125_2；PDF 第 125 页 · b_125_11管程和进程的六点区别？¶
| 维度 | 进程 | 管程 |
|---|---|---|
| 数据结构 | 私有（如 PCB） | 公共（如缓冲区） |
| 任务 | 通用计算 | 同步控制与资源管理 |
| 引入目的 | 实现并发 | 解决共享资源的互斥访问 |
| 主被动 | 主动执行的实体 | ⚠️ 被动调用的模块 |
| 并发性 | 多个进程可并发执行 | ⚠️ 对同一管程的多个调用是互斥的 |
| 生命周期 | 动态（创建到撤销） | ⚠️ 静态资源管理模块 |
b_125_11为什么必须有条件变量？¶
⚠️ 因为进程进入管程后若因条件不满足要等待，它必须释放对管程的占用 —— 否则其他进程无法进入管程，系统停滞。
两种操作： - x.wait()：条件不满足时把自己加入 x 的等待队列，并自动释放管程 - x.signal()：条件可能已满足时唤醒一个阻塞在 x 上的进程
⚠️ 管程中可以设置多个条件变量（不同阻塞原因分别抽象），每个条件变量维护一个等待队列。
b_126_0；PDF 第 126 页 · b_126_1条件变量和信号量的区别？¶
- 相似点：wait/signal 与 P/V 都能实现进程的阻塞与唤醒
- ⚠️ 不同点：信号量有整数值，反映可用资源数量；条件变量不维护数值，仅用于排队和通知 —— 在管程中资源数量由共享变量（如 S）显式记录，条件变量只负责同步
💡 一句话：信号量既记账又排队，条件变量只排队。
b_126_52.4 死锁¶
死锁的定义和典型例子？¶
死锁：多个进程因竞争资源而陷入相互等待的僵局 —— 每个进程都在等待其他进程所占有的资源，而这些资源不会被释放，形成循环等待链，所有进程被永久阻塞。
💡 生活类比：窄巷两端各驶入一辆车，都不肯倒车，彼此阻挡。 💡 系统例子：只有一台打印机和一台扫描仪，P1 占扫描仪要打印机，P2 占打印机要扫描仪。
b_162_1死锁和饥饿的两点区别？¶
| 对比 | 死锁 | 饥饿 |
|---|---|---|
| 进程数量 | ⚠️ 必须涉及两个或更多进程，且有循环等待 | ⚠️ 可以只影响单个进程 |
| 进程状态 | ⚠️ 必定处于阻塞态 | 可能就绪态（如 SPF 下长期拿不到 CPU），也可能阻塞态 |
饥饿的根源：资源分配策略不公平，无法保证"等待时间有上界"。例：打印调度用最短作业优先，长文件请求可能永远排不上。
⚠️ 饥饿时系统可能仍在正常运行，只是个别进程被持续忽略；共同点是相关进程都无法顺利推进。
b_162_6；PDF 第 162 页 · b_162_9死锁产生的两大原因？ ★2考¶
- 系统资源的竞争：⚠️ 死锁的发生与不可剥夺资源密切相关（打印机、磁带机）；对可剥夺资源（如 CPU 时间片），系统可强制回收，单纯竞争这类资源一般不会死锁
- 进程推进顺序非法：即使资源充足，请求和释放顺序不合理仍可能死锁（P1 占 R1 要 R2，P2 占 R2 要 R1）
⚠️ 还有一种易忽略的情形：同步机制使用不当 —— A 等 B 的消息、B 等 A 的消息；消息通道或同步对象可视为一种逻辑资源。
★ 考过 2009、2014
b_162_10死锁的四个必要条件？¶
- 互斥条件：资源要求排他性使用
- 不可剥夺条件：已获得的资源用完前不能被强行剥夺，只能主动释放
- 请求并保持条件：持有至少一个资源的同时又请求新资源，被阻塞时对已占有的资源保持不放
- 循环等待条件：存在进程集合，每个进程等待的资源正被下一个进程占有，形成环
💡 教材类比：别人不能抢走你手上的苹果 = 不可剥夺；你攥着第一个苹果去要第二个 = 请求并保持。
⚠️ 只要任一条件不成立，死锁就不可能发生。
b_163_1资源分配图有环就一定死锁吗？¶
⚠️ 不一定。
根本原因：某类资源有多个实例时，即使图中有环，系统仍可能通过资源重分配打破僵局 —— 教材例：输出设备有两个实例，P0 和 PK 各持一台，只要任一方释放，等待者即可获得资源，环被解除。
💡 结论要背准： - 每类资源只有一个实例时，环是死锁的充分必要条件 - 否则，环的存在仅表明潜在风险，未必实际死锁
b_163_8死锁的三种处理策略？¶
- 预防死锁：设置严格限制条件，破坏四个必要条件中的一个或多个
- 避免死锁：动态分配时判断分配后是否仍处于安全状态，安全才分配
- 检测及解除死锁：不加限制，定期运行检测算法，发现后终止部分进程或剥夺资源
⚠️ 还有第三种态度：完全忽略死锁问题 —— 大多数通用操作系统（Linux、Windows）采用这种策略。
⚠️ 预防和避免都属于事前防范：预防限制严格、实现简单，但效率和资源利用率低；避免限制宽松，但每次分配都要算，实现复杂。
b_163_11三种死锁处理策略的优缺点对照？¶
| 资源分配策略 | 主要优点 | 主要缺点 | |
|---|---|---|---|
| 死锁预防 | 保守，宁可资源闲置 | 无须运行时检测，实现简单 | 资源利用率低；剥夺可能频繁；不适用于动态请求 |
| 死锁避免 | 预防和检测的折中（运行时判断） | 无须资源剥夺，利用率较高 | ⚠️ 须预知最大资源需求；进程可能被无限期推迟 |
| 死锁检测 | 宽松，只要允许就分配 | 不限制申请，无启动延迟 | 检测与解除有额外开销；终止或剥夺导致工作丢失 |
b_164_2破坏互斥和破坏不可剥夺可行吗？ ★1考¶
- 破坏互斥条件：对打印机、磁带机等本质不可共享资源通常不可行；但对只读/可重入资源，或经 SPOOLing 虚拟化后的逻辑设备，可以通过设计消除原来的物理互斥
- 破坏不可剥夺条件：请求新资源失败时强制释放已占有的全部资源；⚠️ 实现复杂、代价高昂 —— 强制释放打印机可能使已完成的工作失效甚至设备状态混乱；频繁申请释放增加开销、延长周转时间、降低吞吐量；实际系统中极少采用
★ 考过 2019 [校订/边界] “破坏互斥不可行”只适用于本质不可共享资源，不能扩大到所有资源。
b_164_5破坏请求并保持的两种做法？¶
- 静态资源分配：⚠️ 运行前一次性申请全部资源，不满足就不投入运行，运行期不再提新请求
- 优点实现简单；⚠️ 缺点：资源浪费严重（末期才用甚至从未用的资源被长期占着）、易引发饥饿
- 动态释放后申请：获得初期资源即可开始执行，但必须先释放所有已用完的资源，才能申请新资源
b_164_12资源有序分配法怎么破坏循环等待？¶
规则：为每类资源赋予唯一编号，进程必须按编号递增的顺序请求，且同类资源须一次性申请 —— 即只有在未持有任何资源、或仅持有较小编号资源时，才能申请更大编号的资源。
⚠️ 为什么有效：任何已持有大编号资源的进程都无法再申请小编号资源 → 资源分配图中不可能出现环。
三个缺点： - 资源编号需相对稳定，不利于新增设备类型 - ⚠️ 实际使用顺序可能与编号次序不一致 → 资源提前占用而长期闲置 - 增加了用户编程的复杂性
b_164_16什么是安全状态和安全序列？ ★1考¶
安全状态：存在一个进程执行序列 (P1,…,Pn)，使得对每个 Pi，在它之前的进程全部执行完并释放资源后，系统仍有足够的可用资源满足 Pi 的尚需资源量（最大需求 − 已分配） —— 这样的序列称为安全序列（可能存在多个）。找不到任何安全序列则为不安全状态。
⚠️ 三句话必须背准： - 系统处于安全状态时，一定不会发生死锁 - 处于不安全状态时，死锁可能发生，但并非必然发生 - 死锁发生时，系统必定处于不安全状态
★ 考过 2018
b_165_612 台磁带机那道经典例题？¶
P1/P2/P3 最大需求 10/4/9，已分配 5/2/2，可用 3。
T0 时刻安全，安全序列 (P2, P1, P3)： - 可用 3 ≥ P2 尚需 2 → P2 完成，释放 4，可用变 5 - 5 ≥ P1 尚需 5 → P1 完成，释放 10，可用变 10 - 10 ≥ P3 尚需 7 → P3 完成
⚠️ 若再分配 1 台给 P3（P3 已分配变 3，可用降为 2）→ 进入不安全状态： 把剩下 2 台给 P2 → P2 完成释放 4，可用 4；但 P1 尚需 5、P3 尚需 6，都不满足 → 相互等待，最终死锁。
💡 解题模板：每轮找一个 Need ≤ Available 的进程，让它跑完并归还 Allocation，反复直到全部完成。
b_165_4；PDF 第 165 页 · b_165_8银行家算法的四个数据结构？ ★2考¶
设 n 个进程、m 类资源： - Available：长度 m 的向量，当前各类可用资源数 - Max：n×m 矩阵，每个进程对各类资源的最大需求 - Allocation：n×m 矩阵，已分配给每个进程的资源数 - Need：n×m 矩阵，每个进程尚需的资源数
⚠️ 核心关系式：Need[i,j] = Max[i,j] − Allocation[i,j]
⚠️ 前提条件：每个进程运行前必须声明最大需求量，且该最大需求量在整个生命周期内不得更改（否则银行家算法的安全性保证失效），总量不得超过系统资源总量。
💡 比喻：操作系统 = 银行家，资源 = 资金，进程请求资源 = 用户申请贷款。
★ 考过 2013、2019
b_165_14银行家算法的四个检查步骤？¶
设 Request_i 是 Pi 的资源请求向量： - ① 合法性检查：Request_i ≤ Need[i]？否则非法请求（申请量超过预先声明的最大需求） - ② 资源可用性检查：Request_i ≤ Available？否则资源不足，Pi 必须等待 - ③ 试探性分配： Available −= Request_i；Allocation[i] += Request_i；Need[i] −= Request_i - ④ 安全性检查：执行安全性算法；⚠️ 安全则正式确认分配，不安全则撤销分配、恢复各数据结构原值，让 Pi 等待
💡 做题时第一步永远是由 Max − Allocation 算出 Need 矩阵。
b_166_0；PDF 第 166 页 · b_166_1安全性算法的四步怎么跑？¶
- ① 设两个向量：Work（长度 m，初值 = Available）、Finish（长度 n 的布尔向量，初值全 false）
- ② 找一个同时满足 Finish[i] = false 且 Need[i] ≤ Work 的进程
- ③ 找到则：Work = Work + Allocation[i]；Finish[i] = true，返回步骤 ②
- ④ 全部 Finish[i] = true → 安全状态；否则不安全
💡 直觉：先让"要得最少的人"跑完还钱，钱变多了再让下一个人跑。
b_166_15；PDF 第 166 页 · b_166_16安全性算法的经典例题（5 进程 3 类资源）？ ★5考¶
总量 A/B/C = 10/5/7，T0 时 Available = (3,3,2)：
| 进程 | Max | Allocation | Need |
|---|---|---|---|
| P0 | 7 5 3 | 0 1 0 | 7 4 3 |
| P1 | 3 2 2 | 2 0 0 | 1 2 2 |
| P2 | 9 0 2 | 3 0 2 | 6 0 0 |
| P3 | 2 2 2 | 2 1 1 | 0 1 1 |
| P4 | 4 3 3 | 0 0 2 | 4 3 1 |
Work 变化：(3,3,2) →P1→ (5,3,2) →P3→ (7,4,3) →P4→ (7,4,5) →P2→ (10,4,7) →P0→ (10,5,7)
安全序列 {P1, P3, P4, P2, P0}，系统处于安全状态。
⚠️ 初始时 P1(1,2,2) 和 P3(0,1,1) 都满足条件，选谁都行 —— 安全序列可能不唯一。
★ 考过 2011、2012、2018、2020、2022
b_167_1P1 请求 (1,0,2) 时怎么判？（批准的例子）¶
- ① Request₁(1,0,2) ≤ Need₁(1,2,2) ✓
- ② Request₁(1,0,2) ≤ Available(3,3,2) ✓
- ③ 试探分配：Available=(2,3,0)，Allocation₁=(3,0,2)，Need₁=(0,2,0)
- ④ 安全性检查：Work 从 (2,3,0) 出发 → 安全序列 {P1, P3, P4, P0, P2} → 安全
结论：正式批准分配。
⚠️ 注意这次的安全序列 {P1,P3,P4,P0,P2} 与 T0 时刻的 {P1,P3,P4,P2,P0} 不同 —— 分配会改变后续可行顺序。
b_168_0P4 请求 (3,3,0) 和 P0 请求 (0,2,0) 为什么都被拒？¶
P4 请求 (3,3,0) —— 卡在第 ② 步： - 合法性 (3,3,0) ≤ Need₄(4,3,1) ✓ - ⚠️ 可用性 (3,3,0) > Available(2,3,0) ✗ → 资源不足，让 P4 等待
P0 请求 (0,2,0) —— 卡在第 ④ 步： - 合法性 ✓、可用性 (0,2,0) ≤ (2,3,0) ✓ - 试探分配后 Available=(2,1,0)，Allocation₀=(0,3,0)，Need₀=(7,2,3) - ⚠️ Available(2,1,0) 无法满足任何进程的尚需资源 → 不安全 → 拒绝请求，撤销试探性分配，恢复原状态
💡 这两例正好演示了两种不同的拒绝理由：一个是"现在没货"，一个是"给了会出事"。
b_168_11死锁避免和死锁检测的根本区别？ ★1考¶
- 死锁避免：要求始终确保系统不进入死锁状态 → ⚠️ 需要进程预先声明对每类资源的最大需求 Max
- 死锁检测：仅判断当前时刻是否已发生死锁 → ⚠️ 无须预知未来请求，只依据当前的资源分配和请求情况
💡 一句话：避免是"提前算好不出事"，检测是"出事了再说"。
⚠️ 校订/边界：银行家算法不要求预知未来每一次请求的时刻和顺序，只需最大需求、当前分配与当前可用量。
★ 考过 2015
b_169_5资源分配图怎么画？ ★2考¶
- 圆圈 = 进程，矩形框 = 一类资源；⚠️ 某类资源有多个实例时，框内用多个圆点表示
- 请求边：从进程指向资源，表示申请一个单位
- 分配边：从资源指向进程，表示一个实例已分配给它
⚠️ 空闲资源数的算法：该类资源总数 − 已分配实例数（即资源节点发出的分配边数量）。
💡 获取顺序题先画图：进程已经占有的资源画“资源→进程”，下一步申请画“进程→资源”；若所有等待边首尾闭合，再结合每类资源实例数判断环是否已经构成死锁。
★ 考过 2016、2021
b_169_10资源分配图的化简步骤和死锁定理？¶
- ① 找一个所有资源请求都能被当前空闲资源满足的进程 Pi，删除它的全部请求边和分配边，使之成为孤立节点
- ② 它释放的资源可能使其他阻塞进程转为可执行，重复上述过程
- ③ 若最终能删除图中所有边，则称该图可完全简化
死锁定理：系统处于死锁状态，当且仅当其资源分配图不可完全简化。
教材例：R1 总数 3、出度 3 → 无空闲；R2 总数 2、出度 1 → 有 1 个空闲 → P1 只请求 1 个 R2，可继续执行；P1 释放 R1 后 P2 的请求也能满足。
⚠️ 经化简后仍有边相连的进程，就是死锁进程。
b_170_2；PDF 第 170 页 · b_170_8解除死锁的三种方法？ ★1考¶
- 资源剥夺法：挂起部分死锁进程，抢占其资源重新分配；⚠️ 需防止被挂起的进程长期得不到资源而饥饿
- 撤销进程法：强制终止部分或全部死锁进程并回收资源；终止顺序按优先级或撤销代价（资源占有量等）；⚠️ 实现简单但代价可能很高 —— 接近完成的进程被终止，已完成的工作全部丢失
- 进程回退法：让死锁进程回退到之前某个足以回避死锁的状态，回退中自愿释放资源；⚠️ 需记录历史状态并设置还原点，实现较复杂
★ 考过 2019
b_170_4【疑难点】第2章¶
进程和程序的四点区别？¶
- 进程是动态概念（一次执行活动），程序是静态实体（一组有序指令的集合）；⚠️ 脱离程序，进程便无意义
- 进程有生命周期、暂时存在；程序可长期保存、永久存在
- ⚠️ 一个进程通常执行一个程序，而一个程序可被多个进程并发执行；进程能创建新进程，程序不能
- 组成不同：进程 = 程序 + 数据 + PCB
b_187_3同步和互斥各体现什么关系？¶
并发进程的两类制约关系： - 互斥 = 竞争关系：竞争使用临界资源，必须互斥访问 - 同步 = 协作关系：协同完成任务，在关键点等待对方的信号以协调执行
b_187_10【易混点】第2章成对概念对照¶
| 概念 A | 概念 B | 一句话切分 |
|---|---|---|
| 进程 | 程序 | 动态、有生命周期、含 PCB vs 静态指令集合 |
| 进程 | 线程 | 资源分配单位 vs CPU 调度单位 |
| 程序段 | 数据段 | 静态可共享 vs 每进程私有 |
| 就绪态 | 阻塞态 | 只缺 CPU vs 缺其他资源或等事件 |
| 运行→阻塞 | 阻塞→就绪 | 主动（自己发系统调用） vs 被动（等中断处理程序） |
| 创建态 | 终止态 | 短暂中间态 vs 不再调度但 PCB 暂留 |
| 用户级线程 | 内核级线程 | 内核看不见、切换快、一阻全阻 vs 内核可见、能多核并行、切换慢 |
| 多对一 / 一对一 / 多对多 | — | 快但不能并行 / 能并行但开销大 / 折中 |
| 共享存储 | 消息传递 | OS 只映射内存，同步要自己做 vs 发送/接收原语封装在内核 |
| 直接通信 | 间接通信 | 指定接收进程 vs 投递到信箱 |
| 高级调度 | 中级调度 | 外存→内存，只一次 vs 对换，挂起态 |
| 调度 | 切换 | 决策：给谁 vs 执行：真正转移 CPU |
| 模式切换 | 上下文切换 | 同一进程内、用户态↔内核态 vs 换进程、必在内核态完成 |
| 周转时间 | 带权周转时间 | 完成−提交 vs 周转 ÷ 实际运行 |
| FCFS | SJF | 利于长作业、CPU 繁忙型 vs 平均周转最优但长作业饥饿 |
| 饥饿 | 死锁 | 可以只一个进程、可就绪态 vs 至少两进程、必阻塞态、循环等待 |
| 空闲让进/忙则等待/有限等待 | 让权等待 | 前三条硬性 vs 第四条原则上应遵循但非必须 |
| 双标志先检查 | 双标志后检查 | 同时进入（违反忙则等待） vs 同时卡死（违反空闲让进） |
| TS 指令 | 关中断 | 共享 lock，适用于多处理器 vs 只对本 CPU 有效 |
| 整型信号量 | 记录型信号量 | 忙等待 vs block/wakeup，实现让权等待 |
| wait 判 S<0 | signal 判 S≤0 | 减完为负才阻塞 vs 加完非正说明还有人等 |
| P(empty) 在前 | P(mutex) 在前 | 正确 vs 死锁 |
| 读者优先 | 写者优先 | 写者饥饿 vs 靠信号量 w 挡新读者（相对优先） |
| 信号量 | 条件变量 | 有整数值记录资源数 vs 无值，只排队和通知 |
| 死锁预防 | 死锁避免 | 破坏必要条件、静态限制 vs 动态判断安全状态 |
| 死锁避免 | 死锁检测 | 需预知全部最大需求 vs 只看当前分配与请求 |
| 安全状态 | 不安全状态 | 一定不死锁 vs 可能死锁但不必然 |
【必背数字】第2章¶
| 数字 | 含义 |
|---|---|
| 三部分 | 进程实体 = 程序段 + 数据段 + PCB（PCB 是存在的唯一标志） |
| 四类信息 | PCB：标识 / 调度 / 资源内存 / 处理机状态 |
| 五种状态 | 运行、就绪、阻塞、创建、终止（前三种为基本状态） |
| PID = 1 / PID = 0 | Linux 的 init 进程 / 闲逛进程 |
| 约 30 种、32 位向量 | Linux 信号种类 / PCB 中记录待处理信号的位向量 |
| SIGILL = 4 | 非法指令信号 |
| 64KB | Linux 管道内核环形缓冲区典型大小 |
| 三级调度 | 高级（作业）、中级（内存/对换）、低级（进程，频率最高） |
| 周转 = 完成 − 提交；带权 = 周转 ÷ 运行 | 调度计算两大公式 |
| 响应比 = (等待 + 运行) ÷ 运行 | 高响应比优先 |
| 2 倍 | 多级反馈队列第 i+1 级时间片是第 i 级的 2 倍 |
| 四条准则 | 空闲让进、忙则等待、有限等待、让权等待 |
| mutex=1, empty=n, full=0 | 生产者-消费者三信号量初值 |
| plate=1, apple=0, orange=0 | 吃水果问题三信号量初值 |
| count=0, mutex=1, rw=1（+w=1） | 读者-写者信号量（写者优先加 w） |
| 5 根筷子，最多允许 4 人同时取 | 哲学家进餐 |
| 四个必要条件 | 互斥、不可剥夺、请求并保持、循环等待 |
| Need = Max − Allocation | 银行家算法核心关系式 |
| {P1,P3,P4,P2,P0} | 教材 T0 时刻安全序列（Available=(3,3,2)） |