1. 为什么“操作系统习题答案”值得认真对待1.1 从一份答案说起操作系统到底难在哪计算机操作系统这门课挂科率在计算机专业里一直不低。我当年学的时候班上一半人期中考试不及格期末靠突击才勉强过关。后来自己带了几届学生发现一个规律真正学明白的人不是刷题最多的而是那些把每道题背后的机制想清楚的人。汤小丹老师这本《计算机操作系统慕课版》是人民邮电出版社出的很多高校用它做教材。这本书的特点是概念密集、章节之间耦合度高前四章引论、进程管理、处理机调度、死锁几乎是后面所有内容的地基。习题答案本身不是目的它是检验你有没有真正理解“进程为什么需要同步”“页面置换算法到底在置换什么”这些问题的工具。我见过太多人拿着答案对一遍错了就改个数字然后继续下一题。这种做法在操作系统这门课上基本等于白学。因为操作系统的题目尤其是计算题和设计题答案往往不是唯一的关键是你的推导过程能不能自洽。比如银行家算法的题目同一个安全序列可能有好几种你算出来的和答案不一样不代表你错了可能是你选的分配顺序不同。所以这篇内容我不打算给你一份干巴巴的答案列表。我想做的是把这本书里最核心的几类习题从“为什么这么问”到“怎么一步步推”再到“容易踩什么坑”完整地拆一遍。你拿着这份东西可以对照着自己的思路走看看卡在哪一步。1.2 这份内容适合谁看怎么用如果你正在学这门课不管是跟着慕课进度走还是期末突击复习这份内容都能用。具体来说正在做课后题的学生每道题先自己推一遍卡住了再看对应的解析。重点看“推导思路”那部分而不是最后的数字。准备考研复试或期末考的人操作系统是408统考的大头汤小丹这本教材的习题覆盖面很广把里面的典型题吃透考试时遇到变种题也不会慌。想补基础的程序员工作几年后回头看操作系统很多概念会有新的理解。比如你写过并发程序再来看PV操作感受完全不一样。我建议的使用方式是先看每节的“核心问题拆解”搞清楚这类题在考什么然后自己动手算最后对照“常见错误”部分看看自己有没有掉进同样的坑。不要一上来就翻答案那样效果至少打对折。提示操作系统习题里计算题只占一部分更多的是概念辨析和设计分析。概念题不要死记硬背试着用自己的话把机制讲一遍讲不通的地方就是你没理解的地方。2. 进程管理与PV操作最容易出错的核心章节2.1 进程同步的本质为什么信号量不是“计数器”汤小丹教材里PV操作wait/signal或者叫P/V原语是第二章的重头戏。很多习题答案只给你一个信号量初值和几行PV代码但没告诉你为什么这么设。我先把这个事说透。信号量本质上是一个受保护的整型变量它的值只能通过P和V两个原子操作来改变。P操作是“申请资源”V操作是“释放资源”。关键在于P和V必须是原子的也就是说当一个进程正在执行P操作时其他进程不能同时执行P或V。这个原子性是由操作系统内核保证的不是靠程序员自己写代码实现的。为什么这一点重要因为如果你不理解原子性你就无法理解为什么信号量能解决互斥问题。举个例子两个进程同时想进入临界区它们都执行P(mutex)。如果P操作不是原子的两个进程可能都读到mutex1然后都减到0然后都进入临界区——互斥就失效了。操作系统通过关中断或硬件原子指令来保证P和V的原子性这是底层机制但理解它才能理解上层代码为什么这么写。教材里常见的习题类型有给一个并发场景让你用PV操作描述进程同步给一段PV代码让你判断是否会发生死锁计算信号量的取值范围我重点讲第一类因为这类题最能拉开差距。2.2 经典模型拆解生产者-消费者、读者-写者、哲学家进餐这三个模型是操作系统习题的“老三样”几乎每本教材都会考。汤小丹这本也不例外。我把每个模型的核心逻辑和常见变种梳理一下。生产者-消费者问题的核心是生产者往缓冲区放数据消费者从缓冲区取数据缓冲区有限。需要三个信号量mutex互斥访问缓冲区、empty空槽位数、full已占槽位数。// 生产者 while (true) { produce_item(); P(empty); // 等待空槽位 P(mutex); // 互斥访问缓冲区 put_item(); V(mutex); V(full); // 通知消费者有数据了 } // 消费者 while (true) { P(full); // 等待数据 P(mutex); get_item(); V(mutex); V(empty); // 通知生产者有空位了 consume_item(); }这里最容易错的地方是P操作的顺序。如果生产者先P(mutex)再P(empty)当缓冲区满时生产者持有mutex等待empty消费者无法进入临界区释放empty直接死锁。所以顺序必须是先P资源信号量再P互斥信号量。V操作的顺序无所谓但习惯上先V互斥再V资源。读者-写者问题分两种读者优先和写者优先。读者优先的经典解法是// 读者 P(rmutex); // 保护readcount if (readcount 0) P(wmutex); // 第一个读者锁住写者 readcount; V(rmutex); read_data(); P(rmutex); readcount--; if (readcount 0) V(wmutex); // 最后一个读者释放写者 V(rmutex); // 写者 P(wmutex); write_data(); V(wmutex);这里的关键是readcount变量本身需要互斥保护所以有rmutex。很多习题答案不写rmutex那是简化版实际考试要写全。哲学家进餐问题的考点在于死锁避免。最简单的解法是要么让哲学家一次拿两只筷子用互斥信号量保护拿筷子的动作要么给筷子编号奇数号先拿左再拿右偶数号先拿右再拿左。教材习题里经常让你分析“为什么原始解法会死锁”答案就是五个哲学家同时拿起左边的筷子然后都在等右边的筷子循环等待。2.3 PV操作习题的通用解题步骤我总结了一个四步法对付教材里90%的PV操作题识别进程和资源有几个并发进程它们共享什么资源资源的数量是多少确定同步关系哪些操作有先后顺序哪些操作必须互斥设置信号量互斥信号量初值一般为1资源信号量初值为资源数量同步信号量初值根据初始状态定通常为0。写出代码框架先写P操作再写V操作注意顺序。注意信号量的初值不是随便设的。同步信号量初值为0表示“初始时没有资源可用”比如生产者-消费者里的full。如果初始缓冲区有数据full的初值就是初始数据量。常见错误速查表错误类型典型表现正确做法P操作顺序错误先P(mutex)再P(empty)先P资源信号量再P互斥信号量忘记互斥保护共享变量readcount直接加减用rmutex保护readcount信号量初值设错full初值设为缓冲区大小full初值为0empty初值为缓冲区大小V操作遗漏只P不V每个P操作都要有对应的V操作死锁未考虑哲学家同时拿左筷子破坏循环等待条件3. 处理机调度与死锁计算题的套路与反套路3.1 调度算法计算从FCFS到多级反馈队列处理机调度这章的习题计算量不大但容易在细节上丢分。汤小丹教材里主要考这几种算法FCFS先来先服务、SJF短作业优先、HRRN高响应比优先、RR时间片轮转、多级反馈队列。我拿一道典型题来拆假设有四个作业到达时间和运行时间如下表分别计算FCFS、SJF非抢占、RR时间片1的平均周转时间和平均带权周转时间。作业到达时间运行时间A07B24C41D54FCFS按到达顺序执行。A从0到7B从7到11C从11到12D从12到16。周转时间完成时间-到达时间A7B9C8D11。平均周转时间(79811)/48.75。带权周转时间周转时间/运行时间A1B2.25C8D2.75。平均带权3.5。SJF非抢占每次选运行时间最短的。0时刻只有AA执行到7。7时刻B、C、D都到了选C运行1。C从7到8。8时刻选B运行4B从8到12。最后D从12到16。周转时间A7B10C4D11。平均8。带权A1B2.5C4D2.75。平均2.5625。RR时间片1这个要画甘特图。0-1 A1-2 A2-3 BA还剩5B剩33-4 A4-5 BA剩4B剩25-6 CC到达6-7 A7-8 BA剩3B剩18-9 DD到达9-10 A10-11 BB完成11-12 D12-13 A13-14 D14-15 A15-16 DD完成16-17 AA完成。完成时间A17B11C6D16。周转时间A17B9C2D11。平均9.75。带权A2.43B2.25C2D2.75。平均2.36。这道题的关键是RR的甘特图不能画错。我见过很多学生把时间片轮转和优先级调度搞混或者忘记新到达的进程要排到队尾。3.2 银行家算法安全序列不是唯一答案银行家算法是死锁避免的经典算法也是考试必考。汤小丹教材里的题目通常给一个资源分配表让你判断当前状态是否安全如果安全给出一个安全序列。核心步骤计算Need矩阵Need Max - Allocation计算Available向量找一个Need ≤ Available的进程假设它完成释放资源重复直到所有进程完成安全或找不到不安全我拿一道题演示系统有3类资源A、B、C数量分别为10、5、7。五个进程P0-P4的Max和Allocation如下进程Max (A,B,C)Allocation (A,B,C)P07,5,30,1,0P13,2,22,0,0P29,0,23,0,2P32,2,22,1,1P44,3,30,0,2先算NeedP0(7,4,3)P1(1,2,2)P2(6,0,0)P3(0,1,1)P4(4,3,1)。Available(10-7, 5-2, 7-5)(3,3,2)。找Need ≤ Available的P1的(1,2,2) ≤ (3,3,2)可以。P1完成Available变为(32,30,20)(5,3,2)。P3的(0,1,1) ≤ (5,3,2)可以。P3完成Available(7,4,3)。P0的(7,4,3) ≤ (7,4,3)可以。P0完成Available(7,5,3)。P2的(6,0,0) ≤ (7,5,3)可以。P2完成Available(10,5,5)。P4的(4,3,1) ≤ (10,5,5)可以。安全序列P1→P3→P0→P2→P4。注意安全序列不唯一。比如P1→P3→P4→P0→P2也是安全的。考试时只要给出一个正确的安全序列就行不用纠结和答案不一样。3.3 死锁检测与解除资源分配图的化简死锁检测的题目通常给一个资源分配图让你判断是否死锁。方法是化简资源分配图找一个既不阻塞又非孤立的进程节点去掉它的所有请求边和分配边使它成为孤立节点。重复这个过程如果所有进程都能变成孤立节点则无死锁否则有死锁。这个方法的本质是如果一个进程能获得它需要的所有资源并最终释放那它就不会死锁。化简过程就是模拟这个“逐步释放”的过程。常见错误把“有环”等同于“死锁”。实际上资源分配图中有环只是死锁的必要条件不是充分条件。如果环上的每个资源类只有一个实例那有环就是死锁如果有多个实例有环不一定死锁。4. 内存管理与页面置换计算量大但套路固定4.1 分页与分段地址转换的两种思路内存管理这章地址转换是基础题。分页和分段的区别教材里讲得很清楚但做题时容易混。分页逻辑地址分为页号和页内偏移。页号用于查页表页内偏移直接作为物理地址的低位。物理地址 页框号 × 页面大小 页内偏移。分段逻辑地址分为段号和段内偏移。段号用于查段表段表项包含段基址和段长。物理地址 段基址 段内偏移但必须检查段内偏移 段长否则越界。我拿一道题对比页面大小4KB逻辑地址0x2F3A页表如下求物理地址。页号页框号0518230x2F3A 0010 1111 0011 1010。页面大小4KB2^12所以低12位是页内偏移高4位是页号。页号2页内偏移0xF3A。查表得页框号3。物理地址3×4KB0xF3A0x3F3A。分段题类似但要注意段长检查。如果段内偏移 ≥ 段长产生越界中断。4.2 页面置换算法FIFO、LRU、OPT的手算技巧页面置换算法的计算题给一个页面引用串和物理块数让你算缺页次数。三种基本算法FIFO先进先出、LRU最近最久未使用、OPT最佳置换。我拿引用串7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1物理块3来演示。FIFO用队列新页面入队尾淘汰队头。缺页次数15。LRU淘汰最久未使用的页面。可以用栈模拟每次访问把页面移到栈顶淘汰栈底。缺页次数12。OPT淘汰未来最长时间不被访问的页面。需要看未来引用串。缺页次数9。手算技巧FIFO用队列画表LRU用栈画表OPT从当前位置往后看。我建议考试时画一个表格每一列是一个引用每一行是一个物理块标出每次置换的页面。这样不容易错。注意Belady异常是FIFO特有的——增加物理块数缺页次数反而可能增加。LRU和OPT不会出现这种情况。教材习题里经常考“为什么FIFO会有Belady异常”答案是因为FIFO没有考虑程序的局部性原理。4.3 虚拟内存与缺页中断从地址转换到页面调入虚拟内存的题目通常综合了地址转换、缺页中断、页面置换。典型流程CPU发出逻辑地址MMU查TLB快表命中则直接得到物理地址TLB未命中查页表页表项有效位为0产生缺页中断操作系统选择一个页面淘汰如果需要调入缺失页面更新页表和TLB重新执行指令计算有效访问时间EAT的公式EAT 命中率 × (TLB访问时间 内存访问时间) 未命中率 × (TLB访问时间 2×内存访问时间 缺页处理时间)。教材习题里经常给TLB命中率、内存访问时间、缺页率让你算EAT。注意缺页处理时间通常远大于内存访问时间所以缺页率对EAT影响很大。5. 文件系统与I/O管理概念题为主计算题有套路5.1 文件分配方式连续、链接、索引的对比文件分配方式有三种连续分配、链接分配、索引分配。教材习题通常让你比较它们的优缺点或者计算访问某个块需要几次磁盘I/O。分配方式优点缺点随机访问连续分配支持随机访问访问速度快产生外部碎片文件扩展困难支持链接分配无外部碎片文件扩展容易只能顺序访问指针占用空间不支持索引分配支持随机访问扩展容易索引块占用空间支持计算题常见形式文件有n个块索引节点有m个直接指针和k个一级间接指针问最大文件大小。答案是直接指针数×块大小 一级间接指针数×块大小×块大小/指针大小 ...5.2 磁盘调度算法FCFS、SSTF、SCAN、C-SCAN磁盘调度算法的计算题给一个磁道请求序列和当前磁头位置让你算总移动磁道数。我拿请求序列98,183,37,122,14,124,65,67当前磁头在53方向为磁道号增加来演示。FCFS按请求顺序走。53→98→183→37→122→14→124→65→67。总移动458514685108110592640。SSTF每次选最近的。53→65→67→37→14→98→122→124→183。总移动12230238424259236。SCAN电梯算法按方向走到底再反向。53→65→67→98→122→124→183→37→14。总移动122312425914623299。C-SCAN按方向走到底然后快速回到另一端。53→65→67→98→122→124→183→14→37。总移动122312425916923322。注意SCAN和C-SCAN的区别在于SCAN反向时还会服务请求C-SCAN反向时直接回到起点不服务。考试时看清题目要求。5.3 I/O管理缓冲、SPOOLing、设备分配I/O管理这章的习题以概念为主。常见考点缓冲技术单缓冲、双缓冲、循环缓冲。计算题通常给处理时间和传输时间让你算处理一块数据的总时间。SPOOLing技术用磁盘模拟独占设备实现虚拟设备。习题常问“SPOOLing系统由哪几部分组成”答案是输入井、输出井、输入进程、输出进程。设备分配独占设备、共享设备、虚拟设备。分配策略有静态分配和动态分配。我重点讲单缓冲和双缓冲的计算。假设从磁盘读一块数据到缓冲区需要T时间从缓冲区送到用户区需要M时间CPU处理需要C时间。单缓冲处理一块数据的时间 max(T, C) M。因为读入和CPU处理可以并行但送到用户区必须串行。双缓冲处理一块数据的时间 max(T, CM)。因为读入和“送到用户区CPU处理”可以并行。教材习题里经常给具体数字让你算总时间。记住公式代入即可。6. 常见问题与排查技巧实录6.1 习题答案对不上怎么办这是最常见的问题。我分几种情况说情况一安全序列不同。银行家算法的安全序列不唯一只要你的推导过程正确答案不同没关系。情况二页面置换缺页次数不同。检查你的引用串有没有抄错物理块数有没有看错算法有没有用错。FIFO和LRU的结果通常不同OPT一定是最少的。情况三PV操作代码不同。信号量的设置方式可能不同比如有些答案用AND信号量有些用普通信号量。只要逻辑正确能解决同步互斥问题就是对的。情况四计算题结果差一点。检查单位换算比如KB和Bms和s。检查有没有四舍五入有些答案保留两位小数有些保留整数。6.2 考试时的时间分配建议操作系统试卷通常计算量不小。我的建议选择题和填空题15分钟内完成概念辨析题20分钟PV操作题15分钟调度算法计算题15分钟银行家算法10分钟页面置换10分钟磁盘调度10分钟综合题25分钟检查10分钟当然具体根据试卷结构调整。关键是不要在一道题上死磕。如果一道PV操作题想了5分钟还没思路先跳过做完后面的再回来。6.3 复习策略从习题反推知识点我带的学生的经验是先做题再看书。具体来说拿一套课后习题不看答案硬做一遍对答案标记错题针对错题回到教材对应章节把相关概念重新看一遍再找类似的题做一遍确认掌握这个方法比“先看书再做题”效率高因为做题能暴露你的知识盲区。看书时你觉得什么都懂一做题就发现什么都不会。提示汤小丹这本教材的习题量不小不用全做。每章挑10-15道典型题就够了。重点是理解解题思路不是刷题数量。6.4 常见问题速查表问题可能原因解决方法PV操作死锁P操作顺序错误先P资源信号量再P互斥信号量银行家算法找不到安全序列Need计算错误重新计算NeedMax-Allocation页面置换缺页次数偏多算法用错确认题目要求的是FIFO、LRU还是OPT磁盘调度总移动数偏大方向判断错误确认当前磁头移动方向地址转换结果不对页号或偏移计算错误确认页面大小重新划分地址位EAT计算偏差大缺页率代入错误确认缺页率是百分比还是小数7. 从习题到实战操作系统知识怎么用起来7.1 写代码时遇到的PV操作工作后你会发现PV操作的思想无处不在。比如你写一个多线程程序用互斥锁保护共享变量本质上就是P(mutex)和V(mutex)。用条件变量等待某个条件成立本质上就是P(condition)和V(condition)。我举个例子一个线程池任务队列是共享资源。生产者线程往队列里加任务消费者线程从队列里取任务。这就是生产者-消费者问题。用C的mutex和condition_variable实现std::mutex mtx; std::condition_variable cv; std::queueTask task_queue; const int MAX_SIZE 100; // 生产者 void producer(Task t) { std::unique_lockstd::mutex lock(mtx); cv.wait(lock, []{ return task_queue.size() MAX_SIZE; }); task_queue.push(t); cv.notify_all(); } // 消费者 Task consumer() { std::unique_lockstd::mutex lock(mtx); cv.wait(lock, []{ return !task_queue.empty(); }); Task t task_queue.front(); task_queue.pop(); cv.notify_all(); return t; }这里的cv.wait就是P操作cv.notify_all就是V操作。unique_lock保证了互斥。你看操作系统的知识直接用在工程里了。7.2 页面置换算法在缓存中的应用LRU页面置换算法在缓存系统里用得很多。比如Redis的缓存淘汰策略就有LRU和LFU。你写一个本地缓存也可以用LRU算法决定淘汰哪个条目。Java的LinkedHashMap可以直接实现LRU缓存class LRUCacheK, V extends LinkedHashMapK, V { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); // accessOrdertrue this.capacity capacity; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() capacity; } }这里的accessOrdertrue就是按访问顺序排序每次get会把条目移到链表尾部淘汰时移除链表头部——这就是LRU。7.3 磁盘调度算法在数据库中的应用数据库的磁盘I/O调度本质上就是磁盘调度算法。MySQL的InnoDB存储引擎在刷脏页时会尽量按物理地址顺序刷减少磁头移动。这就是SCAN算法的思想。你写一个文件系统或者数据库磁盘调度算法的选择直接影响性能。SSD时代磁头移动的代价小了但顺序读写和随机读写的差距依然存在。所以很多系统还是倾向于顺序I/O。8. 最后分享几个实操心得第一不要背答案。操作系统的题目尤其是PV操作和银行家算法背答案没用。考试时题目稍微变一下你就不会了。关键是理解机制理解为什么这么设计。第二画图。调度算法画甘特图页面置换画表格磁盘调度画磁道移动图。画图能帮你理清思路也能让阅卷老师看到你的推导过程。即使最后结果错了过程对也能拿分。第三多问为什么。为什么FIFO有Belady异常为什么银行家算法能避免死锁为什么LRU比FIFO好把这些问题想清楚你就不需要刷很多题了。第四结合实际。学操作系统时想想你写的程序里哪些地方用到了这些知识。比如你用过线程池就想想生产者-消费者你用过缓存就想想LRU。这样学起来不枯燥也记得牢。第五组队学习。操作系统有些概念比较抽象一个人想半天想不通和别人讨论十分钟就明白了。我当年学的时候几个同学一起画PV操作的流程图互相挑毛病进步很快。这门课确实有难度但学明白了对后面学分布式系统、数据库、编译原理都有帮助。习题答案只是工具真正的收获是解题过程中建立起来的系统思维。 操作系统习题答案深度解析：PV操作、调度算法与页面置换核心考点
1. 为什么“操作系统习题答案”值得认真对待1.1 从一份答案说起操作系统到底难在哪计算机操作系统这门课挂科率在计算机专业里一直不低。我当年学的时候班上一半人期中考试不及格期末靠突击才勉强过关。后来自己带了几届学生发现一个规律真正学明白的人不是刷题最多的而是那些把每道题背后的机制想清楚的人。汤小丹老师这本《计算机操作系统慕课版》是人民邮电出版社出的很多高校用它做教材。这本书的特点是概念密集、章节之间耦合度高前四章引论、进程管理、处理机调度、死锁几乎是后面所有内容的地基。习题答案本身不是目的它是检验你有没有真正理解“进程为什么需要同步”“页面置换算法到底在置换什么”这些问题的工具。我见过太多人拿着答案对一遍错了就改个数字然后继续下一题。这种做法在操作系统这门课上基本等于白学。因为操作系统的题目尤其是计算题和设计题答案往往不是唯一的关键是你的推导过程能不能自洽。比如银行家算法的题目同一个安全序列可能有好几种你算出来的和答案不一样不代表你错了可能是你选的分配顺序不同。所以这篇内容我不打算给你一份干巴巴的答案列表。我想做的是把这本书里最核心的几类习题从“为什么这么问”到“怎么一步步推”再到“容易踩什么坑”完整地拆一遍。你拿着这份东西可以对照着自己的思路走看看卡在哪一步。1.2 这份内容适合谁看怎么用如果你正在学这门课不管是跟着慕课进度走还是期末突击复习这份内容都能用。具体来说正在做课后题的学生每道题先自己推一遍卡住了再看对应的解析。重点看“推导思路”那部分而不是最后的数字。准备考研复试或期末考的人操作系统是408统考的大头汤小丹这本教材的习题覆盖面很广把里面的典型题吃透考试时遇到变种题也不会慌。想补基础的程序员工作几年后回头看操作系统很多概念会有新的理解。比如你写过并发程序再来看PV操作感受完全不一样。我建议的使用方式是先看每节的“核心问题拆解”搞清楚这类题在考什么然后自己动手算最后对照“常见错误”部分看看自己有没有掉进同样的坑。不要一上来就翻答案那样效果至少打对折。提示操作系统习题里计算题只占一部分更多的是概念辨析和设计分析。概念题不要死记硬背试着用自己的话把机制讲一遍讲不通的地方就是你没理解的地方。2. 进程管理与PV操作最容易出错的核心章节2.1 进程同步的本质为什么信号量不是“计数器”汤小丹教材里PV操作wait/signal或者叫P/V原语是第二章的重头戏。很多习题答案只给你一个信号量初值和几行PV代码但没告诉你为什么这么设。我先把这个事说透。信号量本质上是一个受保护的整型变量它的值只能通过P和V两个原子操作来改变。P操作是“申请资源”V操作是“释放资源”。关键在于P和V必须是原子的也就是说当一个进程正在执行P操作时其他进程不能同时执行P或V。这个原子性是由操作系统内核保证的不是靠程序员自己写代码实现的。为什么这一点重要因为如果你不理解原子性你就无法理解为什么信号量能解决互斥问题。举个例子两个进程同时想进入临界区它们都执行P(mutex)。如果P操作不是原子的两个进程可能都读到mutex1然后都减到0然后都进入临界区——互斥就失效了。操作系统通过关中断或硬件原子指令来保证P和V的原子性这是底层机制但理解它才能理解上层代码为什么这么写。教材里常见的习题类型有给一个并发场景让你用PV操作描述进程同步给一段PV代码让你判断是否会发生死锁计算信号量的取值范围我重点讲第一类因为这类题最能拉开差距。2.2 经典模型拆解生产者-消费者、读者-写者、哲学家进餐这三个模型是操作系统习题的“老三样”几乎每本教材都会考。汤小丹这本也不例外。我把每个模型的核心逻辑和常见变种梳理一下。生产者-消费者问题的核心是生产者往缓冲区放数据消费者从缓冲区取数据缓冲区有限。需要三个信号量mutex互斥访问缓冲区、empty空槽位数、full已占槽位数。// 生产者 while (true) { produce_item(); P(empty); // 等待空槽位 P(mutex); // 互斥访问缓冲区 put_item(); V(mutex); V(full); // 通知消费者有数据了 } // 消费者 while (true) { P(full); // 等待数据 P(mutex); get_item(); V(mutex); V(empty); // 通知生产者有空位了 consume_item(); }这里最容易错的地方是P操作的顺序。如果生产者先P(mutex)再P(empty)当缓冲区满时生产者持有mutex等待empty消费者无法进入临界区释放empty直接死锁。所以顺序必须是先P资源信号量再P互斥信号量。V操作的顺序无所谓但习惯上先V互斥再V资源。读者-写者问题分两种读者优先和写者优先。读者优先的经典解法是// 读者 P(rmutex); // 保护readcount if (readcount 0) P(wmutex); // 第一个读者锁住写者 readcount; V(rmutex); read_data(); P(rmutex); readcount--; if (readcount 0) V(wmutex); // 最后一个读者释放写者 V(rmutex); // 写者 P(wmutex); write_data(); V(wmutex);这里的关键是readcount变量本身需要互斥保护所以有rmutex。很多习题答案不写rmutex那是简化版实际考试要写全。哲学家进餐问题的考点在于死锁避免。最简单的解法是要么让哲学家一次拿两只筷子用互斥信号量保护拿筷子的动作要么给筷子编号奇数号先拿左再拿右偶数号先拿右再拿左。教材习题里经常让你分析“为什么原始解法会死锁”答案就是五个哲学家同时拿起左边的筷子然后都在等右边的筷子循环等待。2.3 PV操作习题的通用解题步骤我总结了一个四步法对付教材里90%的PV操作题识别进程和资源有几个并发进程它们共享什么资源资源的数量是多少确定同步关系哪些操作有先后顺序哪些操作必须互斥设置信号量互斥信号量初值一般为1资源信号量初值为资源数量同步信号量初值根据初始状态定通常为0。写出代码框架先写P操作再写V操作注意顺序。注意信号量的初值不是随便设的。同步信号量初值为0表示“初始时没有资源可用”比如生产者-消费者里的full。如果初始缓冲区有数据full的初值就是初始数据量。常见错误速查表错误类型典型表现正确做法P操作顺序错误先P(mutex)再P(empty)先P资源信号量再P互斥信号量忘记互斥保护共享变量readcount直接加减用rmutex保护readcount信号量初值设错full初值设为缓冲区大小full初值为0empty初值为缓冲区大小V操作遗漏只P不V每个P操作都要有对应的V操作死锁未考虑哲学家同时拿左筷子破坏循环等待条件3. 处理机调度与死锁计算题的套路与反套路3.1 调度算法计算从FCFS到多级反馈队列处理机调度这章的习题计算量不大但容易在细节上丢分。汤小丹教材里主要考这几种算法FCFS先来先服务、SJF短作业优先、HRRN高响应比优先、RR时间片轮转、多级反馈队列。我拿一道典型题来拆假设有四个作业到达时间和运行时间如下表分别计算FCFS、SJF非抢占、RR时间片1的平均周转时间和平均带权周转时间。作业到达时间运行时间A07B24C41D54FCFS按到达顺序执行。A从0到7B从7到11C从11到12D从12到16。周转时间完成时间-到达时间A7B9C8D11。平均周转时间(79811)/48.75。带权周转时间周转时间/运行时间A1B2.25C8D2.75。平均带权3.5。SJF非抢占每次选运行时间最短的。0时刻只有AA执行到7。7时刻B、C、D都到了选C运行1。C从7到8。8时刻选B运行4B从8到12。最后D从12到16。周转时间A7B10C4D11。平均8。带权A1B2.5C4D2.75。平均2.5625。RR时间片1这个要画甘特图。0-1 A1-2 A2-3 BA还剩5B剩33-4 A4-5 BA剩4B剩25-6 CC到达6-7 A7-8 BA剩3B剩18-9 DD到达9-10 A10-11 BB完成11-12 D12-13 A13-14 D14-15 A15-16 DD完成16-17 AA完成。完成时间A17B11C6D16。周转时间A17B9C2D11。平均9.75。带权A2.43B2.25C2D2.75。平均2.36。这道题的关键是RR的甘特图不能画错。我见过很多学生把时间片轮转和优先级调度搞混或者忘记新到达的进程要排到队尾。3.2 银行家算法安全序列不是唯一答案银行家算法是死锁避免的经典算法也是考试必考。汤小丹教材里的题目通常给一个资源分配表让你判断当前状态是否安全如果安全给出一个安全序列。核心步骤计算Need矩阵Need Max - Allocation计算Available向量找一个Need ≤ Available的进程假设它完成释放资源重复直到所有进程完成安全或找不到不安全我拿一道题演示系统有3类资源A、B、C数量分别为10、5、7。五个进程P0-P4的Max和Allocation如下进程Max (A,B,C)Allocation (A,B,C)P07,5,30,1,0P13,2,22,0,0P29,0,23,0,2P32,2,22,1,1P44,3,30,0,2先算NeedP0(7,4,3)P1(1,2,2)P2(6,0,0)P3(0,1,1)P4(4,3,1)。Available(10-7, 5-2, 7-5)(3,3,2)。找Need ≤ Available的P1的(1,2,2) ≤ (3,3,2)可以。P1完成Available变为(32,30,20)(5,3,2)。P3的(0,1,1) ≤ (5,3,2)可以。P3完成Available(7,4,3)。P0的(7,4,3) ≤ (7,4,3)可以。P0完成Available(7,5,3)。P2的(6,0,0) ≤ (7,5,3)可以。P2完成Available(10,5,5)。P4的(4,3,1) ≤ (10,5,5)可以。安全序列P1→P3→P0→P2→P4。注意安全序列不唯一。比如P1→P3→P4→P0→P2也是安全的。考试时只要给出一个正确的安全序列就行不用纠结和答案不一样。3.3 死锁检测与解除资源分配图的化简死锁检测的题目通常给一个资源分配图让你判断是否死锁。方法是化简资源分配图找一个既不阻塞又非孤立的进程节点去掉它的所有请求边和分配边使它成为孤立节点。重复这个过程如果所有进程都能变成孤立节点则无死锁否则有死锁。这个方法的本质是如果一个进程能获得它需要的所有资源并最终释放那它就不会死锁。化简过程就是模拟这个“逐步释放”的过程。常见错误把“有环”等同于“死锁”。实际上资源分配图中有环只是死锁的必要条件不是充分条件。如果环上的每个资源类只有一个实例那有环就是死锁如果有多个实例有环不一定死锁。4. 内存管理与页面置换计算量大但套路固定4.1 分页与分段地址转换的两种思路内存管理这章地址转换是基础题。分页和分段的区别教材里讲得很清楚但做题时容易混。分页逻辑地址分为页号和页内偏移。页号用于查页表页内偏移直接作为物理地址的低位。物理地址 页框号 × 页面大小 页内偏移。分段逻辑地址分为段号和段内偏移。段号用于查段表段表项包含段基址和段长。物理地址 段基址 段内偏移但必须检查段内偏移 段长否则越界。我拿一道题对比页面大小4KB逻辑地址0x2F3A页表如下求物理地址。页号页框号0518230x2F3A 0010 1111 0011 1010。页面大小4KB2^12所以低12位是页内偏移高4位是页号。页号2页内偏移0xF3A。查表得页框号3。物理地址3×4KB0xF3A0x3F3A。分段题类似但要注意段长检查。如果段内偏移 ≥ 段长产生越界中断。4.2 页面置换算法FIFO、LRU、OPT的手算技巧页面置换算法的计算题给一个页面引用串和物理块数让你算缺页次数。三种基本算法FIFO先进先出、LRU最近最久未使用、OPT最佳置换。我拿引用串7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1物理块3来演示。FIFO用队列新页面入队尾淘汰队头。缺页次数15。LRU淘汰最久未使用的页面。可以用栈模拟每次访问把页面移到栈顶淘汰栈底。缺页次数12。OPT淘汰未来最长时间不被访问的页面。需要看未来引用串。缺页次数9。手算技巧FIFO用队列画表LRU用栈画表OPT从当前位置往后看。我建议考试时画一个表格每一列是一个引用每一行是一个物理块标出每次置换的页面。这样不容易错。注意Belady异常是FIFO特有的——增加物理块数缺页次数反而可能增加。LRU和OPT不会出现这种情况。教材习题里经常考“为什么FIFO会有Belady异常”答案是因为FIFO没有考虑程序的局部性原理。4.3 虚拟内存与缺页中断从地址转换到页面调入虚拟内存的题目通常综合了地址转换、缺页中断、页面置换。典型流程CPU发出逻辑地址MMU查TLB快表命中则直接得到物理地址TLB未命中查页表页表项有效位为0产生缺页中断操作系统选择一个页面淘汰如果需要调入缺失页面更新页表和TLB重新执行指令计算有效访问时间EAT的公式EAT 命中率 × (TLB访问时间 内存访问时间) 未命中率 × (TLB访问时间 2×内存访问时间 缺页处理时间)。教材习题里经常给TLB命中率、内存访问时间、缺页率让你算EAT。注意缺页处理时间通常远大于内存访问时间所以缺页率对EAT影响很大。5. 文件系统与I/O管理概念题为主计算题有套路5.1 文件分配方式连续、链接、索引的对比文件分配方式有三种连续分配、链接分配、索引分配。教材习题通常让你比较它们的优缺点或者计算访问某个块需要几次磁盘I/O。分配方式优点缺点随机访问连续分配支持随机访问访问速度快产生外部碎片文件扩展困难支持链接分配无外部碎片文件扩展容易只能顺序访问指针占用空间不支持索引分配支持随机访问扩展容易索引块占用空间支持计算题常见形式文件有n个块索引节点有m个直接指针和k个一级间接指针问最大文件大小。答案是直接指针数×块大小 一级间接指针数×块大小×块大小/指针大小 ...5.2 磁盘调度算法FCFS、SSTF、SCAN、C-SCAN磁盘调度算法的计算题给一个磁道请求序列和当前磁头位置让你算总移动磁道数。我拿请求序列98,183,37,122,14,124,65,67当前磁头在53方向为磁道号增加来演示。FCFS按请求顺序走。53→98→183→37→122→14→124→65→67。总移动458514685108110592640。SSTF每次选最近的。53→65→67→37→14→98→122→124→183。总移动12230238424259236。SCAN电梯算法按方向走到底再反向。53→65→67→98→122→124→183→37→14。总移动122312425914623299。C-SCAN按方向走到底然后快速回到另一端。53→65→67→98→122→124→183→14→37。总移动122312425916923322。注意SCAN和C-SCAN的区别在于SCAN反向时还会服务请求C-SCAN反向时直接回到起点不服务。考试时看清题目要求。5.3 I/O管理缓冲、SPOOLing、设备分配I/O管理这章的习题以概念为主。常见考点缓冲技术单缓冲、双缓冲、循环缓冲。计算题通常给处理时间和传输时间让你算处理一块数据的总时间。SPOOLing技术用磁盘模拟独占设备实现虚拟设备。习题常问“SPOOLing系统由哪几部分组成”答案是输入井、输出井、输入进程、输出进程。设备分配独占设备、共享设备、虚拟设备。分配策略有静态分配和动态分配。我重点讲单缓冲和双缓冲的计算。假设从磁盘读一块数据到缓冲区需要T时间从缓冲区送到用户区需要M时间CPU处理需要C时间。单缓冲处理一块数据的时间 max(T, C) M。因为读入和CPU处理可以并行但送到用户区必须串行。双缓冲处理一块数据的时间 max(T, CM)。因为读入和“送到用户区CPU处理”可以并行。教材习题里经常给具体数字让你算总时间。记住公式代入即可。6. 常见问题与排查技巧实录6.1 习题答案对不上怎么办这是最常见的问题。我分几种情况说情况一安全序列不同。银行家算法的安全序列不唯一只要你的推导过程正确答案不同没关系。情况二页面置换缺页次数不同。检查你的引用串有没有抄错物理块数有没有看错算法有没有用错。FIFO和LRU的结果通常不同OPT一定是最少的。情况三PV操作代码不同。信号量的设置方式可能不同比如有些答案用AND信号量有些用普通信号量。只要逻辑正确能解决同步互斥问题就是对的。情况四计算题结果差一点。检查单位换算比如KB和Bms和s。检查有没有四舍五入有些答案保留两位小数有些保留整数。6.2 考试时的时间分配建议操作系统试卷通常计算量不小。我的建议选择题和填空题15分钟内完成概念辨析题20分钟PV操作题15分钟调度算法计算题15分钟银行家算法10分钟页面置换10分钟磁盘调度10分钟综合题25分钟检查10分钟当然具体根据试卷结构调整。关键是不要在一道题上死磕。如果一道PV操作题想了5分钟还没思路先跳过做完后面的再回来。6.3 复习策略从习题反推知识点我带的学生的经验是先做题再看书。具体来说拿一套课后习题不看答案硬做一遍对答案标记错题针对错题回到教材对应章节把相关概念重新看一遍再找类似的题做一遍确认掌握这个方法比“先看书再做题”效率高因为做题能暴露你的知识盲区。看书时你觉得什么都懂一做题就发现什么都不会。提示汤小丹这本教材的习题量不小不用全做。每章挑10-15道典型题就够了。重点是理解解题思路不是刷题数量。6.4 常见问题速查表问题可能原因解决方法PV操作死锁P操作顺序错误先P资源信号量再P互斥信号量银行家算法找不到安全序列Need计算错误重新计算NeedMax-Allocation页面置换缺页次数偏多算法用错确认题目要求的是FIFO、LRU还是OPT磁盘调度总移动数偏大方向判断错误确认当前磁头移动方向地址转换结果不对页号或偏移计算错误确认页面大小重新划分地址位EAT计算偏差大缺页率代入错误确认缺页率是百分比还是小数7. 从习题到实战操作系统知识怎么用起来7.1 写代码时遇到的PV操作工作后你会发现PV操作的思想无处不在。比如你写一个多线程程序用互斥锁保护共享变量本质上就是P(mutex)和V(mutex)。用条件变量等待某个条件成立本质上就是P(condition)和V(condition)。我举个例子一个线程池任务队列是共享资源。生产者线程往队列里加任务消费者线程从队列里取任务。这就是生产者-消费者问题。用C的mutex和condition_variable实现std::mutex mtx; std::condition_variable cv; std::queueTask task_queue; const int MAX_SIZE 100; // 生产者 void producer(Task t) { std::unique_lockstd::mutex lock(mtx); cv.wait(lock, []{ return task_queue.size() MAX_SIZE; }); task_queue.push(t); cv.notify_all(); } // 消费者 Task consumer() { std::unique_lockstd::mutex lock(mtx); cv.wait(lock, []{ return !task_queue.empty(); }); Task t task_queue.front(); task_queue.pop(); cv.notify_all(); return t; }这里的cv.wait就是P操作cv.notify_all就是V操作。unique_lock保证了互斥。你看操作系统的知识直接用在工程里了。7.2 页面置换算法在缓存中的应用LRU页面置换算法在缓存系统里用得很多。比如Redis的缓存淘汰策略就有LRU和LFU。你写一个本地缓存也可以用LRU算法决定淘汰哪个条目。Java的LinkedHashMap可以直接实现LRU缓存class LRUCacheK, V extends LinkedHashMapK, V { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); // accessOrdertrue this.capacity capacity; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() capacity; } }这里的accessOrdertrue就是按访问顺序排序每次get会把条目移到链表尾部淘汰时移除链表头部——这就是LRU。7.3 磁盘调度算法在数据库中的应用数据库的磁盘I/O调度本质上就是磁盘调度算法。MySQL的InnoDB存储引擎在刷脏页时会尽量按物理地址顺序刷减少磁头移动。这就是SCAN算法的思想。你写一个文件系统或者数据库磁盘调度算法的选择直接影响性能。SSD时代磁头移动的代价小了但顺序读写和随机读写的差距依然存在。所以很多系统还是倾向于顺序I/O。8. 最后分享几个实操心得第一不要背答案。操作系统的题目尤其是PV操作和银行家算法背答案没用。考试时题目稍微变一下你就不会了。关键是理解机制理解为什么这么设计。第二画图。调度算法画甘特图页面置换画表格磁盘调度画磁道移动图。画图能帮你理清思路也能让阅卷老师看到你的推导过程。即使最后结果错了过程对也能拿分。第三多问为什么。为什么FIFO有Belady异常为什么银行家算法能避免死锁为什么LRU比FIFO好把这些问题想清楚你就不需要刷很多题了。第四结合实际。学操作系统时想想你写的程序里哪些地方用到了这些知识。比如你用过线程池就想想生产者-消费者你用过缓存就想想LRU。这样学起来不枯燥也记得牢。第五组队学习。操作系统有些概念比较抽象一个人想半天想不通和别人讨论十分钟就明白了。我当年学的时候几个同学一起画PV操作的流程图互相挑毛病进步很快。这门课确实有难度但学明白了对后面学分布式系统、数据库、编译原理都有帮助。习题答案只是工具真正的收获是解题过程中建立起来的系统思维。