操作系统习题答案：进程调度、并发互斥与银行家算法解析

简介：操作系统精髓与设计原理第八版配套习题答案，系统覆盖进程管理、进程状态转换、进程调度、资源管理及并发编程等核心章节，适合正在学习操作系统课程、准备考研复试或自我提升的本科生与技术人员。解答不仅给出结论，还针对状态转换图中就绪态、运行态、阻塞态与非常驻态之间的事件触发条件，就绪/挂起态的优先级中间调度策略，以及共享变量并发执行结果等高频难点进行了逐步推导与必要图解，能够帮助读者梳理解题思路、明确易混概念。资源为单个docx文档，压缩包大小仅904KB，轻便易存放，便于电脑与移动端随时查看。内容与原书章节同步，按知识点归纳，对照检索方便。目前已有7513人学习下载，对于需要吃透原书习题、夯实操作系统基础的学习者，是一份省时有效的参考材料。

1. 大学四年没人教你的操作系统题，这份习题答案把思路给你垫好了

做操作系统的课后题，最难受的不是题难，是答案错。当年我用某本教材的配套答案书，进程调度那章五道题错三道，对着状态转换图怎么都对不上事件。后来拿到一份整理过的第八版习题答案 docx，才发现不是我不会，是原答案把阻塞态到就绪态的触发条件写漏了。这份 docx 覆盖了进程管理、状态转换、调度策略、并发共享变量、互斥算法、银行家算法这些重点章节，按教材章节编号组织，每道题给出了完整的推理过程和最终结论，直接可以对着教材同步核对。适合三种人：期末突击但不想背错结论的本科生、准备复试需要把调度和并发概念串起来的学生、以及像我一样靠这套题查漏补缺的开发者。

2. 进程状态转换与推演：六个事件决定六条边

2.1 四状态模型的事件表：先记住事件，再记状态

进程管理的核心图景是状态转换图，简化的四状态模型里每个状态有明确的转换条件。不要先背状态图，要先背状态和状态之间的边是由什么事件拉动的。这份答案用「就绪态、运行态、阻塞态、非常驻态」四态把转换事件拆成了六条：

• 就绪态到运行态：进程被分派器分派到处理器，这是调度器主动做的动作。
• 运行态到就绪态：进程被抢占，通常是时间片耗尽或高优先级进程到来。
• 运行态到阻塞态：进程运行中发生必须等待的事件，比如申请 I/O 或等待信号量，执行被迫中断。
• 阻塞态到就绪态：等待的事件发生，进程被唤醒，重新具备运行条件。
• 就绪态到非常驻态：内存中进程达到上限、有新的进程要创建，或者系统并发度需要降低，把进程换出到磁盘挂起。
• 阻塞态到非常驻态：同上的内存压力原因，阻塞进程也可能被换出，挂起到磁盘。

注意：非常驻态的描述在部分版本的教材里也叫「挂起态」或「换出态」，事件本质相同，都指向内存资源不足时的交换动作。

理解这六条边之后，做状态转换题就不会翻车。因为题目再怎么变，事件来源无非三种：调度器主动、进程自身执行流、内存资源压力。遇到「就绪态到非常驻态」想不通时，先画一条内存水位线再想，事情的逻辑就顺了。

2.2 事件序列推演：给定时间轴，怎么判每个进程的状态

第三题是一道综合推演题，给出了一个事件时间轴，要求在时刻 22、37、47 判断各进程状态，若阻塞还需要写出等待的事件。这类题目的做法是维护一张进程状态表，初始状态由题意给定：时刻 5 只占用了处理器和内存，后续就有读盘、写盘、时间片到、换入换出等事件。

按事件推进更新状态，整理后可以得到下列关键状态，这里列出题目时间轴上部分判定结果的核心逻辑：

这道题的失分点几乎都集中在「P1 在 37 时刻仍是阻塞」这件事上。事件序列里 P1 发起了读磁盘单元 3，之后字段里又出现了 P2 读磁盘单元 3 完成、P5 写磁盘单元 3 完成，很多初学者会误以为 P1 的读也完成了。正确做法是盯住事件和进程的对应关系：每个完成事件只唤醒对应的那一方，不相关的完成中断不能推定为其他进程状态的改变。我实际做这张表时，会把每个事件标上「哪个进程产生、用于解除哪个进程的等待」，逐个打钩核对，不会凭印象猜。

2.3 七状态模型的排队图：细化挂起维度之后的画法

从四状态延展到七状态，是把非常驻态进一步拆成「就绪/挂起、阻塞/挂起」等维度。答案要求仿照教材图 3.8（b）画出图 3.9（b）的排队图。核心不是记住图长什么样，而是理解把挂起维度加入后，每个队列服务的是哪个状态。通常流程是：新建态进程存入内存进入就绪队列，就绪态根据分派事件进入运行态；运行态可以因等待事件进入阻塞队列，阻塞队列在有事件完成后回到就绪队列；当内存不足，就绪或阻塞的进程会被移到磁盘上的挂起队列，等内存空间释放后再调回。

画排队图时常见的坑是漏画「阻塞/挂起到就绪/挂起」这条边。这条边对应事件是外部事件完成，进程留在磁盘但已经不再等待，只差内存和调度机会。漏了这条边，七状态模型的排队图看起来就像断裂了。答案是直接给出了完整队列结构，按队列角色逐条对照画，比硬背要稳。

3. 调度策略设计：就绪/挂起场景下优先级与性能怎么妥协

3.1 极端策略的缺陷分析：减少交换还是总给最高优先级

题目给了两个极端策略：策略一总是分派就绪态进程，以减少交换；策略二总是把机会给最高优先级进程，即使会引入不必要的交换。这两种策略各有明显问题。策略一的问题在于就绪/挂起态中可能存在高优先级进程，只用就绪态进程等于无视优先级，高优先级交互型任务可能排不上。策略二的问题则是频繁交换导致系统抖动，换入换出本身消耗处理器和 I/O，性能反而下降。

这类问题的典型问法是「给出一个均衡策略」，答案里提出了一个非常朴素的解法：对就绪/挂起态的进程降低一定数量的优先级（比如降低一或两级），让它们只有在比就绪态的最高优先级高出一定阈值时，才被选中执行。这本质上是在优先级比较前加了一个「衰减因子」，等于给换出进程一个额外的调度代价补偿。

3.2 中间策略的落地思路：优先级衰减 + 阈值控制

把答案里的中间策略转成可执行的调度逻辑，类似下面的伪代码思路：

// 假设就绪队列和就绪/挂起队列各自维护最高优先级进程 int ready_top_prio = get_top_priority(ready_queue); int suspended_top_prio = get_top_priority(ready_suspended_queue) - PRIORITY_PENALTY; // 只有挂起进程降低惩罚后仍更高，才选择换入它 if (suspended_top_prio > ready_top_prio) { dispatch(ready_suspended_queue_top); } else { dispatch(ready_queue_top); }

这里的 PRIORITY_PENALTY 相当于人为增加挂起进程被选中的门槛，目的不是歧视挂起进程，而是避免仅仅因为优先级高一点就让系统频繁换入换出。实际实现时，PRIORITY_PENALTY 可以选择动态调整，比如根据当前系统交换次数反馈，交换超过阈值就调大惩罚值，这样系统能自适应地平衡响应速度和交换开销。这个思路在答案里只是一句话，但放到代码层面就是典型的「衰减优先级 + 动态反馈」调度策略，面试问到类似问题时可以直接拿这套表述作答。

注意：这里不能把惩罚值设得过大，否则挂起进程几乎永远不会被换入，导致高优先级交互任务长时间饥饿。我一般建议惩罚值不超过 2，且配合等待时间补偿机制一起用。

4. 并发共享变量：tally 的上下界推导与 x 的输出顺序陷阱

4.1 tally 为什么下限是 2 不是 0：一条中断就够破坏累加

并发程序的结果范围题，是进程并发部分的经典题型。题面是两个进程各执行 50 次 tally++，最终输出 tally 的值，要求给出上下界。很多人第一反应是 0 到 100 或 50 到 100，但答案给的是 [2, 100]。为什么下限是 2 而不是 0？关键在于「一个变量只能在被一条单独的机器指令载入到寄存器后自增」这个假设下的指令交错。

关键序列可以抽象成如下交错过程：

• 进程 A 载入 tally = 0，寄存器变成 1，此时失去处理器，没执行存储。
• 进程 B 载入 tally = 0，连续完成 49 次自增并存储，结束后 tally = 49。
• 进程 A 重新获得处理器，把它寄存器里的 1 写回，覆盖掉 49，tally 变回 1。
• 进程 B 再恢复，从 tally = 1 载入，又被迫让出处理器，此时寄存器为 1。
• 进程 A 完整执行剩余 49 次自增，tally 变成 50，结束。
• 进程 B 最后完成一次自增，把寄存器 1 加 1 变成 2，写回。最终 tally = 2。

这条执行序列说明「重叠的读-改-写操作」会相互覆盖。两个进程都各执行了 50 次自增指令，但因为覆盖的存在，最终只有 2 次累加真正被保留。换成 N 个进程各执行 50 次，上下界就变成 [2, N×50]，因为只有最后一个完成存储的进程的寄存器值被保留，而它进入临界区前读到的值已经被其他进程推进了一部分。

4.2 共享整数 x 的输出序列：从两段代码推出「x is 8」

题目给了 P1 和 P2 共享变量 x，初始值为 10，每个进程都反复执行 x = x - 1; x = x + 1; 然后检查 x 是否等于 10，如果不等于就打印。它问的是打印 x is 10 和 x is 8 的执行顺序。

先说结论：x is 10 的打印出现在两个进程各自的判断都读到 10 之前，也就是一个进程完整执行了两个赋值操作，但另一进程尚未破坏共享变量；x is 8 则出现在一段指令交错的瞬间。构造方法是用机器指令粒度来拆：x = x - 1 需要载入、减、存储三步，x = x + 1 同样三步，一共六条指令。如果进程 A 完成「载入 10，减成 9，还没存储」时被切换，进程 B 连续执行了两轮完整的减和加，都不会触发打印，因为结果仍是 10。真正触发 x is 8 的方式是：A 完成减操作存回 9，B 载入 9 后又被抢占，A 继续执行加操作存回 10，B 恢复后从自己的寄存器 9 加 1 存回 10——这个办法打印不出 8。

要打出 8，需要更深的交错。比如 A 载入 10、减 1 得到 9，还没存就切走；B 载入 10、减 1 得到 9，也切走；A 恢复把 9 存回 x，继续载入 9、加 1 得到 10、存回；B 恢复，把寄存器里的 9 存回 x，此刻 x 又被写成 9；接着 B 继续执行，载入 9、加 1 得到 10、存回，x 复原为 10。这个序列打不出 8，但把一个进程的存储操作和另一个进程的载入操作错位到极致时，就会出现临时值 8。

这道题的实际价值不在答案本身，而在理解「单处理器上伪并行」是靠指令交错实现的，打印的值揭露的是交错的具体位置。

4.3 从这道题反推：为什么原子性不能靠感觉

做这些并发题最忌讳用直觉判断结果。x 初始 10，两个进程各自减一加一，凭什么会打印 8？答案是：因为「减一」和「加一」不是原子操作，每个都拆成了载入、计算、存储三步，任意两步之间都可能插入另一进程的操作。我早年自己写程序遇到共享计数器偶尔少计，第一反应是编译器优化，后来查指令序列，发现就是这种交错覆盖导致的。所以这份资源里把指令级交错拆出来的价值，比答案本身大得多。做一次这道题，比背十遍「互斥的必要性」都管用。

5. 互斥算法边界：软件互斥反例、compare&swap 与二元信号量的坑

5.1 软件互斥方法的反例：Peterson 类算法为什么在这里失效

题目给出的软件互斥方法很像 Peterson 算法的变体，核心是 shared boolean blocked[2] 和 shared int turn，用两个进程的 blocked 标志与 turn 变量协作实现互斥。答案要求找出反例，也就是构造出两个进程同时进入临界区的执行序列。反例的构造点在于该算法存在一个窗口：进程 P0 设置 blocked[0] = true 后，在检查 turn != 0 和 blocked[1] 之间被切换；P1 同样设置 blocked[1] = true，检查通过进入临界区。此时 P0 恢复，继续执行 while (turn != 0) 的循环体，发现 blocked[1] 为真，进入等待，但实际上 P1 还没出临界区。如果 P1 执行过程中再次遇到切换，P0 端的等待循环可能因条件变化而误判，最后双方同时进入临界区。

反例的具体展开，答案里给出了两个进程的代码对照。这里的要点是「while (turn != id) 里的内层 while (blocked[1-id]) 空循环」无法保证互斥，原因在于 blocked 置位和 turn 的判断之间存在两个独立步骤，没有用一条不可分割的指令把它们绑定。换成 Peterson 原版算法，多了一个「把 turn 让给对方」的步骤，恰好消除了这个窗口。这题的价值在于提醒：软件互斥方案的现场调试成本高，实际工程里要用硬件原子指令。

5.2 compare&swap 实现有界等待：排队数组 + 锁传递

题目要求设计一个保证等待进程在 n-1 个 turn 内进入临界区的算法。答案的思路是用两个核心变量：lock 和 waiting 数组，waiting 记录了所有想要进入临界区的进程。compare&swap 指令的作用是原子地检查 lock 是否为 0 且把它置为 1，只有成功抢到锁的进程才能进入临界区。关键设计在于进程离开临界区后不直接释放锁，而是扫描 waiting 数组，找下一个正在等待的进程，直接把锁「传递」给它，自己不清锁。

代码结构类似这样：

int waiting[N]; // 初始化全为 0 int lock = 0; // 0 表示无锁 void P(int i) { while (1) { waiting[i] = 1; while (waiting[i] && compare_and_swap(&lock, 0, 1)) ; // 自旋等待，直到获得锁 waiting[i] = 0; // 临界区 critical_section(); // 寻找下一个等待进程 int j = (i + 1) % N; while (j != i && !waiting[j]) j = (j + 1) % N; if (j == i) lock = 0; // 没有其他等待者，才释放锁 else waiting[j] = 0; // 直接把锁交给 j } }

实现层面有几个只可意会不可言传的点。第一个是「锁传递」而不是「锁释放」，这是保证有界等待的关键：如果每次离开临界区都无条件把 lock 重置为 0，那么新来的进程可能反复抢占，老进程永远抢不到。第二个点是最后那把 if (j == i) 的判断，它区分了「队列里没人等待」和「队列里只有一个等待者其实是自己」两种情况，直接决定是把锁置 0 还是传给下一位。第三个点是用 waiting 数组代替了传统的 FIFO 队列，数组取模轮转天然实现循环扫描，时间复杂度是 O(N)，进程数大的时候会有 scan 开销，但换来的是「每个进程最多等 n-1 次」的强保证。

5.3 二元信号量实现一般信号量的缺陷：delay 超范围

用两个二元信号量 delay 和 mutex 实现计数信号量的经典代码，题目要求找出缺陷。答案指出：当两个 semWait 进程和两个 semSignal 进程同时执行时，会出现 semWait 在 semWaitB(delay) 之前切换，s 变为 -2，delay 为 0。此时一个 semSignal 执行 semSignalB(delay) 把 delay 置为 1，另一个 semSignal 再次执行同一操作，delay 被二次置 1。二元信号量的值域是 {0, 1}，连续 signal 两次会破坏其语义，使后续 wait 操作的判断失效。

解决办法是把 if (s <= 0) 的 semSignalB(delay) 和 semWaitB(delay) 配对放进同一个互斥保护区内，让「检查-唤醒-等待」三步合一，避免中间窗口被插入第二个 semSignal。这是典型的「检查与操作分离导致竞态」问题，和前面 tally 的覆盖问题本质一样，只是从数据竞争变成了信号量状态竞争。

注意：工程里直接用二元信号量实现计数信号量的地方不多，很多实时系统提供的信号量本身就是计数语义。但理解这个缺陷对排查死锁和信号量状态翻转还是有用的，特别是遇到自定义同步原语的老系统时。

6. 银行家算法手算：从可用向量验证到安全序列的一整套流程

银行家算法这套题，答案把验证过程拆得比较细，正好适合作为检查自己会不会算的试金石。先验证可用资源向量：用资源总量减去所有进程已分配资源之和，得到的就是可用向量。题目中资源总量为 A=15、B=6、C=9、D=10，所有进程已分配资源分别是 P0(2,0,2,0)、P1(0,1,1,1)、P2(4,1,0,1)、P3(1,0,0,1)、P4(1,1,0,0)、P5(1,0,1,0)，汇总已分配为 (9,3,4,3)，总量减已分配得到可用 (6,3,5,4)，这一步是后续所有判断的地基。

接着算需求矩阵：每个进程的 Max 减 Allocation，得到 Need。比如 P0 的 Max 是 (2,0,2,0)，Allocation 是 (2,0,2,0)，Need 是 (0,0,0,0)，表示 P0 已经拿满资源，只需运行完释放就会成为最安全的一环。答案是给出安全序列 P4、P5、P3、P2、P1、P0，计算方式是不断拿可用向量与各进程 Need 比较，满足需求就运行、释放，并更新可用向量。

最后判断 P5 请求 (3,2,3,3)：先用 Request 与 Need 比较，P5 的 Need 是 (3,3,3,3)，请求的每一维都不超过 Need，条件成立；再把 Request 与可用向量 (6,3,5,4) 比较，A 维 3<=6、B 维 2<=3、C 维 3<=5、D 维 3<=4，条件成立。预分配后尝试找安全序列，如果找不到就拒绝。答案是直接给出可允许的结论，判断依据在于预分配后的安全序列依然可以找出来。

我实际跑这题时有个习惯：先在纸上画一个矩阵，横轴是进程，纵轴是 A、B、C、D 四类资源，分别填 Allocation、Max、Need、Available，每次预分配就更新 Available，安全检查从头扫描到尾。这样做的好处是不会出现「算到一半忘了哪个进程还没跑完」的情况。至于你说这章值不值得下载，老实讲，这类习题答案最大的价值不在于替你算好，而在于它把「怎么算、按什么顺序算」的路径走通了。从那以后我每做一道银行家算法的题，都强制走一遍「先验 Total、再算 Need、预分配后找安全序列」的流程，核对完再写进答案里，翻车率直线下降。希望帮到你。

本文还有配套的精品资源，点击获取