第 2 章 进程与线程（进程、调度、同步与死锁）
本章地位：进程是操作系统的心脏，本章是 408 全卷分值最重、大题最密的一章：操作系统部分约 25 分中通常占 8～14 分，且几乎每年都有一道 P/V 大题或调度计算大题落在这一章。真题集中在四个方向：① 状态转换判断（五态 / 七态，选择题高频）；② 调度算法计算（甘特图 + 周转时间，FCFS/SJF/HRRN/RR/多级反馈队列）；③ P/V 操作设计（生产者-消费者家族：读者-写者、哲学家、苹果-橘子——背模板 + 现场分析）；④ 银行家算法（安全序列 + 请求试分配）。本章按「概念 → 调度 → 同步 → 死锁」四条主线展开，所有大题都配完整推演过程。
| 考点 | 常考题型 | 热度 | 掌握标准 |
|---|---|---|---|
| 进程状态转换（五态 / 七态） | 选择题 | ★★★★★ 几乎必考 | 每条边的触发事件 + 不可能的转换 + 挂起 / 激活 |
| 调度算法计算 | 选择题 + 大题 | ★★★★★ | 甘特图 + 周转 / 带权周转 / 等待时间三指标；HRRN 响应比代数计算 |
| P/V 操作（同步互斥设计） | 大题（代码） | ★★★★★ 每年必考大题 | 互斥夹紧 / 同步前后 / 先同步后互斥三模板 |
| 银行家算法 | 大题 / 选择 | ★★★★ | Need 矩阵、安全性算法、请求试分配三步全流程 |
| 进程通信方式 | 选择题 | ★★★★ | 共享内存 / 消息传递 / 管道 / 信号的特性对比 |
| 线程与多线程模型 | 选择题 | ★★★★ | 用户级 / 内核级区别、多对一 / 一对一 / 多对多 |
| 死锁条件与预防 | 选择题 | ★★★★ | 四必要条件、破坏手段与代价、资源分配图化简 |
| PCB 与进程控制原语 | 选择题 | ★★★ | PCB 三类信息、五种原语步骤、原语运行于核心态 |
2.1 进程的概念、组成与组织
- 动态性：进程是执行过程，有生命周期（创建→运行→消亡），这是与程序最本质的区别；
- 并发性：多个进程实体同存于内存，在一段时间内同时运行；
- 独立性：进程是独立获得资源、独立接受调度的基本单位；
- 异步性：进程按各自独立的、不可预知的速度推进——由此引出同步问题；
- 结构性：进程实体 = PCB + 程序段 + 数据段。
2.1.1 进程 vs 程序：动态与静态
2.1.2 PCB：进程存在的唯一标志
- 进程标识信息：进程 ID（PID）、父进程 ID、用户 ID（UID）；
- 现场信息（处理机上下文）：程序计数器 PC、程序状态字 PSW、通用寄存器、用户栈指针——进程让出 CPU 时保存现场于此，重新运行时恢复；
- 控制信息：进程状态、优先级、程序与数据在内存 / 外存的起始地址、进程同步与通信机制、资源清单（打开文件、设备）、链接指针（挂入各种队列用）。
② 「进程实体（进程映像）= PCB + 程序段 + 数据段」，而 PCB 是进程存在的唯一标志——两句都是高频判断点；
③ 现场信息（寄存器内容）保存在 PCB 里，不是保存在栈或程序段里。
2.1.3 进程的组织：就绪队列与阻塞队列
- 链接方式：具有同一状态的 PCB 链成队列——一个就绪队列（可按优先级分多个）+ 多个阻塞队列（按等待原因分：等待 I/O 队列、等待某事件队列……）；
- 索引方式：系统建立若干索引表（就绪表、阻塞表），表项指向 PCB；
- 线性方式：所有 PCB 放一张线性表中（早期系统，效率低）。
下列关于进程与程序的说法中，错误的是（ ）
A. 进程是动态的，程序是静态的 B. 一个进程可以执行多个程序，一个程序也可对应多个进程
C. 进程就是程序，程序就是进程 D. 进程有生命周期，程序可以长期保存
查看解答
C。A 对：动态性是两者最本质区别；B 对：进程运行中可以 exec 新程序段，同一程序（如 ls）可被多次执行产生多个进程；D 对：程序是文件，可长期存于外存。C 混淆了动静概念，错误。
(1) 下列信息中，不属于 PCB 保存内容的是（ ）
A. 进程优先级 B. 程序计数器 PC 的值 C. 进程对应的源程序代码本身 D. 打开文件列表
(2) 判断：操作系统通过 PCB 感知进程的存在；PCB 中保存的现场信息用于进程切换时保存 / 恢复 CPU 上下文。
查看解答
(1) C。PCB 保存的是控制信息（优先级、文件列表等）与现场信息（PC、寄存器），但代码本身存放在进程地址空间的程序段，PCB 里只存代码的起始地址。
(2) 对。这正是「PCB 是进程存在的唯一标志」与现场信息作用的准确表述。
2.2 进程的状态与转换 高频考点
2.2.1 五态模型：每条边的触发事件
- 创建态（New）：OS 正在为进程分配资源、初始化 PCB，尚未完成；
- 就绪态（Ready）：除 CPU 外的一切资源都已就绪，万事俱备只欠调度；
- 运行态（Running）：正在 CPU 上执行（单核系统任一时刻最多一个）；
- 阻塞态（Waiting/Blocked，又称等待态）：因等待某事件（I/O 完成、资源到达）而暂停运行，即使把 CPU 给它也无法执行；
- 终止态（Terminated）：正在善后（释放资源、撤销 PCB），或等待父进程 / OS 收集信息。
| 转换 | 触发事件 | 主动 / 被动 |
|---|---|---|
| 创建态 → 就绪态 | OS 完成创建工作：分配内存等资源（不含 CPU）、初始化 PCB、插入就绪队列 | OS 操作 |
| 就绪态 → 运行态 | 被进程调度选中，获得 CPU——进入运行态的唯一路径 | 被动（被调度） |
| 运行态 → 就绪态 | 时间片用完；剥夺式调度下被更高优先级进程抢占 | 被动（与自身请求资源无关！） |
| 运行态 → 阻塞态 | 请求某资源（如打印机）暂不可得、启动 I/O 后等待完成、等待某事件发生——进程主动调用阻塞原语 | 主动（是进程自身的请求行为） |
| 阻塞态 → 就绪态 | 所等待的事件发生（I/O 完成由中断处理程序触发唤醒原语），进程被插入就绪队列——不会直接进入运行态 | 被动（别的进程 / 中断唤醒它） |
| 运行态 → 终止态 | 正常结束（exit）；异常（越界、除零）；被父进程或 OS 终止 | —— |
② 阻塞→运行 不可能：唤醒只把你送回就绪队列，必须再等调度；
③ 运行→阻塞是主动行为、阻塞→就绪是被动行为——方向背反是最常见的坑；
④ 「时间片用完」是运行→就绪（回到就绪队列重新排队），不是阻塞。
(1) 下列进程状态转换中，不可能发生的是（ ）
A. 运行态 → 就绪态 B. 运行态 → 阻塞态 C. 就绪态 → 运行态 D. 就绪态 → 阻塞态
(2) 判断正误：① 进程由运行态转为阻塞态是进程的主动行为；② 一个进程被唤醒意味着它立即投入运行；③ 运行中的进程请求打印机失败而被阻塞，属于进程的主动行为。
查看解答
(1) D。A 时间片到即发生；B 等待资源 / I/O 即发生；C 被调度选中即发生；D 不可能——阻塞必须由「运行中发出请求」引发，就绪进程并未运行。
(2) ① 对：阻塞是进程自己发出请求 / 调用阻塞原语的结果；② 错：唤醒只是从阻塞队列移入就绪队列，何时运行还要看调度；③ 对：同①，请求资源失败是主动请求引发的阻塞。
2.2.2 七态模型：挂起与激活
- 活动就绪（在内存，可被调度）与静止就绪（在外存，不能被直接调度，须先激活）；
- 活动阻塞（在内存等事件）与静止阻塞（在外存等事件；事件到来时转为静止就绪而非活动就绪）。
② 静止阻塞的进程等的事件发生 → 转为静止就绪（人还在外存），不是活动就绪；
③ 挂起态与阻塞态是两个独立维度：阻塞 = 等事件；挂起 = 换出内存。活动就绪、静止阻塞等都是两个维度的组合；
④ 挂起是主动的 OS 行为（由 OS / 父进程实施），与「进程因等资源而自己阻塞」不同。
在引入挂起 / 激活机制的系统中，下列转换不可能发生的是（ ）
A. 活动就绪 → 静止就绪 B. 静止阻塞 → 静止就绪 C. 静止就绪 → 运行态 D. 运行态 → 静止就绪
查看解答
C。A 是挂起原语干的事；B 是静止阻塞进程等的事件发生（注意目的地是静止就绪）；D 挂起一个正在运行的进程，它让出 CPU 落到外存成为静止就绪——合法。C 不可能：静止就绪必须先经激活回到活动就绪，再经低级调度才能运行——静止状态进程根本不在内存，CPU 无法直接调度它。
判断正误：(1) 时间片用完的进程转为阻塞态；(2) 处于静止阻塞状态的进程所等待的事件发生后，它转为活动就绪态；(3) 处于运行态的进程申请主存失败而被阻塞，属于主动行为；(4) 一个进程从运行态退出后，处于就绪态与处于阻塞态都不可能直接进入终止态以外的运行态。
查看答案
(1) 错：时间片用完是运行 → 就绪（回就绪队列排队），没有等待任何事件；
(2) 错：事件发生只解除「阻塞」，不解除「静止」——转为静止就绪，激活后才为活动就绪；
(3) 对：申请资源引发的阻塞是进程自己的请求行为（主动）；
(4) 对：只有就绪态经「被调度」进入运行态，阻塞态必须先回就绪——这正是图 2-1 两条 ✗ 边的含义。
2.3 进程控制：五种原语
- 创建原语：申请空白 PCB → 向 PCB 填入标识 / 控制 / 现场信息（进程标识、优先级、程序地址等）→ 为进程分配所需资源（内存、文件、I/O 设备）→ 将 PCB 插入就绪队列。引发创建的事件：用户登录、作业调度、提供服务、应用请求（fork）。
- 终止原语：根据被终止进程的标识符检索 PCB，读出状态 → 若正运行则立即剥夺 CPU 交给终止程序 → 子进程若有则一并终止（可选）→ 归还全部资源给父进程 / OS → 将 PCB 从所在队列摘下并撤销（注意：先释放资源，最后撤销 PCB）。引发终止：正常结束、异常（越界 / 保护错 / 非法指令 / 除零）、外界干预（父进程请求、父进程终止、操作员 / OS 干预）。
- 阻塞原语：找到将要阻塞进程的 PCB → 保护现场（寄存器、PC 存入 PCB）→ 把状态改为「阻塞」并把 PCB 插入对应等待（阻塞）队列 → 调度程序选择新进程运行。主动行为（自己调用 block）。
- 唤醒原语：把 PCB 从等待队列移出 → 状态改为「就绪」→ 插入就绪队列。被动行为（事件发生由别的进程或中断处理程序调用 wakeup）。block 与 wakeup 必须成对使用：一个进程因某事件阻塞，必须有另一进程（或中断处理）在同一事件发生时唤醒它，否则永久阻塞。
- 切换原语（进程切换）：保存当前进程现场到其 PCB → 将其 PCB 移入相应队列（就绪 / 阻塞）→ 调度选择新进程 → 恢复新进程现场（从其 PCB 取寄存器、PC）→ 更新为新进程的地址空间（换页表基址）。
② 进程控制原语、修改 PCB、开关中断都须在核心态下执行——用户态程序直接调用 fork 之前会先陷入（trap）内核；
③ 「进程切换」≠「调度」：调度是决定谁上 CPU（可以只做决定），切换是实际换人（保存 / 恢复现场，有开销）；有调度不一定立即切换（如新选中的就是当前进程）；
④ 陷入内核（系统调用）发生了模式切换（用户态→核心态），但不一定发生进程切换——「模式切换」与「进程切换」是两回事。
(1) 下列操作中，不可能在用户态（目态）下完成、必须由操作系统在核心态完成的是（ ）
A. 读取文件的某段数据 B. 关中断 C. 从内存取一条指令 D. 算术运算
(2) 关于进程控制，说法错误的是（ ）
A. 阻塞原语由被阻塞进程自己调用 B. 唤醒原语通常由与阻塞进程合作的进程或中断处理程序调用
C. 进程创建后立即进入运行态 D. 终止原语执行时应先释放资源、最后撤销 PCB
查看解答
(1) B。关中断是特权指令（原语靠它实现原子性），只能核心态执行；读文件数据要通过系统调用陷入内核，但「发起请求」本身在用户态可行；取指令和运算是普通 CPU 工作。
(2) C。新创建进程进入就绪态（插就绪队列），何时运行由调度决定；A、B、D 均正确——尤其注意 D 的顺序：还资源在前、删 PCB 在后，因为释放过程还要用到 PCB。
2.4 进程通信的四种方式
- 共享内存（Shared Memory）：OS 在物理内存划出一块区域，映射进两个进程的虚拟地址空间，此后双方读写这块区域不再陷入内核、不做数据拷贝，是速度最快的 IPC。两种形式：基于数据结构的共享（如固定格式缓冲区，速度快但限制多）和基于存储区的共享（划出一块区域，数据格式、位置、访问时机都由进程控制，更灵活）。内核只负责建立和撤销共享区，读写互斥同步由用户自己用 P/V 等工具解决。Linux 用
shmget建立、shmat挂接。 - 管道（Pipe）：内存中一块固定大小的缓冲区，按字节流组织，
pipe()系统调用创建，返回「读端 + 写端」两个描述符。四条硬性质（选择题年年变着考）：① 半双工——一个管道同一时刻只能单向传输，双向须建两个管道；② 数据一经读出就不在管道中存在（消费即消失），因此不可能多个进程同时读同一管道抢数据；③ 写满时写进程阻塞、读空时读进程阻塞（互相同步）；④ 通信双方须有亲缘关系——通常父子进程（fork 后子进程继承管道描述符）。 - 消息传递（Message Passing）：格式化的消息（消息头：类型 / 长度 + 消息正文）由内核中转，用一对原语
send(目标, 消息)/receive(来源, 消息)完成，数据要两次拷贝（发送方→内核缓冲→接收方），开销大于共享内存但安全。两种实现：
直接通信——消息直接挂到接收进程的消息缓冲队列上（该队列链在其 PCB 上），send / receive 都指名道姓，一对一；
间接通信（信箱 / mailbox）——消息发往中间信箱，双方通过信箱解耦，可实现多对多，还可异步收发。 - 信号（Signal）：唯一异步的通信机制——用户按 Ctrl+C（SIGINT）、
kill命令、内核检测到异常（如 SIGFPE 除零）时，向目标进程发送一个信号，进程在适当时机（通常在从内核态返回用户态时）暂停当前工作转去执行信号处理程序。只传「事件编号」不传数据，属于低信息量、高及时性的通知。
| 方式 | 数据拷贝 | 同步互斥责任 | 方向 / 关系 | 典型系统调用 / 原语 |
|---|---|---|---|---|
| 共享内存 | 0 次（直接读写同一物理区） | 用户自己（P/V） | 任意进程（同一机器） | shmget / shmat（Linux）、CreateFileMapping（Windows） |
| 管道 | 2 次（写端→管道缓冲→读端） | 内核负责（满阻塞写、空阻塞读） | 半双工；父子等亲缘进程 | pipe() + read() / write() |
| 消息传递 | 2 次（经内核缓冲中转） | 内核负责（send / receive 可阻塞） | 直接一对一；信箱多对多 | send / receive 原语、msgsnd / msgrcv |
| 信号 | 只传编号 | 异步送达 | 任意方向 | kill() / signal() |
② 管道是字节流且无消息边界，消息传递才是格式化消息；
③ 信号量（P/V）在王道体系里被列为「低级通信」，但它不能传送数据，本质是同步互斥工具；本章 2.7 详述；
④ 全双工通信用两个管道，因为单个管道半双工。
(1) 关于管道通信，正确的是（ ）
A. 管道是全双工的，同一时刻可双向传数据 B. 管道中数据一经读出就消失，因此可有多个读进程同时读同一管道
C. 管道通信的双方通常须是有亲缘关系的进程 D. 管道数据放在外存文件中，速度慢
(2) 进程 P1、P2 需高频交换大批量数据，最合适的通信方式是（ ）；操作系统为二者建立通信渠道后，读写同步互斥须由用户自己解决的方式是（ ）
查看解答
(1) C。管道半双工（A 错）；数据读走即消失，多进程同读会互相「抢走」数据，故只允许一个读进程一个写进程（B 错，B 的因果也反了）；管道缓冲区在内存（D 错，名字带「文件」的「命名管道」也是内存缓冲为内核对象）。
(2) 共享内存；共享内存。最快且零拷贝，适合大批量高频；内核只建区不管同步——互斥必须用户自己用信号量保护。
2.5 线程
2.5.1 线程的概念与属性
- 减小并发执行的时空开销：线程只拥有运行所必需的最少资源（线程 ID、PC、寄存器组、栈），创建 / 撤销 / 切换比进程快得多；
- 通信方便：同进程线程共享地址空间，交换数据无需内核帮忙；
- 提高并发度与系统吞吐量；让「一个进程内的多个活动」可以并行（如浏览器同时下载图片和渲染文字）。
| 对比项 | 进程 | 线程 |
|---|---|---|
| 角色 | 资源分配的基本单位 | CPU 调度的基本单位 |
| 拥有资源 | 拥有地址空间、文件、设备等全部资源 | 几乎不拥有资源，仅共享所属进程资源 + 自己的栈 / 寄存器 / TCB |
| 切换开销 | 大：换地址空间（刷快表 / 换页表）、换内核栈，整个进程切换 | 小：同进程内切换只保存 / 恢复寄存器与栈 |
| 通信方式 | 须内核 IPC（共享内存 / 管道 / 消息 / 信号） | 直接读写共享变量（全局区），但要自行同步 |
| 并发与可靠性 | 进程间独立，一个崩溃不影响别的 | 同进程线程一个出错（如段错误）可能带崩整个进程 |
2.5.2 用户级线程 vs 内核级线程
- 用户级线程（ULT）：线程的管理（创建 / 撤销 / 切换 / 调度）全部由用户空间的线程库完成，内核完全感知不到它的存在，仍按进程为单位调度。特点：① 同进程内线程切换不需要核心态（不陷内核），切换极快；② 内核按进程分配时间片，一个进程内多线程分抢一个时间片，「并发」只在进程内部成立，无法利用多核并行；③ 一个线程发起系统调用阻塞，整个进程（及其所有线程）都阻塞；④ 调度算法可由用户库自选。
- 内核级线程（KLT）：线程由内核直接管理，TCB 在内核空间，内核以线程为单位调度。特点：① 线程切换需要进入核心态（由内核完成），开销比用户级大；② 一个线程阻塞不影响同进程的其他线程（内核可调度别的线程）；③ 能利用多核，真正并行；④ 管理开销大（创建 / 切换都要陷入内核）。
2.5.3 三种多线程模型
- 多对一模型：多个用户级线程映射到一个内核级线程。开销小、切换快；但一个线程阻塞则全进程阻塞，且无法并行（多核只能用一个核）；
- 一对一模型：每个用户级线程对应一个内核级线程（如 Linux、Windows）。并发能力最强、一个阻塞不影响别人；但每线程一个内核线程，创建 / 管理开销大；
- 多对多模型：n 个用户级线程映射到 m 个内核级线程（\(n\ge m\)）。折中：既能并行又控制了内核线程数量，一个线程阻塞还可由内核调度同进程其他线程。
(1) 下列关于线程的说法，错误的是（ ）
A. 线程是 CPU 调度的基本单位，不拥有系统资源 B. 同一进程内的线程切换不会导致进程切换
C. 用户级线程的切换需要从用户态转入核心态 D. 内核级线程的一个线程阻塞，同进程其他线程仍可运行
(2) 「多对一模型」的主要缺点是（ ）
A. 内核线程太多、管理开销大 B. 任一用户线程的系统调用阻塞会阻塞整个进程，且不能利用多核并行
C. 无法实现用户级线程 D. 必须为每个线程分配独立地址空间
查看解答
(1) C。用户级线程的管理全在用户空间线程库完成，同进程内切换不陷入内核——这正是它快的根源（反过来说内核级线程切换才需要核心态）。A、B、D 均正确。
(2) B。多对一模型下内核只见一个执行流：某个用户线程发起阻塞式系统调用，内核把整个进程置为阻塞；多核下也只有一个内核线程可跑。A 是一对一模型的缺点；D 恰恰说反——同进程线程共享地址空间。
填空：(1) 引入线程后，______ 是资源分配的基本单位，______ 是 CPU 调度的基本单位；(2) 同一进程内线程间通信可直接读写______变量；(3) 一对一模型的典型系统如______；多对多模型中用户级线程数 n 与内核级线程数 m 满足______。
查看答案
(1) 进程；线程。(2) 全局（共享地址空间中的）。(3) Linux / Windows；\(n\ge m\)（否则蜕化为一对一）。
2.6 处理机调度
2.6.1 三级调度层次
- 高级调度（作业调度）：按某种算法从外存后备队列中挑作业调入内存，为其创建进程、分配资源，插入就绪队列。频率最低（分钟级）。面向作业，回答「谁被允许进入内存」；
- 中级调度（内存调度）：把暂时不能运行的进程换出到外存（挂起），把具备运行条件的再换回内存（激活），目的是提高内存利用率与系统吞吐量——即 2.2.2 的挂起 / 激活机制。频率中等；
- 低级调度（进程调度 / 处理机调度）：按算法从就绪队列选进程，把 CPU 分给它。频率最高（毫秒级），是三种调度中最基本、不可或缺的一种（批处理 / 分时 / 实时系统都必须有）。
| 调度级别 | 对象 / 路径 | 频率 | 关键动作 |
|---|---|---|---|
| 高级（作业）调度 | 作业：外存后备队列 → 内存 | 最低 | 选作业、建进程（PCB）、分配资源、入就绪队列 |
| 中级（内存）调度 | 进程：内存 ↔ 外存 | 中等 | 挂起（换出）、激活（换入），提高内存利用率 |
| 低级（进程）调度 | 进程：就绪队列 → CPU | 最高（毫秒级） | 选进程、分 CPU，最基本、任何系统必备 |
下列关于处理机调度的叙述中，错误的是（ ）
A. 低级调度是所有操作系统都必不可少的
B. 中级调度的作用之一是在内存紧张时把暂时不能运行的进程换出内存
C. 作业调度（高级调度）从就绪队列中选择进程为其分配 CPU
D. 低级调度的频率通常高于高级调度
查看解答
C。高级调度从外存后备队列选「作业」调入内存并建进程；「从就绪队列选进程分 CPU」是低级调度的职责——两个队列 / 两个对象张冠李戴是本题型的标准错误项。A、B、D 均正确。
2.6.2 调度时机、方式与性能指标
- 处理中断的过程中——中断处理不属于任何进程，处理完才能调度；
- 进程在操作系统内核程序临界区中（如正访问就绪队列本身）；
- 其他需要完全屏蔽中断的原子操作过程中（如原语）。
（注意：进程处于普通（用户级）临界区时是可以被调度走的——只有「影响操作系统自身数据结构」的内核临界区才禁止调度。）
- 周转时间：\(T_i = \text{完成时间}_i - \text{到达时间}_i\)（含等待 + 服务）；
- 带权周转时间：\(W_i = \dfrac{T_i}{\text{服务（运行）时间}_i}\)，恒有 \(W_i\ge 1\)，越接近 1 越好（长作业天然偏大，公平）；
- 平均周转 / 平均带权：\(\overline T=\frac{1}{n}\sum T_i\)，\(\overline W=\frac{1}{n}\sum W_i\)；
- 等待时间：等待 = 周转 − 服务（本节简况下，进程在就绪队列里排队的时间总和）；
- 吞吐量：单位时间完成的作业数；CPU 利用率；响应时间（提交请求到首次响应，交互系统核心指标）。
2.6.3 六大调度算法与甘特图计算 高频考点
- FCFS（先来先服务）：按到达先后调度，非剥夺。对长作业有利、对短作业不利——短作业排在长作业后面要等很久（「护航效应」）；不会饥饿；实现最简单；利于 CPU 繁忙型作业（它不怕排队没有 I/O 间隙）、不利于 I/O 繁忙型作业。
- SJF（短作业优先）：选预计运行时间最短者优先，非剥夺式；其剥夺版本叫 SRTF / SPF（最短剩余时间优先）——新到达者剩余时间更短则抢占。平均等待时间 / 平均周转时间最短（在给定作业集下最优）；但对长作业不利，可能饥饿（源源不断的短作业到达，长作业一直排不上）；难点：运行时间只能估计。
四个作业从 8:00 起依次提交：J1 到达 8:00 需 2.0h，J2 到达 8:30 需 0.5h，J3 到达 9:00 需 0.1h，J4 到达 9:30 需 0.2h。采用 HRRN 调度，求调度顺序与各自周转时间。
查看解答
8:00 只有 J1，先运行 J1：8:00—10:00。10:00 时刻算响应比：
\[ R_{J2}=\frac{1.5+0.5}{0.5}=4\qquad R_{J3}=\frac{1.0+0.1}{0.1}=11\qquad R_{J4}=\frac{0.5+0.2}{0.2}=3.5 \]
J3 最高 → 10:00—10:06 运行 J3。10:06 重算：等待 J2 已 1.6h，\(R_{J2}=1+\frac{1.6}{0.5}=4.2\)；J4 已等 0.6h，\(R_{J4}=1+\frac{0.6}{0.2}=4\)。J2 胜 → 10:06—10:36 运行 J2，最后 J4：10:36—10:48。
周转：J1 = 10:00−8:00 = 2.0h；J2 = 10:36−8:30 = 2.1h；J3 = 10:06−9:00 = 1.1h；J4 = 10:48−9:30 = 1.3h；平均 = (2.0+2.1+1.1+1.3)/4 = 1.625h。
套路总结：HRRN 只在「空闲点」重新计算（当前作业跑完时）；响应比 = 1 + 等待/服务，等待 = 当前时刻 − 到达时刻。算之前先把四个数列成一行再比大小，防止手滑。
某时刻系统中仅有进程 P（剩余运行时间 6ms）在运行，此时进程 Q 到达（需运行 3ms）。若采用最短剩余时间优先（SRTF），Q 何时完成？若采用非抢占 SJF 呢？
查看答案
SRTF：Q 到达时比较剩余时间，Q(3) < P(6)，抢占：Q 先跑 3ms 完成；随后 P 再跑 6ms，P 在第 9ms 完成。
非抢占 SJF：P 正在运行不被打断，P 第 6ms 完成，Q 在 6～9ms 运行，第 9ms 完成——本例两算法 Q 的完成时刻恰好相同（差别在 P/Q 的等待分布：SRTF 下 Q 等待 0，非抢占下 Q 等待 6ms）。
易错：SJF 默认非抢占，抢占版叫 SRTF——题目写「短作业优先」又出现「新进程到达」，先问自己是否允许抢占。
- 优先级调度：选优先级最高者。可剥夺（高优先级到达即抢占）或非剥夺。静态优先级：创建时定死，简单但低优先级进程可能饥饿；动态优先级：随等待时间等调整（等待越久优先级越高），可防饥饿。惯例：系统进程 > 用户进程，交互型 > 非交互型，I/O 繁忙型 > CPU 繁忙型（让外设与 CPU 并行、尽早让出 CPU）。
- RR（时间片轮转）：就绪进程排成 FIFO 队列，队首分一个时间片 q；用完还没跑完就被剥夺、排到队尾；剥夺式，适合分时系统。时间片的两极效应（必考）：q 太大（超过所有进程所需时间）→ 退化为 FCFS；q 太小 → 进程切换过于频繁，切换开销淹没有效工作，系统实际吞吐下降。另外 RR 的平均周转时间并不一定短（短作业也要轮好几圈）。
- 新进程先进入第 1 级队列末尾；
- 仅当第 1～i−1 级全空时，才调度第 i 级队列中的进程（按 FCFS + 本级时间片）；
- 第 i 级进程分得的时间片用完仍未完成 → 降入第 i+1 级队尾（「反馈」由此得名）；
- 剥夺规则：低级队列进程运行时，若高一级队列来了新进程（或被唤醒），立即抢占，被抢占者回本队列队尾。
② 多级反馈队列中「新进程」永远进第 1 级，哪怕它是长作业（是否下沉要看它跑不跑得完）；
③ RR 中时间片「适中」即可，不是越小越好；q→∞ 时等价 FCFS；
④ 饥饿 ≠ 死锁：饥饿的进程可能在某天轮到（如动态优先级），死锁的进程永远无法继续。
单 CPU 系统，四个进程同时提交，到达时间与运行（服务）时间如下：
| 进程 | 到达时间 | 服务时间 |
|---|---|---|
| A | 0 | 8 |
| B | 1 | 4 |
| C | 2 | 9 |
| D | 3 | 5 |
(1) 按 FCFS 调度，画甘特图并求平均周转、平均带权周转时间；(2) 按非抢占 SJF 再算；(3) 按 RR（q = 2）再算；(4) 比较结论。
查看解答
(1) FCFS：按到达序 A→B→C→D。
| A 0–8 | B 8–12 | C 12–21 | D 21–26 |
周转：A = 8−0 = 8，B = 12−1 = 11，C = 21−2 = 19，D = 26−3 = 23 → \(\overline T=\frac{8+11+19+23}{4}=15.25\)；带权：\(1,\ 2.75,\ 2.11,\ 4.6\) → \(\overline W\approx 2.62\)；平均等待 = (0+7+10+18)/4 = 8.75。
(2) 非抢占 SJF：0 时刻只有 A → A 0–8；8 时刻 B(4)、C(9)、D(5) 均已到，选最短 B → 8–12；再选 D → 12–17；最后 C → 17–26。
| A 0–8 | B 8–12 | D 12–17 | C 17–26 |
周转：8、11、14、24 → \(\overline T=14.25\)；等待：0、7、9、15 → 平均 7.75；带权：\(1,\ 2.75,\ 2.8,\ 2.67\) → \(\overline W\approx 2.31\)。
(3) RR（q = 2）：规则「新到达者先入队尾，时间片用完者也排队尾」。逐段推演（方括号为就绪队列，队头在左）：0 时刻队 [A] → A(0–2)；t=2 到达者 C 先入、A 再入：[B,C,A] → B(2–4)；t=4（D 已于 t=3 到达）：[C,A,D,B] → C(4–6)；t=6：[A,D,B,C] → A(6–8)；t=8：[D,B,C,A] → D(8–10)；t=10：[B,C,A,D] → B(10–12)，B 完成（恰跑满 4）；t=12：[C,A,D] → C(12–14)；t=14：[A,D,C] → A(14–16)；t=16：[D,C,A] → D(16–18)；t=18：[C,A,D] → C(18–20)；t=20：[A,D,C] → A(20–22)，A 完成（恰跑满 8）；t=22：[D,C] → D(22–23)，D 完成（恰跑满 5）；最后 C(23–26)，C 完成（恰跑满 9）。总跨度 26 = 8+4+9+5 ✓。
| A | B | C | A | D | B | C | A | D | C | A | D | C |
| 时间轴：0 2 4 6 8 10 12 14 16 18 20 22 | 23 26（D 的末片只有 1 个单位，C 的末片 3 个单位） | ||||||||||||
完成时刻：A = 22、B = 12、C = 26、D = 23。周转：A = 22、B = 11、C = 24、D = 20 → \(\overline T=19.25\)；等待：14、7、15、15 → 平均 12.75；带权：2.75、2.75、2.67、4 → \(\overline W\approx 3.04\)。
(4) 结论：本例 \(\overline T\)：SJF(14.25) < FCFS(15.25) < RR(19.25)——SJF 平均等待 / 周转最优；RR 响应最及时（每个进程 2ms 内首次上机）但平均周转反而最长——RR 不保证周转指标，保证的是公平与响应。
套路总结：固定四步——① 画甘特图（抢占式逐片排）② 完成时刻逐一核对 ③ 周转 = 完成 − 到达 ④ 等待 = 周转 − 服务。RR 排队心法：「到队的插队尾，用完片的也插队尾，谁在队头谁跑」。
进程 P1、P2、P3 先后在 0、1、2 时刻到达，服务时间均为 6，RR 时间片 q = 2（新到达者先于被剥夺者入队）。求 P1 的完成时刻与周转时间。
查看答案
排队序：P1(0–2)、P2(2–4)、P3(4–6)、P1(6–8)、P2(8–10)、P3(10–12)、P1(12–14，完成，已跑 6)。
P1 完成时刻 = 14，周转 = 14 − 0 = 14。验证：P2 完成于 16，周转 15；P3 完成于 18，周转 16——三者同时长任务，越晚到周转越长，正常。
某系统采用多级反馈队列调度：队列 1 优先级最高、时间片 1；队列 2 次之、时间片 2；队列 3 最低、时间片 4（FCFS）。仅当高优先级队列为空才调度低级队列。进程 A、B、C 分别在 0、1、2 时刻到达，所需 CPU 时间分别为 8、5、3。求调度序列与各进程周转时间、平均等待时间。
查看解答
逐步推演（新进程一律入 1 级队尾；某级时间片用完未完成则降级）：
- t=0：A 入 Q1 → A 用 1 级片跑 0–1，剩 7 → 降入 Q2；
- t=1：B 入 Q1（1 级非空优先）→ B 跑 1–2，剩 4 → 降入 Q2（Q2 = [A, B]）；
- t=2：C 入 Q1 → C 跑 2–3，剩 2 → 降入 Q2（Q2 = [A, B, C]）；
- t=3：Q1 空 → 调 Q2 队首 A，用 2 级片跑 3–5，剩 5 → 降入 Q3；
- t=5：B 跑 5–7，剩 2 → 降入 Q3（Q3 = [A, B]）；
- t=7：C 跑 7–9，2 级片未用满即完成（C 共需 3 = 1 级片 1 + 2 级片 2）→ C 完成于 9；
- t=9：Q1、Q2 全空 → Q3 队首 A 用 4 级片跑 9–13，剩 1 → 回 Q3 队尾（Q3 = [B, A]）；
- t=13：B 跑 13–15，剩 0 → B 完成于 15；
- t=15：A 跑 15–16（只差 1）→ A 完成于 16。总跨度 16 = 8+5+3 ✓。
调度序列：A B C A B C A B A（时间段 0–1、1–2、2–3、3–5、5–7、7–9、9–13、13–15、15–16）。
周转：A = 16−0 = 16，B = 15−1 = 14，C = 9−2 = 7；\(\overline T=\frac{16+14+7}{3}\approx 12.33\)。等待 = 周转 − 服务：A = 8，B = 9，C = 4 → 平均等待 7。带权：\(2,\ 2.8,\ 2.33\) → \(\overline W\approx 2.38\)。
套路总结：多级反馈队列推演三问——「现在最高非空是哪级？队头是谁？这片跑完去哪（完成 / 降级 / 回本队尾）」。特别防两点：① 降级是「时间片用完」，被高优先级抢占是「回本队列队尾」；② 最后一级的时间片用完回本队队尾继续轮转（本例 A 在 13 后排到 B 后面）。
| 算法 | 剥夺? | 会不会饥饿 | 关键性质 / 口诀 |
|---|---|---|---|
| FCFS 先来先服务 | 非剥夺 | 不会 | 对长作业有利、对短作业不利；利于 CPU 繁忙型；「护航效应」 |
| SJF 短作业优先 | 非剥夺（SRTF 为剥夺） | 可能饥饿 | 平均等待 / 周转最短；需要预估运行时间；对长作业不利 |
| HRRN 高响应比 | 非剥夺 | 不会 | \(R=1+\) 等待 / 服务；先来者优先与短作业优先的折中 |
| 优先级调度 | 皆可 | 静态优先级会饥饿 | 动态优先级（等待越久越高）防饿死；I/O 繁忙型给高优先级 |
| RR 时间片轮转 | 剥夺 | 不会（公平轮转） | q 太大退化 FCFS，q 太小切换开销大；分时系统专属；周转不一定短 |
| 多级反馈队列 | 剥夺 | 长作业可能滞留低级（一般视为不会饿死） | 不必预知运行时间；短作业快跑、长作业不弃；公认较优的通用算法 |
2.7 进程同步与互斥 高频考点
2.7.1 临界资源与四原则
- 空闲让进：临界区空闲时，应允许一个请求进入的进程立即进入；
- 忙则等待：已有进程在临界区时，其他试图进入者必须等待（保证互斥）；
- 有限等待：请求进入的进程应在有限时间内进入（不能饿死）；
- 让权等待：进不去时应释放 CPU（阻塞自己），防止忙等（busy waiting）浪费处理机。
2.7.2 软件法与硬件法：逐个分析
以下四种软件尝试都针对两个进程 P0、P1 争用同一临界区，逐一判断它们满足四准则中的哪几条（高频选择题）：
int turn = 0; // 表示该谁进临界区
// P0 进程 // P1 进程
while (turn != 0); while (turn != 1); // ① 不是自己就忙等
critical section; critical section;
turn = 1; turn = 0;问题：必须轮流进入。若 P0 一直不进临界区（turn=0 但 P0 不想进），P1 也无法进入——违反空闲让进；且 while 忙等违反让权等待。满足忙则等待与有限等待（轮流必有份）。
bool flag[2] = {false, false}; // flag[i]=true 表示 Pi 想进
// P0 // P1
while (flag[1]); // ① 先看对方 while (flag[0]);
flag[0] = true; // ② 再举自己的旗 flag[1] = true;
critical section;
flag[0] = false;
问题：两进程可能同时通过 ① 检查（都见对方 false），再同时举旗进入——违反忙则等待（互斥都不保）。根源：「检查」与「上锁」两步之间可被打断。
// P0 // P1
flag[0] = true; // ① 先举旗 flag[1] = true;
while (flag[1]); // ② 再看对方 while (flag[0]);
critical section;
flag[0] = false;
问题：两进程可能同时举旗，然后互相看着对方的旗永远忙等——违反空闲让进和有限等待（都进不去，饥饿），也违反让权等待。满足忙则等待（互斥保住了，但代价惨重）。
bool flag[2] = {false, false};
int turn = 0;
// P0 // P1
flag[0] = true; // 我想进 flag[1] = true;
turn = 1; // 但让你先 turn = 0;
while (flag[1] && turn == 1); // 你想进且让了你 while (flag[0] && turn == 0);
critical section;
flag[0] = false; // 降旗，允许对方 flag[1] = false;
结合「主动举手 + 客气让位」：想进先举旗，再把 turn 让给对方；仅当对方想进且 turn 指向对方时才等待。分析：满足空闲让进、忙则等待、有限等待（等待至多一轮，必能进入）；但 while 仍是忙等——违反让权等待。这是软件法的天花板，也是统考最爱。
| 方法 | 空闲让进 | 忙则等待 | 有限等待 | 让权等待 |
|---|---|---|---|---|
| 单标志法 | ✗（强制轮流） | ✓ | ✓ | ✗（忙等） |
| 双标志先检查 | ✓ | ✗（可同进） | ✓ | ✗（忙等） |
| 双标志后检查 | ✗ | ✓ | ✗（可永久等待） | ✗（忙等） |
| Peterson | ✓ | ✓ | ✓ | ✗（忙等） |
- 中断屏蔽（关中断）：进入锁测试前关中断、退出后开中断，保证检查与上锁不被打断——简单高效。局限：只适用于单处理机系统（多核下别的核照跑）；关中断是特权指令，不能交给用户进程（滥用 = 系统瘫痪）；关中断时间过长影响并发。
- TestAndSet（TS/TSL 指令）：读旧值 + 置 true 一条原子指令完成。
TS 锁
bool TestAndSet(bool *lock) { // 原子执行 bool old = *lock; // 记下旧值 *lock = true; // 直接上锁 return old; // 返回旧值：false 表示锁原本空闲 } // 使用：while (TestAndSet(&lock)); // 返回 true 则继续忙等 // critical section; // lock = false; - Swap（XCHG 交换指令）：原子交换两个字的内容。
Swap 锁
// 使用：bool old = true; // while (old == true) Swap(&lock, &old); // 原子交换，lock 空则换出 false // critical section; // lock = false;
2.7.3 信号量机制与 P/V 操作 高频考点
- 整型信号量：S 为整数，P 中 S≤0 时
while(S<=0)原地空转——不满足让权等待（忙等），是「记录型」之前的过渡产物； - 记录型信号量（重点）：value（资源数目）+ 链表 L（等待该资源的进程队列）。P/V 中主动放弃 CPU（block 阻塞自己 / wakeup 唤醒别人），四准则全满足——这是考研 P/V 大题使用的版本。
typedef struct {
int value; // 资源剩余数：>0 有资源可用；<0 其绝对值 = 等待进程数
struct process *L; // 等待该资源的进程队列（PCB 链）
} semaphore;
void wait(semaphore *S) { // P 操作：申请一个资源
S->value--;
if (S->value < 0) // 资源不够
block(S->L); // 把自己阻塞，挂入 L 队尾，让出 CPU
}
void signal(semaphore *S) { // V 操作：释放一个资源
S->value++;
if (S->value <= 0) // 仍有进程在等（value<=0 说明队列非空）
wakeup(S->L); // 唤醒 L 队首进程，转入就绪态
}(1) 用记录型信号量 mutex（初值 1）实现两进程互斥，进程 A 在同一路径中连续执行两次 P(mutex)（中间无 V），则 mutex 的 value 与 A 的状态为（ ）
A. value = 0，A 正常运行 B. value = −1，A 阻塞在自己设置的锁上 C. value = −2，A 阻塞 D. value = 1，A 运行
(2) 关于 TS 指令与 Peterson 算法，说法正确的是（ ）
A. 两者都满足让权等待 B. 两者都不满足让权等待，但 TS 满足忙则等待且支持多处理机 C. Peterson 不满足忙则等待 D. TS 只能用于单处理机
查看解答
(1) B。两次 P：第一次 1→0，A 成功进入临界区；第二次 0→−1，A 申请失败阻塞——自己锁死自己（A 排在 mutex 等待队列，等一个永远不会来的 V）。若此后再无 V，A 永久阻塞。教训：P/V 必须成对出现，同一路径内不能重复 P 同一把互斥锁。
(2) B。两者都靠 while 忙等（不满足让权等待）；Peterson 满足互斥（忙则等待），TS 把「读旧值 + 置锁」原子化同样满足互斥；中断屏蔽才只能用于单处理机，TS/Swap 支持多核。
- 实现互斥——「夹紧」：设 semaphore mutex = 1，不同进程对同一临界区的操作用 P(mutex) … V(mutex) 前后夹住：
互斥模板
semaphore mutex = 1; P1: ... P2: ... P(mutex); P(mutex); 临界区; 临界区; V(mutex); V(mutex); // 一个进程 P 后 mutex=0，另一进程再 P 则阻塞，直至前者 V - 实现同步——「前 V 后 P」：要保证「操作 a（P1 中）先于操作 b（P2 中）发生」，设 semaphore s = 0，在 a 后面V(s)，在 b 前面P(s)：
同步模板
semaphore s = 0; P1: 代码1; P2: ... a; P(s); // 若 P1 未执行 V，P2 在此阻塞 V(s); b; // b 必然在 a 之后 // 口诀：「前操作」之后 V，「后操作」之前 P；信号量初值 0 - 实现前驱关系（前驱图）：每条有向边设一个信号量（初值 0）；每个结点是一个进程 / 代码段，入边的信号量全部 P 完才执行，出边逐个 V。前驱图就是若干「前 V 后 P」的叠加。
a=0 b=0
S1 ────────────> S2 ────────────> S3
│
│ c=0
▼
S4
S1: 语句1; V(a); // 源点只 V
S2: P(a); 语句2; V(b); V(c); // 中间点：P 完入边再 V 出边
S3: P(b); 语句3;
S4: P(c); 语句4; // 汇点只 P
// S2 要 P(a) 通过才动身，S3、S4 各等自己的入边——「前 V 后 P」叠加成图(1) 设信号量 S 初值为 2，当前 value = −1，则此时因执行 P(S) 而阻塞的进程数为（ ）
A. 1 B. 2 C. 3 D. 0
(2) 进程 P1 有语句 a、P2 有语句 b，要求 a 必须先于 b 执行。下列方案正确的是（ ）
A. 设 s=1；P1: P(s); a；P2: b; V(s) B. 设 s=0；P1: a; V(s)；P2: P(s); b C. 设 s=0；P1: P(s); a；P2: b; V(s) D. 设 s=1；P1: V(s); a；P2: b; P(s)
查看解答
(1) A。|value| = 1 即等待队列中有 1 个进程（2−3=−1：共被 P 了 3 次、V 了 2 次或类似组合，第 3 个申请者被阻塞）。
(2) B。「前 V 后 P」：前操作 a 之后 V，后操作 b 之前 P，初值 0。A、D 初值错且方向错；C 的 P 在 a 前面反而要求 a 等 b 的 V——次序颠倒，b 先跑 a 反被阻塞。
四个语句 S1→S2、S1→S3、S2→S4、S3→S4 构成前驱图（S1 最先、S4 最后）。写出用信号量实现的前趋语句（各语句处应执行的 P/V 及初值）。
查看答案
每条边一个信号量：a（S1→S2）、b（S1→S3）、c（S2→S4）、d（S3→S4），全部初值 0。
S1: 语句1; V(a); V(b);
S2: P(a); 语句2; V(c);
S3: P(b); 语句3; V(d);
S4: P(c); P(d); 语句4; // 汇点：所有入边都 P 到才能执行口诀：源点只 V 不 P，汇点只 P 不 V，中间点「先 P 完入边、执行、再 V 出边」。
2.7.4 生产者-消费者问题 高频考点
- semaphore mutex = 1——互斥访问缓冲区；
- semaphore empty = n——空缓冲区（格子）数（同步：消费者「生产」空位）；
- semaphore full = 0——产品数（同步：生产者「生产」产品）。
semaphore mutex = 1; // 互斥访问缓冲区
semaphore empty = n; // 空缓冲区数（初值 n：一开始全空）
semaphore full = 0; // 产品数（初值 0：一开始没产品）
producer () { consumer () {
while (true) { while (true) {
生产一个产品; P(full); // 等产品（同步）
P(empty); // 申请一个空位(同步) P(mutex); // 进临界区(互斥)
P(mutex); // 进临界区(互斥) 从缓冲区取产品;
产品放入缓冲区; V(mutex);
V(mutex); V(empty); // 归还一个空位
V(full); // 产品数 +1 消费产品;
} }
} }若把生产者代码中的两个 P 交换为「先 P(mutex)，后 P(empty)」，其他不变，系统会发生什么？请结合 n = 1 的情形详细论证。
查看解答
会发生死锁。推演（缓冲区已满，即 empty = 0、full = n）：
- 生产者执行 P(mutex)：mutex 1→0，成功进入；
- 生产者执行 P(empty)：empty 0→−1，阻塞——但它手里还攥着 mutex（未 V）；
- 消费者想取产品：先 P(full) 成功（full>0），再 P(mutex)：mutex 0→−1，阻塞——取不出产品；
- 消费者的 V(empty) 永远执行不到，生产者等空位、消费者等锁：互相等待对方释放，谁也无法推进 → 死锁。
结论：「先同步（资源）后互斥」——必须先 P(empty)/P(full) 确认有空位 / 有产品，再 P(mutex) 拿缓冲区钥匙；顺序颠倒就可能「拿着钥匙等座位」。
两个 V（V(mutex) 与 V(full)/V(empty)）的顺序则可以交换：V 操作从不阻塞，先释放谁都只会让别的进程更早被唤醒，不会造成死锁（最多影响一点效率）。
套路总结：P 的次序是生死线（资源信号量在前、互斥信号量在后），V 的次序无所谓——这十六个字是所有 P/V 大题的第一条检查项。
2.7.5 读者-写者问题 高频考点
semaphore rw = 1; // 实现对文件(数据)的互斥访问：写者与读者争用
int count = 0; // 正在读的读者数（共享变量）
semaphore mutex = 1; // 保护 count 的互斥访问
writer () { reader () {
while (true) { while (true) {
P(rw); // 独占文件 P(mutex); // ① count 是共享的
写文件; if (count == 0) // ② 我是第一个读者
V(rw); P(rw); // 替所有读者锁文件
} count++;
} V(mutex);
读文件;
P(mutex); // ③ 修改 count 前加锁
count--;
if (count == 0) // ④ 我是最后一个读者
V(rw); // 替大家开锁
V(mutex);
}
}(1) 若去掉保护 count 的 mutex（①③ 处），两个读者同时到达会发生什么？
(2) 5 个读者正在读，1 个写者在等待，此时第 6 个读者到达——谁先进入？写者何时能进？
(3) 要让「写者优先 / 读写公平」（写者等待时阻止新读者插队），最少增加什么？
查看解答
(1) 竞态：两读者同时判 count == 0 成立，都执行 P(rw)——第二个 P(rw) 使 rw = −1，该读者阻塞等自己人开锁；更糟情形是 count 更新丢失。本质：count 是临界资源，未保护即错。
(2) 第 6 个读者立即进入（count = 5 ≠ 0，不再 P(rw)，直接读）——这就是「读者优先」；写者必须等 count 减到 0（最后一个读者 V(rw)）才能进入。若读者源源不断，写者饥饿。
(3) 增加一个信号量 w = 1（初值 1）：读者在 P(mutex) 之前先 P(w)、读完（V(mutex) 之后）V(w)；写者写前 P(w) … V(w)。这样写者等待期间新读者被 w 挡住，实现「先来先服务」的公平竞争（写者不再无限挨饿）。核心口诀：读者对 rw「第一个进锁、最后一个出开」，对 w「人人都要过」。
2.7.6 哲学家进餐问题 高频考点
semaphore room = 4; // 屋里最多 4 人同时「尝试拿筷」
semaphore chopstick[5]; // 每支筷子一个信号量，初值均为 1
philosopher (i) {
while (true) {
思考;
P(room); // 第 5 人须在门外等
P(chopstick[i]); // 拿左
P(chopstick[(i + 1) % 5]); // 拿右
吃饭;
V(chopstick[i]);
V(chopstick[(i + 1) % 5]);
V(room);
}
}
// 4 人抢 5 支筷子，至少 1 人能凑齐一双 → 不会全体僵持philosopher (i) {
while (true) {
思考;
if (i % 2 == 0) { // 偶数号：先左后右
P(chopstick[i]);
P(chopstick[(i + 1) % 5]);
} else { // 奇数号：先右后左
P(chopstick[(i + 1) % 5]);
P(chopstick[i]);
}
吃饭;
V(chopstick[i]);
V(chopstick[(i + 1) % 5]);
}
}
// 相邻二人抢筷顺序相反，不可能形成「人人左手持筷等右手」的环semaphore mutex = 1; // 保护「拿一双」这个动作
philosopher (i) {
while (true) {
思考;
P(mutex); // 一次只允许一人执行「拿双筷」
P(chopstick[i]);
P(chopstick[(i + 1) % 5]); // 两支都到手才放锁（不会拿着一支等另一支）
V(mutex);
吃饭;
V(chopstick[i]);
V(chopstick[(i + 1) % 5]);
}
}
// 不会有哲学家「拿着一支筷子等另一支」→ 破坏请求并保持条件(1) 「最多允许 4 位哲学家同时拿筷子」为什么能防死锁？它破坏了死锁的哪个必要条件？
(2) 判断：奇偶解法中，5 号哲学家（编号 4，偶数）的「左筷」是 4 号筷子、「右筷」是 0 号筷子，他先拿 0 号再拿 4 号是否正确？
查看解答
(1) 4 人最多同时持有 4 支筷子（每人先拿一支），而桌上有 5 支——至少还剩 1 支空闲，离空闲筷最近的某位哲学家必能拿到第二支进食并最终释放；于是僵局不可能形成。严格说它并未破坏四个必要条件本身，而是破坏了「死锁充分场景」（让循环等待凑不齐）；多数教材按「破坏请求并保持 / 限制并发请求数」归类。
(2) 错误。编号 4 是偶数号，按解法二应「先左（4 号）后右（0 号）」；若他反着来，就与 3 号（奇数，先右 = 4 号）形成局部对抢，重新引入僵持风险——奇偶法的正确性恰恰依赖「相邻者顺序相反」这一全局约定，改一人即破功。
2.7.7 变体：苹果-橘子问题（一盘水果版生产者-消费者）
semaphore plate = 1; // 盘中空位数：初值 1（盘子一开始空）
semaphore apple = 0; // 盘中苹果数
semaphore orange = 0; // 盘中橘子数
dad () { mom () { // 两个生产者
while (true) { while (true) {
准备一个苹果; 准备一个橘子;
P(plate); // 等空盘 P(plate);
苹果放入盘中; 橘子放入盘中;
V(apple); // 「有苹果了」 V(orange);
} }
} }
daughter () { son () { // 两个消费者
while (true) { while (true) {
P(apple); // 等苹果 P(orange);
从盘中取出苹果; 从盘中取出橘子;
V(plate); // 腾出盘子 V(plate);
吃苹果; 吃橘子;
} }
}(1) 本题中 P(plate) 若与后续的 V(apple) 都不存在（即爸爸直接放、女儿直接吃），会出现什么错误？
(2) 「吸烟者问题」：供应者每次随机在桌上放两种材料，三个吸烟者各持有一种材料、凑齐三种才能卷烟并抽掉，抽完示意供应者再放。它对应本节哪个模型的推广？信号量应设几个？
查看解答
(1) 两个错误：① 互斥丢失——爸妈可同时往一个格子放水果（数据覆盖）；② 同步丢失——女儿可能在空盘中「取苹果」，儿子可能与女儿同时取同一个水果。P(plate) 兼起「空位同步 + 盘子互斥」作用（容量为 1 时合二为一），V(apple)/V(orange) 是「事件发生」通知——缺一不可。
(2) 是「多生产者-多消费者 + 单缓冲（容量 1）」的推广：供应者 = 生产者，三个吸烟者 = 三类消费者。4 个信号量：offer1、offer2、offer3（三种「材料组合已就绪」事件，初值 0）+ finish（吸烟者抽完通知供应者，初值 0）；供应者 V 两个 offer 后 P(finish) 等通知，某吸烟者 P 到属于自己的 offer 即取料、卷烟、抽烟、V(finish)。模板仍是「先资源后动作，做完发通知」。
① 互斥夹紧：P(mutex) 与 V(mutex) 之间只能夹「真正的临界操作」，P 完必须 V，同一路径不得重复 P 同一把锁；
② 同步前后：「前操作」之后 V、「后操作」之前 P，同步信号量初值 = 初始资源数（无则 0）；
③ 先同步后互斥：一个进程要 P 多个信号量时，资源（同步）信号量的 P 在前，互斥信号量的 P 在后——顺序颠倒可能「持锁等资源」致死锁；V 的先后无所谓。
检查三问：初值对不对？P 的次序对不对？每组 P/V 是否配对（含不同进程间的配对）？
2.8 死锁
2.8.1 概念与四个必要条件
- 饥饿（starvation）：进程长期得不到 CPU / 资源而无法运行，但只要调度条件变化（如优先级提升）仍可能运行——不一定互相等待，不满足「循环等待」；
- 死循环（死循环代码）：进程在运行中跳不出某段程序——它是「活着但空转」，死锁是「想跑跑不了」；死循环是程序逻辑错误，死锁是资源 / 调度策略问题。
- 互斥条件：资源一次只能被一个进程使用（根本原因）；
- 请求并保持（占有并等待）：进程已保持至少一个资源，又提出新请求，等待时不放手已有资源；
- 不可剥夺（不可抢占）：资源只能由占有者用完自愿释放，不能被强行夺走；
- 循环等待：存在进程—资源的环形等待链 P0→P1→…→Pn→P0。
下列叙述中，错误的是（ ）
A. 死锁的进程一定处于阻塞态；饥饿的进程可能处于就绪态
B. 发生死锁时四个必要条件一定同时成立
C. 四个必要条件同时成立时系统一定发生死锁
D. 饥饿不是因为进程互相等待资源，而是因为调度策略长期不选中它
查看解答
C。必要条件 ≠ 充分条件：四条件齐备只说明「可能」死锁，还需资源分配恰好形成僵局（每类资源多实例时尤其如此）。A 对：死锁者在等对方释放资源（阻塞）；饥饿者万事俱备只欠调度（就绪）。B、D 为教材原话。
将「打印机」改为 SPOOLing 假脱机方式使用后，为什么不会因它而死锁？破坏了哪个必要条件？
查看答案
SPOOLing 用磁盘上的输出井模拟出多个「逻辑打印机」，各进程的打印请求变成了向共享的输出井写文件、由打印进程统一取出打印——打印机的独占性（互斥）被破坏（变为可共享资源），不满足互斥条件，自然谈不上死锁。代价：需要磁盘空间与专门进程，并非所有独占资源都能这样改造（如磁带机）。
2.8.2 死锁预防：破坏必要条件
- 破坏互斥条件：把独占资源改造为共享（如 SPOOLing 技术）——但很多资源（磁带机、写文件）天然不可共享，普遍做不到，故这条通常「不破坏」；
- 破坏请求并保持：静态分配（一次性申请全部资源）——运行前一次要齐，要么全给要么都不给。代价：资源利用率极低（用一天的打印机可能申请后闲一周）、可能饥饿（凑不齐资源的进程一直等）；
- 破坏不可剥夺：新请求得不到满足时主动释放已占有资源，以后重新申请；或由 OS 按优先级强行剥夺低优先级进程资源。代价：实现复杂、反复申请释放开销大、只适合易保存 / 恢复的资源（CPU、内存），前两版王道还指出可能让前一阶段工作失效；
- 破坏循环等待：顺序资源分配法——给每类资源编号，进程只能按编号递增顺序申请（同类一次申请齐）。破坏了环形链。代价：编号难定（要按大多数进程使用顺序）、实际使用顺序与编号不符时浪费（先要高号也得先借低号）、编程不便。
2.8.3 死锁避免：银行家算法 高频考点
- Available[m]：当前每类资源的空闲数；
- Max[n][m]：各进程对每类资源的最大需求；
- Allocation[n][m]：各进程已分配到的量；
- Need[n][m] = Max − Allocation：尚需量（先算它，一切判断基于 Need）。
请求尝试算法（进程 Pi 发来 Request）：① Request ≤ Need[i]？（否则错——超过申报的最大值）② Request ≤ Available？（否则 Pi 等待）③ 试探性分配：Available −= Request，Allocation[i] += Request，Need[i] −= Request，然后跑安全性算法：安全 → 正式分配；不安全 → 回滚（恢复原矩阵），Pi 等待。
② 安全性算法判断用 Need ≤ Work（不是 Max、不是 Allocation）；归还的是 Allocation（跑完把已占有的全还）；
③ 「安全序列不唯一」——写出任何一个即可（选择题常问「不可能是安全序列的选项」）；
④ 分配后不安全要回滚本次试探分配，进程进入等待；
⑤ 银行家算法属于死锁避免（动态判断），不是预防（预防是事先破坏条件）——两者分类题年年考。
系统有 A、B、C 三类资源共 10、5、7，当前分配状态如下（Available = (3,3,2)）：
| 进程 | Max（A B C） | Allocation（A B C） | Need = Max − Allocation |
|---|---|---|---|
| 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 |
(1) 判断当前状态是否安全，给出一个安全序列；
(2) P1 发来请求 Request = (1,0,2)，能否分配？
(3) 随后 P4 请求 (3,3,0)、再 P0 请求 (0,2,0)，分别如何处理？
查看解答
(1) Work = Available = (3,3,2)，逐个找 Need ≤ Work 的进程：
| 步骤 | 选中进程 | Need | Work（分配前） | Work += Allocation 后 |
|---|---|---|---|---|
| 1 | P1 | (1,2,2) ≤ (3,3,2) ✓ | (3,3,2) | (5,3,2) |
| 2 | P3 | (0,1,1) ≤ (5,3,2) ✓ | (5,3,2) | (7,4,3) |
| 3 | P4 | (4,3,1) ≤ (7,4,3) ✓ | (7,4,3) | (7,4,5) |
| 4 | P2 | (6,0,0) ≤ (7,4,5) ✓ | (7,4,5) | (10,4,7) |
| 5 | P0 | (7,4,3) ≤ (10,4,7) ✓ | (10,4,7) | (10,5,7) |
全部 Finish = true，安全；安全序列 P1 → P3 → P4 → P2 → P0（P0 → P1 → P2 → P3 → P4 等其他序列也可能成立——只要能逐个满足即可）。
(2) 三步检查：① (1,0,2) ≤ Need[P1] = (1,2,2) ✓；② (1,0,2) ≤ Available = (3,3,2) ✓；③ 试探分配：Available = (2,3,0)，Allocation[P1] = (3,0,2)，Need[P1] = (0,2,0)。对新状态跑安全性算法：Work = (2,3,0)，P1 的 Need (0,2,0) ≤ (2,3,0) ✓ → Work = (5,3,2)；接 P3 → (7,4,3)；接 P4 → (7,4,5)；接 P0 (7,4,3 ≤ 7,4,5) 或 P2 → 全部完成，安全。故可以分配，P1 执行；此刻安全序列如 P1 → P3 → P4 → P0 → P2。
(3) P4 请求 (3,3,0)：① ≤ Need[P4] = (4,3,1) ✓；② 与 Available = (2,3,0) 比较——A 类 3 > 2，资源不足，连试探分配都进不去，P4 阻塞等待。
P0 请求 (0,2,0)：① ≤ Need[P0] = (7,4,3) ✓；② ≤ (2,3,0) ✓；③ 试探分配：Available = (2,1,0)，Allocation[P0] = (0,3,0)，Need[P0] = (7,2,3)。安全性检查：Work = (2,1,0)，逐个比较——P1 Need (0,2,0)：B 类 2 > 1 ✗；P2 (6,0,0)：A 类 6 > 2 ✗；P3 (0,1,1)：C 类 1 > 0 ✗；P4 (4,3,1) ✗；P0 (7,2,3) ✗——无任何进程可完成，不安全！回滚：Available 恢复 (2,3,0)，P0 阻塞等待，让 P1 先跑、释放后再议。
套路总结：请求三步「①比 Need ②比 Available ③试分配 + 安全性检查」；安全性五列表格逐行填 Work；「不安全 → 回滚 → 等待」是标准收尾。真题数值再大也是这套流水线。
2.8.4 死锁检测与解除
- 找非阻塞且非孤立的进程 P（它的所有请求都能被剩余资源满足）；
- 删去 P 的所有请求边与分配边（P 将来能跑完并归还全部资源）→ P 成为孤立点；
- 重复，直到消不完为止。若最终所有进程都孤立 → 无死锁（图可完全化简）；否则剩余进程死锁。
- 资源剥夺：从其他进程剥夺足够资源给死锁进程（被剥夺者挂起，防止其饥饿）；
- 撤销（终止）进程：按代价最小原则强行撤销死锁进程——可以撤销全部死锁进程（简单粗暴），或逐个撤销至死锁解除（每撤一个重新检测）；代价 = 优先级、已运行时间、还要多久、用了多少资源、是否交互式等加权；
- 进程回退：让一个或多个进程退回到足以避开死锁的检查点（要求系统设置检查点、保存现场，实现开销大）。
R1、R2 各有 1 个实例，R3 有 2 个实例。分配：R1→P1，R2→P2，R3→P2，R3→P3；请求：P2→R1，P3→R2，P1→R3。该系统是否死锁？
查看解答
逐个检查「非阻塞」：R1 唯一实例已给 P1，P2 等 R1 ⇒ P2 阻塞；R2 唯一实例已给 P2，P3 等 R2 ⇒ P3 阻塞；R3 有 2 个实例、已分出 2 个（P2、P3 各一），P1 等 R3 ⇒ P1 也阻塞。
三个进程全部阻塞，找不到可化简的非阻塞进程，图不可完全化简——发生死锁（P1→R3→P2→R1 与 P2→R1、P3→R2→P2 交织成环且资源单实例 / 无空闲）。
套路总结：先数「每类资源的空闲实例」，谁的请求都能满足谁非阻塞；化简即「删边孤立」，删不动 = 死锁。快速法：单实例看有环与否；多实例老老实实化简。
判断：(1) 系统处于不安全状态时必然发生死锁；(2) 银行家算法属于死锁预防策略；(3) 死锁检测化简时，删除某进程的所有边表示「它能运行完毕并释放全部资源」；(4) 按序申请资源（编号递增）破坏的是「请求并保持」条件。
查看答案
(1) 错：不安全只是「找不到安全序列」，若各进程实际不再申请或恰好陆续释放，死锁可避免——不安全 ⇒ 可能死锁。
(2) 错：银行家算法是死锁避免（分配前动态判断），预防指事先破坏必要条件（一次性分配、顺序分配等）。
(3) 对：化简的语义正是「该进程可满足全部请求→运行完→归还全部资源」。
(4) 错：顺序资源分配法破坏的是循环等待条件。
2.9 章末自测 真题风格
限时 60 分钟，先做后看答案。难度：★★ 基础 / ★★★ 强化 / ★★★★ 冲刺。大题必须完整写出推演过程（甘特图 / 信号量表 / 安全性表格），只对答案不练过程等于没练。
下列关于进程的说法中，错误的是（ ）
A. 进程实体由 PCB、程序段和数据段三部分组成 B. PCB 是进程存在的唯一标志
C. 进程与程序之间存在一一对应关系 D. 进程具有动态性、并发性、独立性、异步性
查看答案
C。一个程序可对应多个进程（多次执行），一个进程（通过调用）也可执行多个程序；其余三项均为标准表述。
下列事件中，可能引起进程从运行态转变为就绪态的是（ ）
A. 等待的 I/O 操作完成 B. 时间片用完 C. 申请的内存尚未得到 D. 进程执行了 exit
查看答案
B。时间片用完被剥夺 CPU → 回就绪队列。A：事件完成唤醒的是「阻塞中的进程」到就绪，而「等待 I/O 的运行进程」早已在阻塞态；C：资源未得 → 阻塞态；D：exit → 终止态。
在具有挂起机制的系统中，处于静止阻塞状态的进程所等待的事件发生后，该进程将转换为（ ）
A. 活动就绪 B. 静止就绪 C. 运行态 D. 活动阻塞
查看答案
B。事件发生只解除「等待」，不解除「静止」——它仍在外存，先成静止就绪；被激活后才为活动就绪。若答 A 等于认为「事件发生自动把进程换回内存」，越过了中级调度。
关于进程通信，错误的是（ ）
A. 匿名管道通信的双方通常须是有亲缘关系的进程
B. 采用共享内存方式通信时，对共享区的互斥访问由操作系统负责
C. 信号是所有通信方式中唯一的异步机制 D. 信箱通信属于间接通信，可实现多对多
查看答案
B。共享内存方式下内核只建立共享区，读写互斥与同步由用户进程自己（P/V）负责——B 恰好说反，这是高频陷阱。
下列关于线程的叙述中，正确的是（ ）
A. 用户级线程的切换必须陷入内核 B. 内核级线程中一个线程阻塞，同进程的其他线程仍可被调度运行
C. 线程是资源分配的基本单位 D. 多对一模型能充分利用多核并行
查看答案
B。内核感知每个线程，一个阻塞调度别的即可。A 错：用户级线程切换在用户空间线程库内完成；C 错：进程才是资源分配单位（线程是调度单位）；D 错：多对一只有一个内核执行流，单核轮转。
关于调度算法，错误的是（ ）
A. FCFS 对长作业有利，且不会出现饥饿
B. SJF 能使平均等待时间、平均周转时间最短，但可能导致长作业饥饿
C. HRRN 综合了 FCFS 与 SJF 的优点，不会饥饿
D. RR 中时间片越大，系统响应速度越快，性能越好
查看答案
D。时间片过大退化为 FCFS，响应变慢；过小则切换开销过大——要「适中」，不存在越大越好。A、B、C 均为标准结论。
(1) 互斥信号量 mutex 初值为 1，4 个进程并发执行各一次 P(mutex)（均未到 V），则 mutex 的值为 ______，阻塞的进程数为 ______；
(2) 信号量 S 初值为 4，完成 6 次 P、2 次 V 后，S = ______，等待队列中的进程数为 ______。
查看答案
(1) \(1-4=-3\)；阻塞 3 个（第一个进程正常进入临界区，后三个排队）。
(2) \(4-6+2=0\)；等待队列 空（=0 表示资源刚好耗尽、无人等待——第 2 个 V 唤醒了一个先前等待的进程，此值正是无等待时刻）。
生产者-消费者问题中，缓冲区已满（empty = 0、full = n）。生产者误将两个 P 写成「先 P(mutex) 再 P(empty)」，则（ ）
A. 生产者在 P(empty) 处阻塞，消费者正常消费，系统自动恢复
B. 消费者在 P(full) 处阻塞，形成生产者等消费者、消费者等锁的局面，系统死锁
C. 生产者持 mutex 等 empty，消费者在 P(mutex) 处阻塞，互相等待，系统死锁
D. 互斥锁自动释放，两进程均正常运行
查看答案
C。P(full)（full>0）能通过，消费者卡在 P(mutex)：锁在生产者手里；生产者卡在 P(empty)：空位要等消费者取走产品才释放——互等成环，典型「持锁等资源」死锁。恢复只能靠外力（剥夺 / 撤销进程）。
关于死锁，正确的是（ ）
A. 只要四个必要条件同时成立，系统一定死锁
B. 系统发生死锁时，四个必要条件一定同时成立
C. 系统进入不安全状态后一定发生死锁
D. 资源分配图中存在环路，系统一定死锁
查看答案
B。必要 ≠ 充分：A 错；C 错（不安全只是可能死锁）；D 错（每类资源多实例时有环也可能不死锁，需化简判断——死锁定理：不可完全化简 ⇔ 死锁）。
单 CPU 系统，非抢占式静态优先级调度（数字小者优先级高），进程如下：
| 进程 | 到达时间 | 服务时间 | 优先级 |
|---|---|---|---|
| J1 | 0 | 10 | 3 |
| J2 | 1 | 1 | 1 |
| J3 | 2 | 2 | 3 |
| J4 | 3 | 1 | 4 |
求调度顺序、各进程周转时间与平均周转时间、平均等待时间；并回答：若改为抢占式优先级调度，J2 的完成时刻是多少？
查看解答
非抢占：t=0 仅 J1 到达 → J1 运行 0–10（J2 于 t=1 到达也不能抢）；t=10 就绪队列 J2(1)、J3(3)、J4(4) → J2 运行 10–11 → J3 运行 11–13（同级 3 先到者优先）→ J4 运行 13–14。
完成：J1=10、J2=11、J3=13、J4=14。周转：10、10、11、11 → \(\overline T=10.5\)；等待 = 周转 − 服务：0、9、9、10 → 平均 7。
抢占式：J1 跑到 t=1 时 J2（优先级 1）到达即抢占 → J2 运行 1–2，完成时刻 = 2；J1 续跑 2–11；t=11 时 J3(3)、J4(4) → J3 11–13、J4 13–14（t=2~3 间 J3 到达但优先级 3 不高于 J1 的 3，先到先跑不抢占）。
易错：非抢占式下「更高优先级到达」不改变当前运行进程——除非题目说可抢占；同级优先级按到达先后。
公共汽车上，司机进程与售票员进程协同工作：司机启动车辆前必须确认车门已关；售票员开车门必须在车停稳之后。司机的活动：启动车辆、正常行驶、到站停车；售票员的活动：关车门、售票、开车门。用记录型信号量的 P/V 操作写出两进程的同步代码。
查看解答
两条同步关系：「关门 → 启动」（启动前要等到门关信号 door）；「停车 → 开门」（开门前要等到停车信号 stop）。
semaphore door = 0; // 车门已关（售票员 → 司机）
semaphore stop = 0; // 车已停稳（司机 → 售票员）
driver () { conductor () {
while (true) { while (true) {
P(door); // 等门关 关车门;
启动车辆; V(door); // 通知司机
正常行驶; 售票;
到站停车; P(stop); // 等车停
V(stop); // 通知售票员 开车门;
} }
} }检查三条模板：同步信号量初值 0 ✓；「前 V 后 P」（关门前 V(door) 在启动前 P(door) 之前；停车后 V(stop) 在开门前 P(stop) 之前）✓；无共享临界资源、不需要 mutex ✓。
某系统仅一类资源，共 12 个实例。当前 Available = 4，三进程状态：P0 分配 4 / 最大需求 10；P1 分配 2 / 最大需求 4；P2 分配 2 / 最大需求 9。判断系统是否安全并给出安全序列；若 P0 此时申请 1 个实例，能否立即分配？
查看解答
Need：P0 = 10−4 = 6，P1 = 4−2 = 2，P2 = 9−2 = 7。Work = 4：P1 的 Need 2 ≤ 4 ✓ → 归还后 Work = 6；P0 的 6 ≤ 6 ✓ → Work = 10；P2 的 7 ≤ 10 ✓ → Work = 12。安全序列 P1 → P0 → P2（或 P1 → P2 → P0：7 ≤ 6 ✗ 不行！P2 的 Need 7 大于 Work 6，故唯一次序是先 P0 后 P2）。
P0 申请 1：① ≤ Need[P0] = 6 ✓；② ≤ Available = 4 ✓；③ 试分配后 Available = 3，P0 分配 5、Need 5。安全性：P1 Need 2 ≤ 3 ✓ → Work = 5；P0 Need 5 ≤ 5 ✓ → 10；P2 ✓ → 12，仍安全（P1 → P0 → P2）→ 可以分配。
易错：试分配后 P0 的 Need 变成 5（不是 6），安全序列判断用新 Need——别忘了减去本次请求。
2.10 本章考点总结
| 考点 | 常考题型 | 热度 | 核心方法 |
|---|---|---|---|
| 进程状态转换（五态 / 七态） | 选择题 | ★★★★★ | 每条边的触发事件背熟；两条不可能边（就绪→阻塞、阻塞→运行）；挂起 = 换出内存，事件发生只解除阻塞 |
| PCB 与进程控制原语 | 选择题 | ★★★ | PCB = 标识 + 现场 + 控制信息，进程存在的唯一标志；五种原语步骤；原语在核心态 |
| 进程通信 | 选择题 | ★★★★ | 共享内存最快（同步用户管）；管道半双工 / 字节流 / 亲缘 / 读后即焚；消息直接 vs 信箱；信号唯一异步 |
| 线程与多线程模型 | 选择题 | ★★★★ | 进程 = 资源单位，线程 = 调度单位；内核感知与否定分水岭；多对一 / 一对一 / 多对多特性 |
| 调度算法计算 | 选择 + 大题 | ★★★★★ | 甘特图 → 完成时刻 → 周转 / 等待 / 带权；HRRN \(R=1+\) 等待 / 服务；RR「到达先入队、用完片插队尾」；多级反馈队列「时间片用完降级、被抢占回本队尾」 |
| 软件法 / 硬件法互斥 | 选择题 | ★★★★ | 单标志（违反空闲让进）、先检查（可同进）、后检查（都可不进）、Peterson（只差让权等待）；TS/Swap 原子但不让权 |
| P/V 操作设计 | 大题（每年必考） | ★★★★★ | 互斥夹紧 / 同步前 V 后 P / 先同步后互斥；生产者-消费者（empty/full/mutex）、读者-写者（count + 首尾锁 + 公平锁 w）、哲学家（限 4 / 奇偶 / 原子拿双）、苹果-橘子（plate + 各水果） |
| 银行家算法 | 大题 / 选择 | ★★★★ | Need = Max − Allocation；安全性算法五列表；请求三步（比 Need → 比 Available → 试分配查安全，不安全回滚） |
| 死锁条件 / 预防 / 检测 | 选择题 | ★★★★ | 四必要条件与破坏手段对应；死锁定理（不可完全化简 ⇔ 死锁）；解除：剥夺 / 撤销 / 回退 |