多个进程同时运行时，需要考虑如何对他们进行调度。调度器（scheduler）即是实现这套逻辑的 OS 组件。

对于调度系统，

1. 需要考虑的 维度 是 效率 和 公平
2. 如何体现上述的维度，则需要设计 度量方式（metrics），用来衡量不同的算法在不同情况下的表现

常见的 度量方式 有几种：

• turnaround time，即任务开始排队到完成的平均时间。这个指标越低则越高效
• response time，即任务开始排队到被执行的平均时间。这个指标越低则（往往）越公平

这其中会涉及到一个问题，调度过程是 抢占式的（preemptive） 还是 非抢占式的（non-preemptive）。抢占式的，表示调度器可以暂停一个任务（process）的运行，而切换到另外一个任务。现代操作系统是抢占式的。抢占式意味着 CPU 运行需要有固定的时间片（time slice），即每次运行一个进程至少一个时间片长度的时间。

有几种简单的调度算法。

调度算法

First In, First Out (FIFO)

这种算法实现是不考虑抢占的。显然很容易有 bad case 影响整体的性能。

Shortest Job First (SJF)

这种算法能实现最优的效率。但是它是非抢占式的，如果新任务进入的时间点不合适，会影响其性能。

Shortest Time-to-Completion First (STCF)

总是运行当前任务列表中，最快可以完成的任务。这种算法可以说是 SJF 的抢占式版本。效率是最优的，但是是非常不公平的。

Round Robin

轮转执行各任务。这种算法是平均响应时间（看上述 response time 定义）最短的，是最公平的，但相对地 turnaround time 不是最优。

而且需要考虑 频繁的上下文切换（context switch）带来的性能损失。不仅包含存取寄存器的开销，还有 CPU 缓存、页表缓存、分支判断上的损耗。

研究方法

这一章在研究方法上是个非常好的范例。

1. 对于调度系统，需要考虑的 维度 是 效率 和 公平
2. 如何体现上述的维度，则需要设计 度量方式（metrics）。比如文中的 turnaround time 及 response time
3. 为了让问题更容易解决，在一开始做一些 简化的假设，再将假设移除。比如文中一开始做的假设是：
   1. Each job runs for the same amount of time.
   2. All jobs arrive at the same time.
   3. Once started, each job runs to completion.
   4. All jobs only use the CPU (i.e., they perform no I/O)
   5. The run-time of each job is known.

虽然书中并不是按我上面这样 top-bottom 行文的，而是 bottom-top，但是思考这类问题的思路是一致的。