Question

操作系统导论(3)

Answer 1

上篇文章介绍了OS虚拟化CPU的低层实现方法，这篇文章来介绍虚拟化CPU中的调度策略，即进程切换时到底应该换哪个进程独占CPU？

在设计调度策略之前，我们需要对进程的某些信息做出假设，这有助于简化问题，并且这些假设会在后面一步步消除，最后得到一个能在真实计算机中运行的调度算法。

上述假设看起来是不太现实的，但我们能因此开发出基本的调度策略，并在之上进行改进。

要设计一个优秀的调度策略，调度指标的选取很重要。有如下指标可供选取：

评估调度策略的优劣使用平均周转时间来评价。

顾名思义，先到达的进程可先得到CPU使用权。

如果假设1不满足的话，FIFO的平均周转时间就取决于进程的到来顺序以及其运行时间了。

举个例子：
有进程A、B、C。其中A运行100秒，B与C都运行10秒。如果A、B、C大致同时到达，但A的到达时间快了那么一点点，根据FIFO，OS先选择运行A，那么B与C就必须等待A运行直到完成。此时的平均周转时间

这显然让人沮丧。

上述问题被称为护航效应(convey effect)。一些耗时较少的资源消费者排在重量级的资源消费者之后。

FIFO让进程B、C的“满意度”大打折扣，如何改进FIFO，照顾到它们的情绪呢？

我们去掉假设1，如果先运行上述的B、C，那么平均周转时间为

在平均周转时间这一指标上，SJF比FIFO的效果好得多，并且在假设2满足的情况下，SJF即为最优算法。

如果假设2不满足呢？即进程的到达时间点不一致，此时如果使用SJF仍会存在护航问题，如何改进？我们去掉假设3，即认为进程在运行过程是可以切换的，向SJF添加抢占功能，即可转化为STCF调度策略。

每当新进程到达（就绪状态）时，OS会比较正在CPU运行的进程的剩余时间与新进程的剩余时间比较，选择剩余时间少的运行。就平均周转时间而言，STCF在当前假设下是最优的。

上述调度算法都是针对平均周转时间进行设计的。
如果只考虑响应时间，那么每个进程仅仅只能运行很短的一段时间，然后又切换到另一个进程，这样就保证了每个进程都能照顾到，提高了用户体验。进程运行的一个时间周期被称为时间片， 注意 ，时间片的长度必须是时钟中断周期的倍数，例如假设时钟中断是每10ms中断一次，则时间片可以10ms，20ms等等。

我的理解是时钟中断进行了一个强制性的控制权转让，从进程传给了OS，此时OS可以根据当前的影响因素，例如剩余时间片长度，进程优先级等来决定是否继续运行之前进程或是切换到另一个进程。因此时间片长度与时钟中断的关系是前者是后者的一个影响因素。

RR虽然在交互性上表现上佳，但是它也造成了一些额外的开销，因为频繁的进程切换会占用一定的时间。此时需要使用摊销(amortize)来降低进程切换成本。具体做法是权衡增加时间片的长度，这样系统进行进程切换的次数便减少了，用于进程切换的额外时间也降低了。

虽然RR大大减少了响应时间，但也造成周转时间的增加。更一般地说，一些公平的调度策略例如RR，在小规模时间内将CPU均匀分配到活动进程之间，它们在周转时间这类指标上表现不佳。周转时间与响应时间是一个矛盾的双方。

进程在运行时有可能会进行I/O操作，因此去掉假设4更符合实际情况。如果正在运行的进程A将执行I/O操作，那么OS会进行调度，在进程A执行I/O期间，将CPU分配给其他待执行进程，进程A进入阻塞状态。当I/O完成后，会产生一个外部中断，使OS重获CPU控制权，并且进程A转为就绪状态。OS再决定下个执行程序。

进程的执行时间我们是无法知道的，在实际情况中要求我们根据最近的运行历史来预测未来，从而解决不可预知的问题。

由上文可知设计一个好的调度策略要兼顾以下因素：

针对上述要点，OS专家提出了一个综合性调度算法——多优先级反馈队列算法(Multi-level Feedback Queue)。它由以下部分组成：

给进程分配优先级是一个问题，到底该怎么分配呢？系统中既有长工作又有短工作。MLFQ选择的方式是给初始化后的进程分配最高优先级，并根据进程的运行状况来动态调整优先级。

基本的MLFQ规则如下：

首先一个长工作A到达了系统，OS赋予它最高优先级，长工作在用完若干个时间片后，此时其优先级已经降到最底层的队列。

短工作B进来后，系统同样赋予其最高优先级，它的执行时间比A短，消耗的时间片少，因此它在移入底层队列之前已经执行完毕了。此后A继续运行。上述过程类似于SJF。OS并不知道进程的执行时间，但是通过上述操作使得周转时间得到了降低，同时保证了响应时间。

如果进程存在频繁的I/O操作，那么进程在时间片内通过中断主动放弃CPU，此时它的优先级不变，CPU转而执行其他进程，具体过程在后续I/O的控制方式中会详细阐述。这样就保证了交互性程序的响应时间很短。

但上述MLFQ的规则还存在一些问题：

针对上述问题，MLFQ又新增和改进了如下规则：

MLFQ存在很多参数，例如每层队列的时间片大小，提升所有进程优先级的间隔时间，优先级队列的数量。这些参数调整都没有固定的值，只能依赖于设计者的实践和调优经验。