CPU Virtualization-Scheduling(Introduction)

上节介绍的是low-level的mechanisms，比如线程如何切换。本节主要介绍的是Scheduling和一些scheduling policies，线程调度问题。这些是属于high-level policies。

1. Workload Assumption

在讨论本节内容之前，我们先对进程做一些简化与假设：

1. 每个进程运行相同的时间
2. 所有任务在同一时间到达
3. 一旦任务开启，将会一直运行至结束
4. 所有任务只会用到CPU（将不会使用I/O等）
5. 每个任务的运行时间是已知的

2. Scheduling Metrics

我们需要定义一个衡量调度策略的方法，在这里，我们只定义一个方法，$T_{turnaround}$，用任务完成的时间减去任务到达的时间：$$T_{turnaround}=T_{completion}-T_{arrival}$$

因为现在假设所有任务在同一时间到达，所以$T_{turnaround} = T_{completion}$。需要注意的是，$T_{turnaround}$是用来衡量performance，另一个需要关注的点是fairness公平性，实际上，这两个指标往往是相斥的。

3. FIFO/FCFS

First In, First Out或者First Come, First Serve. 先到先处理原则，简单易于实现。下面的例子，任务A，B，C依次进入，但是根据假设，它们的到达时间可以认为是相同的。所以在这里，平均$$T_{turnaround}=\frac{(10-0)+(20-0)+(30-0)}{3}=20$$。


现在我们使假设1不成立，恰好有一个进程运行时间比其它进程久且第一个运行，如下图所示：



此时，平均$T_{turnaround}=\frac{(100-0)+(110-0)+(120-0)}{3}=110$，所以在这种情况下，A这个较长运行时间的进程将使得整体$T_{turnaround}$表现变差，文中举了个例子，好比是在超市结账的时候，在我们前面有个人有很多货品需要结账，这样就会使后面的人等待很长时间。

4. Shortest Job First(SJF)

AKA最短时间优先原则，在这种规则下，我们按照进程运行时间依次运行，运行时间越短的越先运行。用上面的例子来分析：



当A、B、C同时进入，因为B、C运行时间较短，在这种情况下先运行B、C，最后运行A，所以它的平均$T_{turnaround}=\frac{(10-0)+(20-0)+(120-0)}{3}=50$。

在我们的假设中，所有进程/任务都是在同一时间到达，但是很明显这是很理想化的，所以我们可能会遇到这样的问题：当任务A先到达时，B、C随之而来，假设它们的$T_{completion}=10$，这样的话，该种情况下的平均$T_{turnaround}=\frac{(100-0)+(110-10)+(120-10)}{3}=103.33$。注意：过去，我们会使用一些非抢占式的调度，这意味着系统在决定是否运行一个新的进程/任务时，会把当前任务执行完毕，这也是为什么在这里B、C不会在进入调度后立马执行。但是，现在我们会应用抢占式调度，这也就需要用到上一节上下文切换还/Context Switch的内容。

5. Shortest Time-to-Completion First(STCF)

AKA最短剩余时间优先原则，SJF是属于一种非抢占式的调度方式，为了解决上述问题，STCF被提出来，在STCF中，每进来一个任务，该调度方法会调度当前剩余未完成的任务中剩余时间最少的任务，在上述例子中，任务B、C会抢占A，如下图所示，平均$T_{turnaround}=\frac{(20-10)+(30-10)+(120-0)}{3}=50$。

6. A New Metric: Response Time

如果假设4、5成立，所有任务时长都已知且只使用CPU，$T_{turnaround}$的衡量方法下的STCF表现较好，但是现在我们需要进行一些交互式的操作，所以一种新的衡量方式出现，Response time/反应时间。它的定义为任务第一次被调度的时间减去任务到达的时间：$$T_{response}=T_{firstrun}-T_{arrival}$$。以STCF中的图为例，A、B、C的反应时间分别为0、0、10，平均为3.33。下面会介绍在反应时间上表现较好的调度方法。

7. Round Robin(轮询)

在RR调度方法中，我们不会把某个任务一直运行到结束，而是分配给它一个时间片（time slice/scheduling quantum），当使用完该时间片后，我们会切换到另一个任务/进程，用下图来举个例子：



在该例中，时间片的长度为一个单位时间1，任务A、B、C的$T_{response}=\frac{0-0)+(1-0)+(2-0)}{3}=1$。再看看如果用的是SJF：



在SJF中，任务A、B、C的$T_{response}=\frac{0-0)+(5-0)+(10-0)}{3}=5$。很明显，在Response time的衡量标准下，RR的表现更好，但同时也能发现，时间片的大小对RR也是至关重要的，当时间片越小时，反应时间表现越好，但同时切换任务时上下文切换会消耗很多性能，所以我们需要合理设置时间片的长度来分摊这一消耗。值得注意的是，上下文切换不仅仅是操作系统保存和恢复一些寄存器，程序在运行时，在CPU的高速缓存、TLB、分支预测器和一些其他硬件上也建立了大量状态。所以不同的调度算法会在周转时间和响应时间做不同的平衡。下面一小节要介绍在考虑IO操作的情况下的调度方法。

8. 结合I/O

当前进程需要访问I/O的时候，它会被阻塞直到I/O操作完成，如果这一操作需要访问磁盘，当前进程可能会被阻塞几毫秒或更长的时间，这时候当前进程并没有用到CPU，所以这时我们可以调度其他的进程。文中举了这样一个例子：两个任务A、B，且都需要使用50ms的CPU，但A每10ms会发起一次I/O操作，假设每次I/O操作耗时10ms，而B任务只是使用50ms的CPU。在这里如果使用STCF，按照之前的调度规则，我们可能会把A分成5个子任务，但总体还是两个任务运行，如下图所示：



这样的调度使得CPU资源没有得到充分利用，我们可以把A的5个子任务当成5个独立的任务，当一个A子任务完成调度，只剩下B任务，当后面的A子任务进来时，它将抢占当前运行的B，这样可以利用I/O过程中的CPU空闲期，如下图所示：

9. No More Oracle

前面介绍了一些基本的IO操作情况下的调度，还有一点就是我们通常不知道进程/任务的运行时间，后面将介绍这个问题。