简介这份《计算机操作系统教程》左万利、王英第四版课后习题答案面向正在学习操作系统课程、准备期末考试或考研复习的高校学生用于核对课后重点习题的解题过程与结论。整包仅含 1 个 doc 文档约 4.21MB内容按章节整理便于对照教材逐题查阅。文档覆盖进程调度、实时调度、死锁避免与同步互斥等核心章节第三章给出 EDF 与 RMS 调度判断及 Gantt 图并汇总 FCFS、SJB、HRN 三种算法下平均周转时间、平均带权周转时间的计算第四章讨论读者/写者问题的信号量解法与写者优先策略第五章借助银行家算法判断安全状态并演示死锁检测中资源请求后的状态变化。文档以教材习题编号为线索重点呈现调度计算表、资源分配表与安全序列推导适合课后自测与考前查漏补缺。已有 6331 人学习下载适合需要逐题复盘、梳理计算步骤与验证答案的读者参考。1. 拿到左万利、王英第四版课后习题答案先别急着对答案多数人用这份答案的姿势是写完一题翻到答案对上了打勾对不上抄一遍然后合上。等考试里出现「用 PV 操作描述生产者与消费者」抄过的那三行信号量早就想不起谁先谁后。真正卡住人的地方往往不是算错而是判定条件读偏了。信号量初值取几、物理块初始装几页、安全序列从哪一行开始排、磁盘调度题里磁头初始朝哪个方向走这些前提在习题答案里都是以结果的形式给出的答案本身不会告诉你它为什么这么假设。抄结果等于跳过了建模这一步。把《计算机操作系统教程》这本教材的课后习题答案当成一组验证用例更划算先用课本上的判定规则手推一遍再用几十行代码把同一道题跑一遍两者对得上说明模型建对了对不上就是概念优先级排错了。这套方法适合正在上操作系统课的学生、准备考研操作系统科目的同学也适合工作几年后想拿这些经典题重新校准底层认知的开发者。同一道 PV 题在慕课版、汤小丹版里编号和表述都不同所以练的是方法不是题号。2. 计算机操作系统教程课后习题答案的同步互斥主线2.1 PV 操作题的答案其实只有四种骨架教材里的同步互斥习题凡是要求「用 P、V 操作实现 XX」答案结构基本落在四类上单互斥、互斥加同步、资源计数、有限缓冲。判分逻辑也跟着这三件事走——先数清有几个互斥资源再数清有几组前后依赖最后确定每个信号量的初值。题型信号量个数典型初值答案里的关键判定点单互斥11P、V 严格包住临界区边界不多不少生产者-消费者3mutex1、emptyn、full0先申请资源信号量再申请互斥信号量读者-写者3 到 4rmutex1、wmutex1、计数器互斥第一个读者 P(wmutex)最后一个读者 V(wmutex)哲学家进餐5每把叉一个初值为 1必须破坏循环等待不能顺序拿叉最容易失分的是第二类。缓冲区满时如果先 P(mutex) 再 P(empty)生产者会抱着互斥锁进入等待消费者永远进不来整段代码直接变成死锁。答案里那个顺序看起来随意实际上就是这道题的考点本身。2.2 用 Python 信号量把生产者-消费者的标准答案跑出来光看答案看不出死锁把顺序换一下就能亲眼看到程序卡住。下面这段代码和教材答案是一一对应的。import threading, time, random BUFFER_SIZE 5 buffer [] mutex threading.Semaphore(1) # 互斥信号量保护 buffer empty threading.Semaphore(BUFFER_SIZE) # 空槽位计数初值等于缓冲容量 full threading.Semaphore(0) # 已占用槽位计数初值为 0 def producer(pid): for i in range(3): item fP{pid}-{i} empty.acquire() # 先申请资源有空位才继续 mutex.acquire() # 再申请互斥进临界区 buffer.append(item) print(f[producer {pid}] put {item}, buffer{buffer}) mutex.release() full.release() # 通知消费者多了一个满槽 time.sleep(random.random() * 0.1) def consumer(cid): for _ in range(3): full.acquire() # 先等有数据 mutex.acquire() item buffer.pop(0) print(f[consumer {cid}] get {item}, buffer{buffer}) mutex.release() empty.release() # 通知生产者空出一个位置 time.sleep(random.random() * 0.1) ps [threading.Thread(targetproducer, args(i,)) for i in range(2)] cs [threading.Thread(targetconsumer, args(i,)) for i in range(2)] [t.start() for t in ps cs] [t.join() for t in ps cs]三个信号量对应答案里的三个变量empty的初值是缓冲区容量full的初值是 0。把BUFFER_SIZE改成 2再把mutex.acquire()提到empty.acquire()前面在满载情况下程序会停在mutex.acquire()上不再前进这就是教材里「判断代码是否可能死锁」那道题的可运行版本。注意Semaphore的acquire()顺序不是风格问题它决定了答案对不对答题时也建议在注释里写明「先资源后互斥」。2.3 读者-写者与哲学家进餐答案里最容易漏掉的判定点这两类题的答案长度往往比前两类长一倍多出来的部分全是判定点。题面关键词答案里必须出现的判定常见错答允许多个读者同时读读者计数的加减本身需要互斥只设一个 wmutex把计数器暴露在外面写者优先增加写者等待计数信号量用同一个 wmutex 兼顾写者仍会被读者饿死哲学家同时拿起两只叉提供一次性取两只叉的原子语义顺序拿忽略了循环等待条件破坏循环等待最省事的写法是按编号奇偶区分拿叉顺序。import threading forks [threading.Semaphore(1) for _ in range(5)] def philosopher(i): left, right i, (i 1) % 5 # 偶数号先左后右奇数号先右后左打破环路 first, second (left, right) if i % 2 0 else (right, left) forks[first].acquire() forks[second].acquire() # 进餐临界区 forks[second].release() forks[first].release()forks长度固定为 5编号从 0 开始(i 1) % 5让 4 号哲学家的右手回到 0 号叉。参数改动会直接影响正确性如果允许哲学家数量变成偶数以外奇偶策略需要重新设计如果想改成整桌互斥就要在进餐前加一道全局信号量代价是并发度归零。手写答案时这两种解法都可以但要写清楚选了哪一种以及它破坏了四个必要条件里的哪一个。2.4 管程和协程教材答案写法与工程实现的距离教材里管程题的答法是把互斥交给管程自己承担进入管程自动互斥等待和唤醒通过条件变量的 wait/signal 表达。答题时要写清两件事管程内同一时刻只有一个进程在跑signal 唤醒的是等待队列里的哪一个。Python 的threading.Condition、Java 的synchronized配合wait/notify都是这个模型在工程里的落地。协程是另一条线上的东西。协程在用户态做任务切换解决的是 IO 密集场景下的调度开销和上下文成本它不提供互斥语义。很多人答错过一道选择题就是把「协作式调度」和「互斥保护」混成了一件事。import asyncio async def worker(lock, n): async with lock: # 协程之间共享可变状态仍然需要显式互斥 await asyncio.sleep(0.01) return n * n async def main(): lock asyncio.Lock() results await asyncio.gather(*(worker(lock, i) for i in range(5))) print(results) asyncio.run(main())asyncio.Lock只在同一个事件循环内保护协程跨线程、跨进程它不起作用。答题或者写代码时如果题目问的是进程间的互斥答案里出现协程就已经偏了。2.5 同步类习题的判分口径作业和考试的判分点通常只有四个信号量个数对不对、初值对不对、P 和 V 是否配对、临界区是否最小。少一个信号量基本全错多一个有时不扣分所以对答案时先数个数再看 P/V 的位置。如果自己的答案和参考解结构不同但四个判定点全中通常也算对这一点在读者-写者这类多解题目上尤其明显。3. 内存管理与页面置换课后习题答案里的算法复现3.1 页面置换手算题的三步固定流程教材里页面置换题几乎都按同一套流程批改先写物理块数量与初始装入的页面再顺着访问串逐格判断命中还是缺页最后在缺页的那一格按算法规则挑淘汰页。手算失分集中在第二步到第三步的衔接上很多人缺页判定对了淘汰页却选错。算法淘汰规则手算时需要额外维护的数据OPT淘汰未来最长时间不再访问的页完整访问串的后续部分FIFO淘汰最早进入内存的页进入内存的先后队列LRU淘汰最久没被访问的页最近一次访问的时间戳或访问栈CLOCK环形扫描访问位为 0 就淘汰访问位数组和循环指针3.2 用代码把三种置换算法的答案跑出来把人手做的事交给代码最大的好处是访问串换一组就能立刻重算不用重画表格。def fifo(pages, frames): mem, queue, faults [], [], 0 for p in pages: if p in mem: continue faults 1 if len(mem) frames: mem.append(p) else: old queue.pop(0) mem[mem.index(old)] p queue.append(p) return faults def lru(pages, frames): mem, recent, faults [], [], 0 for p in pages: if p in mem: recent.remove(p) recent.append(p) continue faults 1 if len(mem) frames: mem.append(p) else: old recent.pop(0) mem[mem.index(old)] p recent.append(p) return faults def opt(pages, frames): mem, faults [], 0 for i, p in enumerate(pages): if p in mem: continue faults 1 if len(mem) frames: mem.append(p) continue victim, far None, -1 for m in mem: rest pages[i 1:] nxt rest.index(m) if m in rest else float(inf) if nxt far: far, victim nxt, m mem[mem.index(victim)] p return faults 访问串 [7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1] for f in (3, 4): print(f, fifo(访问串, f), lru(访问串, f), opt(访问串, f))pages是访问串frames是物理块个数返回值是缺页次数。opt里用float(inf)表示该页之后不再出现这是判断「最久不用」的标准写法。这组访问串在经典教材例子里 3 个物理块下 FIFO 是 15 次缺页、LRU 是 12 次、OPT 是 9 次自己手算一遍再和这三个数对能立刻发现是判定错还是淘汰规则错。提示FIFO 会出现 Belady 异常物理块从 3 增加到 4 缺页次数反而可能上升LRU 和 OPT 不会。手算题里如果出现这种「违反直觉」的结果先别改答案先确认自己用的是不是 FIFO。3.3 缺页率题里三个容易算错的参数缺页率等于缺页次数除以总访问次数不是除以不同页面的个数这是第一处。第二处是初始装入题目写「已装入第 1、2 页」时这两次不能算进缺页次数但它们在访问串里照常参与命中判断。第三处是写操作有的题目设定写时分配页面那么一次写缺页会带来两次内存访问缺页率的分子不变、分母要按访问次数重新算。参数常见错法正确口径分母用不同页面数用访问串总长度初始装入把预装入算成缺页预装入不计缺页但仍占物理块写操作与读操作同等对待按题目给出的分配策略单独处理3.4 分页、分段与混合寻址题的答案结构这类题考的是拆地址。给定逻辑地址和页面大小页号是整除结果页内偏移是取余结果。二级页表再把页号拆成页目录号和页表索引两段段页式则先做段号拆分再做页号拆分。PAGE_SIZE 4096 def split(addr, page_sizePAGE_SIZE): return addr // page_size, addr % page_size # (页号, 页内偏移) def split_two_level(addr, page_sizePAGE_SIZE, entries1024): p, off split(addr, page_size) return p // entries, p % entries, off # (页目录号, 页表索引, 偏移) print(split(0x2A3F)) print(split_two_level(0x2A3F))page_size决定偏移位数entries是每张页表能放的表项数改成 512 或 2048 会让拆分结果整体变化。答题时把每一步的除法、取余写出来比直接写最终三元组更容易拿过程分。4. 文件系统、磁盘调度与死锁习题答案的验证路径4.1 磁盘调度题的排序先行原则磁盘调度题的答案几乎都是先排序再找下一个访问目标顺序错了后面全错。SCAN 和 C-SCAN 还要看题目给的初始移动方向方向相反会得到完全不同的磁道移动序列和总距离这一点在答案里通常只用一句话带过也最容易被忽略。算法选下一个请求的规则需要额外确认的参数FCFS按到达顺序无SSTF距当前磁头最近的请求无SCAN沿当前方向走到端点再折返初始方向C-SCAN单向扫描到端点直接回到另一端初始方向、是否算回程LOOK到该方向最后一个请求就折返初始方向def sstf(reqs, head): reqs list(reqs) seq, total, cur [head], 0, head while reqs: nxt min(reqs, keylambda x: abs(x - cur)) total abs(nxt - cur) seq.append(nxt) reqs.remove(nxt) cur nxt return seq, total seq, total sstf([98, 183, 37, 122, 14, 124, 65, 67], 53) print(seq) print(总移动磁道数, total, 平均寻道长度, total / (len(seq) - 1))reqs是磁道请求序列head是初始磁头位置返回值里seq是访问顺序、total是累计移动距离。答案通常还要求平均寻道长度注意分母是请求个数不是seq的长度——seq里多了一个初始位置。4.2 银行家算法答案的安全序列怎么排银行家算法的答案是一张迭代表每次找出一条能满足Need Work的进程把它标记为完成并把它的Allocation加回Work直到所有进程完成或者再也找不到可满足的进程为止。迭代轮次Work 向量可满足的进程完成后的 Work1当前 Available第一条满足 Need 的行Work 该行 Allocation2上一轮结果剩余未完成进程中满足的行继续累加失败任意轮次找不到可满足的行系统处于不安全状态def safety(avail, alloc, need): n, m len(alloc), len(avail) work avail[:] finish [False] * n seq [] while len(seq) n: for i in range(n): if not finish[i] and all(need[i][j] work[j] for j in range(m)): work [work[j] alloc[i][j] for j in range(m)] finish[i] True seq.append(i) break else: return None # 不存在安全序列系统不安全 return seq avail [3, 3, 2] alloc [[0, 1, 0], [2, 0, 0], [3, 0, 2], [2, 1, 1], [0, 0, 2]] need [[7, 4, 3], [1, 2, 2], [6, 0, 0], [0, 1, 1], [4, 3, 1]] print(safety(avail, alloc, need))avail是当前可用资源向量alloc和need是矩阵函数返回进程号的完成顺序返回None表示不安全。安全序列一般不唯一上面的实现按进程号从小到大扫描得到的是其中一条自己手算出来的顺序和它不一样只要每一步都满足Need Work就是正确答案。4.3 索引节点题的位运算答法文件系统题里关于最大文件大小的计算只要记住「直接块 一级 二级 三级间接块」这个结构剩下的全是算每块能放多少指针。BLOCK 4096 PTR_SIZE 4 DIRECT 12 ptr_per_block BLOCK // PTR_SIZE # 每块可存放的指针个数 max_blocks DIRECT ptr_per_block ptr_per_block ** 2 ptr_per_block ** 3 print(最大文件大小, max_blocks * BLOCK / (1 40), TiB)BLOCK是磁盘块大小PTR_SIZE是指针宽度DIRECT是直接块数量。这三个参数任意改动都会让结果跨数量级变化答题时先把它们写清楚再代数比只写最终数更容易拿分。5. 把课后习题答案变成可复现回归测试的几个技巧5.1 用 pytest 把每类题的答案固化成断言答案里给出的数字是最好的断言素材。把第 3 章的三个函数抽到paging.py里写一个测试文件改完实现只要跑一遍就知道有没有破坏原有行为。import pytest from paging import fifo, lru, opt REF [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1] pytest.mark.parametrize(frames,expected, [(3, 15)]) def test_fifo(frames, expected): assert fifo(REF, frames) expected pytest.mark.parametrize(frames,expected, [(3, 12)]) def test_lru(frames, expected): assert lru(REF, frames) expected pytest.mark.parametrize(frames,expected, [(3, 9)]) def test_opt(frames, expected): assert opt(REF, frames) expectedparametrize的第一个参数是物理块个数第二个是答案里给的缺页次数。同一道题想换访问串只改REF一行就行断言会自动重跑。这套写法对银行家算法、磁盘调度同样适用——把答案里的安全序列和总磁道数写成期望值即可。5.2 用随机访问串反查自己的手算手算题做多了会产生一种错觉以为自己掌握了判定规则。用随机串做批量自检能戳破这种错觉在 200 组随机访问串上跑三个算法只要 OPT 不是缺页次数最少的那个实现里就一定有问题因为 OPT 是理论下界。import random from paging import fifo, lru, opt for _ in range(200): ref [random.randint(0, 7) for _ in range(30)] f 3 assert opt(ref, f) min(fifo(ref, f), lru(ref, f)), ref print(OPT 上界性质成立)注意这里只断言 OPT 的上界性质不能顺手写成 LRU 一定优于 FIFO——FIFO 存在 Belady 异常两者谁更优和访问串有关硬写这条断言迟早会被随机数据打脸。同理把「安全序列唯一」写进断言也是错的银行家算法的正确判据是每一步的Need Work不是某条固定序列。5.3 手算与代码不一致时的排查顺序两边结果对不上按固定顺序查比逐行重算快得多先看物理块初始状态是否一致再看判定用的是不是同一个访问串然后看淘汰规则有没有把「命中也要更新」这件事做对——LRU 和 CLOCK 在命中时都要更新状态漏掉这一步是手写实现最常见的错误。pytest -q --tbshort python -c from paging import lru; print(lru([1,2,3,4,1,2,5,1,2,3,4,5], 3))命令行里-q只输出结果行--tbshort把失败堆栈压成几行。补一条手工命令是为了在断言失败时能立刻打印单组数据不用为了看一眼中间过程去改测试文件。这套「答案当断言、随机串当回归、命令行当探针」的组合用在死锁检测、调度算法这类题目上同样能省下大量反复手算的时间。本文还有配套的精品资源点击获取
简介这份《计算机操作系统教程》左万利、王英第四版课后习题答案面向正在学习操作系统课程、准备期末考试或考研复习的高校学生用于核对课后重点习题的解题过程与结论。整包仅含 1 个 doc 文档约 4.21MB内容按章节整理便于对照教材逐题查阅。文档覆盖进程调度、实时调度、死锁避免与同步互斥等核心章节第三章给出 EDF 与 RMS 调度判断及 Gantt 图并汇总 FCFS、SJB、HRN 三种算法下平均周转时间、平均带权周转时间的计算第四章讨论读者/写者问题的信号量解法与写者优先策略第五章借助银行家算法判断安全状态并演示死锁检测中资源请求后的状态变化。文档以教材习题编号为线索重点呈现调度计算表、资源分配表与安全序列推导适合课后自测与考前查漏补缺。已有 6331 人学习下载适合需要逐题复盘、梳理计算步骤与验证答案的读者参考。1. 拿到左万利、王英第四版课后习题答案先别急着对答案多数人用这份答案的姿势是写完一题翻到答案对上了打勾对不上抄一遍然后合上。等考试里出现「用 PV 操作描述生产者与消费者」抄过的那三行信号量早就想不起谁先谁后。真正卡住人的地方往往不是算错而是判定条件读偏了。信号量初值取几、物理块初始装几页、安全序列从哪一行开始排、磁盘调度题里磁头初始朝哪个方向走这些前提在习题答案里都是以结果的形式给出的答案本身不会告诉你它为什么这么假设。抄结果等于跳过了建模这一步。把《计算机操作系统教程》这本教材的课后习题答案当成一组验证用例更划算先用课本上的判定规则手推一遍再用几十行代码把同一道题跑一遍两者对得上说明模型建对了对不上就是概念优先级排错了。这套方法适合正在上操作系统课的学生、准备考研操作系统科目的同学也适合工作几年后想拿这些经典题重新校准底层认知的开发者。同一道 PV 题在慕课版、汤小丹版里编号和表述都不同所以练的是方法不是题号。2. 计算机操作系统教程课后习题答案的同步互斥主线2.1 PV 操作题的答案其实只有四种骨架教材里的同步互斥习题凡是要求「用 P、V 操作实现 XX」答案结构基本落在四类上单互斥、互斥加同步、资源计数、有限缓冲。判分逻辑也跟着这三件事走——先数清有几个互斥资源再数清有几组前后依赖最后确定每个信号量的初值。题型信号量个数典型初值答案里的关键判定点单互斥11P、V 严格包住临界区边界不多不少生产者-消费者3mutex1、emptyn、full0先申请资源信号量再申请互斥信号量读者-写者3 到 4rmutex1、wmutex1、计数器互斥第一个读者 P(wmutex)最后一个读者 V(wmutex)哲学家进餐5每把叉一个初值为 1必须破坏循环等待不能顺序拿叉最容易失分的是第二类。缓冲区满时如果先 P(mutex) 再 P(empty)生产者会抱着互斥锁进入等待消费者永远进不来整段代码直接变成死锁。答案里那个顺序看起来随意实际上就是这道题的考点本身。2.2 用 Python 信号量把生产者-消费者的标准答案跑出来光看答案看不出死锁把顺序换一下就能亲眼看到程序卡住。下面这段代码和教材答案是一一对应的。import threading, time, random BUFFER_SIZE 5 buffer [] mutex threading.Semaphore(1) # 互斥信号量保护 buffer empty threading.Semaphore(BUFFER_SIZE) # 空槽位计数初值等于缓冲容量 full threading.Semaphore(0) # 已占用槽位计数初值为 0 def producer(pid): for i in range(3): item fP{pid}-{i} empty.acquire() # 先申请资源有空位才继续 mutex.acquire() # 再申请互斥进临界区 buffer.append(item) print(f[producer {pid}] put {item}, buffer{buffer}) mutex.release() full.release() # 通知消费者多了一个满槽 time.sleep(random.random() * 0.1) def consumer(cid): for _ in range(3): full.acquire() # 先等有数据 mutex.acquire() item buffer.pop(0) print(f[consumer {cid}] get {item}, buffer{buffer}) mutex.release() empty.release() # 通知生产者空出一个位置 time.sleep(random.random() * 0.1) ps [threading.Thread(targetproducer, args(i,)) for i in range(2)] cs [threading.Thread(targetconsumer, args(i,)) for i in range(2)] [t.start() for t in ps cs] [t.join() for t in ps cs]三个信号量对应答案里的三个变量empty的初值是缓冲区容量full的初值是 0。把BUFFER_SIZE改成 2再把mutex.acquire()提到empty.acquire()前面在满载情况下程序会停在mutex.acquire()上不再前进这就是教材里「判断代码是否可能死锁」那道题的可运行版本。注意Semaphore的acquire()顺序不是风格问题它决定了答案对不对答题时也建议在注释里写明「先资源后互斥」。2.3 读者-写者与哲学家进餐答案里最容易漏掉的判定点这两类题的答案长度往往比前两类长一倍多出来的部分全是判定点。题面关键词答案里必须出现的判定常见错答允许多个读者同时读读者计数的加减本身需要互斥只设一个 wmutex把计数器暴露在外面写者优先增加写者等待计数信号量用同一个 wmutex 兼顾写者仍会被读者饿死哲学家同时拿起两只叉提供一次性取两只叉的原子语义顺序拿忽略了循环等待条件破坏循环等待最省事的写法是按编号奇偶区分拿叉顺序。import threading forks [threading.Semaphore(1) for _ in range(5)] def philosopher(i): left, right i, (i 1) % 5 # 偶数号先左后右奇数号先右后左打破环路 first, second (left, right) if i % 2 0 else (right, left) forks[first].acquire() forks[second].acquire() # 进餐临界区 forks[second].release() forks[first].release()forks长度固定为 5编号从 0 开始(i 1) % 5让 4 号哲学家的右手回到 0 号叉。参数改动会直接影响正确性如果允许哲学家数量变成偶数以外奇偶策略需要重新设计如果想改成整桌互斥就要在进餐前加一道全局信号量代价是并发度归零。手写答案时这两种解法都可以但要写清楚选了哪一种以及它破坏了四个必要条件里的哪一个。2.4 管程和协程教材答案写法与工程实现的距离教材里管程题的答法是把互斥交给管程自己承担进入管程自动互斥等待和唤醒通过条件变量的 wait/signal 表达。答题时要写清两件事管程内同一时刻只有一个进程在跑signal 唤醒的是等待队列里的哪一个。Python 的threading.Condition、Java 的synchronized配合wait/notify都是这个模型在工程里的落地。协程是另一条线上的东西。协程在用户态做任务切换解决的是 IO 密集场景下的调度开销和上下文成本它不提供互斥语义。很多人答错过一道选择题就是把「协作式调度」和「互斥保护」混成了一件事。import asyncio async def worker(lock, n): async with lock: # 协程之间共享可变状态仍然需要显式互斥 await asyncio.sleep(0.01) return n * n async def main(): lock asyncio.Lock() results await asyncio.gather(*(worker(lock, i) for i in range(5))) print(results) asyncio.run(main())asyncio.Lock只在同一个事件循环内保护协程跨线程、跨进程它不起作用。答题或者写代码时如果题目问的是进程间的互斥答案里出现协程就已经偏了。2.5 同步类习题的判分口径作业和考试的判分点通常只有四个信号量个数对不对、初值对不对、P 和 V 是否配对、临界区是否最小。少一个信号量基本全错多一个有时不扣分所以对答案时先数个数再看 P/V 的位置。如果自己的答案和参考解结构不同但四个判定点全中通常也算对这一点在读者-写者这类多解题目上尤其明显。3. 内存管理与页面置换课后习题答案里的算法复现3.1 页面置换手算题的三步固定流程教材里页面置换题几乎都按同一套流程批改先写物理块数量与初始装入的页面再顺着访问串逐格判断命中还是缺页最后在缺页的那一格按算法规则挑淘汰页。手算失分集中在第二步到第三步的衔接上很多人缺页判定对了淘汰页却选错。算法淘汰规则手算时需要额外维护的数据OPT淘汰未来最长时间不再访问的页完整访问串的后续部分FIFO淘汰最早进入内存的页进入内存的先后队列LRU淘汰最久没被访问的页最近一次访问的时间戳或访问栈CLOCK环形扫描访问位为 0 就淘汰访问位数组和循环指针3.2 用代码把三种置换算法的答案跑出来把人手做的事交给代码最大的好处是访问串换一组就能立刻重算不用重画表格。def fifo(pages, frames): mem, queue, faults [], [], 0 for p in pages: if p in mem: continue faults 1 if len(mem) frames: mem.append(p) else: old queue.pop(0) mem[mem.index(old)] p queue.append(p) return faults def lru(pages, frames): mem, recent, faults [], [], 0 for p in pages: if p in mem: recent.remove(p) recent.append(p) continue faults 1 if len(mem) frames: mem.append(p) else: old recent.pop(0) mem[mem.index(old)] p recent.append(p) return faults def opt(pages, frames): mem, faults [], 0 for i, p in enumerate(pages): if p in mem: continue faults 1 if len(mem) frames: mem.append(p) continue victim, far None, -1 for m in mem: rest pages[i 1:] nxt rest.index(m) if m in rest else float(inf) if nxt far: far, victim nxt, m mem[mem.index(victim)] p return faults 访问串 [7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1] for f in (3, 4): print(f, fifo(访问串, f), lru(访问串, f), opt(访问串, f))pages是访问串frames是物理块个数返回值是缺页次数。opt里用float(inf)表示该页之后不再出现这是判断「最久不用」的标准写法。这组访问串在经典教材例子里 3 个物理块下 FIFO 是 15 次缺页、LRU 是 12 次、OPT 是 9 次自己手算一遍再和这三个数对能立刻发现是判定错还是淘汰规则错。提示FIFO 会出现 Belady 异常物理块从 3 增加到 4 缺页次数反而可能上升LRU 和 OPT 不会。手算题里如果出现这种「违反直觉」的结果先别改答案先确认自己用的是不是 FIFO。3.3 缺页率题里三个容易算错的参数缺页率等于缺页次数除以总访问次数不是除以不同页面的个数这是第一处。第二处是初始装入题目写「已装入第 1、2 页」时这两次不能算进缺页次数但它们在访问串里照常参与命中判断。第三处是写操作有的题目设定写时分配页面那么一次写缺页会带来两次内存访问缺页率的分子不变、分母要按访问次数重新算。参数常见错法正确口径分母用不同页面数用访问串总长度初始装入把预装入算成缺页预装入不计缺页但仍占物理块写操作与读操作同等对待按题目给出的分配策略单独处理3.4 分页、分段与混合寻址题的答案结构这类题考的是拆地址。给定逻辑地址和页面大小页号是整除结果页内偏移是取余结果。二级页表再把页号拆成页目录号和页表索引两段段页式则先做段号拆分再做页号拆分。PAGE_SIZE 4096 def split(addr, page_sizePAGE_SIZE): return addr // page_size, addr % page_size # (页号, 页内偏移) def split_two_level(addr, page_sizePAGE_SIZE, entries1024): p, off split(addr, page_size) return p // entries, p % entries, off # (页目录号, 页表索引, 偏移) print(split(0x2A3F)) print(split_two_level(0x2A3F))page_size决定偏移位数entries是每张页表能放的表项数改成 512 或 2048 会让拆分结果整体变化。答题时把每一步的除法、取余写出来比直接写最终三元组更容易拿过程分。4. 文件系统、磁盘调度与死锁习题答案的验证路径4.1 磁盘调度题的排序先行原则磁盘调度题的答案几乎都是先排序再找下一个访问目标顺序错了后面全错。SCAN 和 C-SCAN 还要看题目给的初始移动方向方向相反会得到完全不同的磁道移动序列和总距离这一点在答案里通常只用一句话带过也最容易被忽略。算法选下一个请求的规则需要额外确认的参数FCFS按到达顺序无SSTF距当前磁头最近的请求无SCAN沿当前方向走到端点再折返初始方向C-SCAN单向扫描到端点直接回到另一端初始方向、是否算回程LOOK到该方向最后一个请求就折返初始方向def sstf(reqs, head): reqs list(reqs) seq, total, cur [head], 0, head while reqs: nxt min(reqs, keylambda x: abs(x - cur)) total abs(nxt - cur) seq.append(nxt) reqs.remove(nxt) cur nxt return seq, total seq, total sstf([98, 183, 37, 122, 14, 124, 65, 67], 53) print(seq) print(总移动磁道数, total, 平均寻道长度, total / (len(seq) - 1))reqs是磁道请求序列head是初始磁头位置返回值里seq是访问顺序、total是累计移动距离。答案通常还要求平均寻道长度注意分母是请求个数不是seq的长度——seq里多了一个初始位置。4.2 银行家算法答案的安全序列怎么排银行家算法的答案是一张迭代表每次找出一条能满足Need Work的进程把它标记为完成并把它的Allocation加回Work直到所有进程完成或者再也找不到可满足的进程为止。迭代轮次Work 向量可满足的进程完成后的 Work1当前 Available第一条满足 Need 的行Work 该行 Allocation2上一轮结果剩余未完成进程中满足的行继续累加失败任意轮次找不到可满足的行系统处于不安全状态def safety(avail, alloc, need): n, m len(alloc), len(avail) work avail[:] finish [False] * n seq [] while len(seq) n: for i in range(n): if not finish[i] and all(need[i][j] work[j] for j in range(m)): work [work[j] alloc[i][j] for j in range(m)] finish[i] True seq.append(i) break else: return None # 不存在安全序列系统不安全 return seq avail [3, 3, 2] alloc [[0, 1, 0], [2, 0, 0], [3, 0, 2], [2, 1, 1], [0, 0, 2]] need [[7, 4, 3], [1, 2, 2], [6, 0, 0], [0, 1, 1], [4, 3, 1]] print(safety(avail, alloc, need))avail是当前可用资源向量alloc和need是矩阵函数返回进程号的完成顺序返回None表示不安全。安全序列一般不唯一上面的实现按进程号从小到大扫描得到的是其中一条自己手算出来的顺序和它不一样只要每一步都满足Need Work就是正确答案。4.3 索引节点题的位运算答法文件系统题里关于最大文件大小的计算只要记住「直接块 一级 二级 三级间接块」这个结构剩下的全是算每块能放多少指针。BLOCK 4096 PTR_SIZE 4 DIRECT 12 ptr_per_block BLOCK // PTR_SIZE # 每块可存放的指针个数 max_blocks DIRECT ptr_per_block ptr_per_block ** 2 ptr_per_block ** 3 print(最大文件大小, max_blocks * BLOCK / (1 40), TiB)BLOCK是磁盘块大小PTR_SIZE是指针宽度DIRECT是直接块数量。这三个参数任意改动都会让结果跨数量级变化答题时先把它们写清楚再代数比只写最终数更容易拿分。5. 把课后习题答案变成可复现回归测试的几个技巧5.1 用 pytest 把每类题的答案固化成断言答案里给出的数字是最好的断言素材。把第 3 章的三个函数抽到paging.py里写一个测试文件改完实现只要跑一遍就知道有没有破坏原有行为。import pytest from paging import fifo, lru, opt REF [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1] pytest.mark.parametrize(frames,expected, [(3, 15)]) def test_fifo(frames, expected): assert fifo(REF, frames) expected pytest.mark.parametrize(frames,expected, [(3, 12)]) def test_lru(frames, expected): assert lru(REF, frames) expected pytest.mark.parametrize(frames,expected, [(3, 9)]) def test_opt(frames, expected): assert opt(REF, frames) expectedparametrize的第一个参数是物理块个数第二个是答案里给的缺页次数。同一道题想换访问串只改REF一行就行断言会自动重跑。这套写法对银行家算法、磁盘调度同样适用——把答案里的安全序列和总磁道数写成期望值即可。5.2 用随机访问串反查自己的手算手算题做多了会产生一种错觉以为自己掌握了判定规则。用随机串做批量自检能戳破这种错觉在 200 组随机访问串上跑三个算法只要 OPT 不是缺页次数最少的那个实现里就一定有问题因为 OPT 是理论下界。import random from paging import fifo, lru, opt for _ in range(200): ref [random.randint(0, 7) for _ in range(30)] f 3 assert opt(ref, f) min(fifo(ref, f), lru(ref, f)), ref print(OPT 上界性质成立)注意这里只断言 OPT 的上界性质不能顺手写成 LRU 一定优于 FIFO——FIFO 存在 Belady 异常两者谁更优和访问串有关硬写这条断言迟早会被随机数据打脸。同理把「安全序列唯一」写进断言也是错的银行家算法的正确判据是每一步的Need Work不是某条固定序列。5.3 手算与代码不一致时的排查顺序两边结果对不上按固定顺序查比逐行重算快得多先看物理块初始状态是否一致再看判定用的是不是同一个访问串然后看淘汰规则有没有把「命中也要更新」这件事做对——LRU 和 CLOCK 在命中时都要更新状态漏掉这一步是手写实现最常见的错误。pytest -q --tbshort python -c from paging import lru; print(lru([1,2,3,4,1,2,5,1,2,3,4,5], 3))命令行里-q只输出结果行--tbshort把失败堆栈压成几行。补一条手工命令是为了在断言失败时能立刻打印单组数据不用为了看一眼中间过程去改测试文件。这套「答案当断言、随机串当回归、命令行当探针」的组合用在死锁检测、调度算法这类题目上同样能省下大量反复手算的时间。本文还有配套的精品资源点击获取
