操作系统 8 大核心算法实战：从 FCFS 到银行家，附 10 道典型例题解析

引言

操作系统作为计算机科学的基础课程，其核心算法不仅是理论研究的重点，更是实际系统设计的关键。对于正在备考的大学生而言，单纯记忆概念往往难以应对复杂的应用题。本文精选处理机调度、内存管理、进程同步等领域的8类经典算法，通过10道典型例题的实战解析，帮助读者掌握从问题分析到算法选择的完整解题逻辑。

不同于传统知识罗列式复习，我们将以"问题驱动"的方式展开。每个算法模块包含：

• 场景化例题：模拟真实考试中的综合应用题
• 手写计算过程：展示分步骤的解题细节
• 常见错误预警：标注易错点和验证方法
• 变式拓展：提供相似题型的解题思路

1. 处理机调度算法实战

1.1 FCFS调度与周转时间计算

例题1：现有四个进程到达时间和运行时间如下表，请计算采用FCFS算法时的平均周转时间和平均带权周转时间。

解题步骤：

1. 绘制甘特图：

   0-5:P1, 5-8:P2, 8-16:P3, 16-22:P4

2. 计算各进程完成时间：
   • P1: 5
   • P2: 8
   • P3: 16
   • P4: 22
3. 周转时间 = 完成时间 - 到达时间
   • P1:5-0=5; P2:8-1=7; P3:16-2=14; P4:22-3=19
4. 带权周转时间 = 周转时间/运行时间
   • P1:5/5=1; P2:7/3≈2.33; P3:14/8=1.75; P4:19/6≈3.17
5. 平均值计算：
   • 平均周转时间：(5+7+14+19)/4=11.25
   • 平均带权周转时间：(1+2.33+1.75+3.17)/4≈2.06

注意：FCFS算法对短进程不利，本例中运行时间短的P2反而有较大的带权周转时间

1.2 SJF调度与响应比优化

例题2：在例题1条件下改为非抢占式SJF算法，重新计算各项指标。

关键步骤：

1. 初始时只有P1可执行，执行后时间点来到5
2. 此时就绪队列有P2(剩余3)、P3(8)、P4(6)，选择最短的P2
3. P2完成后时间点来到8，剩余P3(8)、P4(6)，选择P4
4. 最终执行顺序：P1→P2→P4→P3

对比分析：

• 平均周转时间从11.25降至10.25
• 平均带权周转时间从2.06降至1.57
• SJF能有效降低短进程的等待时间

2. 死锁处理算法专题

2.1 银行家算法安全序列判断

例题3：某系统当前资源分配情况如下，判断系统是否安全？若进程P2请求(1,0,2)能否立即分配？

安全序列查找过程：

1. 计算Work初始值=Available=(3,3,2)
2. 查找Need≤Work的进程：
   • P3满足(0,1,1)<=(3,3,2)，假设执行后释放资源，Work=(5,4,3)
   • 接着P1满足条件，Work=(7,4,3)
   • 然后P0/P2/P4依次执行
3. 存在安全序列如P3→P1→P0→P2→P4

请求处理：

1. 检查请求是否≤Need：(1,0,2)<=(6,0,0) ✔
2. 检查请求是否≤Available：(1,0,2)<=(3,3,2) ✔
3. 假设分配后：
   • Available=(2,3,0)
   • P2 Allocation=(4,0,4), Need=(5,0,0)
4. 重新执行安全性算法仍能找到安全序列

关键：每次分配后必须确保至少存在一个安全序列

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次

算法对比表：

4. 进程同步经典问题

4.1 生产者-消费者问题实现

例题5：使用信号量实现缓冲区大小为N的生产者-消费者同步模型，要求：

1. 多个生产者/消费者线程安全访问
2. 缓冲区满时生产者阻塞
3. 缓冲区空时消费者阻塞

#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解法：

1. 当前100，最近的是90
2. 接着90最近的是58
3. 顺序：100→90→58→55→39→38→18→150→160→184
4. 移动距离：10+32+3+16+1+20+132+10+24=248

SCAN解法（假设初始方向向磁道号增大）：

1. 移动路径：100→150→160→184→90→58→55→39→38→18
2. 移动距离：50+10+24+94+32+3+16+1+20=250

性能对比：

• SSTF平均寻道时间更短但可能导致饥饿
• SCAN算法更公平但效率略低
• 现代系统多采用C-SCAN（循环扫描）优化

6. 银行家算法进阶训练

6.1 多资源类型安全检测

例题7：系统有A/B/C三类资源，数量为(10,5,7)，五个进程当前状态如下：

当前Available = (3,3,2)，判断系统是否安全？若P1请求(1,0,2)能否分配？

安全序列查找：

1. Work初始=Available=(3,3,2)
2. 找出Need<=Work的进程：
   • P3(0,1,1)<=(3,3,2) ✔
   • 执行P3后Work=(5,4,3)
3. 接下来P1(1,2,2)<=(5,4,3) ✔
   • Work=(7,4,3)
4. 依次可找到安全序列P3→P1→P0→P2→P4

请求处理：

1. 检查(1,0,2)<=P1.Need ✔
2. 检查(1,0,2)<=Available ✔
3. 假设分配后：
   • Available=(2,3,0)
   • P1.Allocation=(3,0,2)
   • P1.Need=(0,2,0)
4. 重新执行安全算法仍能找到安全序列

关键点：多资源类型需要逐维度比较Need和Work向量

7. 综合应用题解析

7.1 调度算法综合应用

例题8：某系统采用多级反馈队列调度，规则如下：

• Q1：RR时间片4ms，优先级最高
• Q2：RR时间片8ms，次高优先级
• Q3：FCFS，最低优先级
• 新进程进入Q1，若时间片用完未完成则降级
• 仅当高优先级队列空时才调度低优先级

现有四个进程：

• P1(到达0ms，需要12ms)
• P2(到达5ms，需要18ms)
• P3(到达8ms，需要6ms)
• P4(到达10ms，需要9ms)

绘制甘特图并计算平均周转时间。

解题过程：

1. 时间0-4：P1在Q1执行4ms（剩余8ms）
2. 时间4-8：P1降级到Q2，执行8ms（完成于12ms）
3. 时间5-9：P2在Q1执行4ms（剩余14ms）后降级
4. 时间8-12：P3到达并立即在Q1执行4ms（剩余2ms）
5. 时间10-14：P4在Q1执行4ms（剩余5ms）
6. 最终执行顺序：

   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-0=12
• P2:24-5=19
• P3:18-8=10
• P4:29-10=19
• 平均值：(12+19+10+19)/4=15ms

8. 内存分配策略对比

8.1 动态分区分配算法

例题9：某系统采用动态分区分配，当前内存空闲块按地址顺序为：

• 起始100K，大小150K
• 起始400K，大小80K
• 起始600K，大小200K

现有进程依次请求分配：120K、80K、90K，分别采用首次适应(FF)、最佳适应(BF)、最坏适应(WF)策略，给出分配结果和剩余空闲区。

FF算法：

1. 120K分配在100K块（剩余30K）
2. 80K分配在400K块（刚好用完）
3. 90K分配在600K块（剩余110K） 最终空闲区：

• 100K+150K→30K
• 400K+80K→0K
• 600K+200K→110K

BF算法：

1. 120K选择最接近的150K块（剩余30K）
2. 80K选择正好匹配的80K块
3. 90K选择200K块（剩余110K） 分配结果与FF相同但选择逻辑不同

WF算法：

1. 120K选择最大的200K块（剩余80K）
2. 80K选择剩余的150K块（剩余70K）
3. 90K无法分配（最大剩余80K<90K） 最终分配成功两个请求

算法对比：

9. 信号量应用题精讲

9.1 读者-写者问题变种

例题10：实现读者优先的读者-写者问题，要求：

1. 多个读者可同时访问
2. 写者必须独占访问
3. 当有写者等待时，新读者需等待

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锁，保证先到先服务原则。