《操作系统导论》三、进程调度

7-进程调度：介绍

关键问题：如何开发调度策略

我们该如何开发一个考虑调度策略的基本框架？什么是关键假设？哪些指标非常重要？哪些基本方法已经在早期的系统中使用？

• 工作负载

• 调度指标：
  周转时间：定义为任务完成时间减去任务到达系统的时间(是一个性能指标)。
  

  公平
  性能和公平在调度系统中往往是矛盾的。
  响应时间

下面的分析基于以下假设，然后依次放开相关假设：
1、每一个工作运行相同的时间。
2、所有的工作同时到达。
3、一旦开始，每个工作保持运行直到完成。
4、所有的工作只是用CPU(即它们不执行IO操作)。
5、每个工作的运行时间是已知的。

先进先出(FIFO)

现在假设(T到达时间 = 0)，3个工作A、B、C，假设同时到达;
1、每个工作运行时间10s，那么这些工作的平均周期时间为：

A在10s时完成，B在20s时，C在30s时。因此，平均周转时间为(10+20+30)/3 = 20s

2、假设A运行100s，B和C运行10s

系统的平均周转时间为：(100+110+120)/3 = 110s

提示：SJF原则

最短任务优先代表一个总体调度原则，可以应用于所有系统，只要其中平均客户(或在我们案例中的任务)周转时间很重要。

最短任务优先(SJF)

先运行最短的任务，然后是次短的任务，如此下去。

上面的例子采用SJF作为策略，则平均周转时间为(10+20+120)/3 = 50s
事实上，考虑到所有工作同时到达的假设，我们可以证明SJF确实是一个最优(optimal)调度算法。

补充：抢占式调度程序

在过去的批处理计算中，开发了一些非抢占式(non-preemptive)调度程序。这样的系统会将每项工作做完，再考虑是否运行新工作。
几乎所有现代化的调度程序都是抢占式的，非常愿意停止一个进程以运行另一个进程。这意味着调度程序采用了我们之前学习的机制。特别是调度程序可以进行上下文切换，临时停止一个运行进程，并恢复(或启动)另一个进程。

假设A在t=0时到达，且需要运行100s，而B和C在t=10到达，则各需要运行10s。用纯SJF，我们将会得到：

平均周转时间为(100 + (110-10) + (120-10))/3 = 103.33s

最短完成时间优先(STCF)

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

平均周转时间
(120 + (20 - 10) + (30 - 10))/3 = 50s

新度量指标：响应时间

响应时间定义为从任务到达系统到首次运行的时间，更正式的定义是：

例如上面的调度(A在时间0到达，B和C在时间10到达)。每个作业的响应时间如下：作业A为0，B为0，C为19(平均为：3.33).

STCF和相关方法在响应时间上并不是很好。例如，如果3个工作同时到达，第三个工作必须等待前两个工作全部运行后才能运行。这种方法虽然由很好的周转时间，但对于响应时间和交互性是相当糟糕的。

轮转

新的调度算法：轮转(Round-Robin)调度。
RR在一个时间片(time slice，又是称为调度量子，scheduling quantum)内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务完成。
假设ABC三个任务同时到达，均运行5s。1s的时间片

RR的平均响应时间是：(0+1+2)/3 =1；
SJF算法的平均响应时间是：(0+5+10)/3 = 5.

时间片长度对RR至关重要。越短，响应时间越小。然而时间片太短会造成上下文切换的成本增加，影响整体性能.

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

上面的例子中，平均周转时间将会变成14.
任何公平的策略(如RR),即在小规模的时间内将CPU均匀的分配到活动进程之间，在周转时间这类指标上表现不佳。事实上，这是固有的权衡：如果你愿意不公平，你可以运行较短的工作直到完成，但是要以响应时间为代价。如果你重视公平性，则响应时间会较短，但会以周期时间为代价。

结合I/O

接下来，我们放开没有I/O操作的假设。

重叠可以提高利用率

如有可能，重叠(overlap)操作可以最大限度地提高系统的利用率。重叠在许多不同的领域很有用，包括执行磁盘I/O或将消息发送到远程机器时。在任何一种情况下，开始操作然后切换到其他工作都是一个好主意，这也提高了系统的整体利用率和效率。

无法预知

最后的假设：调度程序知道每个工作的长度。
这可能是可以做出的最糟糕的假设。
事实上，在一个通用的操作系统中，操作系统通常对每个作业的长度知之甚少。
因此，我们如何建立一个没有这种先验知识的SJF/STCF？更进一步，我们如何能够将已经看到的一些想法与RR调度程序结合起来，以便响应时间也变得相当不错？

8-调度：多级反馈队列

多级反馈队列(Multi-level Feedback Queue, MLFQ)需要解决两个问题：

• 优化周转时间(依赖于知道任务需要的执行时间)
• MLFQ希望给交互用户很好的交互体验，因此需要降低响应时间

关键问题：没有完备的知识如何调度？

没有工作长度的先验(priori)知识，如何设计一个能同时减少响应时间和周转时间的调度程序？

提示：从历史中学习

多级反馈队列是用历史经验预测未来的一个典型的例子，操作系统中有很多地方采用了这种技术(同样存在于计算机科学领域的很多其他地方，比如硬件的分支预测及缓冲算法)。如果工作有明显的阶段性行为，因此可以预测，那么这种方式会很有效。当然，必须十分小心地使用这种技术，因为它可能出错，让系统做出比一无所知的时候更糟的决定。

MLFQ:基本规则

MLFQ中有许多独立的队列(queue)，每个队列有不同的优先级(priority level)。任何时刻，一个工作只能存在于一个队列中。MLFQ总是优先执行较高优先级的工作(即在较高队列中的工作)。

当然，每个队列中可能会有多个工作，因此具有同样的优先级。在这种情况下，我们就对这些工作采用轮转调度。

MLFQ调度策略的关键在于如何设置优先级？

MLFQ没有为每个工作指定不变的优先级，而是根据观察到的行为调整它的优先级。例如，如果一个工作不断放弃CPU去等待键盘输入，这是交互型进程的可能行为，MLFQ因此会让它保持高优先级。相反，如果一个工作长时间地占用CPU，MLFQ会降低其优先级。通过这种方式，MLFQ在进程运行过程中学习其行为，从而利用工作的历史来预测它未来的行为。

至此，我们得到了MLFQ的两条基本规则：
规则1：如果A的优先级 > B的优先级， 运行A
规则2：如果A的优先级 = B的优先级，轮转运行A和B

但是存在问题：当优先级高的任务一直运行，可能造成低优先级的任务永远都没有机会运行.

尝试1：如何改变优先级

尝试增加规则调整优先级
规则3：工作进入系统时，放在最高优先级(最上层队列)
规则4a：工作用完整个时间片后，降低优先级(移入下一个队列)
规则4b：如果工作在其时间片以内主动释放CPU，则优先级不变。

实例1：
如果系统有一个需要长时间运行的工作，则随着时间的推移，优先级不断下降。

实例2：
有两个工作：A是一个长时间运行的CPU密集型工作，B是一个运行时间很短的交互型工作。假设A执行一段时间后B到达。

通过这个例子，你大概可以体会到这个算法的一个主要目标：如果不知道工作是短工作还是长工作，那么就在开始的时候假设其是短工作，并赋予最高优先级。 类似于SJF

实例3：如果有I/O呢？
根据4b规则，交互型工作中有大量的I/O操作，它会在时间片用完之前放弃CPU。这种情况下保持它的优先级不变。

交互型工作B每执行1ms便进行I/O操作，A为长时间运行的工作。

至此，MLFQ看起来似乎相当不错了。但是**存在一些严重的缺点:饥饿(starvation)问题。**如果系统有"太多"交互型工作，就会不断占用CPU，导致长工作永远无法得到CPU。

聪明的用户会重写程序，愚弄调度程序(game the scheduler)。愚弄调度程序指的是用一些卑鄙的手段欺骗调度程序，让它给你超公平的资源。上述算法对如下的攻击束手无策：进程在时间片用完之前，调用一个I/O操作(比如访问一个无关的文件)，从而主动释放CPU。如此便可以保持在高优先级，占用更多的CPU时间。做得好时(比如，每运行99%的时间片时间就主动放弃依次CPU)，工作可以几乎独占CPU.

另一个问题：一个程序在不同的时间表现不同。一个密集的进程可能在某段时间表现为一个交互型的进程。

尝试2：提升优先级

规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。

新规则一下解决两个问题：
进程不会饿死；
如果一个CPU密集型工作变成交互型，当它优先级提升时，调度程序会正确对待它。

例子：避免饿死

S的设置：如果S设置得太高，长时间会饥饿；如果设置太低，交互型工作又得不到合适的CPU时间比例。

尝试3：更好的即使方式

如何阻止调度程序被愚弄？

解决方案:为MLFQ的每层队列提供更完善的CPU计时方式(accounting)。调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程用完了自己的配额，就将它降低到低一优先级的队列中取。不论它是一次用完的，还是拆成很多次用完。

重写规则4a和4b：
规则4：一旦工作用完了其在某一层中的时间配额(无论中间主动放弃了多少次CPU)，就降低其优先级(移入低一级队列)

MLFQ调优及其他问题

其中一个大问题是如何配置一个调度程序：
配置多少队列？每一层队列的时间片配置多大？多久提升一次进程的优先级？
这些问题都没有显而易见的答案，因此只有利用对工作负载的经验，以及后续对调度程序的调优，才会导致令人满意的平衡。

大多数的MLFQ变体都支持不同队列可变的时间片长度。高优先级队列通常只有较短的时间片，因而这一层的交互工作可以更快地切换。

MLFQ有趣的原因是：它不需要对工作的运行方式有先验知识，而是通过观察工作的运行来给出对应的优先级。通过这种方式，MLFQ可以同时满足各种工作的需求：对于短时间运行的交互型工作，获得类似于SJF/STCF的很好的全局性能，同时对长时间运行的CPU密集型负载也可以公平地、不断地稳步向前。因此，许多系统使用某种类型的MLFQ作为自己的基础调度程序，包括类BSD UNIX系统[LM+89，B86]、Solaris[M06]以及Windows NT和其后的Window系列操作系统。

9-调度：比例份额

比例调度(proportional-share)调度程序，也称为公平调度(fair-share)调度程序。比例份额算法基于一个简单的想法：调度程序的最终目标，是确保每个工作获得一定比例的CPU时间，而不是优化周转时间和响应时间。

**调度(lottery scheduling)：每隔一段时间，都会举行一次**抽奖。以确定接下来应该运行哪个进程。

通过不断定时地抽取**，**调度从概率上获得这种份额比例。

例如：调度程序知道总共的**数(假设100)。调度程序抽取0_{99之间的一个数，我们希望A占用75%的CPU时间，B占用25%。那么进程A拥有0}74共75张**，B拥有75~99的25张。

关键问题：如何按比例分配CPU

如何设计调度程序来按比例分配CPU？其关键的机制是什么？效率如何？

**数表示份额

**数(ticket)代表了进程(或用户或其他)占有某个资源的份额。

提示：利用随机性

**调度最精彩的地方在于利用了随机性。
随机方法相对于传统的决策方式，至少3点优势。
第一，随机方法常常可以避免奇怪的边角情况.
第二，随机方法很轻量，几乎不需要记录任何状态。在传统的公平份额调度算法中，记录每隔进程已经获得了多少的CPU时间，需要对每个进程进行计时，这必须在每次运行结束后更新。而采用随机方式后每隔进程只需要非常少的状态(即每个进程拥有的**号码)。
随机方法很快。只要能很快的产生随机数，做出决策就很快。

**机制

**调度还提供了一些机制，以不同且有效的方式来调度**。

一种方式是利用**货币(ticket currency)的概念。这种方式允许拥有一组**的用户以他们喜欢的某种货币，将**分给自己的不同工作。之后操作系统再自动将这种货币兑换为正确的全局**。

另一个有用的机制是**转让(ticket transfer)。通过转让，一个进程可以临时将自己的**交给另一个进程。这种机制在客户端/服务端交互的场景中尤其有用，在这种场景中，客户端进程向服务端发送消息，请求其按照自己的需求执行工作，为了加速服务端的执行，客户端可以将自己的**转让给服务端，从而尽可能加速服务端执行自己请求的速度。服务端执行结束后将这部分**归还给客户端。

最后，**膨胀(ticket inflation)有时也很有用。利用膨胀，一个进程可以临时提升或降低自己拥有的**数量。当然在竞争环境中，进程之间互相不信任，这种机制就没什么意义。一个贪婪的进程可能给自己非常多的**，从而接管机器。但是，通胀可以用于进程之间相互信任的环境。在这种情况下，如果一个进程知道它需要更多CPU的时间，就可以增加自己的**，从而将自己的需求告知操作系统，这一切不需要与其他进程通信。

实现

**调度只需要一个不错的随机数生成器来选择中奖**和一个记录系统中所有进程的数据结构(一个列表)，以及所有**的总数。

如何分配**

关于**调度，还有一个问题，那就是如何为工作分配**？系统的运行严重依赖于**的分配。

步长调度

步长调度(strude scheduling),一个确定性的公平分配算法。
假设A，B，C这3个工作的票数分布为100，50，250；
使用10000除以这些票数，作为3个进程的步长：100，200，40；在运行过程中，执行一次时间片，累加历程，下次选取里程最小的工作运行。

既然有了可以精确控制的步长调度算法，为什么还要**调度算法呢？
**调度有一个步长调度没有的优势—不需要全局状态。假设一个新的进程在上面的步长调度执行过程中加入系统，应该怎么设置它的行程值呢？设置成0的话，它就独占CPU了。而**调度算法不需要对每个进程记录全局状态，只需要用新进程的票数更新全局的总票数就可以了。因此**调度算法能够更合理地处理新加入的进程。

本章介绍的**调度和步长调度都没有作为CPU调度程序被广泛使用，一个原因是这两种方式都不能很好地适合I/O；另一个原因是其中最难的票数分配问题并没有确定的解决方式。