操作系统作业调度习题详解与实战演练：掌握先来先服务短作业优先及多级反馈队列调度算法的解题技巧与常见误区分析

引言：作业调度的核心地位

在操作系统中，作业调度（Job Scheduling）是多道程序设计和分时系统的基础。它的主要任务是按照某种策略，从后备队列中选择一个或多个作业投入运行。这直接决定了系统的吞吐量（单位时间内完成的作业数）、周转时间（作业从提交到完成的时间）和CPU利用率。

对于学习操作系统的学生而言，作业调度不仅仅是背诵概念，更重要的是能够通过具体的习题来计算指标、分析性能并理解算法的优劣。本文将深入剖析三种最经典的调度算法：先来先服务（FCFS）、短作业优先（SJF） 和 多级反馈队列（MFQ），通过详细的习题解答、代码模拟和误区分析，帮助你彻底掌握这一章节。

一、先来先服务（FCFS, First-Come, First-Served）

1.1 算法原理

FCFS 是最简单的调度算法。它严格按照作业到达后备队列的顺序进行调度，类似于在银行排队办理业务，先到先得。

特点：非抢占式（Non-preemptive）。
优点：公平，易于实现。
缺点：平均等待时间往往较长，对短作业不利（“护航效应”）。

1.2 习题详解

题目：假设系统中有三个作业，它们几乎同时到达（到达时间均为 0），但服务时间（Burst Time）不同。请分别计算在 FCFS 调度下的平均周转时间和平均等待时间。

作业 (Job)	服务时间 (Service Time)
J1	24
J2	3
J3	3

解题步骤：

确定执行顺序：因为到达时间均为 0，且是 FCFS，我们假设输入顺序即为到达顺序：J1 -> J2 -> J3。
计算开始时间、完成时间、周转时间、等待时间：
- 周转时间 = 完成时间 - 到达时间
- 等待时间 = 周转时间 - 服务时间

作业	服务时间	开始时间	完成时间	周转时间	等待时间
J1	24	0	24	24 - 0 = 24	24 - 24 = 0
J2	3	24	27	27 - 0 = 27	27 - 3 = 24
J3	3	27	30	30 - 0 = 30	30 - 3 = 27

计算平均值：
- 平均周转时间 = \((24 + 27 + 30) / 3 = 27\)
- 平均等待时间 = \((0 + 24 + 27) / 3 = 17\)

分析：可以看到，虽然 J2 和 J3 只需要很短的 3 个单位时间，但因为排在长作业 J1 后面，不得不等待很长时间。这就是 FCFS 的典型缺陷。

二、短作业优先（SJF, Shortest Job First）

2.1 算法原理

SJF 调度算法每次从后备队列中选择服务时间最短的作业投入运行。

特点：
- 非抢占式（Non-preemptive SJF）：一旦作业开始运行，直到完成，即使有新来的更短作业，也不中断。
- 抢占式（Shortest Remaining Time First, SRTF）：当新作业到达且其服务时间比当前正在运行的作业的剩余时间更短时，剥夺当前作业的 CPU。
优点：在所有算法中，能提供最小的平均等待时间和平均周转时间。
缺点：可能导致长作业“饥饿”（Starvation）；需要预知作业的未来服务时间（这在实际中很难做到）。

2.2 习题详解（非抢占式）

题目：假设系统中有四个作业，到达时间和服务时间如下。请计算在非抢占式 SJF 调度下的平均周转时间和平均等待时间。

作业	到达时间	服务时间
J1	0	7
J2	2	4
J3	4	1
J4	5	4

解题步骤：

Gantt 图分析（甘特图）：
- t=0: 只有 J1 到达，必须选 J1。
- t=7: J1 完成。此时 J2(到达时间2), J3(到达时间4), J4(到达时间5) 都已在队列中。
  - 比较它们的服务时间：J2(4), J3(1), J4(4)。
  - J3 服务时间最短（1），所以接下来运行 J3。
- t=8: J3 完成。队列中剩下 J2(4), J4(4)。
  - 服务时间相同，按到达顺序（或作业号）处理，选 J2。
- t=12: J2 完成。队列中剩下 J4(4)。
- t=16: J4 完成。
列表计算：

作业	到达时间	服务时间	开始时间	完成时间	周转时间	等待时间
J1	0	7	0	7	7	0
J3	4	1	7	8	4	3
J2	2	4	8	12	10	6
J4	5	4	12	16	11	7

注：J3 的周转时间 = 8 - 4 = 4。

计算平均值：
- 平均周转时间 = \((7 + 4 + 10 + 11) / 4 = 8.0\)
- 平均等待时间 = \((0 + 3 + 6 + 7) / 4 = 4.0\)

2.3 实战演练：Python 模拟 SJF 调度

为了更直观地理解，我们可以编写一段 Python 代码来模拟上述过程。

import heapq

class Job:
    def __init__(self, job_id, arrival_time, burst_time):
        self.job_id = job_id
        self.arrival_time = arrival_time
        self.burst_time = burst_time
        self.waiting_time = 0
        self.turnaround_time = 0
        self.completion_time = 0
        self.remaining_time = burst_time

    # 定义比较操作符，用于优先队列（按服务时间排序）
    def __lt__(self, other):
        if self.burst_time == other.burst_time:
            return self.arrival_time < other.arrival_time
        return self.burst_time < other.burst_time

def simulate_sjf(jobs):
    # 按到达时间排序
    jobs.sort(key=lambda x: x.arrival_time)
    
    current_time = 0
    completed_jobs = []
    ready_queue = [] # 优先队列
    
    i = 0 # 已加入队列的作业索引
    
    print(f"{'Time':<5} | {'Event':<20} | {'Ready Queue':<20}")
    print("-" * 55)
    
    while i < len(jobs) or ready_queue:
        # 1. 将当前时间到达的作业加入就绪队列
        while i < len(jobs) and jobs[i].arrival_time <= current_time:
            heapq.heappush(ready_queue, jobs[i])
            print(f"{current_time:<5} | Job {jobs[i].job_id} Arrived      | {[f'J{x.job_id}(t={x.burst_time})' for x in ready_queue]}")
            i += 1
        
        if not ready_queue:
            # 如果没有作业，时间跳到下一个作业到达
            if i < len(jobs):
                current_time = jobs[i].arrival_time
                continue
            else:
                break
        
        # 2. 从就绪队列取出服务时间最短的作业
        current_job = heapq.heappop(ready_queue)
        start_time = max(current_time, current_job.arrival_time)
        
        # 3. 执行作业
        print(f"{start_time:<5} | Start Job {current_job.job_id}       | {[f'J{x.job_id}(t={x.burst_time})' for x in ready_queue]}")
        
        # 非抢占式，直接运行完
        current_job.completion_time = start_time + current_job.burst_time
        current_job.turnaround_time = current_job.completion_time - current_job.arrival_time
        current_job.waiting_time = current_job.turnaround_time - current_job.burst_time
        
        current_time = current_job.completion_time
        completed_jobs.append(current_job)
        
        print(f"{current_time:<5} | Finish Job {current_job.job_id}      | {[f'J{x.job_id}(t={x.burst_time})' for x in ready_queue]}")

    return completed_jobs

# 数据输入
job_list = [
    Job(1, 0, 7),
    Job(2, 2, 4),
    Job(3, 4, 1),
    Job(4, 5, 4)
]

result = simulate_sjf(job_list)

# 输出统计结果
print("\n统计结果:")
total_wait = sum(j.waiting_time for j in result)
total_turnaround = sum(j.turnaround_time for j in result)
print(f"平均等待时间: {total_wait / len(result):.2f}")
print(f"平均周转时间: {total_turnaround / len(result):.2f}")

三、多级反馈队列（MFQ, Multilevel Feedback Queue）

3.1 算法原理

MFQ 是最通用也是最复杂的调度算法，它结合了 FCFS 和 SJF（以及时间片轮转）的优点。

核心机制：
1. 多级队列：设置多个就绪队列（Q0, Q1, Q2…），每个队列优先级不同（Q0 最高）。
2. 时间片大小不同：优先级越高的队列，时间片（Time Quantum）越短；优先级越低的队列，时间片越长。
3. 调度规则：
  - 新进程进入 Q0。
  - 若在 Q0 的时间片内未完成，则被剥夺 CPU，降级放入 Q1。
  - 以此类推，直到进入最低级队列。
  - 仅当高级队列为空时，才调度低级队列。
4. 老化（Aging）：为防止低级队列作业饥饿，可规定在低级队列等待过久的作业提升到高级队列。

3.2 习题详解

题目：假设有一个三级反馈队列：

Q0: 优先级最高，时间片 = 4ms
Q1: 优先级中等，时间片 = 8ms
Q2: 优先级最低，FCFS

现有三个作业：

P1: 需 10ms (到达时间 0)
P2: 需 4ms (到达时间 1)
P3: 需 6ms (到达时间 2)

解题过程：

t=0: P1 到达，进入 Q0。P1 运行 4ms（用完 Q0 时间片），剩余 6ms，降级到 Q1。
t=1: P2 到达，进入 Q0。因为 Q0 有 P2，且 P1 已在 Q1，优先运行 Q0 的 P2。
- P2 需 4ms，正好在 Q0 的时间片内完成（运行 1ms-5ms）。
t=5: Q0 为空。调度 Q1 中的 P1。
- P1 在 Q1，时间片 8ms。P1 还需 6ms。
- P1 运行 6ms 完成（运行 5ms-11ms）。
t=2: P3 到达。此时 P1 正在运行（t=2 在 0-5 之间）。
- P3 进入 Q0 等待。
- 在 t=5 时，Q0 有 P3，Q1 有 P1。但 P1 已经在运行了吗？不，t=5 是调度点。
- 修正时间线：
  - t=0: P1(Q0) 运行 4ms -> t=4。P1 降级 Q1。
  - t=1: P2(Q0) 到达。此时 t=4，调度器工作。
  - t=4: 检查队列。Q0 有 P2，Q1 有 P1。优先调度 Q0 的 P2。
  - t=4: P2 运行。P2 需 4ms，Q0 时间片 4ms。P2 在 t=8 完成。
  - t=2: P3 到达。此时 t=2 < t=4，P3 进入 Q0 等待。
  - t=8: Q0 为空。调度 Q1 的 P1。
  - t=8: P1 运行。P1 还需 6ms，Q1 时间片 8ms。P1 运行 6ms -> t=14 完成。
  - t=14: Q0, Q1 为空。调度 Q2 (空)。
  - Wait: P3 去哪了？P3 在 t=2 进入 Q0，但在 t=4 调度时，Q0 有 P2 和 P3。FCFS 还是按到达时间？
  - 重新梳理：
    - t=0: P1(Q0) 进入。运行。
    - t=1: P2(Q0) 到达。P1 还在运行。
    - t=2: P3(Q0) 到达。P1 还在运行。
    - t=4: P1 时间片用完，剩余6ms -> 降级 Q1。
    - t=4: 调度器选择。Q0 中有 P2(到达1), P3(到达2)。按到达顺序，P2 优先。
    - t=4: P2 运行。P2 需 4ms。Q0 时间片 4ms。
    - t=8: P2 完成。
    - t=8: 调度器选择。Q0 中有 P3。Q1 中有 P1。
    - t=8: P3 运行。P3 需 6ms。Q0 时间片 4ms。
    - t=12: P3 时间片用完，剩余 2ms -> 降级 Q1。
    - t=12: 调度器选择。Q0 空。Q1 中有 P1(剩余6), P3(剩余2)。
    - t=12: Q1 时间片 8ms。按什么顺序？通常同级队列按 FCFS 或优先级。假设 Q1 也是 FCFS (P1 先进)。
    - t=12: P1 运行。P1 需 6ms。Q1 时间片 8ms。P1 运行完。
    - t=18: P1 完成。
    - t=18: Q1 中有 P3。
    - t=18: P3 运行。P3 需 2ms。
    - t=20: P3 完成。

Gantt 图： [P1(0-4)] [P2(4-8)] [P3(8-12)] [P1(12-18)] [P3(18-20)]

注意：多级反馈队列的实现细节（如队列内部排序、抢占时机）在不同教材中可能略有差异，但核心思想是：高优先级（短时间片）队列先运行，用不完时间片才降级。

四、常见误区分析

在做作业调度习题时，学生常犯以下错误：

误区 1：混淆“到达时间”与“开始时间”

错误：计算周转时间时，直接用完成时间减去上一个作业的完成时间。
正解：周转时间 = 完成时间 - 该作业的到达时间。如果作业到达很晚，即使它运行很快，其周转时间也可能很长。

误区 2：SJF 的抢占与非抢占混淆

错误：在做 SRTF（最短剩余时间优先）题目时，只在作业完成时才检查是否有新作业到达。
正解：SRTF 是抢占式的。每当有新作业到达，或者当前作业完成时，都要重新比较当前剩余时间与新作业的服务时间。

误区 3：时间片轮转（RR）的最后处理

错误：在 RR 算法中，如果一个作业在最后一个时间片内提前完成，认为它会立即释放 CPU 给下一个作业，且下一个作业的开始时间是当前时间片的结束时间。
正解：如果作业在时间片中间完成，CPU 会立即切换（如果队列不为空），下一个作业的开始时间就是上一个作业的完成时间，而不是等到时间片结束。

误区 4：多级反馈队列的“饥饿”

错误：认为只要设置了多级队列，系统就能完美工作。
正解：如果不引入老化（Aging）机制，源源不断的短作业会一直占据 Q0，导致 Q2 中的长作业永远得不到执行（饥饿）。

五、总结与实战建议

掌握作业调度算法的关键在于：

画图：遇到复杂的题目，一定要画 Gantt 图。
列表：建立“作业-到达-服务-开始-完成-周转-等待”的表格。
代码模拟：通过编写类似上文的 Python 脚本，可以验证你的手算结果，加深对算法动态执行过程的理解。

通过本文对 FCFS、SJF 和 MFQ 的详细拆解，相信你已经对这些经典算法有了更深刻的认识。在实际的操作系统（如 Linux 的 CFS 调度器）中，虽然算法更加复杂，但其核心思想依然离不开这些基础理论。多做练习，多思考不同参数对结果的影响，是掌握本章内容的不二法门。