进程调度——操作系统概念

进程调度是操作系统决定下一个由哪个就绪进程获得 CPU 的过程。通俗地说，它就是规定“现在谁运行、谁等待”的规则。这个规则会影响等待时间、响应时间、公平性以及整体吞吐量。

进程调度之所以重要，是因为同一组进程在 FCFS、SJF 或时间片轮转下，完成顺序可能完全不同。只要理解这一点，大多数教材中的例题都会更容易看懂。

操作系统中的进程调度是什么意思

在常见的操作系统模型中，进程会在就绪、运行、等待等状态之间切换。调度器会在所有就绪进程中做出选择。

这也是为什么进程调度常常被称为 CPU 调度。它不会创造新的工作，只是决定等待中的任务按什么顺序获得 CPU 服务。

在现代系统中，内核通常会直接调度线程，但“进程调度”仍然是教学中最常用的经典术语。

调度器想要优化什么

调度器通常要在多个目标之间取得平衡：

• 较低的等待时间
• 交互式任务的快速响应
• 良好的吞吐量
• 公平性
• 可预测的行为

这些目标之间可能会冲突。某种策略在一个简化例子中降低了平均等待时间，但在实际使用中仍可能让人觉得不公平；而一种公平的时间共享策略，也可能会延迟短任务的完成。

抢占式调度与非抢占式调度

非抢占式调度器会让正在运行的进程一直占用 CPU，直到它完成当前 CPU burst 或发生阻塞。先来先服务就是标准例子。

抢占式调度器可以中断当前正在运行的进程，把 CPU 分配给另一个进程。时间片轮转和许多优先级调度都属于这种情况。

这个区别很重要，因为当系统允许抢占长时间运行的任务时，响应时间通常会更好。

常见的进程调度算法

先来先服务

先来先服务，也就是 FCFS，会按照到达顺序运行进程。它容易理解，实现也简单，但如果队首是一个长任务，后面的所有短任务都可能被迫等待很久。

最短作业优先

最短作业优先，也就是 SJF，会优先选择 CPU burst 最短的进程。在一个能够准确知道运行时间的简化场景中，它可以降低平均等待时间。但在真实系统里，这个运行时间通常只能估计。

时间片轮转

时间片轮转会给每个就绪进程分配一个较短的时间片，称为 quantum。如果进程在这个时间片内没有完成，它就会回到就绪队列。这通常能提升交互式负载下的公平性和响应性。

优先级调度

优先级调度会先运行优先级最高的就绪进程。当某些任务比其他任务更重要时，它会很有用；但如果低优先级任务等待太久，就可能出现饥饿问题。

一个带等待时间的完整例子

假设有三个进程都在时间 $0$ 到达，并且每个进程只需要 CPU 时间：

• $P_1$: $6\ \mathrm{ms}$
• $P_2$: $2\ \mathrm{ms}$
• $P_3$: $1\ \mathrm{ms}$

假设：

• 只有一个 CPU
• 没有 I/O 阻塞
• 忽略上下文切换开销

在这些条件下，等待时间指的是进程运行之前在就绪队列中停留的时间。周转时间为

$$\text{turnaround time} = \text{completion time} - \text{arrival time}$$

FCFS

如果使用 FCFS，顺序为 $P_1 \rightarrow P_2 \rightarrow P_3$。

时间线：

$$0 \to 6: P_1,\qquad 6 \to 8: P_2,\qquad 8 \to 9: P_3$$

等待时间：

• $P_1 = 0$
• $P_2 = 6$
• $P_3 = 8$

平均等待时间：

$$\frac{0 + 6 + 8}{3} = \frac{14}{3}\ \mathrm{ms}$$

SJF

如果使用非抢占式 SJF，顺序为 $P_3 \rightarrow P_2 \rightarrow P_1$。

时间线：

$$0 \to 1: P_3,\qquad 1 \to 3: P_2,\qquad 3 \to 9: P_1$$

等待时间：

• $P_3 = 0$
• $P_2 = 1$
• $P_1 = 3$

平均等待时间：

$$\frac{0 + 1 + 3}{3} = \frac{4}{3}\ \mathrm{ms}$$

这个例子展示了最核心的直觉。工作负载没有变化，但规则变了，结果也就变了。在这里，SJF 的平均等待时间更低，因为短任务不会被长任务挡在后面。

但这并不意味着 SJF 在现实中总是最好的选择。它只说明，在这个例子的假设条件下，调度顺序会极大影响结果。

需要记住的直觉

可以把进程调度理解为 CPU 的排队规则。就绪队列里可能还是同样的任务，但服务这个队列的规则不同，用户感受到的结果也会不同。

如果你最关心第一次响应要快，可能会更偏好频繁共享 CPU 的策略。如果你最关心尽快完成许多短任务，可能会更偏好优先短 burst 的策略。如果你关心严格的时间要求，那就可能需要另一种调度器。

调度题中的常见错误

认为某一种策略在任何情况下都是最优的

不存在适用于所有工作负载的唯一赢家。某种策略在平均等待时间上看起来很优秀，但在公平性或截止期限方面仍可能表现很差。

混淆等待时间、响应时间和周转时间

这些指标彼此相关，但并不相同。尤其是，响应时间通常指第一次获得 CPU 服务或第一次产生可见响应所需的时间，而周转时间衡量的是任务从到达到完成的整个过程。

忽略公式成立的前提条件

指标只有在给定假设下才有意义。如果题目包含 I/O 阻塞、不同的到达时间或上下文切换开销，那么时间线和结果都会改变。

忘记区分策略是否可抢占

SJF 和最短剩余时间优先并不是同一种规则。优先级调度在高优先级任务能否打断当前任务时，行为也会不同。

进程调度用在哪里

只要操作系统需要共享 CPU 时间，进程调度就很重要：

• 需要应用响应迅速的桌面和移动系统
• 处理大量请求的服务器
• 关注吞吐量的批处理系统
• 关注时间保证的实时系统

真实调度器通常比教材中的版本复杂得多，但其中的权衡关系依然相同。

试着自己改一个版本

你可以把例子改成让 $P_2$ 更晚到达，或者把 FCFS 换成时间片为 $2\ \mathrm{ms}$ 的时间片轮转，看看等待模式会怎样变化。如果你手算完还想再多做一步，可以把你自己的版本放进 GPAI Solver，对比你预测的时间线和计算结果。