前言
上篇文章介绍了OS虚拟化CPU的低层实现方法，这篇文章来介绍虚拟化CPU中的调度策略，即进程切换时到底应该换哪个进程独占CPU？
工作负载假设
在设计调度策略之前，我们需要对进程的某些信息做出假设，这有助于简化问题，并且这些假设会在后面一步步消除，最后得到一个能在真实计算机中运行的调度算法。
- 1.每一个进程运行相同的时间
- 2.所有的进程同时到达
- 3.一旦进程开始运行，则其一直运行到结束。
- 4.所有的进程只使用CPU而不进行I/O操作。
- 5.每个进程的运行时间是已知的。
上述假设看起来是不太现实的，但我们能因此开发出基本的调度策略，并在之上进行改进。
调度指标
要设计一个优秀的调度策略，调度指标的选取很重要。有如下指标可供选取：
- 周转时间(turnaround time)
定义为进程的完成时间减去进程第一次可供CPU使用的时间（可认为是进程的到达时间）。由假设2可知，可设到达时间为0，则
周转时间T=进程的完成时间
评估调度策略的优劣使用平均周转时间来评价。
- 响应时间
对于早期的一些批处理系统，通常使用周转时间来进行设计调度策略，因为这类系统对用户与计算机间的交互性要求不高，所以并没考虑到响应时间。但自从分时系统出现以后，响应时间也成为了一个新的度量指标。
先进先出（FIFO）
顾名思义，先到达的进程可先得到CPU使用权。
如果假设1不满足的话，FIFO的平均周转时间就取决于进程的到来顺序以及其运行时间了。
举个例子：
有进程A、B、C。其中A运行100秒，B与C都运行10秒。如果A、B、C大致同时到达，但A的到达时间快了那么一点点，根据FIFO，OS先选择运行A，那么B与C就必须等待A运行直到完成。此时的平均周转时间
这显然让人沮丧。
上述问题被称为护航效应(convey effect)。一些耗时较少的资源消费者排在重量级的资源消费者之后。
最短任务优先(SJF)
FIFO让进程B、C的“满意度”大打折扣，如何改进FIFO，照顾到它们的情绪呢？
我们去掉假设1，如果先运行上述的B、C，那么平均周转时间为
在平均周转时间这一指标上，SJF比FIFO的效果好得多，并且在假设2满足的情况下，SJF即为最优算法。
抢占式最短任务优先（STCF）
如果假设2不满足呢？即进程的到达时间点不一致，此时如果使用SJF仍会存在护航问题，如何改进？我们去掉假设3，即认为进程在运行过程是可以切换的，向SJF添加抢占功能，即可转化为STCF调度策略。
每当新进程到达（就绪状态）时，OS会比较正在CPU运行的进程的剩余时间与新进程的剩余时间比较，选择剩余时间少的运行。就平均周转时间而言，STCF在当前假设下是最优的。
轮转（RR）
上述调度算法都是针对平均周转时间进行设计的。
如果只考虑响应时间，那么每个进程仅仅只能运行很短的一段时间，然后又切换到另一个进程，这样就保证了每个进程都能照顾到，提高了用户体验。进程运行的一个时间周期被称为时间片，注意，时间片的长度必须是时钟中断周期的倍数，例如假设时钟中断是每10ms中断一次，则时间片可以10ms，20ms等等。
我的理解是时钟中断进行了一个强制性的控制权转让，从进程传给了OS，此时OS可以根据当前的影响因素，例如剩余时间片长度，进程优先级等来决定是否继续运行之前进程或是切换到另一个进程。因此时间片长度与时钟中断的关系是前者是后者的一个影响因素。
RR虽然在交互性上表现上佳，但是它也造成了一些额外的开销，因为频繁的进程切换会占用一定的时间。此时需要使用摊销(amortize)来降低进程切换成本。具体做法是权衡增加时间片的长度，这样系统进行进程切换的次数便减少了，用于进程切换的额外时间也降低了。
虽然RR大大减少了响应时间，但也造成周转时间的增加。更一般地说，一些公平的调度策略例如RR，在小规模时间内将CPU均匀分配到活动进程之间，它们在周转时间这类指标上表现不佳。周转时间与响应时间是一个矛盾的双方。
去掉假设4
进程在运行时有可能会进行I/O操作，因此去掉假设4更符合实际情况。如果正在运行的进程A将执行I/O操作，那么OS会进行调度，在进程A执行I/O期间，将CPU分配给其他待执行进程，进程A进入阻塞状态。当I/O完成后，会产生一个外部中断，使OS重获CPU控制权，并且进程A转为就绪状态。OS再决定下个执行程序。
去掉假设5
进程的执行时间我们是无法知道的，在实际情况中要求我们根据最近的运行历史来预测未来，从而解决不可预知的问题。
多优先级反馈队列
由上文可知设计一个好的调度策略要兼顾以下因素：
- ① 响应时间
- ② 周转时间
- ③ 进程的运行时间未知
- ④ 进程可能存在I/O操作
- ⑤ 进程到达时间不一致（进程转为就绪态的时间未知）
针对上述要点，OS专家提出了一个综合性调度算法——多优先级反馈队列算法(Multi-level Feedback Queue)。它由以下部分组成：
给进程分配优先级是一个问题，到底该怎么分配呢？系统中既有长工作又有短工作。MLFQ选择的方式是给初始化后的进程分配最高优先级，并根据进程的运行状况来动态调整优先级。
基本的MLFQ规则如下：
- A、B进入系统时均被赋予最高优先级。
- 如果A的优先级>B的优先级，那么OS将CPU分配给A。
- 如果A的优先级==B的优先级，那么OS将使用RR算法使A和B都能得到CPU。
- A、B用完整个时间片后，降低其优先级（移入下一层优先级队列）
- A、B在其时间片内主动释放CPU，例如通过I/O中断，则A、B的优先级不变。
应用场景
单个长工作
首先一个长工作A到达了系统，OS赋予它最高优先级，长工作在用完若干个时间片后，此时其优先级已经降到最底层的队列。
进来一个短工作
短工作B进来后，系统同样赋予其最高优先级，它的执行时间比A短，消耗的时间片少，因此它在移入底层队列之前已经执行完毕了。此后A继续运行。上述过程类似于SJF。OS并不知道进程的执行时间，但是通过上述操作使得周转时间得到了降低，同时保证了响应时间。
工作中包含I/O操作
如果进程存在频繁的I/O操作，那么进程在时间片内通过中断主动放弃CPU，此时它的优先级不变，CPU转而执行其他进程，具体过程在后续I/O的控制方式中会详细阐述。这样就保证了交互性程序的响应时间很短。
存在问题
但上述MLFQ的规则还存在一些问题：
如果系统中存在很多的交互型工作，那么CPU密集型工作就会存在“饥饿”现象，即长时间得不到CPU。甚至于永远得不到。
MLFQ的最后一条规则存在漏洞，如果用户程序主动通过系统调用在时间片消耗完前就主动放弃CPU，以此来达到长期占用CPU的目的。
如果工作即有长时间占用CPU的部分，又有频繁交互的部分，并且频繁交互的部分位于长期CPU工作之后，那么在上述规则下它的优先级就受限于长期CPU工作的那部分，导致得不到交互型程序应有的待遇。
改进
针对上述问题，MLFQ又新增和改进了如下规则：
经过一段时间S，将系统中所有工作重新加入最高优先级队列。
（缓解了第1个问题和第3个问题）针对基本的MLFQ的规则，最后两条规则重写如下：
如果进程用完了在某一层优先级队列分配的时间配额，那么就会被移入下层优先级队列，无论中间主动放弃了多少次CPU。
参数设置
MLFQ存在很多参数，例如每层队列的时间片大小，提升所有进程优先级的间隔时间，优先级队列的数量。这些参数调整都没有固定的值，只能依赖于设计者的实践和调优经验。
