1. 简介
调度（Scheduling）是指在计算系统中决定任务或进程何时执行以及执行顺序的机制。调度是现代计算系统中至关重要的组成部分，它帮助我们高效、合理地管理可用资源，例如 CPU 时间和内存。
在本文中，我们将重点介绍两个用于评估调度算法性能的重要指标：
- 完成时间（Completion Time）
- 响应时间（Response Time）
这两个指标从不同角度反映了系统的执行效率和响应能力，是设计和优化调度算法时的重要参考。
2. 完成时间
完成时间（Completion Time）指的是一个进程完成其全部执行并正常终止的时刻。
它用于衡量系统的整体执行效率。完成时间越短，说明系统处理任务越快，整体性能越高。
一些以完成时间为优化目标的调度算法包括：
- Earliest Deadline First (EDF)
- Rate Monotonic Scheduling (RMS)
- Least Laxity First (LLF)
完成时间的计算公式如下：
$$ Completion Time (CT) = Arrival Time (AT) + Execution Time (ET) + Waiting Time (WT) $$
其中：
- **Arrival Time (AT)**：任务到达系统并准备执行的时间
- **Execution Time (ET)**：任务从开始执行到完成所需的时间
- **Waiting Time (WT)**：任务在执行前等待调度的时间
2.1 影响完成时间的因素
- 每个任务所需的执行时间
- 系统中待执行任务的数量
- 任务的优先级设置
3. 响应时间
响应时间（Response Time）指的是任务被提交后，系统首次开始执行该任务的时间差。
它衡量系统的响应速度。响应时间越短，表示系统越快响应用户请求，用户体验更好。
一些以响应时间为优化目标的调度算法包括：
- Round Robin（轮转法）
- First-Come First-Served（先来先服务）
响应时间的计算公式如下：
$$ Response Time = Time it Started Executing - Arrival Time $$
3.1 影响响应时间的因素
- 每个任务的执行时间
- 系统中任务的数量
- 任务的优先级
- 系统资源的可用性
4. 示例说明
我们来看一个具体的例子，帮助理解这两个指标的计算方式。
假设有三个任务 A、B 和 C，它们的执行时间和到达时间如下：
| 任务 | 执行时间 | 到达时间 |
|---|---|---|
| A | 2 | 0 |
| B | 3 | 1 |
| C | 1 | 2 |
我们使用 First-Come First-Served (FCFS) 调度算法进行调度。
执行过程
- T=0：任务 A 到达并立即开始执行（等待时间为 0）
- T=1：任务 B 到达，A 正在执行，B 进入等待队列
- T=2：任务 A 完成执行，任务 C 到达，B 开始执行（B 等待时间 = 1）
- T=5：任务 B 完成执行，任务 C 开始执行（C 等待时间 = 3）
- T=6：任务 C 完成执行
完成时间计算
$$ Completion Time = AT + ET + WT $$
- A：0 + 2 + 0 = 2
- B：1 + 3 + 1 = 5
- C：2 + 1 + 3 = 6
响应时间计算
$$ Response Time = Start Time - Arrival Time $$
- A：0 - 0 = 0
- B：2 - 1 = 1
- C：5 - 2 = 3
5. 完成时间 vs. 响应时间
| 完成时间 | 响应时间 |
|---|---|
| 表示任务完成执行的时刻 | 表示任务开始执行的时刻 |
| 衡量任务整体执行效率 | 衡量系统响应速度 |
| 包含执行时间和等待时间 | 仅包含开始前的等待时间 |
| 计算公式：CT = AT + ET + WT | 计算公式：RT = Start Time - AT |
✅ 完成时间 更关注任务执行的总耗时
❌ 响应时间 更关注用户首次感知到的反馈速度
6. 总结
在调度算法设计中，完成时间 和 响应时间 是两个核心性能指标：
- 完成时间 反映任务执行的整体效率
- 响应时间 反映系统的响应能力
它们各自侧重不同场景：
- 实时系统中可能更关注完成时间（如航空控制系统）
- 用户交互系统中更关注响应时间（如 Web 服务）
在设计调度算法时，应根据具体需求权衡这两个指标，确保系统性能达到最优。