操作系统面试必问：FCFS、SJF、HRRN调度算法到底怎么算？一个例子讲透

操作系统面试必问：FCFS、SJF、HRRN调度算法实战解析

在计算机操作系统的面试中，进程调度算法几乎是必考的核心知识点。无论是校招笔试还是技术面谈，面试官都喜欢用"给定一组进程的到达时间和服务时间，请计算不同调度算法下的完成时间和周转时间"这类题目来考察候选人对操作系统原理的理解深度。本文将用同一组进程数据，手把手带你演练FCFS、SJF、HRRN三种经典调度算法的完整计算过程，帮你建立清晰的解题框架。

1. 理解进程调度的基本概念

进程调度是操作系统内核的核心功能之一，它决定了CPU资源如何分配给多个竞争执行的进程。一个优秀的调度算法需要在公平性和效率之间找到平衡点，同时考虑响应时间和吞吐量等关键指标。

关键术语解析：

• 到达时间(Arrival Time): 进程进入就绪队列的时间点
• 服务时间(Serve Time): 进程需要占用CPU执行的总时间
• 完成时间(Finish Time): 进程结束执行的时间点
• 周转时间(Turnaround Time): 完成时间减去到达时间
• 带权周转时间(Weighted Turnaround Time): 周转时间与服务时间的比值

提示：带权周转时间反映了进程的相对等待成本，数值越小表示调度效率越高

我们以这组进程数据为例，贯穿全文演示计算过程：

2. 先来先服务(FCFS)调度算法详解

FCFS(First Come First Serve)是最直观的调度策略，就像超市收银台排队一样，严格按照进程到达的顺序分配CPU资源。

2.1 FCFS算法执行流程

1. 初始化：维护一个时间线变量current_time，初始为0
2. 调度规则：
   • 选择当前已到达但未执行的进程中到达时间最早的
   • 如果多个进程同时到达，通常按输入顺序处理
3. 计算步骤：
   • 进程开始执行时间 = max(进程到达时间, 前一个进程完成时间)
   • 完成时间 = 开始执行时间 + 服务时间
   • 周转时间 = 完成时间 - 到达时间
   • 带权周转时间 = 周转时间 / 服务时间

2.2 实例计算过程

让我们用表格形式展示FCFS算法的完整计算过程：

执行时间线可视化：

0-3:A | 3-9:B | 9-13:C | 13-18:D | 18-20:E

2.3 FCFS算法的特点分析

优势：

• 实现简单，调度开销小
• 对所有进程公平，无饥饿现象

劣势：

• 平均等待时间较长（本例中为8.6）
• 对短作业不友好（如进程E的带权周转时间高达6.0）
• 可能导致CPU和I/O设备利用率低下

注意：FCFS算法在进程到达顺序不理想时，可能出现"护航效应"(Convoy Effect)，即长进程阻塞后方短进程的执行

3. 短作业优先(SJF)调度算法深度剖析

SJF(Shortest Job First)算法试图优化系统平均周转时间，优先执行预计运行时间短的进程。

3.1 SJF算法的两种变体

1. 非抢占式SJF：一旦进程开始执行就运行到完成
2. 抢占式SJF(又称最短剩余时间优先)：当新进程到达时，如果其服务时间比当前执行进程的剩余时间短，则抢占CPU

本文重点讲解非抢占式SJF的实现。

3.2 SJF算法执行步骤

1. 初始状态：所有进程标记为未调度，current_time = 0
2. 调度时机：每当CPU空闲时（初始时或进程完成时）
3. 选择策略：从已到达的未调度进程中选择服务时间最短的
4. 计算指标：同FCFS算法

3.3 实例计算过程

让我们逐步计算SJF调度下的各项指标：

第一轮调度（current_time=0）：

• 就绪进程：A
• 选择A执行，完成时间=3

第二轮调度（current_time=3）：

• 已到达进程：B(到达时间2)、C(到达时间4还未到)
• 只有B就绪，选择B执行，完成时间=9

第三轮调度（current_time=9）：

• 已到达未调度进程：C、D、E
• 比较服务时间：C(4)、D(5)、E(2)
• 选择E执行（虽然E到达时间是8，但当前时间已到9），完成时间=11

第四轮调度（current_time=11）：

• 剩余进程：C(4)、D(5)
• 选择C执行，完成时间=15

第五轮调度（current_time=15）：

• 剩余进程：D
• 选择D执行，完成时间=20

最终结果表格：

执行时间线：

0-3:A | 3-9:B | 9-11:E | 11-15:C | 15-20:D

3.4 SJF算法优劣分析

优势：

• 理论上能提供最小的平均周转时间
• 特别适合短作业繁多的场景

劣势：

• 长作业可能饥饿（本例中D进程最后执行）
• 需要预知或估算进程运行时间（实际系统中难以精确获取）
• 实现复杂度高于FCFS

4. 高响应比优先(HRRN)调度算法实战

HRRN(Highest Response Ratio Next)算法试图平衡等待时间和服务时间，克服FCFS和SJF的某些缺点。

4.1 响应比计算公式

响应比(RR) = (等待时间 + 服务时间) / 服务时间 = 1 + (等待时间 / 服务时间)

其中，等待时间 = current_time - 到达时间

4.2 HRRN算法执行流程

1. 初始状态：current_time=0，所有进程未调度
2. 调度时机：CPU空闲时（初始或进程完成时）
3. 选择策略：
   • 计算所有已到达未调度进程的响应比
   • 选择响应比最高的进程执行
4. 指标计算：同前两种算法

4.3 实例逐步计算

第一轮调度（current_time=0）：

• 只有A到达，选择A执行，完成时间=3

第二轮调度（current_time=3）：

• 就绪进程：B(到达时间2)
• 计算响应比：B的等待时间=3-2=1，RR=1+1/6≈1.17
• 选择B执行，完成时间=9

第三轮调度（current_time=9）：

• 就绪进程：C(到达时间4)、D(到达时间6)、E(到达时间8)
• 计算各进程响应比：
  • C: 等待时间=9-4=5，RR=1+5/4=2.25
  • D: 等待时间=9-6=3，RR=1+3/5=1.6
  • E: 等待时间=9-8=1，RR=1+1/2=1.5
• 选择响应比最高的C执行，完成时间=13

第四轮调度（current_time=13）：

• 就绪进程：D、E
• 计算响应比：
  • D: 等待时间=13-6=7，RR=1+7/5=2.4
  • E: 等待时间=13-8=5，RR=1+5/2=3.5
• 选择E执行（虽然服务时间短，但响应比更高），完成时间=15

第五轮调度（current_time=15）：

• 剩余进程：D
• 选择D执行，完成时间=20

最终结果表格：

执行时间线：

0-3:A | 3-9:B | 9-13:C | 13-15:E | 15-20:D

4.4 HRRN算法特点总结

优势：

• 兼顾了等待时间和服务时间
• 长作业随着等待时间增加，响应比会上升，避免了饥饿
• 平均周转时间通常优于FCFS

劣势：

• 每次调度都需要计算所有就绪进程的响应比，开销较大
• 仍然需要预知服务时间

5. 三种算法综合对比与面试技巧

通过同一组进程数据的计算，我们可以直观比较三种算法的表现：

性能指标对比表：

面试常见问题解析：

1. 如何选择调度算法？

   • 批处理系统：SJF或HRRN
   • 交互式系统：时间片轮转或多级反馈队列
   • 实时系统：优先级调度

2. SJF为什么能提供最小平均周转时间？

   • 数学上可以证明，通过交换论证：任何非SJF的调度顺序通过交换相邻的逆序对都能减少平均周转时间

3. HRRN中响应比公式的设计原理？

   • 分子体现公平性（等待时间），分母体现效率（服务时间）
   • 形式为(等待+服务)/服务而非等待/服务，确保数值≥1

面试实战建议：

• 遇到调度算法题，先明确是哪种调度策略
• 画时间线图可以帮助理清思路
• 计算时注意检查进程到达时间与当前时间的关系
• 可以先用简单例子验证算法理解是否正确