操作系统 8 大核心算法实战从 FCFS 到银行家附 10 道典型例题解析引言操作系统作为计算机科学的基础课程其核心算法不仅是理论研究的重点更是实际系统设计的关键。对于正在备考的大学生而言单纯记忆概念往往难以应对复杂的应用题。本文精选处理机调度、内存管理、进程同步等领域的8类经典算法通过10道典型例题的实战解析帮助读者掌握从问题分析到算法选择的完整解题逻辑。不同于传统知识罗列式复习我们将以问题驱动的方式展开。每个算法模块包含场景化例题模拟真实考试中的综合应用题手写计算过程展示分步骤的解题细节常见错误预警标注易错点和验证方法变式拓展提供相似题型的解题思路1. 处理机调度算法实战1.1 FCFS调度与周转时间计算例题1现有四个进程到达时间和运行时间如下表请计算采用FCFS算法时的平均周转时间和平均带权周转时间。进程到达时间运行时间P105P213P328P436解题步骤绘制甘特图0-5:P1, 5-8:P2, 8-16:P3, 16-22:P4计算各进程完成时间P1: 5P2: 8P3: 16P4: 22周转时间 完成时间 - 到达时间P1:5-05; P2:8-17; P3:16-214; P4:22-319带权周转时间 周转时间/运行时间P1:5/51; P2:7/3≈2.33; P3:14/81.75; P4:19/6≈3.17平均值计算平均周转时间(571419)/411.25平均带权周转时间(12.331.753.17)/4≈2.06注意FCFS算法对短进程不利本例中运行时间短的P2反而有较大的带权周转时间1.2 SJF调度与响应比优化例题2在例题1条件下改为非抢占式SJF算法重新计算各项指标。关键步骤初始时只有P1可执行执行后时间点来到5此时就绪队列有P2(剩余3)、P3(8)、P4(6)选择最短的P2P2完成后时间点来到8剩余P3(8)、P4(6)选择P4最终执行顺序P1→P2→P4→P3对比分析平均周转时间从11.25降至10.25平均带权周转时间从2.06降至1.57SJF能有效降低短进程的等待时间2. 死锁处理算法专题2.1 银行家算法安全序列判断例题3某系统当前资源分配情况如下判断系统是否安全若进程P2请求(1,0,2)能否立即分配进程MaxAllocationNeedP0(7,5,3)(0,1,0)(7,4,3)P1(3,2,2)(2,0,0)(1,2,2)P2(9,0,2)(3,0,2)(6,0,0)P3(2,2,2)(2,1,1)(0,1,1)P4(4,3,3)(0,0,2)(4,3,1)当前可用资源 Available (3,3,2)安全序列查找过程计算Work初始值Available(3,3,2)查找Need≤Work的进程P3满足(0,1,1)(3,3,2)假设执行后释放资源Work(5,4,3)接着P1满足条件Work(7,4,3)然后P0/P2/P4依次执行存在安全序列如P3→P1→P0→P2→P4请求处理检查请求是否≤Need(1,0,2)(6,0,0) ✔检查请求是否≤Available(1,0,2)(3,3,2) ✔假设分配后Available(2,3,0)P2 Allocation(4,0,4), Need(5,0,0)重新执行安全性算法仍能找到安全序列关键每次分配后必须确保至少存在一个安全序列3. 内存管理算法精解3.1 页面置换算法对比例题4假设页面引用串为7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1物理块数3分别计算FIFO、LRU、OPT算法的缺页次数。FIFO实现引用串7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 页面框[7], [7,0], [7,0,1] // 前三次缺页 替换顺序7被2替换0被3替换1被4替换... 缺页标记x x x x x x x x x x x x 总缺页次数15次LRU实现当访问2(第4个)时最近最久未使用的是7 当访问3(第6个)时LRU队列为2,0,1 → 替换1 缺页次数12次OPT实现访问2时预测7在未来最远不被使用 访问3时预测1在后续引用串中最远 缺页次数9次算法对比表算法缺页次数适用场景FIFO15实现简单但Belady异常LRU12接近OPT但开销较大OPT9理论最优但无法实际实现4. 进程同步经典问题4.1 生产者-消费者问题实现例题5使用信号量实现缓冲区大小为N的生产者-消费者同步模型要求多个生产者/消费者线程安全访问缓冲区满时生产者阻塞缓冲区空时消费者阻塞#define N 100 semaphore mutex 1; // 缓冲区互斥锁 semaphore empty N; // 空槽位计数 semaphore full 0; // 满槽位计数 void producer() { while(1) { item produce_item(); P(empty); // 等待空位 P(mutex); // 获取缓冲区锁 insert_item(item); V(mutex); V(full); // 增加满计数 } } void consumer() { while(1) { P(full); // 等待有数据 P(mutex); item remove_item(); V(mutex); V(empty); // 增加空计数 consume_item(item); } }注意P操作顺序不能颠倒否则可能引发死锁。例如若先P(mutex)再P(empty)当缓冲区满时生产者持有mutex等待empty而消费者因无法获取mutex而无法消费。5. 磁盘调度算法应用5.1 寻道时间优化计算例题6磁盘当前位于磁道100请求队列为55, 58, 39, 18, 90, 160, 150, 38, 184。分别计算SSTF、SCAN算法的磁头移动总距离。SSTF解法当前100最近的是90接着90最近的是58顺序100→90→58→55→39→38→18→150→160→184移动距离10323161201321024248SCAN解法假设初始方向向磁道号增大移动路径100→150→160→184→90→58→55→39→38→18移动距离5010249432316120250性能对比SSTF平均寻道时间更短但可能导致饥饿SCAN算法更公平但效率略低现代系统多采用C-SCAN循环扫描优化6. 银行家算法进阶训练6.1 多资源类型安全检测例题7系统有A/B/C三类资源数量为(10,5,7)五个进程当前状态如下进程AllocationMaxNeedP0(0,1,0)(7,5,3)(7,4,3)P1(2,0,0)(3,2,2)(1,2,2)P2(3,0,2)(9,0,2)(6,0,0)P3(2,1,1)(2,2,2)(0,1,1)P4(0,0,2)(4,3,3)(4,3,1)当前Available (3,3,2)判断系统是否安全若P1请求(1,0,2)能否分配安全序列查找Work初始Available(3,3,2)找出NeedWork的进程P3(0,1,1)(3,3,2) ✔执行P3后Work(5,4,3)接下来P1(1,2,2)(5,4,3) ✔Work(7,4,3)依次可找到安全序列P3→P1→P0→P2→P4请求处理检查(1,0,2)P1.Need ✔检查(1,0,2)Available ✔假设分配后Available(2,3,0)P1.Allocation(3,0,2)P1.Need(0,2,0)重新执行安全算法仍能找到安全序列关键点多资源类型需要逐维度比较Need和Work向量7. 综合应用题解析7.1 调度算法综合应用例题8某系统采用多级反馈队列调度规则如下Q1RR时间片4ms优先级最高Q2RR时间片8ms次高优先级Q3FCFS最低优先级新进程进入Q1若时间片用完未完成则降级仅当高优先级队列空时才调度低优先级现有四个进程P1(到达0ms需要12ms)P2(到达5ms需要18ms)P3(到达8ms需要6ms)P4(到达10ms需要9ms)绘制甘特图并计算平均周转时间。解题过程时间0-4P1在Q1执行4ms剩余8ms时间4-8P1降级到Q2执行8ms完成于12ms时间5-9P2在Q1执行4ms剩余14ms后降级时间8-12P3到达并立即在Q1执行4ms剩余2ms时间10-14P4在Q1执行4ms剩余5ms最终执行顺序Q1: P1(0-4)→P2(5-9)→P3(9-12)→P4(12-16) Q2: P1(4-12)→P2(16-24) Q3: P3(16-18)→P4(24-29)周转时间计算P1:12-012P2:24-519P3:18-810P4:29-1019平均值(12191019)/415ms8. 内存分配策略对比8.1 动态分区分配算法例题9某系统采用动态分区分配当前内存空闲块按地址顺序为起始100K大小150K起始400K大小80K起始600K大小200K现有进程依次请求分配120K、80K、90K分别采用首次适应(FF)、最佳适应(BF)、最坏适应(WF)策略给出分配结果和剩余空闲区。FF算法120K分配在100K块剩余30K80K分配在400K块刚好用完90K分配在600K块剩余110K 最终空闲区100K150K→30K400K80K→0K600K200K→110KBF算法120K选择最接近的150K块剩余30K80K选择正好匹配的80K块90K选择200K块剩余110K 分配结果与FF相同但选择逻辑不同WF算法120K选择最大的200K块剩余80K80K选择剩余的150K块剩余70K90K无法分配最大剩余80K90K 最终分配成功两个请求算法对比策略优点缺点FF分配速度快容易产生外部碎片BF碎片利用率高可能留太多小碎片WF减少小碎片产生大空闲块容易被拆分9. 信号量应用题精讲9.1 读者-写者问题变种例题10实现读者优先的读者-写者问题要求多个读者可同时访问写者必须独占访问当有写者等待时新读者需等待int readcount 0; // 当前读者数 semaphore rmutex 1; // 保护readcount semaphore wmutex 1; // 写者互斥 semaphore queue 1; // 公平排队 void reader() { P(queue); // 排队保证公平 P(rmutex); if(readcount 0) P(wmutex); // 第一个读者加锁 readcount; V(rmutex); V(queue); // 释放排队锁 perform_read(); P(rmutex); readcount--; if(readcount 0) V(wmutex); // 最后一个读者释放 V(rmutex); } void writer() { P(queue); // 所有进程统一排队 P(wmutex); V(queue); perform_write(); V(wmutex); }改进点通过queue信号量消除写者饥饿问题。所有进程必须先获取queue锁保证先到先服务原则。