《Operating Systems: Three Easy Pieces》学习笔记(五) 进程调度：介绍

假设

为了方便概念的描述，对操作系统中运行的进程（有时也叫工作任务）做出如下的假设：

工作负载

1. 每一个工作运行相同的时间。
2. 所有的工作同时到达。
3. 一旦开始，每个工作保持运行直到完成。
4. 所有的工作只是用 CPU（即它们不执行 IO 操作）。
5. 每个工作的运行时间是已知的。

调度指标

任务的周转时间定义为任务完成时间减去任务到达系统的时间。更正式的周转时间定义 T_{周转时间} 是：

T_{周转时间} = T_{完成时间}−T_{到达时间}

因为我们假设所有的任务在同一时间到达，那么 T_{到达时间} = 0，因此 T_{周转时间}= T_{完成时间}。随着我们放宽上述假设，这个情况将改变

先进先出（FIFO）

先进先出（First In First Out 或 FIFO）调度，有时候也称为先到先服务（First Come First Served 或 FCFS）。

假设有三个几乎同时到达的进程，到达顺序为 A,B,C，B 和 C 执行 10s，A 有执行 10s 和执行 100s 的情况，调度结果如下图：

两者的平均周转周期

• 左：(10 + 20 + 30)/3 = 20

• 右：(100 + 110 + 120)/3 = 110

这个问题通常被称为护航效应（convoy effect），一些耗时较少的潜在资源消费者被排在重量级的资源消费者之后。

最短任务优先（SJF）

最短任务优先（Shortest Job First，SJF）：先运行最短的任务，然后是次短的任务，如此下去

左图是在上一节条件下使用 SJF 策略时的表现，右图是在到达时间间隔 10s 条件下使用 SJF 策略时的表现：

两者的平均周转周期

• 左：(10 + 20 + 120)/3 = 50

• 右：(100+(110−10)+(120−10))/3 = 103.33

从图中可以看出，当 ABC 几乎同时到达时，SJF 相较于 FIFO 有较好的表现，但当 B 和 C 在 A 之后不久到达，由于 SJF 无法抢占，它们仍然被迫等到 A 完成，从而遭遇同样的护航问题。

最短完成时间优先(STCF)

我们放宽第一节提出的假设条件 3（工作必须保持运行直到完成），也就是允许抢占

向 SJF 添加抢占，称为最短完成时间优先（Shortest Time-to-Completion First，STCF）或抢占式最短作业优先（Preemptive Shortest Job First ，PSJF）调度程序

每当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作:

平均周转周期为：

(120 + 10 + 20)/3 = 50

新度量指标：响应时间

响应时间定义为从任务到达系统到首次运行的时间。更正式的定义是： T_{响应时间} = T_{首次运行} − T_{到达时间}

用户将会坐在终端前面，同时也要求系统的交互性和响应性好，所以响应时间是有意义的

例如，如果我们有上面的调度（A 在时间 0 到达，B 和 C 在时间 10 达到），每个作业的响应时间如下：作业 A 为 0，B 为 0，C 为 10（平均：3.33），STCF 和相关方法在响应时间上并不是很好，对用户来说，打开 C 软件后可能要 10s 后才会有响应

时间片轮转

轮转（Round-Robin，RR）调度：在一个时间片（time slice，有时称为调度量子，scheduling quantum）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务完成。因此，RR 有时被称为时间切片（time-slicing）。

请注意，时间片长度必须是时钟中断周期的倍数。因此，如果时钟中断是每 10ms 中断一次，则时间片可以是 10ms、20ms 或 10ms 的任何其他倍数。

来看一个例子：假设 3 个任务 A、B 和 C 在系统中同时到达，并且它们都希望运行 5s。

平均响应时间：

• SJF：(0 + 5 + 10)/ 3 = 5

• RR：(0 + 1 + 2)/3 = 1

SJF 调度程序必须运行完当前任务才可运行下一个任务。相比之下，1s 时间片的 RR 可以快速地循环工作

时间片长度

时间片长度对于 RR 是至关重要的。时间片长度越短，RR 在响应时间上表现越好。然而，时间片太短是有问题的：突然上下文切换的成本将影响整体性能。因此，系统设计者需要权衡时间片的长度，使其足够长，以便摊销（amortize）上下文切换成本，而又不会使系统不及时响应

请注意，上下文切换的成本不仅仅来自保存和恢复少量寄存器的操作系统操作。程序运行时，它们在CPU 高速缓存、TLB、分支预测器和其他片上硬件中建立了大量的状态。切换到另一个工作会导致此状态被刷新，且与当前运行的作业相关的新状态被引入，这可能导致显著的性能成本。

结合 I/O

首先，我们将放宽假设 4：所有程序都不执行 I/O。

一种常见的方法是将 A 的每个 10ms 的子工作视为一项独立的工作。因此，当系统启动时，它的选择是调度 10ms 的 A，还是 50ms 的 B。对于 最短完成时间优先(STCF)，选择是明确的：选择较短的一个，在这种情况下是 A。然后，A 的工作已完成，只剩下 B，并开始运行。然后提交 A 的一个新子工作，它抢占 B 并运行 10ms。这样做可以实现重叠（overlap），一个进程在等待另一个进程的 I/O 完成时使用 CPU，系统因此得到更好的利用

小结

我们开发了两种调度程序。

• 第一种类型（SJF、STCF）优化周转时间，但对响应时间不利。

• 第二种类型（RR）优化响应时间，但对周转时间不利。

作业

以后再做

参考

• Operating Systems: Three Easy Pieces 中文版