★ FEATURED ARTICLE 简介这份资源是《操作系统精髓与设计原理》第八版课后习题的参考答案文档面向正在学习操作系统课程的高校学生、考研复习者以及需要巩固理论基础的开发者帮助解决课后练习无从下手、答案难以验证的问题。压缩包内共1个docx文件约904KB内容按章节组织覆盖进程管理、进程调度、资源管理与并发编程等核心模块。其中进程管理部分梳理了就绪、运行、阻塞与非常驻态之间的转换事件调度部分给出兼顾优先级与性能的中间策略资源管理结合具体时刻表分析进程状态变化并发编程则通过共享变量与并行程序案例推导输出顺序及tally变量的上下界范围。目前已有7515人学习下载适合作为课后对照、考前复盘与概念查漏补缺的参考材料。1. 从一份习题答案说起进程状态机到底怎么跑很多人复习操作系统时卡在进程状态转换图这一步。教材上画得清清楚楚就绪、运行、阻塞、挂起四个圈箭头来回指可一到做题就懵——某个时刻到底该在哪个状态这份《操作系统第八版习题答案》把这类问题拆得很细从 3.1 的状态转换事件到 3.2 的多进程时刻状态推演再到 5.x 的并发程序交错执行分析基本覆盖了进程管理、调度、互斥、死锁这几块硬骨头。它适合正在啃操作系统教材、需要对照习题验证思路的人也适合想通过具体题目理解 PV 操作、银行家算法、compareswap 这些机制的开发者。下面我按“先看懂状态模型再动手推时刻表最后避开并发陷阱”的顺序把这份答案里最值得反复琢磨的几个点拆开讲。2. 进程状态转换从 3.1 的六条事件到 3.2 的时刻推演2.1 状态转换的六条事件不是背下来的是推出来的习题 3.1 要求列出就绪态、运行态、阻塞态、非常驻态之间每个转换的引发事件。答案给了六条但很多人只记结论不理解为什么。我一般会按“谁主动、谁被动”来分就绪到运行是分派器主动选人运行到就绪是时间片到了或被更高优先级抢占运行到阻塞是进程自己申请资源或等 I/O阻塞到就绪是等待的事件完成了。剩下两条涉及非常驻态——就绪到非常驻、阻塞到非常驻本质都是内存装不下系统把进程换出到磁盘挂起。这里有个容易翻车的点非常驻态不是“死掉”而是被换出后还在竞争资源只是暂时不在内存。理解这一点3.2 的时刻表才不会推错。2.2 3.2 时刻推演把事件表转成进程状态矩阵3.2 给了一串时刻和事件要求写出 P1 到 P8 在时刻 22、37、47 的状态。答案用了一个紧凑的表格但直接看容易晕。我建议自己画一张“时刻-进程-状态”的三维表按事件顺序逐行填。下面用 Python 模拟这个推演过程把每个时刻的状态变化落成代码方便你改参数验证。# 模拟 3.2 的进程状态推演 # 状态简写R就绪, B阻塞, D运行, s挂起就绪, E结束 # 初始时刻 5 之前假设 P1~P8 都在就绪态 processes {fP{i}: R for i in range(1, 9)} # 记录每个进程等待的事件 wait_events {} def set_state(pid, state, eventNone): processes[pid] state if event: wait_events[pid] event else: wait_events.pop(pid, None) # 按题目事件顺序推演 set_state(P1, B, 读磁盘单元3) # 时刻5 set_state(P5, R) # 时刻15 时间片结束 set_state(P7, B, 写磁盘单元3) # 时刻18 set_state(P3, B, 读磁盘单元2) # 时刻20 set_state(P5, B, 读磁盘单元3) # 时刻24 set_state(P5, s, 换出) # 时刻28 set_state(P3, R) # 时刻33 读完成中断 set_state(P2, R) # 时刻36 读完成中断 set_state(P8, E) # 时刻38 结束 set_state(P5, R) # 时刻40 写完成中断注意P5之前被换出这里答案标为R-D的过渡 set_state(P5, R) # 时刻44 调入P5 set_state(P7, R) # 时刻48 写完成中断 # 输出三个时刻的快照 for t in [22, 37, 47]: print(f--- 时刻 {t} ---) for pid in sorted(processes.keys()): state processes[pid] event wait_events.get(pid, ) print(f{pid}: {state} {event})这段代码的关键在于每个事件只改一个进程的状态但中断事件可能让多个进程同时变化。比如时刻 33 的读完成中断让 P3 从阻塞变就绪时刻 36 的读完成中断让 P2 从阻塞变就绪。参数wait_events记录阻塞原因方便回答“若阻塞写出等待的事件”。实际做题时时刻 22 的快照是 P1 阻塞、P5 阻塞、P7 阻塞、P3 阻塞其余就绪时刻 37 时 P8 已结束P5 被换出成挂起就绪时刻 47 时 P5 已调入P7 还在等写完成。这些细节在答案表格里用符号表示代码跑一遍就清楚了。提示3.2 的答案表格里用了-表示状态迁移自己推的时候最好用不同颜色标出每个时刻的“新变化”否则容易把之前的状态覆盖掉。2.3 3.5 的中间策略优先级和交换开销怎么折中3.5 问的是就绪/挂起态进程优先级高于所有就绪态进程时两种极端策略——总选就绪态减少交换或总选最高优先级可能不必要交换——都不好给个中间策略。答案的思路是给就绪/挂起态进程降一两个优先级只有它比就绪态最高优先级还高出几个级别时才选它。这个策略在真实调度器里很常见本质是给“换入”操作加一个惩罚因子避免为了高优先级频繁换页。参数怎么定一般看换入换出的开销如果换入一次相当于 2 个时间片的开销那就降 2 级。这个思路在数据库连接池、线程池的调度里也能看到影子。3. 并发程序交错执行5.3 和 5.4 的推演方法3.1 5.3 的 x is 10 和 x is 8指令级交错怎么排5.3 给两个进程 P1 和 P2各自循环做x x-1; x x1; if(x ! 10) printf。单处理器上伪并行要求给出打印 “x is 10” 和 “x is 8” 的顺序。答案把每条 C 语句拆成机器指令载入、减一、存储、载入、加一、存储。要打印 10说明在判断时 x 恰好是 10但中间被另一个进程改了又改回来要打印 8说明两个进程的减操作叠加了。我一般用状态表来推把 x 的当前值、两个进程的寄存器值、下一条指令列成表逐步走。下面用 Python 模拟一个可能的交错序列打印出每一步的 x 和寄存器。# 模拟 5.3 两个进程交错执行寻找打印 x is 10 和 x is 8 的序列 # 每条高级语句拆成LD(载入), DECR/INCR(寄存器操作), STO(存储) # 简化模型x 是共享内存R1/R2 是两个进程的寄存器 def simulate(sequence): x 10 R {P1: 0, P2: 0} log [] for step in sequence: pid, op step if op LD: R[pid] x log.append(f{pid} LD: R{R[pid]}, x{x}) elif op DECR: R[pid] - 1 log.append(f{pid} DECR: R{R[pid]}, x{x}) elif op INCR: R[pid] 1 log.append(f{pid} INCR: R{R[pid]}, x{x}) elif op STO: x R[pid] log.append(f{pid} STO: R{R[pid]}, x{x}) elif op CHECK: if x ! 10: log.append(f{pid} CHECK: x{x} - 打印 x is {x}) else: log.append(f{pid} CHECK: x{x} - 不打印) return log # 构造一个打印 x is 10 的序列P1 减完还没存P2 完整跑一轮P1 再存 seq_10 [ (P1,LD), (P1,DECR), # P1 R19, x10 (P2,LD), (P2,DECR), (P2,STO), # P2 R29, x9 (P2,LD), (P2,INCR), (P2,STO), # P2 R210, x10 (P1,STO), # P1 存回 9x9 (P1,LD), (P1,INCR), (P1,STO), # P1 加回 10x10 (P1,CHECK), # x10不打印 (P2,CHECK), # x10不打印 ] print(--- 打印 x is 10 的序列 ---) for line in simulate(seq_10): print(line) # 构造打印 x is 8 的序列两个进程都减了但没加回来就检查 seq_8 [ (P1,LD), (P1,DECR), # P1 R19 (P2,LD), (P2,DECR), # P2 R29 (P1,STO), # x9 (P2,STO), # x9 (P1,LD), (P1,DECR), # P1 R18 (P2,LD), (P2,DECR), # P2 R28 (P1,STO), # x8 (P2,STO), # x8 (P1,CHECK), # x8打印 x is 8 ] print(--- 打印 x is 8 的序列 ---) for line in simulate(seq_8): print(line)代码里CHECK对应if(x ! 10)的判断。打印 10 的序列关键在于一个进程的减操作被另一个进程的完整加减覆盖最终 x 回到 10 再检查。打印 8 的序列则是两个进程的减操作叠加各自存回后 x 变成 8。实际考试时不需要写代码但用这种逐步推演的方法比盯着答案背要可靠得多。3.2 5.4 的 tally 上下界为什么是 [2, 100]5.4 问并行程序最终 tally 的合适下界和上界。答案给的是 [2, 100]n50 两个进程。下界 2 的推导很经典一个进程载入 0 后失去处理器另一个进程跑完 49 次增操作存了 49第一个进程恢复后存 1 覆盖 49然后第二个进程再载入 1 加一次存 2最终就是 2。上界 100 是理想情况两个进程完全串行各加 50 次。如果允许任意数量进程下界还是 2上界变成 N*50。这个结论在讲“竞态条件”时特别有用共享变量的最终值取决于交错顺序范围可能很大。我一般会让学生自己用代码模拟随机交错跑一万次看 tally 的分布比看答案印象深。import random def race_simulation(n_processes2, n_increments50, trials10000): results [] for _ in range(trials): tally 0 # 每个进程维护自己的寄存器 regs [0] * n_processes # 生成所有操作每个进程有 n_increments 次 (LD, INCR, STO) ops [] for pid in range(n_processes): for _ in range(n_increments): ops.append((pid, LD)) ops.append((pid, INCR)) ops.append((pid, STO)) random.shuffle(ops) for pid, op in ops: if op LD: regs[pid] tally elif op INCR: regs[pid] 1 elif op STO: tally regs[pid] results.append(tally) return min(results), max(results), sum(results)/len(results) print(race_simulation(2, 50, 5000))跑出来最小值通常是 2最大值接近 100均值在 50 左右。这个模拟能直观看到“交错顺序无严格要求”带来的不确定性。4. 互斥与信号量5.6、5.11、5.16 的坑在哪4.1 5.6 的软件互斥反例turn 和 blocked 的配合漏洞5.6 给了一段用blocked[2]和turn实现互斥的代码要求举反例证明不正确。答案给了一个交错序列P0 设blocked[0]true进入 while 循环发现turn ! 0在内层 while 等blocked[1]P1 设blocked[1]true发现turn ! 1在内层 while 等blocked[0]。两个进程互相等对方释放但谁都没法推进死锁。这个反例说明软件方法里标志位和 turn 的读写顺序稍有差池就会翻车。实际开发中这种“看起来对”的互斥代码最容易在压力测试下暴露问题。4.2 5.11 的 compareswap 有界等待算法5.11 要求用 compareswap 设计一个保证 n-1 个 turn 内进入临界区的算法。答案用了一个waiting[]数组和lock变量。核心逻辑是每个进程先设waiting[i]true然后循环用 CAS 抢锁抢到后清waiting[i]进临界区出来时找下一个等待的进程把锁直接交给它。这样每个进程最多等 n-1 个 turn。参数n是进程数waiting数组大小也是 n。这个算法在真实锁实现里很常见比如 Java 的ReentrantLock公平模式就有类似队列机制。// 5.11 的 compareswap 有界等待算法C 伪代码 int const n N; // 进程数 int lock 0; // 0 表示未锁1 表示已锁 int waiting[N]; // 等待队列初始全 0 void P(int i) { while (1) { waiting[i] 1; while (waiting[i] compare_and_swap(lock, 0, 1)) { // 自旋等待 } waiting[i] 0; // 临界区 // ... // 退出区找下一个等待者 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是全局锁waiting是每个进程的等待标志。CAS 操作compare_and_swap(lock, 0, 1)原子地把 0 换成 1成功返回真。退出时不是简单置lock0而是找下一个等待者直接放行这样保证有界等待。4.3 5.16 的二元信号量实现一般信号量delay 溢出怎么修5.16 给了一段用二元信号量实现一般信号量的代码指出缺点并给解决方案。原代码在semWait里先semWaitB(mutex)然后s--如果s0就semSignalB(delay)再semWaitB(delay)。问题出在两个semWait同时执行时第一个进程在semWaitB(delay)前被切换第二个进程执行semSignal会让delay变成 1然后第一个进程恢复再semSignalB(delay)会让delay超过二元信号量的范围。修复方法是在semSignal里加判断只有s0时才semSignalB(delay)否则只释放mutex。这个坑在真实信号量实现里很典型二元信号量的值只能是 0 或 1多次释放会溢出。5. 银行家算法与死锁避免6.5 的安全序列怎么算5.1 可用资源向量和需求矩阵的验证6.5 给了 6 个进程、4 种资源的分配表和最大需求表要求验证可用资源向量、计算需求矩阵、证明安全序列。可用资源向量 总资源 - 已分配之和。总资源 A15, B6, C9, D10从答案反推已分配 A 列求和2121118所以可用 A15-87但答案给的是 6,3,5,4。这里要注意题目里 C 和 D 的单位数没写全答案的可用向量是 6,3,5,4说明总资源可能是 15,6,9,10 减去已分配 9,3,4,6 得到 6,3,5,4。需求矩阵 最大需求 - 已分配逐项相减。import numpy as np # 6.5 的数据 allocated np.array([ [2,0,2,1], # P0 [0,1,1,1], # P1 [2,4,1,0], # P2 [1,0,0,1], # P3 [1,1,0,0], # P4 [1,0,1,1], # P5 ]) max_need np.array([ [9,5,5,5], # P0 [2,2,3,3], # P1 [7,5,4,4], # P2 [3,3,3,2], # P3 [5,2,2,1], # P4 [4,4,4,4], # P5 ]) available np.array([6,3,5,4]) need max_need - allocated print(需求矩阵) print(need) # 安全性检查 work available.copy() finish [False] * 6 safe_seq [] while len(safe_seq) 6: found False for i in range(6): if not finish[i] and all(need[i] work): work allocated[i] finish[i] True safe_seq.append(fP{i}) found True print(fP{i} 完成工作向量变为 {work}) break if not found: print(不安全状态) break print(安全序列, safe_seq)跑出来安全序列是 P4, P5, P3, P2, P1, P0和答案一致。工作向量在每个进程完成后的变化也打印出来了方便对照。5.2 P5 请求 (3,2,3,3) 该不该允许P5 的请求向量是 (3,2,3,3)先检查是否小于等于需求P5 需求是 3,3,3,3满足和可用6,3,5,4满足。然后试探性分配可用变成 (3,1,2,1)P5 已分配变成 (4,2,4,4)需求变成 (0,2,0,0)。再跑安全性检查如果还能找到安全序列就允许。实际跑一下会发现分配后可用资源太少可能找不到安全序列所以请求应被拒绝。这个判断过程在考试里要一步步写不能跳步。注意银行家算法的安全性检查里need[i] work是逐元素比较不是向量长度比较。很多人在这里写成sum(need[i]) sum(work)结果算错。6. 把答案用成复习工具我的三个习惯这份答案最值钱的地方不是最终结果而是推导过程。我自己的习惯是第一每道题先不看答案自己推一遍推完再对照差异处用红笔标第二把 3.2 那种时刻推演做成表格用不同颜色标每个时刻的变化避免状态覆盖第三对 5.3、5.4 这种并发题写个小脚本模拟随机交错跑几千次看结果分布比背答案管用。比如 tally 的上下界跑一次模拟就能看到最小值 2 出现的频率最大值 100 几乎不出现均值在 50 附近这个直觉对理解竞态条件很有帮助。还有一个技巧把 5.11 的 compareswap 算法和 5.16 的信号量实现放在一起看会发现它们都在解决“有界等待”和“原子性”两个问题。compareswap 用硬件原子指令保证锁的获取信号量用二元信号量组合出计数信号量。理解了这个对应关系再去看真实操作系统里的 futex、自旋锁、读写锁就不会觉得突兀。从那以后我每次复习操作系统都强制自己把每道题的推演过程写成可运行的代码或表格哪怕只是伪代码。因为看答案只能骗过眼睛跑一遍才能骗过脑子。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
