操作系统 3：CPU 调度

操作系统按照一定的策略从就绪进程中选择一个进程，将 CPU 的过程交给该进程的过程，即是 CPU 的调度。调度的资源是 CPU 的使用权即 CPU 的时间片。进程和线程在此时视为一种事物（都称「进程」）。

调度

为什么要进行调度

尽管看上去只是「一瞬间」的事情，但事实上切换进程是一个复杂的过程：

• 保存处理器上下文，包括 PC 和其他寄存器。

• 更新 PCB 信息。将其移入相应的队列，如就绪、阻塞。

• 选择另一个进程执行，更新它的 PCB。

• 更新内存管理的数据结构（Cache、TLB）

• 恢复处理器上下文。

进程切换的开销有直接和间接的开销两部分。直接开销如寄存器的保存和恢复、虚拟地址空间的切换；间接开销有 Cache 的刷新、TLB 的刷新等。因此，使用一个公平、合理、高效的调度策略，将能显著地影响一个操作系统的性能。

调度的准则

公平、高效：合理地分配 CPU 使得 CPU 尽可能地忙，从而来提高 CPU 的利用率。

• 吞吐量：单位时间内提交的任务量。

• 周转时间：从任务提交到任务结束的时间。\(T_\text{任务完成}-T_\text{任务到达就绪队列}\)。

• 等待时间：任务在就绪队列中等待的时间总和。

• 响应时间：从任务提交到首次运行的时间。\(T_\text{任务首次运行}-T_\text{任务到达就绪队列}\)。

这些指标并不是全部越短越好——它们之间甚至是矛盾的。比如，如果想让响应时间尽可能地短，就应该让前台任务的优先级高，但这样会造成后台任务得不到 CPU；又比如，想让吞吐量大，就要用更大的时间片，但时间片大意味着更长的响应时间。协调多个目标是操作系统之所以复杂的一个重要原因，也是复杂操作系统的一个特点。

调度算法

现在有下面的任务，完成它们所需要的 CPU 时间亦已经列出：

在时刻 0，任务 1—5 按顺序到达了就绪队列。

先到先服务（FCFS）

按任务到达就绪队列的顺序进行调度，即「先做完 1，再做完 2，……」。

计算得到：

• 平均等待时间 = 28 ms，平均响应时间 = 28 ms

• 平均周转时间 = 40.2 ms

这是一种简单但公平的调度策略，但它不适合交互式的应用。

最短作业优先调度（SJF）

每次都取 CPU 区间长度最小的那个任务优先调度。

计算得到：

• 平均等待时间 = 平均响应时间 = 13 ms

• 平均周转时间 = 25.2 ms

事实上，对于同时到达的作业，在所有调度算法中，SJF 是平均等待时间最小的。这在数学上称为 排序不等式。在生活中我们也经常能看到这种方法的应用。

最短剩余作业优先调度（SRJF）

是 SJF 的可抢占版本。在这个语境下，任务到来有先后。例如：

实时检查 现在 队列中其他任务的 CPU 时间，然后挑选一个时间最短的调度，保证正在执行的那个任务的时间是最短的。调度结果为：

事实上，我们不可能在任务开始前就知道任务所要用的时间，因此需要进行预测。一般使用指数平均法进行任务时间的预测。

轮询调度算法（RR）

按时间片轮转调度——我不管你要执行多长时间，到点了你必须走。当时间片为 10 ms 时，前面的例子调度结果为：

计算可知：

• 平均等待时间 = 23 ms

• 平均响应时间 = 16.6 ms

• 平均周转时间 = 35.2 ms

• 上下文切换：7 次

优点：定时有响应，响应时间短；缺点：上下文切换次数多，带来额外开销。

多级反馈队列（MFQS）

按照任务的优先级分为多个队列，每次从优先级最高的队列选择任务。优先级由任务的 CPU 时间决定，允许任务在队列间移动：

• 使用太多 CPU 时间的任务会被放置在低优先级的队列。

• 在低优先级队列停留过久的任务会被上移。

此为最为通用但复杂的 CPU 调度算法。

彩票算法（Lottery）

以进程需要的 CPU 时间为比例向它们发行「彩票」，然后调度器随机选择彩票中奖号码，加载中奖进程并运行它。