操作系统（第四版）期末大题精讲：从经典例题到解题模板

1. 进程同步大题解题模板信号量机制是操作系统期末考试中几乎必考的核心知识点。很多同学一看到用信号量实现XX同步问题就头疼其实这类题目有固定套路。我当年备考时总结了一套信号量三步法至今仍觉得非常实用。1.1 生产者-消费者模型这是最基础的同步问题模板。以经典的文件打印问题为例PA读文件到缓冲区1PB复制到缓冲区2PC打印。解题步骤如下分析资源竞争点缓冲区1和缓冲区2都是临界资源需要互斥访问同时缓冲区空/满状态需要同步控制定义信号量semaphore mutex1 1; // 缓冲区1互斥锁 semaphore mutex2 1; // 缓冲区2互斥锁 semaphore empty1 1; // 缓冲区1空位 semaphore full1 0; // 缓冲区1数据 semaphore empty2 1; // 缓冲区2空位 semaphore full2 0; // 缓冲区2数据编写进程代码// PA进程 while(1){ wait(empty1); wait(mutex1); 读取记录到缓冲区1; signal(mutex1); signal(full1); } // PB进程 while(1){ wait(full1); wait(mutex1); wait(empty2); wait(mutex2); 复制缓冲区1到缓冲区2; signal(mutex1); signal(empty1); signal(mutex2); signal(full2); }常见错误是忘记对第二个缓冲区的互斥控制或者同步信号量的顺序错误。记住一个原则先检查资源可用性empty/full再获取互斥锁。1.2 读者-写者问题变种过独木桥问题就是典型的读者-写者变种。解题关键识别类比关系将两个方向的行人看作两类读者设计计数器分别统计两个方向的过桥人数实现互斥int countA0, countB0; semaphore bridge1; // 桥互斥 semaphore mutexA1, mutexB1; // 计数器互斥 // A方向行人 wait(mutexA); if(countA0) wait(bridge); countA; signal(mutexA); 过桥; wait(mutexA); countA--; if(countA0) signal(bridge); signal(mutexA);这类题最容易出错的是计数器更新时的互斥保护。我在第一次做题时就忘了给countA加锁导致出现竞态条件。记住任何共享变量的修改都必须互斥。2. 调度算法计算题套路2.1 基础指标计算无论哪种调度算法都要掌握以下核心指标周转时间 完成时间 - 到达时间带权周转时间 周转时间 / 服务时间平均周转时间 所有作业周转时间之和 / 作业数量以FCFS算法为例作业 到达时间 服务时间 A 0 3 B 2 6 C 4 4计算步骤确定调度顺序A→B→C计算完成时间A(3), B(369), C(9413)周转时间A(3-03), B(9-27), C(13-49)带权周转时间A(3/31), B(7/6≈1.17), C(9/42.25)2.2 银行家算法步骤安全检测是银行家算法的难点我总结为五步法计算Available 总资源 - ∑Allocation寻找Need ≤ Available的进程假设分配资源更新Available和进程状态重复步骤2-3直到所有进程完成如果所有进程都能完成则系统安全例题Max Allocation Need Available P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0解题过程Work Available (3,3,2)找到Need(P1)(1,2,2) ≤ Work假设分配Work (3,3,2)(2,0,0)(5,3,2)接着分配P3→P4→P2→P0得到安全序列P1,P3,P4,P2,P0常见错误是忽略进程的释放资源会重新加入Available。建议画表格逐步演算我在考试时会专门留出一页草稿纸做这个计算。3. 存储管理大题模板3.1 地址转换通用解法无论是分页还是分段系统地址转换都遵循相同模式确定地址结构分页系统页号 页内偏移分段系统段号 段内偏移计算各部分位数页内偏移位数 log₂(页面大小)页号位数 逻辑地址位数 - 页内偏移位数例题32位系统页面大小4KB则页内偏移 12位 (因为4KB2¹²)页号 32-1220位查表转换分页页表[页号] 物理块号分段段表[段号].base 段内偏移3.2 页面置换算法对比三种常见算法的解题要点FIFO维护一个队列记录页面进入顺序替换最早进入的页面Belady异常分配物理块增加但缺页率反而升高LRU维护访问时间戳替换最久未被访问的页面实现开销大但效果好Clock使用访问位模拟LRU像时钟指针循环查找访问位为0的页面第二机会算法第一次遇到访问位1会置0给第二次机会例题引用串1,3,2,1,4,5,1,2,3,4 物理块3FIFO缺页次数6次 LRU缺页次数5次这类题最容易错的是Belady现象的判断。我建议画置换图时用不同颜色标注缺页这样一目了然。4. 磁盘调度算法实战4.1 算法特性对比算法特点适用场景可能问题FCFS简单公平负载轻时寻道时间长SSTF最短寻道优先中等负载可能饥饿SCAN电梯算法重负载两端请求等待久C-SCAN循环扫描均匀服务单向浪费4.2 计算题标准解法例题磁道请求序列98, 183, 37, 122, 14, 124, 65, 67。磁头初始位置53向0移动。SCAN算法步骤排序请求14, 37, 65, 67, 98, 122, 124, 183确定移动方向向0移动处理路径53→37→14→0→65→67→98→122→124→183计算总寻道长度 (53-37)(37-14)(14-0)(65-0)(67-65)... 236SSTF算法步骤找最近请求53→65距离12接着找65→67距离2继续67→37距离30注意方向改变总寻道长度122302384259 212这类题最容易错的是SCAN算法在磁头到达磁盘端后的折返处理。我建议先在草稿纸上画出磁道数轴标出所有请求位置再模拟磁头移动轨迹。在实际考试中我发现很多同学会混淆SCAN和C-SCAN的区别。记住SCAN是双向移动像电梯C-SCAN是单向循环移动像旋转门。考试前把这个对比图画在便签上带进考场非常有用。